Hi Tim,
On Sat, Jul 06, 2024 at 09:13:12PM +0200, Tim Duesterhus wrote:
> Willy,
>
> I'm not particularly happy with out the patch turned out, but this is the
> best I could come up with. If you are also unhappy with it, then please
> consider this email to be a bug report and adjust my patch as necessary /
> fix it yourself. Unfortunately I don't currently have the time to spend
> further time on this. Of course if you are happy, then feel free to apply :-)
>
> Best regards
> Tim Düsterhus
>
> Apply with `git am --scissors` to automatically cut the commit message.
>
> -- >8 --
> RFC 9562 specifies specifies that the top-most 48 bits of a UUIDv7 represent a
> unix timestamp with millisecond resolution, allowing a user to extract the
> timestamp. The remaining bits (except for version and variant) are left
> unspecified. However it still requires that generated UUIDv7 are monotonic.
>
> Section 6.2 describes several methods to generate monotonic UUIDs. This patch
> employs "Method 3", filling the left-most bits "rnd_a" with increased clock
> precision, guaranteeing monotonicity up to a 244ns resolution.
>
> UUIDv7 was added with HAProxy 3.0, this patch should be backported there.
Well, I must confess that while I understand what you tried to do, it's
less clear what is the problem you wanted to address. I think that your
concern is the possible lack of monotonicity, is that it ?
If so we already have a monotonic date (global_now_ns), it's just that the
offset applied at boot is lost. By keeping it we now have a monotonic date
across all threads (see attached patch).
Also there's no point increasing time precision, it's the opposite that
must be done when looking for monotonicity, even if that sounds counter
intuitive. The reason is that system clocks are not precise and that by
feeding more bits from time into the output, you end up preventing that
output from changing between multiple calls, while instead it could
contain a counter or a random. For example in VMs and some embedded
systems it's not rare at all to see the clock source set to "jiffies"
since the other ones are either totally unreliable or horribly slow
(e.g. emulating hardware), resulting in 1, 4 or 10ms time resolution.
And on systems not doing this you can see apparently good precision
that doesn't change between multiple calls, for various reasons, or
even time jumping backwards when using TSC on multi-processor systems
or VMs.
In any case there are much less risks of collisions by filling bits
with random than with clock bits. Here if I read correctly, you're
only keeping 64 bits of random, which means that on average you'll
experience a collision every 2^32 generations. At 50k/s, it happens
once a day. With the 96 bits used previously, it will only happen
every 2^48, which is once every 178 years (which obviously reduces
in distributed systems).
Finally, the purpose of having the timestamp in UUIDv7 (like ULID)
is to group simultaneous operations. They keep caches hot, they allow
events to be found grouped in logs, and offer easier purge mechanisms
for recycling entries (no longer need to look up, just apply a time
offset and eliminate all those below). In that sense there's no quest
for extreme precision (which cannot work on distributed systems anyway),
rather for a reasonably good and reasonably monotonic ordering that
still prevents collisions across multiple systems.
So if that's also what you're looking for, I'm proposing that we
instead change the use of the unreliable date variable with a call
to now_mono_date_ns() that we can then use as the date source, and
keep the rest of the randoms.
Just let me know what you think.
Thanks!
Willy
>From 8952b22c9209ea9c2c82bd645141beec968873a9 Mon Sep 17 00:00:00 2001
From: Willy Tarreau <w...@1wt.eu>
Date: Mon, 8 Jul 2024 06:01:59 +0200
Subject: MINOR: clock: provide a new monotonic date function
The global_now_ns variable is derived from the system date, corrected
for monotonicity and with an offset applied so that global_now_ms wraps
soon after boot.
A monotonic date has plenty of use cases (such as generating UUIDv7),
but for the sake of avoiding wrapping between process restarts, we must
drop the boot offset.
This commit adds a variable now_offset_boot that contains a copy of the
initial offset applied to global_now_ns, and a function now_mono_date_ns()
that subtracts it from global_now_ns so that the resulting value remains
as close as possible to system time more or less drift corrections.
---
include/haproxy/clock.h | 2 ++
src/clock.c | 12 ++++++++++++
2 files changed, 14 insertions(+)
diff --git a/include/haproxy/clock.h b/include/haproxy/clock.h
index 264363e27b..1064d430b0 100644
--- a/include/haproxy/clock.h
+++ b/include/haproxy/clock.h
@@ -28,6 +28,7 @@
extern struct timeval start_date; /* the process's start date
in wall-clock time */
extern struct timeval ready_date; /* date when the process was
considered ready */
extern ullong start_time_ns; /* the process's start date
in internal monotonic time (ns) */
+extern llong now_offset_boot; /* now_offset at boot (for
conversions to monotonic wall-clock time) */
extern volatile ullong global_now_ns; /* common monotonic date
between all threads, in ns (wraps every 585 yr) */
extern THREAD_LOCAL ullong now_ns; /* internal monotonic date
derived from real clock, in ns (wraps every 585 yr) */
@@ -38,6 +39,7 @@ uint64_t now_mono_time(void);
uint64_t now_mono_time_fast(void);
uint64_t now_cpu_time(void);
uint64_t now_cpu_time_fast(void);
+uint64_t now_mono_date_ns(void);
void clock_set_local_source(void);
void clock_update_local_date(int max_wait, int interrupted);
void clock_update_global_date();
diff --git a/src/clock.c b/src/clock.c
index 7734389a71..c90813f780 100644
--- a/src/clock.c
+++ b/src/clock.c
@@ -29,6 +29,7 @@
struct timeval start_date; /* the process's start date
in wall-clock time */
struct timeval ready_date; /* date when the process was
considered ready */
ullong start_time_ns; /* the process's start date
in internal monotonic time (ns) */
+llong now_offset_boot; /* now_offset at boot (for
conversions to monotonic wall-clock time) */
volatile ullong global_now_ns; /* common monotonic date
between all threads, in ns (wraps every 585 yr) */
volatile uint global_now_ms; /* common monotonic date in
milliseconds (may wrap) */
@@ -132,6 +133,16 @@ uint64_t now_cpu_time_thread(int thr)
return ret;
}
+/* returns the global date in nanoseconds, corrected for monotonicity. The
+ * global date in global_now_ns is already monotonic, derived from the system's
+ * date, but it has an offset applied at boot (now_offset_boot) to force now_ms
+ * to wrap 20s after booting, that we need to subtract.
+ */
+uint64_t now_mono_date_ns(void)
+{
+ return _HA_ATOMIC_LOAD(&global_now_ns) - now_offset_boot;
+}
+
/* set the clock source for the local thread */
void clock_set_local_source(void)
{
@@ -296,6 +307,7 @@ void clock_init_process_date(void)
* match and continue from this shifted date.
*/
now_offset = sec_to_ns((uint)((uint)(-global_now_ms) / 1000U -
BOOT_TIME_WRAP_SEC));
+ now_offset_boot = now_offset;
global_now_ns += now_offset;
now_ns = global_now_ns;
now_ms = global_now_ms = ns_to_ms(now_ns);
--
2.35.3
