UUID or cached sequences?
Tags: database, postgres, sql, yugabytedb
Published: 2021-08-30 07:41:47



One reason why people choose a UUID for the surrogate key is scalability. Because it generates unique values without having to synchronize with a central generator like a sequence. There are other reasons to use UUID but this post is about scalability. In most databases, sequence generators can be scalable with a cache: which means the central catalog object that manages the sequence doesn't have to be read each time a next value is needed. Even when the database does not provide a sequence cache, it is very easy to mimic one  from the application" when you read from the sequence, multiply it by 50 and use it as the starting number to add to a local counter from 1 to 50. This makes the database read the next value from the central point of truth only once every 50 next values. This is what a JPA @SequenceGenerator is doing and 50 is the Hibernate default.
 
If your insert rate still manages to bottleneck on the sequence number generation, you can increase the cache. Reading from the central sequence every 32767 inserts is probably a negligible overhead. Why am I putting 32767 ? Because this takes 2 bytes, out of the 8 bytes of the PostgreSQL bigint. So, even if the cached values are not used (which should happen only when connections in the pool are recycled) it remains 1e14 numbers from the bigint - enough to ingest a million rows every second for 30 years. You see where I'm going: even with a huge cache, an 8 bytes sequence is sufficient for scalability, compared to the 16 bytes UUID required to ensure unicity without a sequence.

## PostgreSQL

In PostgreSQL the sequence cache is per session. If you constantly connect and disconnect, you will waste the cache range each time. But even outside of sequences, this is not how the database should be used. A connection is a process creation on the backend and if you do that for each transaction, you have a bigger problem than the wasted sequence cache. The application server should use a connection pool, and then the database session is re-used. I've created the following python example that reads the nextval() in each session grabbed from the pool. This is done with  5 concurrent threads and a connection pool that can grow to 5 connections.

```python
import sqlalchemy
from   sqlalchemy import Sequence
import threading

yb=sqlalchemy.create_engine('postgresql+psycopg2://franck:yugabyte@yba.pachot.net:5433/yb_demo_northwind',pool_size=1,max_overflow=4)

def mythread():
 print(threading.current_thread().name)
 for i in range(100):
  nextid = yb.connect().execute(Sequence('myseq'))
  print(f'{nextid:6d} from {threading.current_thread().name:8s} {yb.pool.status()}');

yb.connect().execute('drop sequence if exists myseq; create sequence myseq cache 32767')

mythreads=[]
for i in range(5):
 t=threading.Thread(target=mythread)
 mythreads.append(t)
 t.start()

for i in mythreads:
 t.join()

exit();
```

Here is the beginning of the output:

```
     1 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     2 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     3 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     4 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     5 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     6 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 32768 from Thread-4 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     7 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 65535 from Thread-5 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 98302 from Thread-2 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
131069 from Thread-3 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 32769 from Thread-4 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     8 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 65536 from Thread-5 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
131070 from Thread-3 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 98303 from Thread-2 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 32770 from Thread-4 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
     9 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 65537 from Thread-5 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
131071 from Thread-3 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 98304 from Thread-2 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
 32771 from Thread-4 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
    10 from Thread-1 Pool size: 1  Connections in pool: 1 Current Overflow: 4 Current Checked out connections: 4
...
```

Even if I am using a different session each time, they are grabbed from the connection pool and the sequence cache is still there from the previous one. Thread 1 has started first and grabs the first connection from the pool, and uses numbers from the sequence within the cached range of 1-32767. It may not use them all if the connection is recycled but for sure the waste of numbers is not as large as the cache value. You can see that the other threads grab additional connections, starting at 32768, 65535... and then using the values in this range. So, with this solution, you waste only occasionally a small part of the 2 bytes range. Nothing to worry when compared to the UUID which has to waste a lot more (UUID is 16 bytes) to ensure a very low probability of collision.
(Here is a [kaggle](https://www.kaggle.com/franckpachot/https-dev-to-yugabyte-uuid-or-cached-sequences-c/log) with this example if you want to play with)

## YugabyteDB

I said PostgreSQL but I was connected to a YugabyteDB database which is fully compatible with postgres. The same query layer is used but the storage layer is different. In Yugabyte, all sequences are stored in a distributed table ("system_postgres"."sequences_data") which is replicated according to the replication factor, and is still available in the event of a node crash or network failure. Because the leader tablet for the sequence may be on another node, the latency to read it is higher. And because it is replicated to other nodes, the latency to write to the quorum is also higher than monolith PostgreSQL. Because of the described implications to latency with a distributed database, it's strongly recommended to configure a cache which is large enough to not have to visit the database and suffer the latency penalty of obtaining a new value too much. To be sure that performance is fine even when not defining the cache explicitly, the default in YugabyteDB is increased to 100 instead of 1 in PostgreSQL, and can be set higher with the `ysql_sequence_cache_minval` flag. If the insert rate is high enough that the cache is exhausted very quickly, it is highly recommended to go higher. Don't worry about the gap, using a UUID every number has a gap, because a UUID is a random number.. 

Despites their name, sequence generators are efficient to provide unique numbers, not no-gap series of numbers. There's a lot to say about primary key, surrogate keys... I will discuss about this at [Joker 2021](https://jokerconf.com/en/) in October: [SQL primary key, surrogate key, composite keys, foreign keys... and JPA](https://jokerconf.com/en/2021/talks/4sezsd94jevt4zjyiuje3w/)

Of course, with YugabyteDB using PostgreSQL as a query layer, you can generate a UUID with gen_random_uuid() because pgcrypto is there by default, ready to `create extension`. You can also install uuid-ossp.

But let's see another advantage of the cached sequence in a distributed database: they can be used with hash or range sharding. You may want to distribute all rows even when generated from the same session. And this will be the case if you define the primary key with HASH sharding, the default. 
Like this:

```sql
create table t1 (
 id bigint generated always as identity
 ( start with 1 cache 32767 ),
 value text,
 constraint t1_id primary key ( id HASH ));
```

Or you may prefer to keep clustered the rows that are inserted together:

```sql
create table t1 (
 id bigint generated always as identity
 ( start with 1 cache 32767 ),
 value text,
 constraint t1_id primary key ( id ASC ));
```

You can even define the ranges. The cache range will put rows in a different place, in the same tablet if they are all in the same range. That's a choice, you can also rely on [Automatic Tablet Splitting](https://docs.yugabyte.com/latest/architecture/docdb-sharding/tablet-splitting/#automatic-tablet-splitting).

## In short

You have multiple options. There are reasons to use a UUID which have nothing to do with size or performance. For example, seeing UUID in logs rarely raises security audit concerns but having numbers generated in sequence may allow some guesses about your business information. This can be mitigated by starting at a high number, and it is highly randomized by the cache, but anyway, security policy may not allow it.

However, when the concern is scalability you clearly need to define your goal. At first glance, it seems that a cache has to maintain a state which must be shared by all sessions, and then is not scalable. But with a large cache, querying and updating the sequence becomes an infrequent operation. With appropriate configuration, you can get all the advantages of a sequence. The ascending nature of the number helps clustering rows together to accelerate bulk loads if that is preferred, or, can be spread by hash sharding if that's preferable to distribute the load to many nodes. 
The size also matters. 16 bytes in the primary and foreign keys is large compared to 8 bytes for bigint. And operations such as comparing or increasing an integer, is a very simple CPU operation when compared to generating a UUID with enough randomness. 

The following test illustrates the performance difference between UUIDs and sequences. This can be run onPostgreSQL or YugabyteDB:

```sql
create extension pgcrypto;
\timing on
create sequence myseq cache 32767;
select count(nextval('myseq') ) from generate_series(1,10000000);
select count(gen_random_uuid()) from generate_series(1,10000000);
```

With this large cache, the sequence generates 3 million unique numbers per second, but less than one million per second for the UUID:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rrp9qr8a4lp6iy7g1ld9.jpg)

There's a good chance that you think sequences are not scalable if  you never thought about the sequence cache size. The problem is not the SQL sequence, but keeping the defaults that are often too small.