stevenhartley
commented
2 months ago Since the
rand_bfield is unchanging through the lifecycle of a uE, and it does not significantly contribute to the uniqueness of the UUID, fewer bits can be allocated to this purpose. It only needs to be enough to provide
This is not true, the rand_b generation guarantees that al of the UUIDs from one uE is unique to another uE but I agree it doesn't' solve the time issue. Reusing portions of rand_b for monotonic clock would loose the entropy for the random numbers and we are back to potential collisions if uEs are gPTP clock synchronized and happen to have the (much smaller) random number generation that collides.
gregmedd
sophokles73
int0x27
The Problem
The current UUID spec for uProtocol defines a UUIDv7-like format with one major change: the
rand_bvalue will be generated once at startup for a uEntity and then reused for the lifetime of that uE.This drastically reduces the uniqueness guarantees of these UUIDs in such a way that it may not be possible to distinguish between true message duplication and UUID reuse caused by time synchronization issues.
Background: Why is the uP UUID like this?
By fixing the
rand_bfield at a value generated when the uE starts, it is possible to derive uE lifecycle information from the UUIDs generated by that uE. If therand_bfield changes for a given uE, then we can reasonably assume it has restarted.Background: Clock Sources and Time Synchronization
In general, we have two clocks we can choose from on Linux when we want to know the time: the system clock with UTC time (also called the "wall clock"), and the monotonic clock with a system-local monotonically counting representation of time. The system clock is what is used when agreement about time between multiple systems is needed. It is typically kept synchronized using network protocols, such as NTP or PTP, or through some timecode receiving hardware, such as a GNSS receiver or an IRIG capture device.
When connectivity to an upstream time source is lost (e.g. network connection lost or GNSS satellites not visible due to obstruction), the local system clock will free-run and drift over time due to instability in local frequency sources. In this free-running holdover mode, a system's clock could drift by several seconds over the course of a week.
When connectivity to an upstream time source is restored, the drift in the local system clock needs to be corrected. If the difference is small, this is usually done by subtly adjusting the clock frequency to slew the clock's time back into alignment. However, if the difference is large (on the order of seconds), this strategy will not work and the clock must be "jumped" to the correct time.
UUIDs and Uniqueness
As uProtocol UUIDs are defined today, reuse of UUIDs is practically guaranteed if the clock has run fast and must be jumped backwards to an earlier time. This is because the only fields that change for each newly generated UUID are the
unix_ts_ms(time in milliseconds) and thecounter(monotonically increases per message within that millisecond, resetting to zero at the top of each millisecond).This poses a problem for several usage models of uProtocol. For the RPC model, these UUIDs are used to match replies to requests. For logging (and possibly playback) of messages, it's often necessary to be able to identify if a message is unique or if it is repeated. In the event of a backward time jump, it will no longer be possible to guarantee unique UUIDs and these uses can break down.
UUIDs and Clock Sources
In uProtocol, the time field on a UUID is used, in part, to enforce a message's TTL (time to live). When a message is received, the TTL is added to the UUID's time stamp then compared to the current system clock time; if the system time is earlier, then the message is still valid. As such, agreement about the current time is needed between uE.
This means it's not possible to switch to a monotonic clock for generating UUID values, even though this would guarantee time-ordering of messages regardless of what happens with the system clock. The monotonic clock's very nature is that it can always count upwards because it does not have to be the same value as any other clock. It cannot be synchronized with another system without introducing the same time jump issue as the system clock, violating its monotonicity in the process.
UUIDs and Ordering
While uProtocol itself makes no guarantee on the order of message delivery, there are scenarios where determining the transmission order of messages is necessary. One such example is capture and playback of uProtocol messages. Another is event logging.
In these scenarios, a clock-synchronizing jump to an earlier time will result in messages being sorted differently than their true transmission order. This could be solved for a single uE source by using a monotonic clock when generating UUIDs, but then the messages could not be sorted to other uE running on different systems (and TTL could not be enforced).
For applications on top of uProtocol that need ordering, a monotonic value could be simply embedded in the message payload. However, this does not cover the needs of logging, capture, and playback which need to operate at layer 1 or layer 2.
Proposals
The proposals below seek to address these issues:
Switch to UUIDv7
This proposal addresses the three issues with:
UUIDv7 is almost identical to the uProtocol UUIDv8 except that
rand_bis required to be randomly generated each time a UUID is created. Therand_bfield is sufficiently large such that a uE using a single pseudorandom number generator is unlikely to repeat a random value within the time scales were a time jump would be a concern. Even if time jumps backward, new messages can always be distinguished from repeated messages.Applications are free to embed any data into their message payload to meet their needs. An application needing to know true transmission ordering can embed a monotonic timestamp into the message before it is sent. The receiving end of the application can use these values to detect time jumps, verify ordering of messages, and even to correlate monotonic time offsets between systems. Details of this would be left to application designers.
Logging and capture/playback uses could instead record the receiving system's monotonic time when each message arrives and store the two together. In post processing, this monotonic time can be used to detect time jumps in the UUIDs, assuming a) the synchronization jump threshold is known and b) the maximum network latency jitter is significantly less than the jump threshold. If the changes in the offset between the receive timestamp and the UUID timestamp are within the jump threshold, then we can reason that no jump has occurred. If the delta between the received timestamp and UUID timestamp changes by more than the jump threshold, we can assume a time jump has occurred.
uE lifecycles can be handled at the application layer. A standard uE health module could be made that periodically publishes uE uptime and other metrics such that restarts can be detected. Any uE that cares about the lifecycle of another uE could subscribe to these messages.
Steal some bits from
rand_bfor a monotonic timestampA smaller modification would be to steal some bits from the
rand_bfield to embed part of the sender's monotonic time in. It wouldn't need a huge number of bits, maybe enough for about 1 hour of range. This would a) result in unique UUIDs even if time jumps occur (so long as they are smaller than the range of the monotonic time field), b) assist in preserving absolute ordering for a given uE's messages, and c) preserve the existing uE lifecycle tracking by using a fixed random value for each start.Since the
rand_bfield is unchanging through the lifecycle of a uE, and it does not significantly contribute to the uniqueness of the UUID, fewer bits can be allocated to this purpose. It only needs to be enough to provide