Hacker News Reader

Comment by wood_spirit | Hacker News Reader

This is why you should use ids that combine both a time component and a sequence.

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.

View on HN

I’m feeling a bit like an accidental time traveler, because I can recall a conversation at a tech meetup that had to have been at least ten years ago where someone was struggling with unique UUIDs because they were bursting above 1000 UUIDs per millisecond and not happy with the available options.

How old is UUID7? I can’t get the internet to tell me.

UUID7 was first drafted a bit over a year ago: https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...

That's kinda what I figured. So you can see my confusion.

Perhaps one of many on this list[1]? ULID is listed as having 1.21e+24 unique per millisecond. I have no idea though about what may match up with your timeline(s).

[1] https://github.com/swyxio/brain/blob/master/R%20-%20Dev%20No...

Were they not happy due to possible collisions or something else?

Yeah they had a problem where the amortized ID rate was less than the number of valid UUIDs you could generate in a given time interval, but with a peak rate well above that, so UUIDs weren't quite going to function for naming/numbering them. You gotta be pushing a lot of messages through a system to hit that, but it's possible. And adding more layers of coordination on top of something meant to reduce coordination overhead tends to... make things messy.

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.

UUIDv7 was first proposed just a few years ago, but the rfc contains a good list of well known ULID systems that predate it.

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.)

Why do you need the time component anyway? It's just eating up bits in your UUID without contributing much entropy.

Because it allows te encoding of information the id. This makes it, at least in my experience, somewhat sortable.

You need it to make database indices perform better.

If you don't need that, but just need a random UUID, UUIDv4 is better.

But shouldn't that be a separate field then?

The logistics of combining fields in indexes and identifiers is relatively complex, while the logistics of indexing a single field is comparatively trivial. This is also why you don't ship timestamps using separate fields for second/minute/hour/day/month/year, but a single ISO-string or UNIX timestamp as representation: it makes querying and interpreting the value more consistent.

Create a new column with an MD5 hash of the other columns. Easy.

This is how it works, except it's not MD5 but a less-costly hash function

MD5 is a useless hash function these days.

It's not cryptographically secure (anymore). And there are cheaper non-cryptographically secure hash functions.

Disagree on "relatively complex".

    create index on $table ($field1, $field2);

Seems pretty simple to me.

It is noy just the DDL of the primary table that needs to care about it, but also all foreign keys, DML, queries, APIs accessing the data, etc. Storing that UUIDv7 is likely going to be cheaper than pushing the cost of keeping a composite identity onto other components and systems that work with that data.

Well, that depends on how you manage it. An ORM will find it trivial. Custom SQL, not always so much.

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...

I am curios about this, and might be misunderstanding what you mean.

Can you layout a demo architecture where you use multiple keys like you propose?

There are many DBMSes that combine columns into a singular primary key. Performance tradeoffs vary, especially when it comes to indexing.

Any pure relational database design will eschew surrogate keys - most real-world systems will (should) add them back - because a surprising number of good natural keys end up changing (names change, phone numbers change, emails change, twitter handles become irrelevant/disappear, location of birth may change subject to geographic regions changing size...).

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...

> location of birth may change

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.)

So British place of birth means "mother's residence" and not place of birth?

Official guidances here: https://assets.publishing.service.gov.uk/government/uploads/...

Could maybe be just a mistake when doing the UK registration ? It's an easy fix if wanted.

> Could maybe be just a mistake when doing the UK registration ? It's an easy fix if wanted.

Changes! lol

That's my memory of it. My British passport is expired, and is probably somewhere in my parents' house. I don't actually know what it says on it. I do clearly remember that at least one British form of ID I had at one time recorded my mother's place of residence rather than my actual birth place. I thought it was the passport. Maybe I was wrong.

But then you have 2 identifiers which complicates everything.

I feel like v7 is almost a strictly better v4. Assuming you can generate a v7 (you have a time source), what are the disadvantages?

Entropy. You loose bits to a known source, which reduce entropy of the UUID.

128 bits is a lot of entropy to go around, though.

I do feel 74 bits per second is enough though. That would require 2^(74/2) = 137 billion UUIDs generated in a single second for a 50% chance of a single collision.

You can hand out uuidv4 to clients without revealing anything.

Anyone who can see the uuidv7 can determine at what time it was generated. You might not want that for things exposed to users.

I dont know why people use relational databases other than they were first and “that’s the way it’s always been done”.

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?

They were not first.

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.

https://en.m.wikipedia.org/wiki/ISAM

I've been interested in learning more about them and how to best utilize them in my company. What graph database and query language would you recommend (regardless of stack)?

1. Memgraph 2. Neo4j

As for query language: definitely Cypher!

How do you do constant time lookup an graph databases?

My intuition let's me know that you can not get below O(n log n) (Lower limit for comparison based ordering)

> 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

You aren't describing a property of a graph database. You're describing a property of some set of key value based systems.

The reason why you want indices is because some query patterns don't have a key to perform a look up on.

You might want to read Codd's paper: https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

When you sort them they will be ordered by generation time. This is useful in UIs, and greatly improves performance in databases (how much depends on DB and use case).

Iirc you dont want to spend entropy that you don't need. The advantage of using the time means you need to spend less bits on expensive randomness and thus generation is cheaper.

I only work in embedded, so I’m not sure about fancy computers - but when we make UUIDv7s, I am certain the random is faster than pulling the time, formatting for milliseconds, then storing in position.

PRNGs are cheap to compute, and 'random' enough.

> Why do you need the time component anyway?

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.

More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.

Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything

That sounds too good to be true. Is that really true of all grapdb’s?

Also, if that’s really true why can’t everyone just use graphdb’s?

Because of vendor lock-in with the LAMP stack over the years. Every host used MySQL, how many had Neo4j as available?

How big is the 1 though?

Look, if you have N items related to X, at insert time, you store them in an array and have X point to that array, instead of foreign keys.

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?

How is that different from a clustered index?

A clustered index requires O(log N) lookups, since it's still an index.

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.

What about when you delete rows? Do you just leave the space unused now? Or if you update a row to be larger? Rewrite the whole array (so possibly O(n) updates)?

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.

When you’re talking about data sets so large they dictate what hardware you use, and introduce terms like “cluster”, then 1 = √n

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.

Why sqrt(n) and not log(n)?

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.

Speed of light.

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.

Oooh interesting, thank you. I totally misunderstood this as the "integers never need more than 64 bits, so hash tables are constant" argument.

Integer arithmetic is really quantized logarithmic complexity. If your hardware has a bucket your number fits into, you're calculating n+1 or nxn in constant time. But if your data set doubles in size (especially for multiplication) you may find yourself in a bucket that doesn't exist or a more expensive one. Contemporary code is more likely to reach for bignum which is logn, but again stairstepped to each number of integers it takes to represent the entire number. A bigger problem when your data set is sparse, so that values grow faster than population (eg, UUID).

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.

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.

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.

Are your hash keys 8 bytes long? Mine aren't. Mine aren't even close.

Sure, they can be and are often longer, but not because you were forced to use long keys, it just happened that the thing you want to store in a hash table is a long string. The way you worded it made it sound to me like you were saying that one has to use long keys, not that in practice one often has to deal with long keys. But even then I am not convinced that this should give an additional factor in the complexity analyses, I think I would argue, at least in some situations, that calculating hashes of long keys should still be considered constant time, that for the longest keys. But I can also imagine to take this into account if the key length is not only big but also highly variable.

That will depend on which graph database you use as a graph database might just store the graph in an underlying relational database. And it will also depend on what kind of data you have and what kind of queries you want to perform. For a graph database it might be faster to navigate along links in the graph but I would guess you will have to pay a big performance penalty if you have to operate orthogonally to your links, like aggregate across all instances of some entity.

Graph databases don't solve that. All databases, document, graph, rel ALL implement indexes to find specific things in the exactly the same way. Very well known tree, hash and other techniques.

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.

Page splits… page splits everywhere.

depending on scale and architecture, either behavior can be better. 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)

If that is the case then why shouldn't the storage system hash the IDs itself, to spread them as it requires?

Because sometimes you want some data to be collocated, while the rest sharded.

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.

Sounds like it should be an attribute of the index and not require a change in the data. To me, anyway.

    CREATE INDEX ... USING HASH;

I’ve never seen that kind of optimization on a dataset that would fit on a database server of any kind. Tens of PB or EB usually, but sometimes only several hundred TB if it’s high load/in-memory only.

Just swizzle the ID.

Being random within each shard is still bad for write performance. Going fully random seems like a bad way to accomplish this goal.

Why not keep the timestamp bits to use when appropriate, but use some of the random bits for shard selection?

Only when writing all at once and when you know what the shard boundaries are and the number of shards (and boundaries) are stable. If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically.

Very large real world datasets are unlikely to be static long enough, and equipment stable enough, to not consider this effect.

> If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically.

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.

I never said anything about bit or key length at all? Let alone how much was random or not? Perhaps you’re confused?

Let's start over.

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.

UUIDv7 has a specific format that doesn’t support that.

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?

What do you mean it doesn't support that?

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.

Except you literally can't do random distribution AND be compliant with UUIDv7 if you use any sort of normal lexical sorting/indexing, as they use the start of the key as the most significant bits. UUIDv7 is literally designed to have stable lexical sorting orders, have the time as the most significant bits, and have the most significant bits of the time as the most significant bits of the key! It's their primary design criteria!

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.

> Except you literally can't do random distribution AND be compliant with UUIDv7 if you use any sort of normal lexical sorting/indexing, as they use the start of the key as the most significant bits. UUIDv7 is literally designed to have stable lexical sorting orders, have the time as the most significant bits, and have the most significant bits of the time as the most significant bits of the key! It's their primary design criteria!

> 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.

The point I'm making is all these shenanigans are completely unnecessary, don't really help, and make everything extremely hard to manage, reason about, and get performance from - all to try to force usage of a specific key format (UUID) in a situation which it is not designed for, and for which it is not suited.

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!

"it allows easy/cheap write combining" is not "completely unnecessary". What the heck, at least be consistent.

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.

Wow a long thread of back and forth and confusion :)

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 :)

Just explicitly use (time, random uuid) as a key in your sorting, instead of sullying your uuid with time information?

ULID schemes aren't just about big endian sorting advantages, they often better enable time-based sorting mechanisms.

One benefit of keeping it separate is that you can choose the precision of the timestamp necessary. "Millisecond precision" is arbitrary and commonly insufficient.

it's commonly totally sufficient for IDs to represent a rough sort order

millisecond precision is great for a lot of use cases

I didn't say that it wasn't. Hell even ms is too precise for many use cases (usually where date is used instead).

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.

Lucky for you, they also define UUIDv8 as a free-for-all where you can do whatever you want, and nanosecond precision is one of the examples given in the RFC.

> 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.

You could name them by (time, id)?

UUIDs can serve different purposes. As others have mentioned, database performance on inserts might trump the need for difficult to guess UUIDs.

In other cases, the UUID needs to be as random as possible.

It really depends on the use case.

Yea. This is an easy one. We use both.

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.

Otherwise, failure recovery requires robust storage. Upon startup, you just wait until your timestamp ticks over, and then you know you're not re-issuing any UUIDs.

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.

> 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.

Yes, a pure counter based system is probably worse than one that uses time. Don't use counters, especially not in a distributed setting.

And they play nicely with sort ordering in popular databases like postgres!

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)

The problem with UUIDs is they are completely unreadable. Not just you can't understand them, it is prohibitively hard to even distinguish between them visually. This is why identifiers which would not include any bit of information (or noise) beyond the necessary minimum are useful in some cases.

Thus UUIDv7.

Don't even need the "same millisecond" part to save a few cycles, use case depending. An overflowing increment with a counter of any sort plus a few random bits is usually enough.

If you're clever enough, neither needs a branch.

UUIDv7 has two at least two such monotonic strategies. You can use a counter, or you can use those bytes to increase the random entropy.

Isn’t it simpler to use sequence keys then?

Yes, but only on single machines, UUID and co are intended for distributed systems.

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.

You could also keep a global incremental index for that, assuming there's some authoritative server that has to be polled sequentially to get them.

Probably too much overhead when conflicting UUIDs are a few orders of magnitude less likely than the clients crashing from some random bug though.

So just prefix the node ID which is assigned when the node joins a swarm

How is that easier or better? Now you're letting your infrastructure details bleed into your database.

They should bleed into your database. The database is part of your infrastructure and it contains details like where to find the replicas and so on

Why? Tight coupling doesn't make things easier.

You’re complaining that the infrastructure details are bleeding into the intrastructure implementation?

Infrastructure details are bleeding into non-infrastructure implementation. Your database content is not an infrastructure implementation.

the content is not, but it can use a database function, such as CURRENT_TIMESTAMP or RANDOM() can it not?

I'm not sure what you're getting at. How are those connected to the topic? Those functions aren't infrastructure implementations either.

Ah but you see, UUIDs are web scale.

And by web scale, I mean they're too big to exchange by any offline channel.

It's 128 bits vs 64 bits - not really that much of a difference.

FWIW… we’re using UUIDv7s over BLE.

Should you, though? BLE itself uses UUIDs, but the ones it uses are in a shortened format just because the BLE frames are small and the protocol is not too fast.

Granted I've even used JSON over GATT so maybe I should keep my mouth shut :).

It’s for an auth use. And at least we’re using CBOR. But I get your point.

> This is why you should use ids that combine both a time component and a sequence.

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.

> threads are assigned to cores when they are started

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.

>> threads are assigned to cores when they are started

>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?

Reply on news.ycombinator.com