# Billions of ids per second, no coordinator needed

> Source: <https://infino.ai/blog/id-generation/>
> Published: 2026-11-06 00:00:00+00:00

# Billions of ids per second, no coordinator needed

## Introduction

While designing Infino, which as of this writing is [the fastest engine for search queries](https://infino-ai.github.io/search-benchmark-game/full/) on the Search Benchmark Game and [the fastest search engine](https://benchmark.clickhouse.com/#system=-&type=+sac) on ClickBench, we had to think through many parts of the engine from the ground up to design for scale and for the performance agent queries need. Identifier (id) generation and usage is one such part, and this post describes how our ids work. Writers mint these ids at billions per second without coordinating with each other, the ids don’t collide in practice, and after compression each copy of an id is stored in a little over a byte.

Every row in an Infino table has a system-managed `_id` column, which the engine assigns and users cannot set. It is returned with every search result, as users may want to later issue update or delete requests for documents they see in search, and need a way to identify a document. Also, every row in the table needs to store it, so that it can be returned, and at a trillion rows, every byte of an id costs a terabyte of storage as well as cache.

Our [previous post on Infino’s object-store architecture](https://infino.ai/blog/search-index-on-s3/) may be helpful, but is not required before reading further.

## Design goals

Given how Infino writes and queries data, we looked for the following properties in an id scheme.

**No coordination between writers:** Infino writers can run as multiple processes, on multiple machines, all appending to the same table on object storage, and there is no central server to hand out identifiers. A writer should be able to mint ids on its own from the moment it starts, without registering with anyone.

**Ordered by time:** Many use-cases need to retrieve rows based on creation time, such as fetching fresh data or debugging. It would be nice if the id itself recorded the creation time of a row, so that a separate timestamp field to store creation time is not needed. Since Infino tracks the min and max id of each superfile (Infino’s Parquet file that holds data and indexes), time-ordered ids also let updates and deletes skip every superfile whose id range can’t hold the id they are looking for.

**Compact when stored:** Every row stores its id, so ids written close together should share most of their bits and compress well (random bits do not compress).

**Readable by any Parquet reader:** Since superfiles are plain Parquet files that DuckDB, PyArrow or any other Parquet reader can open, the `_id` should be a column type those readers understand and can sort in time order.

**Room to grow:** A busy writer should never hit a ceiling on how many ids it can mint per millisecond, and the id’s timestamp should not run out while the data is still in use, as some schemes’ timestamps do within a few decades.

## The common choices

There are several common ways to generate ids. [Auto-increment](https://www.postgresql.org/docs/current/sql-createsequence.html) is a counter, as in a database sequence. The ids are small and ordered, but every writer has to go through the one counter, so writers on different machines need a coordinator.

[UUIDv4](https://www.rfc-editor.org/rfc/rfc9562#section-5.4) is 122 random bits, so no coordination is needed, but the ids are in no order and do not compress. [UUIDv7](https://www.rfc-editor.org/rfc/rfc9562#section-5.7) and [ULID](https://github.com/ulid/spec) both start with a 48-bit millisecond timestamp followed by random bits, so they are ordered by time, though within a millisecond they stay ordered only if the generator keeps a counter in the random bits [\[1\]](#fn-1).

Finally, Twitter’s [Snowflake](https://github.com/twitter-archive/snowflake) packs a 41-bit millisecond timestamp, a 10-bit machine id and a 12-bit sequence number into 64 bits. These ids are small and ordered by time, but someone has to assign every machine a unique machine id, and a machine can mint at most 4,096 ids per millisecond.

The table below compares these against the properties we need, along with Infino’s id, which we describe in the next section.

|  | Auto-increment | UUIDv4 | UUIDv7 | ULID | Snowflake | Infino | 
|---|---|---|---|---|---|---|
| Writers mint ids independently | no | yes | yes | yes | no, machine ids are assigned | yes | 
| Ordered by time | by insertion | no | yes | yes | yes | yes | 
| Strictly ordered within a writer | yes | no | depends on the implementation | with a monotonic generator | yes | yes | 
| Size | 64 bits | 128 bits | 128 bits | 128 bits | 64 bits | 128 bits | 
| Compresses well when stored | yes | no | partly, the random tail does not | partly, or fully with a monotonic generator | yes | yes | 
| Ids per writer per millisecond | no limit | no limit | no hard limit | no hard limit | 4,096 | about 16.7 million | 
| Runs out | not in practice | never | in the year 10889 | in the year 10889 | about 69 years after its custom epoch | millions of years | 
| Parquet column type | 64-bit integer | 16-byte binary (UUID) | 16-byte binary (UUID) | 16-byte binary or a 26-character string | 64-bit integer | `Decimal128(38, 0)` | 

None of the common schemes has all the properties. Auto-increment and Snowflake need coordination, and UUIDv4 has no order. UUIDv7 and ULID come close, but their random bits cost storage unless the generator happens to be monotonic, and within a millisecond they are ordered only if the generator keeps a counter. We designed our own Snowflake-style id to address these shortcomings.

## Infino’s id

Infino’s id is a 128-bit Snowflake-style id [\[2\]](#fn-2), made up of a 64-bit millisecond timestamp, a 40-bit writer id and a 24-bit sequence number, in that order.

It differs from a Snowflake id in three ways. First, the writer id is random rather than assigned. Each writer draws 40 random bits when it starts, and with 40 bits, the chance that any two writers of a table draw the same bits stays below 1% for up to about 148,000 concurrent writers. Thus, no service is needed to hand out writer ids. Snowflake can’t do the same with its 10-bit machine id, since with just 32 writers, two of them would draw the same id 38% of the time.

Second, the sequence number has 24 bits instead of 12, so a writer can mint about 16.7 million ids per millisecond before it has to wait for the clock to tick, which is far more than a writer appends in a millisecond.

Third, the timestamp has 64 bits instead of 41. It needs no custom epoch, and the id stays positive as a signed 128-bit integer for millions of years. This lets us store the id as a plain `Decimal128(38, 0)` Parquet column, which any Parquet reader can read as a number, and sorting the ids sorts them by the millisecond they were minted in.

The generator itself keeps very little state, i.e. just the last id it handed out. It reads the current time from a shared millisecond clock that a background thread updates [\[3\]](#fn-3), so reading the time is a load from memory rather than a system call, and the clock never goes backwards. If the clock has ticked since the last id, the next id starts the new millisecond at sequence 0; otherwise, it is the last id plus one. Note that a writer never writes to memory that another writer reads, so writers don’t slow each other down, even within one process.

## Minting ids in batches

When an append writes a batch, it asks the generator for as many ids as the batch has rows. The generator reads the clock once and hands out a whole run of sequence numbers, i.e. a first id and a count [\[4\]](#fn-4), and the append then fills in the ids as the first id, plus one, plus two, and so on. A run can hold up to 16.7 million ids, so a batch almost always needs a single clock read, however many rows it has.

As a result, minting an id in an append costs under a nanosecond. We measured this with idbench, a small benchmark that mints ids through Infino’s own generator [\[5\]](#fn-5). On an 8-vCPU machine, one writer minting in batches of 1,024 produces about 1.4 billion ids per second, and eight writers together produce about 4.5 billion. Even one id at a time, the generator takes about 1 ns per id.

Several threads can append to the same table through one table handle, in which case they share the handle’s generator behind a lock. An append holds the lock only while it reserves its run of ids, and fills in the ids after letting go, so the other appends wait for one clock read and not for the length of the batch. With eight threads sharing one generator, taking the lock once per batch of 1,024 mints about 3.75 billion ids per second, while taking it for every id mints only about 4.7 million [\[5\]](#fn-5).

Reserving ids up front also makes updates safe to replay. An update writes its reserved runs to the write-ahead log before doing any work that depends on them. If the process crashes partway, the process that recovers reads the same runs back from the log, rather than minting new ids with its own, different writer id.

## Storing and resolving ids

Inside a superfile, the full-text and vector indexes don’t store the `_id` of a document. They refer to it by its position in the file instead, say 0, 1, 2 and so on (we do this as these numbers compress much more efficiently in the inverted index, a topic for another post someday). So at the end of every search, we need to turn the positions of the top hits into `_id` s, and we store every id twice in a superfile to make this fast: once in the Parquet `_id` column, which any Parquet reader can see, and once in a small id sidecar, which the engine uses to resolve hits [\[6\]](#fn-6).

The Parquet column compresses well, since the ids a writer mints in a run have the same timestamp and writer bits, and differ only in the last few bits. However, to read an id from Parquet, we need to find the page that holds the row, decompress it and decode it, which is a lot of work just to get 10 ids at the end of a search. In our tests, resolving a top-10 from the Parquet column took about 214 µs, even with the file’s footer and page index already decoded [\[5\]](#fn-5).

The sidecar splits the ids into blocks of 1,024, and stores each block as a base (the smallest id in the block) along with the offset of every id from that base. The offsets are bit-packed at the width the largest offset needs, and each 64-bit half of the id is packed separately, so a block of ids minted close together takes about a byte per id. To resolve a hit, the engine finds the block of the hit by division, reads the base and widths of the block, and extracts two bit-packed values, with no decompression needed. In our tests, the sidecar took 1.29 bytes per id, close to the 1.08 bytes of the Parquet column, and resolving a top-10 from it took about half a microsecond, which is roughly 400 times faster than from Parquet [\[5\]](#fn-5).

## Finding a row by id

For a delete or an update, the engine first collects the `_id` s of the rows its predicate matches, and then has to find the row that holds each of them. As mentioned earlier, since Infino tracks the min and max id of each superfile, the engine skips every superfile whose range can’t hold the id, and scans the `_id` column of the rest.

With one writer, superfiles cover separate stretches of time, so a lookup lands in a single superfile. With several writers ingesting at the same time, say four, the superfiles they write cover the same stretch of time, so about four superfiles can hold any given id, and a lookup scans those four instead of one. In our tests with a table of 100 superfiles, a lookup scanned exactly one superfile with one writer, and four with four writers [\[5\]](#fn-5). Note that every time-ordered scheme in the table above gets this property, and Infino’s id is no better at it than UUIDv7, ULID or Snowflake. A UUIDv4, on the other hand, can’t be found without scanning every superfile, and the cost of that grows with the table.

## Trade-offs

Our design has a few trade-offs. Since the id encodes the creation time of a row, anyone who sees an `_id` can tell when the row was written, to the millisecond. For most tables this is harmless, but an id shouldn’t be treated as a secret, and the same is true of UUIDv7, ULID and Snowflake. Also, ids are strictly ordered only within a writer. The clocks of two machines can differ by a few milliseconds, so ids minted at the same moment on two machines can come out in either order.

An id also names a version of a row rather than the row itself. An `UPDATE` writes the new rows with new `_id` s and deletes the old ones, so an id stays valid only until the row is changed.

Lastly, two writers can draw the same writer id. With 1,000 writers on a table, the chance of that is about 1 in 2.2 million, and it stays below 1% up to about 148,000 writers [\[7\]](#fn-7). Even then, the two writers would also have to mint the same sequence number in the same millisecond to produce the same id.

## Summary

A search engine touches the id of a document on every write, search, update, and delete, so the id scheme matters more than it first seems. None of the common schemes gave us everything we needed, so we designed our own 128-bit Snowflake-style id, with a random writer id and a wide sequence number. In this post, we described how Infino mints these ids at billions per second without any coordination between writers, stores each copy in a little over a byte, and uses them to resolve search hits and find rows for updates and deletes.

If you have reached this far, please consider giving [our open source repo (infino-ai/infino)](https://github.com/infino-ai/infino) a star on GitHub.

## Footnotes

1. RFC 9562 lets a UUIDv7 generator use some of the random bits as a counter, so that ids within a millisecond stay ordered. Whether a library does this, and per process or per generator, varies. [↩](#ref-1)
2. [src/supertable/utils/idgen.rs](https://github.com/infino-ai/infino/blob/c5a80fa9800d5d0004ae0d0ff1493923e3707d66/src/supertable/utils/idgen.rs)[↩](#ref-2)
3. The millisecond clock is [ferroid](https://crates.io/crates/ferroid) ’s`MonotonicClock` . The generator on top of it is Infino’s own, since it hands out a whole run of sequence numbers per clock read.[↩](#ref-3)
4. Minting a batch per clock read landed in [infino-ai/infino#1046](https://github.com/infino-ai/infino/pull/1046) .[↩](#ref-4)
5. idbench, in [infino-ai/retrievalbench](https://github.com/infino-ai/retrievalbench/tree/main/idbench) . Measured on 5 Nov 2026 on a Google Cloud`c3-highcpu-8` VM (Intel Xeon Platinum 8481C, 8 vCPUs, 16 GB), with Infino at commit[c5a80fa9](https://github.com/infino-ai/infino/commit/c5a80fa9800d5d0004ae0d0ff1493923e3707d66) , release build, each minting rep run for 1 second and the median of 5 reps taken. The[results file](https://github.com/infino-ai/retrievalbench/blob/main/idbench/results/2026-11-05-gcp-c3-highcpu-8.md) records the machine, the toolchain and both commits. To reproduce: clone the repo, then`cd idbench && cargo run --release` , or`cargo run --release -- mint` for the minting tables alone. Back to the text:[a](#ref-5a)[b](#ref-5b)[c](#ref-5c)[d](#ref-5d)[e](#ref-5e)
6. [src/superfile/ids.rs](https://github.com/infino-ai/infino/blob/c5a80fa9800d5d0004ae0d0ff1493923e3707d66/src/superfile/ids.rs)[↩](#ref-6)
7. This is the birthday problem. With n writers each drawing a random 40-bit writer id, the chance that any two of them draw the same one is about n(n − 1)/2 ÷ 2⁴⁰. For 1,000 writers, that is 499,500 ÷ 1.1 × 10¹², or about 4.5 × 10⁻⁷, i.e. 1 in 2.2 million. It reaches 1% at about 148,000 writers. [↩](#ref-7)