commit 58f3c93b660499e85f08a4f63373040bcae28732
from: Astronomax <fgfgfb93@gmail.com>
via: Serge Petrenko <35663196+sergepetrenko@users.noreply.github.com>
date: Fri Oct 04 15:41:26 2024 UTC

vclock: introduce `vclock_nth_element` and `vclock_count_ge`

Two new vclock methods have been added: `vclock_nth_element` and
`vclock_count_ge`.
* `vclock_nth_element` takes n and returns whatever element would occur in
nth position if vclock were sorted. This method is very useful for
synchronous replication because it can be used to find out the lsn of the
last confirmed transaction - it's simply the result of calling this
method with argument {vclock_size - replication_synchro_quorum} (provided
that vclock_size >= replication synchro quorum, otherwise it is obvious
that no transaction has yet been confirmed).
* `vclock_count_ge` takes lsn and returns the number of components whose
value is greater than or equal to lsn. This can be useful to understand
how many replicas have already received a transaction with a given lsn.

Part of #9917

NO_CHANGELOG=Will be added in another commit
NO_DOC=internal

commit - f0f9647d8b80a2bad56b9462fff28b28af2203aa
commit + 58f3c93b660499e85f08a4f63373040bcae28732
blob - 81d3eeb50549b09d7bdea5f459384f97dfa2ecad
blob + 2e73d5fbe1d5c3b30abc2cff2c3c092009c0cc94
--- src/lib/vclock/vclock.c
+++ src/lib/vclock/vclock.c
@@ -175,4 +175,36 @@ vclockset_node_compare(const struct vclock *a, const s
 	return res;
 }
 
+int64_t
+vclock_nth_element(const struct vclock *vclock, uint32_t n)
+{
+	if (n >= vclock_size(vclock))
+		return -1;
+	struct vclock_iterator it1, it2;
+
+	vclock_iterator_init(&it1, vclock);
+	vclock_foreach(&it1, vc1) {
+		uint32_t le = 0, leq = 0;
+		vclock_iterator_init(&it2, vclock);
+		vclock_foreach(&it2, vc2) {
+			le += vc2.lsn < vc1.lsn;
+			leq += vc2.lsn <= vc1.lsn;
+		}
+		if (le <= n && n < leq)
+			return vc1.lsn;
+	}
+	unreachable();
+}
+
+int
+vclock_count_ge(const struct vclock *vclock, int64_t lsn)
+{
+	int count = 0;
+	struct vclock_iterator it;
+	vclock_iterator_init(&it, vclock);
+	vclock_foreach(&it, vc1)
+		count += vc1.lsn >= lsn;
+	return count;
+}
+
 rb_gen(, vclockset_, vclockset_t, struct vclock, link, vclockset_node_compare);
blob - 85aa011beecdd272ae6ca412dfd2d367928930b5
blob + d966b7430e92a0560ec184d85b0652fc3986bac6
--- src/lib/vclock/vclock.h
+++ src/lib/vclock/vclock.h
@@ -480,6 +480,18 @@ vclockset_match(vclockset_t *set, const struct vclock 
 	 */
 	return vclockset_first(set);
 }
+
+/**
+ * Calculates the kth order statistic.
+ */
+int64_t
+vclock_nth_element(const struct vclock *vclock, uint32_t n);
+
+/**
+ * Count the number of components that are more than or equal to a given value.
+ */
+int
+vclock_count_ge(const struct vclock *vclock, int64_t lsn);
 
 #define vclockset_foreach(set, vclock) \
 	for ((vclock) = vclockset_first(set); \
blob - 563e0406741beb9b2ad9e095013a19362d111ca6
blob + 2486eeb7d2c283de6ebc15801f88799d87acb77e
--- test/unit/vclock.cc
+++ test/unit/vclock.cc
@@ -524,11 +524,74 @@ test_mp_invalid(void)
 }
 
 #undef test
+
+#define test(s, n, expected) ({						\
+	struct vclock vc;						\
+	vclock_create(&vc);						\
+	vclock_from_string(&vc, (s));					\
+	is(vclock_nth_element(&vc, n), expected,			\
+		"vclock_nth_element \"%s\", %d => %d", s, n, expected);	\
+})
+
+static int
+test_nth_element(void)
+{
+	plan(11);
+	header();
 
+	test("{0: 1, 2: 3, 5: 7, 10: 3}", 2, 3);
+	test("{1: 4, 3: 2, 4: 8, 8: 6, 9: 7}", 3, 7);
+	test("{0: 10, 1: 11, 3: 12, 7: 13, 9: 14}", 1, 11);
+	test("{2: 5, 4: 6, 6: 7, 8: 8, 10: 9}", 3, 8);
+	test("{1: 9, 3: 1, 5: 2, 7: 3, 11: 4}", 2, 3);
+	test("{0: 0, 2: 2, 4: 4, 6: 6, 8: 8, 10: 10}", 5, 10);
+	test("{1: 3, 2: 6, 3: 9, 4: 12, 5: 15}", 3, 12);
+	test("{0: 10, 2: 20, 4: 30, 6: 40, 8: 50}", 2, 30);
+	test("{1: 2, 3: 4, 5: 6, 7: 8, 9: 10}", 4, 10);
+	test("{2: 1, 4: 2, 6: 3, 8: 4, 10: 5}", 1, 2);
+	test("{2: 5, 4: 6, 6: 7, 8: 8, 10: 9}", 5, -1);
+
+	footer();
+	return check_plan();
+}
+
+#undef test
+
+#define test(s, lsn, expected) ({					\
+	struct vclock vc;						\
+	vclock_create(&vc);						\
+	vclock_from_string(&vc, (s));					\
+	is(vclock_count_ge(&vc, lsn), expected,				\
+		"vclock_count_ge \"%s\", %d => %u", s, lsn, expected);	\
+})
+
+static int
+test_count_ge(void)
+{
+	plan(10);
+	header();
+
+	test("{0: 1, 2: 3, 5: 7, 10: 3}", 3, 3);
+	test("{1: 4, 3: 2, 4: 8, 8: 6, 9: 7}", 5, 3);
+	test("{0: 10, 1: 11, 3: 12, 7: 13, 9: 14}", 11, 4);
+	test("{2: 5, 4: 6, 6: 7, 8: 8, 10: 9}", 6, 4);
+	test("{1: 9, 3: 1, 5: 2, 7: 3, 11: 4}", 4, 2);
+	test("{0: 0, 2: 2, 4: 4, 6: 6, 8: 8, 10: 10}", 5, 3);
+	test("{1: 3, 2: 6, 3: 9, 4: 12, 5: 15}", 7, 3);
+	test("{0: 10, 2: 20, 4: 30, 6: 40, 8: 50}", 25, 3);
+	test("{1: 2, 3: 4, 5: 6, 7: 8, 9: 10}", 5, 3);
+	test("{2: 1, 4: 2, 6: 3, 8: 4, 10: 5}", 3, 3);
+
+	footer();
+	return check_plan();
+}
+
+#undef test
+
 int
 main(void)
 {
-	plan(8);
+	plan(10);
 
 	test_compare();
 	test_isearch();
@@ -538,6 +601,8 @@ main(void)
 	test_minmax();
 	test_mp();
 	test_mp_invalid();
+	test_nth_element();
+	test_count_ge();
 
 	return check_plan();
 }
blob - 605fe07574e1f5789a923fd35364edf141322f50
blob + a1f152fd4fbf08f58e75e4396b4d36e0a41c8470
--- test/unit/vclock.result
+++ test/unit/vclock.result
@@ -1,4 +1,4 @@
-1..8
+1..10
     1..40
 	*** test_compare ***
     ok 1 - compare (), () => 0
@@ -180,3 +180,32 @@ ok 7 - subtests
     ok 8 - Decoder must fail
 	*** test_mp_invalid: done ***
 ok 8 - subtests
+    1..11
+	*** test_nth_element ***
+    ok 1 - vclock_nth_element "{0: 1, 2: 3, 5: 7, 10: 3}", 2 => 3
+    ok 2 - vclock_nth_element "{1: 4, 3: 2, 4: 8, 8: 6, 9: 7}", 3 => 7
+    ok 3 - vclock_nth_element "{0: 10, 1: 11, 3: 12, 7: 13, 9: 14}", 1 => 11
+    ok 4 - vclock_nth_element "{2: 5, 4: 6, 6: 7, 8: 8, 10: 9}", 3 => 8
+    ok 5 - vclock_nth_element "{1: 9, 3: 1, 5: 2, 7: 3, 11: 4}", 2 => 3
+    ok 6 - vclock_nth_element "{0: 0, 2: 2, 4: 4, 6: 6, 8: 8, 10: 10}", 5 => 10
+    ok 7 - vclock_nth_element "{1: 3, 2: 6, 3: 9, 4: 12, 5: 15}", 3 => 12
+    ok 8 - vclock_nth_element "{0: 10, 2: 20, 4: 30, 6: 40, 8: 50}", 2 => 30
+    ok 9 - vclock_nth_element "{1: 2, 3: 4, 5: 6, 7: 8, 9: 10}", 4 => 10
+    ok 10 - vclock_nth_element "{2: 1, 4: 2, 6: 3, 8: 4, 10: 5}", 1 => 2
+    ok 11 - vclock_nth_element "{2: 5, 4: 6, 6: 7, 8: 8, 10: 9}", 5 => -1
+	*** test_nth_element: done ***
+ok 9 - subtests
+    1..10
+	*** test_count_ge ***
+    ok 1 - vclock_count_ge "{0: 1, 2: 3, 5: 7, 10: 3}", 3 => 3
+    ok 2 - vclock_count_ge "{1: 4, 3: 2, 4: 8, 8: 6, 9: 7}", 5 => 3
+    ok 3 - vclock_count_ge "{0: 10, 1: 11, 3: 12, 7: 13, 9: 14}", 11 => 4
+    ok 4 - vclock_count_ge "{2: 5, 4: 6, 6: 7, 8: 8, 10: 9}", 6 => 4
+    ok 5 - vclock_count_ge "{1: 9, 3: 1, 5: 2, 7: 3, 11: 4}", 4 => 2
+    ok 6 - vclock_count_ge "{0: 0, 2: 2, 4: 4, 6: 6, 8: 8, 10: 10}", 5 => 3
+    ok 7 - vclock_count_ge "{1: 3, 2: 6, 3: 9, 4: 12, 5: 15}", 7 => 3
+    ok 8 - vclock_count_ge "{0: 10, 2: 20, 4: 30, 6: 40, 8: 50}", 25 => 3
+    ok 9 - vclock_count_ge "{1: 2, 3: 4, 5: 6, 7: 8, 9: 10}", 5 => 3
+    ok 10 - vclock_count_ge "{2: 1, 4: 2, 6: 3, 8: 4, 10: 5}", 3 => 3
+	*** test_count_ge: done ***
+ok 10 - subtests