Nanosecond timestamp collisions are common
evanjones.ca
evanjones.ca
Eg UUIDv7 has a milliseconds time component and then a field that increments for each event in the same millisecond, and then enough random bits to make collisions between ids generated on different machines astronomically unlikely.
Of course there are only so many bits so you might generate too many events in the same time slice so the sequence overflows, and you might actually get collisions between machines, and you are limiting your event generation speed by forcing your cpu to sync on the increment etc.
But in practice UUIDv7 works great at scale.
Computers should run like clockwork, so in this example of using all the cores, in Windows and likely some other OS's, threads are assigned to cores when they are started and you can have many threads per core, ergo the time component should also have the thread and the core number combined with it with multi core systems.
Its possible to write the code in such a way some variables are bounced out of the cpu cache back to memory to avoid any caching issues because I think the cache on some cpu's are per core, and some are per cpu.
Do they? I thought the normal behaviour was for cores to pick any available thread to run, so core migration is quite normal.
> ergo the time component should also have the thread and the core number combined with it with multi core systems.
Sorry, how exactly does it follow from the previous? You seem to have omitted the other half of your syllogism. After all, clockworks do not have thread nor core numbers so I don't quite see how having those in UUIDs will make computers run like clockwork.
>Do they? I thought the normal behaviour was for cores to pick any available thread to run, so core migration is quite normal.
The CPU and its cores know very little about threads, threads are a figment of the OS.
>Sorry, how exactly does it follow from the previous? You seem to have omitted the other half of your syllogism
Syllogism would perhaps be a intuitive word to use, why is this? What happened to you?
Although now I wonder if / how UUID v7 can do sequential keys on distributed systems. Mind you, on those systems "close enough" will probably be good enough, and sorting will be done by date instead of incremental ID.
Probably too much overhead when conflicting UUIDs are a few orders of magnitude less likely than the clients crashing from some random bug though.
And by web scale, I mean they're too big to exchange by any offline channel.
Granted I've even used JSON over GATT so maybe I should keep my mouth shut :).
If you don't need that, but just need a random UUID, UUIDv4 is better.
/s
It's not cryptographically secure (anymore). And there are cheaper non-cryptographically secure hash functions.
create index on $table ($field1, $field2);
That said, PostgreSQL offers https://www.postgresql.org/docs/current/rowtypes.html which gives you the best of both worlds. A single field which contains 2 fields that can later be extracted. So everywhere you can write a single field for joins, etc. But then when you need it broken out...
Can you layout a demo architecture where you use multiple keys like you propose?
And on top of all that, there are efficiency concerns.
That said, at least for join tables AFAIK - there aren't often a need for row IDs beyond the involved foreign keys - unless you need to add meta data from other relations/tables...
My British passport says I was born in Birr; my Irish passport says I was born in Galway. These are both correct, because they are answering different questions. (I was born in the town of Ballinasloe in County Galway, but my mother's place of residence at the time of my birth was the town of Birr in County Offaly.)
Could maybe be just a mistake when doing the UK registration ? It's an easy fix if wanted.
Changes! lol
Why not use a graph database? O(1) lookups instead of O(N). Why need indices if you can just point to the data. Why use JOINs when map-reduce querying is far more flexible?
ISAM and VSAM come to mind. Yes it says "files" in there a lot but it got used like a database with programming interfaces like finding records in a database. If you will this method is more like NoSQL databases than a relational DB. The I in ISAM was a step towards not having to know the key (true "NoSQL"). Kind of like today's NoSQL databases all also give the ability to add indexes now.
As for query language: definitely Cypher!
My intuition let's me know that you can not get below O(n log n) (Lower limit for comparison based ordering)
That intuition should point at O(log n), shouldn't it?
In any case, it totally depends how your data is stored and how/what you want to look up.
If you already have some kind of id of your node in the graph you want to look up, you can get O(1) lookup and still call it a graph database. If you have to traverse the graph, then it depends on the structure of the graph and where your entry point is, etc.
I'm rather skeptical of graph databases. Whatever they can do, you can do with a relation database and datalog. (Think of datalog as SQL plus recursion, perhaps.) See https://en.wikipedia.org/wiki/Datalog
The reason why you want indices is because some query patterns don't have a key to perform a look up on.
To sort or filter the records by time. Sure, you can just add an extra column if you need this, but there are cases when this is not convenient to do. E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them.
Also, if that’s really true why can’t everyone just use graphdb’s?
For example, when a user has 7 articles. Do you want to just point to where the articles are stored? Or do you want to do O(log n) lookup for each article?
And if you have many-to-many, do you want to join an Intermediate Table for even more processing, or just follow a pointer to a range of an intermediate node directly and traverse?
I'm talking about pointing directly to the location of an array where things are stored. That array isn't a clustered index. Each array is different.
How do you deal with data that gets accessed in different orders based on relationships from multiple other entities? Duplicate the data? If so, updates now get amplified and you can fit less data in RAM so you're more likely to require disk IO. If not, you need a layer of indirection (so you have an array of pointers instead of an array of data).
Even with a layer of indirection, updates that grow a row and require a reallocation will cause you to have to go update all pointers (also, those pointers need to be indexed to find who you need to update). To avoid write amplification, you can use an array of ids instead of an array of pointers. Now you want an id <-> pointer lookup, which could be done with a hash map in O(1), or with a tree in O(logN) if you want to also allow efficient range queries.
I'm not exactly sure on the implementation details, but for ballpark numbers, for an 8 kB page size with 80% fill factor and 16 B entries (8 B key + 8 B pointer), with 10E9 rows, log(N) ought to be ~4 (page IOs). Not ideal, but the point is for a lot of real-world engineering, O(logN) is effectively O(1) (with a small enough constant factor that it's fine for general use).
So if your data is not write-once, trees are a well-rounded default data structure.
Which is why we need a version 2 of complexity theory, that doesn’t treat memory access or arithmetic on arbitrary precision numbers (aka as n actually goes to infinity) as O(1) operations. They aren’t. Which every large system engineer knows but few will talk about.
And that complexity theory already exists. Typical whiteboard engineering uses transdichotomous models to gloss over some polylogarithmic factors (as do much of the literature), but more accurate models exist.
The difference isn't usually super relevant when comparing multiple solutions all using the same model of computation though since the extra terms don't tend to bump one complexity class above another when switching models, and if you cared about actual runtime characteristics you wouldn't be relying on log factors in such a crude tool anyway.
Imagine a data center containing exabytes of data. How long does it take to access an arbitrary bit of that data?
We use clusters because computers cannot contain an infinite amount of memory, storage, or CPUs, because of physics. You see this same thing play out at smaller scales but it's more obvious at the macro scale. More addresses take logn time to sort out, but time to access is measured in radii, not gate depth.
In a world where clusters are rare, Knuth made decent approximations. In a world where clusters are not only de rigeur but hosted on multitenant hardware spread out over upwards of 100 miles, those approximations are bullshit and need to change.
But on the topic of hash tables, you can only reach 'O(1)' if you can avoid collisions. And to avoid collisions you need a key of length m, which grows as n grows. You cannot put 51 pigeons in 50 pigeonholes. So the key length of your hash keys is m >= logn, which means the time to compare keys is also logn, which means hash tables are never actually O(1) access or insert time. Actual access time for a hash table on non-imaginary hardware is √nlogn, not O(1).
If you consider that we have applications that are just a single hash table occupying the entire RAM of a single machine, then this is not picking nits. It's capacity planning.
I am not sure I am following this argument. You are not going to have more than 2^64 pigeons and pigeonholes on any system soon and I almost dare to say you will never ever get to 2^128. And for 64 or 128 bit keys comparisons and many other operations are for all practical purposes constant time. I guess you could argue that this is sweeping a factor of log(n) under the rug because of things like carry chains which could be faster for smaller bit sizes but I am not sure that this is really useful on common hardware, an addition will take one clock cycle independent of the operand values.
The representation (outside of indexing) has properties that make your USE CASE better or worse. EGreg would not be someone to hire to architect a solution. He'll just put your 1Trillion row per month use-case in a graph DB like Neo4J and you'll just watch it fall over when you run billing.
For instance, you might use a random object ID as a prefix value in the index, followed by attribute ID which isn’t. Or a modified time, so you can have a history of values which can be read out linearly.
If using it directly, that means Objects and their data are sharded randomly across, but when looking for an objects attributes (or attribute by time), their index entries are always co-located and you can read them out linearly with good performance.
If blindly hashing keys to distribute them, you can’t do that. Also, you can’t really do a linear read at all, since no data will be ‘associatable’ with others, as the index value is randomized, and what is stored in the index has no related to the key provided by the user.
You can only do a straight get, not a read. That is very limiting, and expensive with large data sets as most algorithms benefit greatly from having ordered data. (Well, you could do a read, but you’d get back entries in completely random order)
Needless to say, this is ‘advanced’ usage and requires pretty deep understanding of your data and indexing/write/read patterns, which is why random hashing is the most common hash map behavior.
CREATE INDEX ... USING HASH;Why not keep the timestamp bits to use when appropriate, but use some of the random bits for shard selection?
Very large real world datasets are unlikely to be static long enough, and equipment stable enough, to not consider this effect.
I'm confused by your reply, because I never suggested not to use random bits for sharding.
I'm just saying that 60+ random bits should be enough to shard, change, grow, and sub-shard with. You don't need 122.
People were talking about the value of time+random UUIDs versus all-random UUIDs, and how those behave.
You said that sometimes the random behavior is preferable.
In response to that, I was saying that even if you want to sort randomly at some particular step, you should use the time+random format, because other steps might not want to sort randomly. You should directly choose to use the random part, instead of indirectly forcing it by making the entire UUID random.
Then you said "Only when writing all at once and when you know what the shard boundaries are and the number of shards (and boundaries) are stable."
I can't figure out how that relates to my post. I thought you were worried about insufficient random bits to use for sharding, but apparently that wasn't your concern. So I have no idea what your concern is. If you have a use case for randomness, use the random half of the UUID.
For the case I’m describing, you can’t use it.
For situations you want write coalescing it’s fine though.
Not sure it we’re agreeing here?
There's some flexibility in how you fill in a UUIDv7, but let's go ahead and say that the ones we're worried about have the first 32 bits filled with timestamp and the last 32 bits filled with random.
If you want pure sort-by-time, then use it the normal way. If you want pure sort-by-random, then it's slightly awkward but you can prioritize the random part.
But the additional power is that you can shard by the last 32 bits, then sort by the first 32 bits within a shard. And you don't need weird workarounds like hashing the UUID.
You said "it’s easier to shard when writes occur randomly over the overall space. it’s easier to coalesce when writes all happen in a given place (head or tail)". But you can have both at the same time. You can have easy sharding and easy coalescing.
You can't 'prioritize' random parts of a key for sorting without writing a bunch of custom sorting (and key parsing) logic, which is generally undesirable for a number of reasons - and frankly completely unnecessary in these cases. You just wouldn't use UUIDv7 (or probably a UUID in general), and the benefits would pay for themselves very quickly anyway.
To quote the UUIDv7 RFC:
"This document presents new time-based UUID formats which are suited for use as a database key." (as the first line of the abstract)
"Due to the shortcomings of UUIDv1 and UUIDv4 details so far, many widely distributed database applications and large application vendors have sought to solve the problem of creating a better time-based, sortable unique identifier for use as a database key."
"- Timestamps MUST be k-sortable. That is, values within or close to the same timestamp are ordered properly by sorting algorithms.
- Timestamps SHOULD be big-endian with the most-significant bits of the time embedded as-is without reordering.
- Timestamps SHOULD utilize millisecond precision and Unix Epoch as timestamp source. Although, there is some variation to this among implementations depending on the application requirements.
- The ID format SHOULD be Lexicographically sortable while in the textual representation.
- IDs MUST ensure proper embedded sequencing to facilitate sorting when multiple UUIDs are created during a given timestamp.
- IDs MUST NOT require unique network identifiers as part of achieving uniqueness.
- Distributed nodes MUST be able to create collision resistant Unique IDs without a consulting a centralized resource."
[https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...]
I'm pointing out that for some systems, that makes UUIDv7 unsuitable because you WANT the keys to be randomly distributed to avoid hotspots. Using UUIDv7 in these situations will result in a single node receiving all writes (and all reads for a given time range), which in the dataset sizes I'm referring to is usually impossible to handle. No single node can handle that kind of load, regardless of how efficient it may be.
For other types of systems (such as single machine databases or 'tight' clusters of databases without extreme write loads), UUIDv7 and similar is great, as it allows easy/cheap write combining when that is actually possible for a machine to handle the load.
> You can't 'prioritize' random parts of a key for sorting without writing a bunch of custom sorting (and key parsing) logic, which is generally undesirable for a number of reasons - and frankly completely unnecessary in these cases. You just wouldn't use UUIDv7 (or probably a UUID in general), and the benefits would pay for themselves very quickly anyway.
Forget prioritizing, that was about going fully random. Seriously, let's pretend I never said that specific sentence.
Let's focus on just the sharding scenario. None of what you said there conflicts with what I said about sharding.
Unless these database engines are so incompetent that you can't shard on something as simple as id[12:16]?
> I'm pointing out that for some systems, that makes UUIDv7 unsuitable because you WANT the keys to be randomly distributed to avoid hotspots. Using UUIDv7 in these situations will result in a single node receiving all writes (and all reads for a given time range), which in the dataset sizes I'm referring to is usually impossible to handle. No single node can handle that kind of load, regardless of how efficient it may be.
You only want the keys to be randomly distributed at the sharding layer. Once it reaches its home node, you don't want random distribution within that node. At best you begrudgingly accept it.
It's within a node that things like "normal lexical sorting" matter the most, so UUIDv7 does a great job of making that smooth.
You don't need lexical sorting between shards, especially when you're randomizing the shard.
It's square peg, round hole.
And folks working on Exabyte sized indexed datasets generally already get this. So I'm not sure why i'm even having this discussion? I'm not even getting paid for this!
Ciao!
And it's not shenanigans! You could shard based on the first bytes of a key, or you could shard based on the last bytes of the key. Neither one should be harder. Neither one is shenanigans.
> It's square peg, round hole.
Going entirely random is an even worse peg.
Fwiw I’m with Dylan on this one!
I have direct experience of absolutely humongous data processing using random bits for shard selection where each shard uses sorted storage and benefits from the sortability of the time bits so, with just the smallest buffering, all inserts are basically super fast appends.
This is super normal in my experience. And I can’t wait for the new UUID formats to land and get widely supported in libs to simplify discussions with event producers :)
millisecond precision is great for a lot of use cases
What I said was that it's useful to be able to select timestamp precision independently of UUID implementation. One size that fits all fits none best.
You could name them by (time, id)?
In other cases, the UUID needs to be as random as possible.
It really depends on the use case.
For our “session” records, it’s a UUIDv7. This sorts beautifully, and if I wanted to, I could look at a log and easily see all the entries in a particular session.
For a larger db, we just need unique entries and at least in Dynamo, it is an advantage to equally distribute them as much as possible. UUIDv4 there.
With a pure counter-based system, you need robust distributed storage and you need the machine to reserve batches of IDs via committing writes to the robust distributed storage. Otherwise, a disk failure may cause you re-issue UUIDs.
Though, seeding a thread-local AES-256-ctr or ChaCha20 instance via getrandom()/getentropy() is probably a better fit for most situations. If you need sequential IDs for database performance, seed a simple 128-bit counter using getrandom()/getenropy(). If you're going to need more than 2^40 unique IDs, then use IDs larger than 128 bits.
Assuming getrandom()/getentropy() is getting you a high-entropy seed, it's easy to size the IDs to bring the probability of collision much lower than the probability of background radiation flipping a bit and breaking your equality test between IDs. If you're not running redundant calculations and/or on radiation-hardened hardware, it's difficult to argue against randomized IDs.
Yes, a pure counter based system is probably worse than one that uses time. Don't use counters, especially not in a distributed setting.
If you're clever enough, neither needs a branch.
They’re not in tree yet but there are a bunch of awesome pg extensions that provide access to uuidv7 (outside of just using it at the application level)
How old is UUID7? I can’t get the internet to tell me.
[1] https://github.com/swyxio/brain/blob/master/R%20-%20Dev%20No...
I've half-heartedly tried to look up his problem every time I've had to introduce UUIDs to something (most recently fixing agents not generating correlation IDs), and I have not figured out which version of UUID he was talking about. I now suspect it was some proprietary or industry-specific quote-unquote UUID spec rather than an industry wide one. I may look through the UUID7 spec at some point to see if they mention prior art. Much more plausible than him being a time traveler.
Putting the timestamp in the high bits of random ids is a “trick” i learned from DBAs (that used to be a thing!) in the 90s. And often the drive was to improve DB insert performance as it was for the other uses of an ID you can order and reason about.)
I used to be the program manager owner of the security event log in windows.
When things happen simultaneously or very closely in time on multi-core systems, thread scheduling can significantly affect observations of those things. For example, your thread quantum might expire before you get to the syscall to get a time stamp, or before you can pass a buffer to queue your event for subsequent time stamping.
In fact, on multiprocessing systems, it was very common to see out of order event log entries on Windows back in the day (2000-oughts). You also could not count on the log timestamp accuracy too precisely; 1s was pretty much the safe lower bound (some components truncated or rounded time stamps IIRC).
The probability of a collision is roughly the same as the probability of a fully grown dinosaur spontaneously manifesting in your bedroom due to quantum fluctuations.
More seriously, If you can use them, good old increments are probably best. They are fast and cheap. Especially in a database. They can have privacy/security issues (you could guess things by the values of ids of stuff). UUIDs are better in those case or when you deal with a distributed system.
Push them through a secure hash function, and that problem is solved too (assuming you can keep the base counter private).
Is generating UUIDv4 or UUIDv7 really too much effort? I'd assume that writing the row to the database takes longer than generating the UUID.
If I'm in a scenario where I think I need consecutive ids internally and random ones externally, I'll just have two fields in my tables.
This keeps your database simple and performant, and pushes complexity and work to the backend servers. This can be nice because developers are typically more at home at that layer, and scaling the backend can be a lot easier than scaling your database. But it also comes with the downsides listed in this thread.
I guess you could do this with complete table scans, hashing the ids and looking for matches, but that would be horribly inefficient. You could maintain your own internal reverse index of hash -> id but now I have to ask what's the point? You aren't saving any storage and you're adding a lot of complexity.
Seems like if you want random unguessable external ids, you're always better off just generating them and using them as primary keys.
Also, you aren't protecting your database "from collisions under all circumstances" - there's no guarantee your hash won't collide even if the input is small.
If you want a secure identifier, make a random 64 or 128 bits number (a UUID type 4). And do not use this number as an internal identifier, because identifiers performance is all about predictability and low entropy.
I'd love to see the math for the probability of the second option.
In the end we have to make some assumptions about the correctness of (some of the) components.
So depending on the consequences you might opt to reduce the risk or help mitigate the consequences.
To just state that it is about as likely as my coffee maker being a portal to the future isn't very helpful. Poor entropy sources or bugs are not uncommon.
But now the probability of bad things happening increased by about a factor of two, which is not acceptable.
(Anyways, comparing the probabilities does not necessarily mean that the things being compared are both bad or both good.)
ARMv8 guarantees that it's clock increments at at least 1Ghz, for intel and earlier ARM it's more complicated
In the early nineties it was not so, you'd get the same number of clock cycles again n again n again.
N then it gets tricky because cycle counts are thresholds set within which, if voltages n frequency are proper, the operation will complete deterministically w a soft error rate no greater than the system as a whole, about one per 30 years of hammering on the chip at sea level. Which is not enough for my tastes, n the jitter is a fucking mess.
I much prefer the GA144, least jitter of any platform bar none, sensible because it is fully asynchronous logic, no clock anywhere in sight until you connect it to an oscillator, n even then the vibration doesn't rock the system like that of a grandfather clock synchs w another grandfather clock with whose pendulum's swing the former clock's pendulum swing is aligned. GA144 it's pretty easy to tell average case complexity of a function down to the tens of picoseconds, at which point you have to check that there's no open window letting a draft in. In fact the time trial will tell you such a draft is coming into the house, it happened to me, while not from a parallel universe in spacial dimensions it is by all means from another universe in the time dimension.
It's nanoseconds.
https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
> In a monotonically increasing sequence of values, all values that have a predecessor are either larger than or equal to its predecessor.
These are available via the https://www.erlang.org/doc/man/erlang.html#monotonic_time-0 function.
https://www.erlang.org/doc/apps/erts/time_correction.html#st...
> In a strictly monotonically increasing sequence of values, all values that have a predecessor are larger than its predecessor.
Strictly monotonic values imply some synchronization / coordination, with an associated performance impact when there are many concurrent processes. This functionality is available via the https://www.erlang.org/doc/man/erlang.html#unique_integer-1 function. With a warning associated with it:
> Strictly monotonically increasing values are inherently quite expensive to generate and scales poorly. This is because the values need to be synchronized between CPU cores. That is, do not pass the monotonic modifier unless you really need strictly monotonically increasing values.
You only really need strictly monotonic global identifiers if you need immediately-consistent first/last-write-wins. If you can instead rely on eventually-consistent first/last-write-wins (i.e. if your write events enter an event store/queue that linearizes them by ID, and then all "simultaneous" writes but the one with highest ID priority can be dropped/ignored, either during processing, or on read), then I'd recommend first considering packed (nodeID, seq) pairs. And, if you want global event orderibility, considering the snowflake ID formulation (timestampMajor, nodeID, timestampMinor, seq) specifically.
> ./clock_gettime_demo/clock_gettime_demo
clock_getres(CLOCK_REALTIME, ...)=1 ns
clock_getres(CLOCK_MONOTONIC, ...)=1 ns
CLOCK_REALTIME 30 samples:
1689957434662039455
1689957434662039526 (diff=71)
1689957434662039566 (diff=40)
1689957434662039606 (diff=40)
1689957434662039636 (diff=30)
1689957434662039676 (diff=40)
1689957434662039706 (diff=30)
1689957434662039736 (diff=30)
1689957434662039766 (diff=30)
1689957434662039796 (diff=30)
1689957434662039826 (diff=30)
1689957434662039856 (diff=30)
1689957434662039886 (diff=30)
1689957434662039916 (diff=30)
1689957434662039946 (diff=30)
1689957434662039987 (diff=41)
1689957434662040016 (diff=29)
1689957434662040047 (diff=31)
1689957434662040076 (diff=29)
1689957434662040107 (diff=31)
1689957434662040137 (diff=30)
1689957434662040167 (diff=30)
1689957434662040197 (diff=30)
1689957434662040227 (diff=30)
1689957434662040257 (diff=30)
1689957434662040297 (diff=40)
1689957434662040327 (diff=30)
1689957434662040357 (diff=30)
1689957434662040387 (diff=30)
1689957434662040417 (diff=30)
CLOCK_MONOTONIC 30 samples:
2168262770533974
2168262770534023 (diff=49)
2168262770534054 (diff=31)
2168262770534094 (diff=40)
2168262770534124 (diff=30)
2168262770534164 (diff=40)
2168262770534194 (diff=30)
2168262770534224 (diff=30)
2168262770534254 (diff=30)
2168262770534284 (diff=30)
2168262770534314 (diff=30)
2168262770534344 (diff=30)
2168262770534374 (diff=30)
2168262770534404 (diff=30)
2168262770534435 (diff=31)
2168262770534464 (diff=29)
2168262770534495 (diff=31)
2168262770534524 (diff=29)
2168262770534555 (diff=31)
2168262770534585 (diff=30)
2168262770534615 (diff=30)
2168262770534645 (diff=30)
2168262770534685 (diff=40)
2168262770534715 (diff=30)
2168262770534745 (diff=30)
2168262770534775 (diff=30)
2168262770534805 (diff=30)
2168262770534835 (diff=30)
2168262770534865 (diff=30)
2168262770534895 (diff=30) running longer zeros test ...
sampled 10000000 pairs; 0 time diff zeros = 0.000000%; 0 nano diff zeros = 0.000000%
starting parallel test 24 goroutines x 10000000 samples ...
10000000 samples from a thread; 0 collisions inside the thread; 0 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 945466 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 1982688 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 2739919 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 3334361 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 4109772 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 4489881 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 5157178 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 5596508 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 5854763 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 5937583 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 6434076 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 6521917 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 6932626 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7104428 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7285076 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7514904 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7833317 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7737265 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7723545 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7730441 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 8311161 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 7965117 collisions with other threads
10000000 samples from a thread; 0 collisions inside the thread; 8460173 collisions with other threads
102297835 final samples; 137702165 total collisions = 57.375902%; possible duplicate collisions? 0I bet there is a fair amount of optimization in the compiler that leads to back to back assembly calls of reading the clock register. If subsequent time.Now() calls happen within 3 clock cycles of each other, can you really fairly expect unique nanosecond precision…
My most memorable and least favorite variety of this is when people try to assemble a timestamp from two system calls, one for the most significant digits and a second for the least.
If the smallest digits roll over from 99x to 00x after you read the large digits, due to process preemption, you can create a time stamp for an entity that happens before the entity that caused it to exist. This breaks some code spectacularly (I’ve seen infinite loops at least twice).
If you haven’t memorized this as a thing to always avoid, you end up with tests that pass 99.5% of the time, and it can take someone with very good pattern matching skills to catch that the same test has been red once a week for a month and a half, which is a very long time for a logic bomb to live in CI/CD code before getting fixed.
“It can’t be a race condition as those two events happened in the exact same time”
If the global is less than the timer, use the timer value and set the global to it.
If the global is greater than or equal to the timer, increment it and use that value.
Then you aren’t using a nanosecond clock.
If you want actual nanosecond precision then you probably want rdtsc.
HLC captures the causality relationship like logical clocks, and enables easy identification of consistent snapshots in distributed systems. Dually, HLC can be used in lieu of physical/NTP clocks since it maintains its logical clock to be always close to the NTP clock. Moreover HLC fits in to 64 bits NTP timestamp format, and is masking tolerant to NTP kinks and uncertainties.
Ended up working around it by adding numbers after the decimal point. DynamoDB apparently supports up to 38 digits of precision, and JavaScript (we're NodeJS based) by default encodes numbers to allow for up to 16 digits (combined, before and after the decimal point). A UNIX epoch millisecond timestamp is 13 digits, so we were able to use 3 just to add uniqueness without having to update anything else in our codebase.
We certainly now plan to essentially always use string-based (and generically named) partition and sort keys, which would allow us to more easily do what you're describing.
Probably a good idea to have somewhere to silo bespoke implementations. Just gotta hope they end up being unique.
https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...
It's a draft but there's a lot of implementations out there.
Go implementation: https://github.com/segmentio/ksuid
A few things to consider:
1. This would depend a lot on how regularly you are checking, the more regular, the more collisions.
2. There may also be some weirdness where threads doing similar tasks will synchronise or desynchronise to maximize throughput.
3. Your system may not offer accurate nanosecond time. For this reason some OSes tend not to offer lower than microsecond time, as the clocks simply cannot offer higher usable accuracy. You're also measuring the time to call the function(s), create the timestamp, etc.
A simple solution I had years ago was to add random precision to reduce collisions. That breaks most tie situations. If you have 5% ties in nano seconds, with random pico second accuracy your collisions are down to 0.005%. You could also seed the random offset by an ID.
The high resolution precision time counters are derived from the system base clock, usually operating at ~33MHz, which translates exactly into that 30ns granularity observed.
If you really want robust time derived timestamp identifiers, truncate the high resolution timer to at best 10µs resolution replace the low bits with the hash of them, concatenated with the value of the CPU cycle counter (`RDTSC` on x86).
constant_tsc has been a thing for more than a decade
> execute instructions out of order, and even speculatively execute
rdtscp serialises
> Not to mention that it'll have a dozen different clocks - which are not guaranteed to be in sync.
synchronised_tsc has been a think for about 6 years now
Generally, you can have consistency, speed, or low cost - but not more than two at the same time.
[https://community.intel.com/t5/Software-Tuning-Performance/H...]
If you really, really, really need system wide, nanosecond precision timestamps, you'll have to resort to dedicated hardware incrementing a counter at the desired rate, and with a well known latency for each read access. On the hardware and driver level you'd have some MMIO port mapped into user space with an identity transform between bus address and process address space.
However this still doesn't solve the problem, of the scheduler being able to throw in several milliseconds between reading the high precision timer value into a register and writing it back into the memory holding the timestamp variable. Seriously, on your typical computer system software derived timestamps at more than 100µs resolution are kind of bogus.
Constant-rate TSCs are ~15-20 years old. Synchronized TSCs are at least ten.
Also RDTSC produces a 64-bit result, so it does not overflow at a rate of several Hz.
Here's a small online visualization of RDTSC average and standard deviation I just hacked together: https://gist.github.com/datenwolf/151486f6d73c9b25ac701bdbde...
On a system with frequency scaling you can see that under higher load the difference between RDTSC in subsequent iterations of a tight loop that does nothing else than reading that register will drop. Here's how it looks on the system I'm currently using: https://www.youtube.com/watch?v=FKKjSJ1JZ78
Unfortunate wording, RDTSC itself is not influenced by frequency scaling, it has constant frequency on modern CPUs after all. Your video nicely shows that RDTSC delta is influenced by CPU frequency, as expected, but how does it affect using RDTSC as a clock? On my CPU RDTSC seems to tick at 3GHz, for example. I wonder how precise it is though, how much its frequency can drift from spec.
Doesn't this hash-step only increase the probability of collisions?
What is this step intended to solve?
you're concatenating two values and then taking the hash of the combination, ie:
hash(low bits + CPU cycle counter)
When you are trying to reduce collisions, why would you use a function that is known to introduce collisions?
Knowing the timestamp delta is ~30ns then even a 1 THz processor would only execute 30,000 cycles before said timestamp increases and the outcome stays unique anyways. From that perspective, taking the low 16 bits of the cycle counter is already guaranteed to help produce perfectly unique timestamps, and without the risk of introducing hash collisions. It's also significantly easier to compute and now monotonic* now, whereas hashes were neither. From that perspective, I too don't see what value the hash is supposed to add to the information being fed to it in this case.
In threaded/distributed/parallel scenarios you may wish to throw the lane/core/node number in the bits as well. In the case having the same timestamp is supposed to be invalid this leaves you a simple deterministic way to tiebreak the situation as part of the creation of the timestamp itself.
*A 10 GHz CPU running for a little over 58 years could risk a 64 bit counter rollover in the middle of a time delta. If that's too close for comfort or you want the code to work on e.g. 32 bit counter systems, you'd need to eat more cycles and registers to set another bit to the outcome of whether current cycle count is < the one at the start of the current timestamp delta.
TIMESTAMP010111101010101TSC "looks better" than TIMESTAMP000000000000000TSC even though they contain the same information.
I would drop the hash, it's deceptive.
I don't believe it breaks the monotonicity, though? I mean, it would if it weren't already broken. If you're taking the low 16 bits of the TSC, then a rollover in those 16 bits during the same timestamp will already go backwards. TIMESTAMP0...0 follows TIMESTAMPf...f.
In the cycle based case looking at the whole value is the same thing as looking at a relative time stamp which has more precision that the system clock. In this way, it's "truly" monotonic across the entire value, not just monotonic on a part and unique in another.
Side topic: It also comes with an even stronger guarantee of always increasing instead of just "not changing direction". Is there a name for that?
It's a nitpick, but it concentrates the entropy. It doesn't create any.
I do think it will make the answer more clear, as the hash concentrates the less than 64 bits of entropy on that 128 bits of original data into a usable 64 bits package.
Ok, what is the entropy created by this function that maps a 4-bit number to a 64 bit number:
0 -> 0
1 -> 1
2 -> 1
3 -> 1
4 -> 1
...
15 -> 1(I'm using Shannon entropy.)
then it's Kolmogorov complexity is also extremely low.
Look if you have a well enough hash function, it output should be near the Shannon limit and hardly compressible, and ideally contain as much entropy as it has bits. But you can feed in just a single bit or the entire knowledge of humanity, in the end you're going to get a fixed amount of bits, and entropy near of that, and if you throw any form of lossless compression at it, it will hardly compress.
But quantum mechanics tells us, that information cannot be destroyed. So when you feed it more bits, than it emits, then its mostly the entropy of the information you feed in, that you get out of the hash. But if you feed it just a single bit, the additional entropy comes from the computational process.
I know, this is now getting really philosophical, but here's something to ponder on: How would you implement a hash function for a reversible computing architecture?
Hashes are EXTREMELY compressible, albeit known algorithms are extraordinarily slow. E.g. I can compress any SHA256 output to a matter of kilobytes, maybe less, by using the SHA256 algorithm as the compressor algorithm and iterating through seeds until I get a match. With true entropy you can't guarantee that for all inputs, regardless of how long you take.
Different types of "information" ate at play here with the different types of entropy as well. If I have a 16 bit hash function and feed it a 64 bit value 48 bits of computational information is lost (at minimum). What happens with the physical information you used to represent the computation after you get the information result is separate from what happens with the computational information.
The result of applying a deterministic function on a random variable cannot have more entropy than the underlying random variable. This is a theorem, one that is trivial enough to not have a name. But you can find solution sets to homework that will prove it for you: https://my.ece.utah.edu/~rchen/courses/homework1_sol_rr.pdf
low bits + CPU cycle counter
It's not worse than the hash solution, I'm just saying it's not necessary to hash it if the only objective is to reduce collisions.
In fact the hashing solution, if it is replacing the low bits with a hash of low bits plus something else, is actually destroying valuable time information.
The combination of multiple counters incremented by individual unsteady clocks used to be a source for pseudo random scrambler sequences; these days we prefer LFSRs, but overall this is something that can be weird.
Hence my recommendation: Just throw xxHash32 on concatenation of the HPTC's low bits and the CPU clock cycle counter, and forgo any pretense of monotony in the low bits (because very likely you don't have it anyway).
But here are two more doubts:
1. On at least some systems, clock_gettime will be implemented by a vdso call that (on x86) uses rdtsc to give you the time, so you should expect its results to be pretty highly correlated with an rdtsc immediately afterwards, so you aren’t really adding useful entropy (whereas you are losing time-locality of your identifiers which may be desirable if they are to end up as primary keys somewhere)
2. On some systems (eg some AMD processors), rdtsc gave me pretty low precision results (eg rounding to the nearest 10 cycles) so you also won’t necessarily get the entropy you would expect from the description of the instruction. I failed to find a reference for this too apart from an offhand mention in a paper about timing attacks.
It is reasonable to assume that a raw nanosecond timestamp is a unique identifier in cases when you can reasonably expect such identifiers are not generated too offten.
I.e. this is Ok (and even redundant) for identifying manual interactions a single user would pdosuce. It probably is also Ok for labelling manual interactions multiple users would produce if that's a small team.
But this got me thinking, how feasible it would be to tie the various clock systems of a computer to some reference clock, like 10 MHz GPSDO? Obviously it wouldn't improve the granularity, but you could ensure that the timestamps are actually accurate. Because otherwise I doubt that random computer clock would be accurate down to 32ns even with NTP.
There's still an in-between of PPS and NTP: PTP.
Measuring that error is difficult. A possibility is to run a program periodically making random reads from memory (avoiding the CPU cache) to generate a PPS signal on the memory bus, which can be observed with a scope. There is a lot of noise due to other memory activity, RAM refresh, etc. From the configured memory speed and tRCD+tCL timings the uncertainty of the error can be reduced.
This might improve with new hardware. There is a feature called Precision Time Measurement (PTM), which is a hardware implementation of an NTP-like protocol in PCIe, but so far I have seen this working only on some onboard NICs.
Problem solved for the next 200 years.
At some point we have to question the sanity of using one single flat address space for everything from the tiniest identifier to the... well, "Universe", as if it makes sense.
We can have registrars for global ids, and we can nest local ids inside them, we can have a hierarchy, and we can have local compact ids, 32, 64 or 128 bit, which will never collide, and be locally cohesive.
So why aren't we doing this? Is it ignorance? Is it because magic is easier than actually figuring out the synchronization and order of things in a system like this (and no, synchronization does NOT imply you need to issue ids strictly linearly).
Honestly I'm at a loss of words.
Wikipedia gives a different history, that it was originally for networked computers - https://en.wikipedia.org/wiki/Universally_unique_identifier#...
isn't IPv6 is basically that? just restricted to internet addresses
We have this. It's called OID (Object Identifier) and is used in X.509, LDAP, SNMP, and many other technologies. A global registry exists (I have an entry) and it's a giant tree.
> So why aren't we doing this? Is it ignorance?
The problem you are solving here is for durable, long-lasting keys. There is also a need to generate large batches of short-lived keys that need to never collide for security/identification purposes. A centralized registry will not work for that and it requires a wholly different technique.
And continue this concept downward. Except when it's inside your org, you're the registrar of your namespace's sub-OIDs, and so on. And there's precisely no reason not to have hierarchical sequential ids for everything. You need to generate ids on 100 servers? Good, give each server a namespace. You need to do that in a 100 processes on each server? Good, give a sub-namespace to those too.
And the best of all is that the above-organization OID part of the tree is ONLY needed if you show these ids outside your organization. Otherwise you can use the internal private part of the identifiers.
So what am I missing here? Maybe they need to be hard to guess, so add a random key part to them (distinct from the generated sequence part) as a "password". Done.
What do I gain for this? UUIDs solve all of this because the chance of creating a duplicate is so low it can effectively be ignored. I can namespace UUIDS and create chains of them if needed.
This is the reason both exist. We need both. We can use both.
More specifically:
1. When you create something, the creator names it.
2. When you bring something you created outside your scope, you prepend your name to it.
It's kind of what we do with (actual) children if you think, slightly less structured, but the idea was always there. Just add recursion to complete the principle.
I've never seen duplicated UUID generated, and if that's the issue, you may think about using cryptographic randomness source to generate it.
UUID v7 has millisecond precision + 72 bits of randomness, which is _a lot_.
Also, central registry for IDs seems like a great way to shoot yourself in a foot, in case it's down, your network is down, you're on cellular connection, on a plane...
For example, you might have "comments" and "posts", and later merge the two entities and call them "notes". Now you have to figure out a way to merge the identifiers -- with UUIDs you don't have issues like this, because they are universally unique.
A lot of developers have found that UUIDv7 provides the properties they want (unique identifiers which sort by creation time), and they don't come with the hassle that other approaches come with.