Understanding the high-contention-allocator

I was reading the HCA code in various implementation to get a better understanding of FDB, and came across this line:

I was a bit confused because AIUI, all reads within the same transaction see a consistent snapshot of the database. How is it possible that latest_counter[0] > start could ever be True, when start is initialized using the same range query as latest_counter[0] and within the same transaction?

I was also wondering what the trade-offs of the HCA are, compared to eg. creating 256 counters and picking a random counter to increment and generate an ID (with the index of the counter shifted into the low bits).

I think the reason for that line is that another thread could use the same transaction and advance the window, in which case this may not become apparent until later in this allocation attempt. Any writes to the a transaction would be visible to later reads in that transaction, so you could see the counter advance here.

I haven’t thought about this extensively, but I guess one thing I notice is that the HCA uses a window quite a bit larger than 256. You could equally run more counters, though if the counter index becomes the low order bits we may have a reduced ability to generate shorter prefixes when the number of directories is small. That said, you should be able to easily get a good amount of concurrency while still starting at 2-byte integers.

I see, that does make sense… Although that would be a slightly horrifying way to use a database transaction.