Repository files navigation

This PostgreSQL extension implements two UUID generators with sequentialpatterns, which helps to reduce random I/O patterns associated withregular entirely-random UUID.

Regular random UUIDs are distributed uniformly over the whole range ofpossible values. This results in poor locality when inserting data intoindexes - all index leaf pages are equally likely to be hit, forcingthe whole index into memory. With small indexes that's fine, but oncethe index size exceeds shared buffers (or RAM), the cache hit ratioquickly deteriorates.

Compare this to sequences and timestamps, which have a more sequentialpattern and the new data almost always end up in the right-most part ofthe index (new sequence value is larger than all preceding values, samefor timestamp). This results in a nicer and cache-friendlier behavior,but the values are predictable and may easily collide cross machines.

The main goal of the two generators implemented by this extension, isgenerating UUIDS in a more sequential pattern, but without reducing therandomness too much (which could increase the probability of collisionand predictability of the generated UUIDs). This idea is not new, andit's pretty much what the UUID wikipedia article [1] calls COMB(combined-time GUID) and is more more thoroughly explained in [2].

The benefits (performance, reduced amount of WAL, ...) are demonstratedin a blog post on 2ndQuadrant site [3].

The extension provides two functions generating sequential UUIDs usingeither a sequence or timestamp.

• uuid_sequence_nextval(sequence regclass, block_size int default 65536, block_count int default 65536)

• uuid_time_nextval(interval_length int default 60, interval_count int default 65536) RETURNS uuid

The default values for parameters are selected to work well for a rangeof workloads. See the next section explaining the design for additionalinformation about the meaning of those parameters.

The easiest way to make UUIDs more sequential is to use some sequentialvalue as a prefix. For example, we might take a sequence or a timestampand add random data until we have 16B in total. The resulting valueswould be almost perfectly sequential, but there are two issues with it:

• reduction of randomness - E.g. with a sequence producing bigint valuesthis would reduce the randomness from 16B to 8B. Timestamps do reducethe randomness in a similar way, depending on the accuracy. Thisincreases both the collision probability and predictability (e.g. itallows determining which UUIDs were generated close to each other, andperhaps the exact timestamp).

• bloat - If the values only grow, this may result in bloat in indexesafter deleting historical data. This is a well-known issue e.g. withindexes on timestamps in log tables.

To address both of these issues, the implemented generators are designedto wrap-around regularly, either after generating a certain number ofUUIDs or some amount of time. In both cases, the UUIDs are generates inblocks and have the form of

(block ID; random data)

The size of the block ID depends on the number of blocks and is fixed(depends on generator parameters). For example with the default 64kblocks we need 2 bytes to store it. The block ID increments regularly,and eventually wraps around.

For sequence-based generators the block size is determined by the numberof UUIDs generated. For example we may use blocks of 256 values, inwhich case the two-byte block ID may be computed like this:

(nextval('s') / 256) % 65536

So the generator wraps-around every ~16M UUIDs (because 256 * 65536).

For timestamp-based generators, the block size is defined as intervallength, with the default value 60 seconds. As the default number ofblocks is 64k (same as for sequence-based generators), the block may becomputed like this

(timestamp / 60) % 65536

Which means the generator wraps around every ~45 days.

Currently, this extension works only on releases since PostgreSQL 10. Itcan be made working on older releases with some minor code tweaks ifsomeone wants to spend a bit of time on that.

[1]https://en.wikipedia.org/wiki/Universally_unique_identifier

[2]http://www.informit.com/articles/article.aspx?p=25862

[3]https://www.2ndquadrant.com/en/blog/sequential-uuid-generators/