Hi hackers, I want to discuss a new feature for assigning a snowflake ID[1], which can be cluster-wide unique numbers. Also, Snowflake ID can be allocated standalone.
# Use case
A typical use case is a multi-master system constructed by logical replication.
This feature allows multi-node system to use GENERATED values. IIUC, this is
desired in another thread [2].
When the postgres is standalone, it is quite often that a sequence is used as
default value of the primary key. However, this cannot be done on the
multi-master
system as it is because the value on nodeA might be already used on nodeB.
Logical decoding of sequence partially solves the issue, but not sufficient -
what about the case of asynchronous replication? Managing chucks of values is
worse.
# What is the formats of Snowflake ID?
Snowflake ID has a below form:
[1bit - unused] + [41bit millisecond timestamp] + [10bit machine ID] + [12bit
local sequence number]
Trivially, the millisecond timestamp represents the time when the number is
allocated.
I.e., the time nextval() is called. Using a UNIX time seems an easiest way.
Machine ID can be an arbitrary number, but recommended to be unique in the
system.
Duplicated machine ID might trigger a conflict.
## Characteristics of snowflake ID
Snowflake ID can generate a unique numbers standalone. According to the old
discussion,
allocating value spaces to each nodes was considered [3], but it must
communicating
with other nodes, this brings extra difficulties. (e.g., Which protocol would
be used?)
Also, Snowflake IDs are roughly time ordered. As Andres pointed out in the old
discussions [4], large indexes over random values perform worse.
Snowflake can avoid the situation.
Moreover, Snowflake IDs are 64-bit integer, shorter than UUID (128-bit).
# Implementation
There are several approaches for implementing a snowflake ID. For example,
* Implement as contrib module. Features needed for each components of
snowflakeID
have already been implemented in core, so basically it can be.
* Implement as a variant of sequence access method. I found that sequence AM was
proposed many years ago [5], but it has not been active now. It might be a
fundamental way but needs a huge works.
Attached patch adds a minimal contrib module which can be used for testing my
proposal.
Below shows an usage.
```
-- Create an extension
postgres=# CREATE EXTENSION snowflake_sequence ;
CREATE EXTENSION
-- Create a sequence which generates snowflake IDs
postgres=# SELECT snowflake_sequence.create_sequence('test_sequence');
create_sequence
-----------------
(1 row)
-- Get next snowflake ID
postgres=# SELECT snowflake_sequence.nextval('test_sequence');
nextval
---------------------
3162329056562487297
(1 row)
```
How do you think?
[1]:
https://github.com/twitter-archive/snowflake/tree/b3f6a3c6ca8e1b6847baa6ff42bf72201e2c2231
[2]:
https://www.postgresql.org/message-id/1b25328f-5f4d-9b75-b3f2-f9d9931d1b9d%40postgresql.org
[3]:
https://www.postgresql.org/message-id/CA%2BU5nMLSh4fttA4BhAknpCE-iAWgK%2BBG-_wuJS%3DEAcx7hTYn-Q%40mail.gmail.com
[4]:
https://www.postgresql.org/message-id/201210161515.54895.andres%402ndquadrant.com
[5]:
https://www.postgresql.org/message-id/flat/CA%2BU5nMLV3ccdzbqCvcedd-HfrE4dUmoFmTBPL_uJ9YjsQbR7iQ%40mail.gmail.com
Best Regards,
Hayato Kuroda
FUJITSU LIMITED
0001-initial-commit-for-snowflake_sequence.patch
Description: 0001-initial-commit-for-snowflake_sequence.patch
