How do atomic updates work at scale?

Question

I am working on a weird ID system where I generate all the IDs in advance and need to atomically pop() one from the database, so no ID is read twice at the same time (and so used more than once). This is simple and straightforward when you have 1 request per minute, but hardly at 1 per second or faster than that.

I am aware of the concept of atomicity but don't know how it's typically implemented in a database. My question is, first of all, what it's roughly doing to implement it on a single machine instance. But more importantly, how it is implemented at scale.

If I want to have the ability to pop millions or billions of IDs per second from this database, I can't conceive of anything except one physical machine with maximum file system, cpus, and memory size that today's technology allows, and it allowing traditional database atomic operations on these records. Then all HTTP requests to the machine would be taken to a single IP address of a single machine. But even with the best technology I imagine it would be a bottleneck. Could a single stock machine reach billions of writes like this per second? From my readings, the answer is no.

So I'm wondering, how do you do atomic operations on a distributed network of databases/machines? If I have 10 thousand machines, I can imagine 1 billion writes would be a piece of cake. But how do you do these atomic interactions in such a system, given there is likely more than one copy of the database, and so likely data would get out of sync, and IDs would get used more than once.

I could see this being a problem with more than just my system, but with any atomic operation.

In searching for this, you find stuff like distributed counters, but that is different. That makes sense. You write to your queue or whatever, and then sum the end result over time. It doesn't address the atomicity problem here.

It seems at some place you need a single point of entry. But I don't know how that could possibly work at scale.

On a practical level, I am looking for how to do this on Google Cloud, but that's beside the point.

Answer 1

First things first, based on this question it appears you do not at all understand the concept of atomicity. I’d recommend doing a bit more work to understand that before moving on to distributed computing concepts.

Secondly, why in God’s name are you making a weird ID system? People have made perfectly fine, safe, practical ID systems for decades. Ones that are well tested, scale to millions of entries per second, and are already done. I am highly skeptical that your needs are unique in decades of computing, or that making your own will add meaningful value.

My question is, first of all, what it's roughly doing to implement it on a single machine instance.

It is incrementing an int (or at least a word sized value). Fetch and increment is an actual atomic operation, and it gives you your unique IDs.

Persisting the record isn’t atomic, but inserting into a queue can be done in a lockless manner (though not quite atomic). That gives you a transaction log, which eliminates half of your concurrency problems (ordering). As each transaction is processed, the uniqueness constraint is checked (usually during a collision during insertion into the index).

So I'm wondering, how do you do atomic operations on a distributed network of databases/machines?

You do not. By definition, any distributed operation is interruptible.

For IDs, scale is achieved by scaling the request. Instead of requesting a single ID, you request blocks of IDs. It is much faster to count to a million when you increment by 1000 rather than 1. The entire block is marked as “used” and the client can safely use those thousand IDs (or whatever your block size is) safely. You can then (if needed) build a pyramid scheme of these servers. The top server hands our blocks of millions, the next ones down break down the millions block they got from the top into thousands for direct consumers. Add layers as needed. Standard load balancers are your single point of access for clients to get at the bottom of the pyramid.

And again, persisting the record is far, far more difficult. How to make a distributed database system is well beyond the scope of a StackExchange answer, even at a high level. Unless you work for a company making a distributed database, not something you need to understand in depth. “Hey maybe I need to make my own database” is pretty much the definition of “in the weeds”. Get out of the weeds, go back to the problem you started with. There’s no need to make it harder.

Answer 2

How does it work?

Database atomicity (aka the A of ACID) is an appearance of atomicity. The general idea for an update is:

• keep the old value where it is unchanged
• as long as the transaction is not committed, continue to provide the old value to every other db session;
• the operations belonging to the transaction, i.e the updated values, are written to a new place that is reserved for this transaction;
• once all the transactional steps are performed a commit is initiated;
• if the commit succeeds, the old value in the old place is no longer accessed, and all the future access access the new value.
• if the commit fails, the new things are just ignored.
• The key to atomicity is the final step of committing, because the switch from old to new should not be interrupted. Since this might require several writes, it’s not real atomicity as in a cpu, but a simulation of atomicity with locking and a clever data layout.

This approach is fairly general, and common many kind of databases and even queue managers. But this explanation extremely simplified: in a database you’d need to add a lot of administrative storage management (record pointers, management of storage pages or blocks, update of indexes, discarding of old data vs reuse of place, etc.), as well as some locking schemes to prevent two processes to update the same value in the same time. But these details depend a lot on the context and type of db considered (e.g. in a key/value store with optimistic locking, you’d not do it exactly as in an rdbms with serializable isolation level active)

How to scale

First of all, db engines are highly optimized and can achieve a high level of concurrency on a single server.

Then you can scale by partitioning data on several servers. DB atomicity is then reached using a distributed 2 phase commit.

But your problem implies a bottleneck that makes it difficult to parallelize : you have keys that you have to provide in a given order. As long as this order is fixed, and you cannot afford to loose a key, it will all come down to depend on a single node to ensure the proper serialization. Vertical scalability is the only option.

If you can relax the order, you could compute keys in advance and distribute them on several nodes, each being the free to pop them “atomically” without relying in a synchronous manner on a single server. Horizontal scaling will do the rest.