commit c2c87816ff11447d2e5861eb509eaf6d0da6de1c
from: Astronomax <fgfgfb93@gmail.com>
via: Serge Petrenko <35663196+sergepetrenko@users.noreply.github.com>
date: Mon Oct 07 11:14:29 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

(cherry picked from commit 58f3c93b660499e85f08a4f63373040bcae28732)

commit - e92f78068eecc73d20ca936c07d710fa462434af
commit + c2c87816ff11447d2e5861eb509eaf6d0da6de1c
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 - c94a59b42f956a42b5fac8d27e3e6ba8f1aec4b2
blob + dfd292929dab1df71715dbeabb19fef139901afb
--- test/unit/vclock.cc
+++ test/unit/vclock.cc
@@ -443,11 +443,74 @@ test_minmax(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(6);
+	plan(8);
 
 	test_compare();
 	test_isearch();
@@ -455,6 +518,8 @@ main(void)
 	test_fromstring();
 	test_fromstring_invalid();
 	test_minmax();
+	test_nth_element();
+	test_count_ge();
 
 	return check_plan();
 }
blob - af2afb803fb9805d28ca73195d5575e06941e8f1
blob + b8c25e5d0b5de99792e6423e4815f3265b0b6a44
--- test/unit/vclock.result
+++ test/unit/vclock.result
@@ -1,4 +1,4 @@
-1..6
+1..8
     1..40
 	*** test_compare ***
     ok 1 - compare (), () => 0
@@ -157,3 +157,32 @@ ok 5 - subtests
     ok 6 - min between {0: 10, 1: 17, 2: 3} and {0: 1, 1: 5, 2: 7} is {0: 1, 1: 5, 2: 3}
 	*** test_minmax: done ***
 ok 6 - 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 7 - 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 8 - subtests