Sequences¶

Many applications require that unique surrogate ids be assigned to database entries.Often the database SEQUENCE object is used to produce these. InPostgreSQL these can be either a manually created sequence using theCREATE SEQUENCE command and retrieved by calling nextval() function,or serial and bigserial columns or alternativelyGENERATED BY DEFAULT AS IDENTITY columns.

However, standard sequences in PostgreSQL are not multi-node aware, and onlyproduce values that are unique on the local node. This is important becauseunique ids generated by such sequences will cause conflict and data loss (bymeans of discarded INSERTs) in multi-master replication.

BDR Global Sequences¶

For this reason, BDR provides an application-transparent way to generate uniqueids using sequences on bigint or bigserial datatypes across the whole BDR group,called global sequences.

BDR global sequences provide an easy way for applications to use thedatabase to generate unique synthetic keys in an asynchronous distributedsystem that works for most - but not necessarily all - cases.

Using BDR global sequences allows you to avoid the problems with insertconflicts. If you define a PRIMARY KEY or UNIQUE constraint on a columnwhich is using a global sequence, it is not possible for any node to ever getthe same value as any other node. When BDR synchronizes inserts between thenodes, they can never conflict.

BDR global sequences extend PostgreSQL sequences, so are crash-safe. To usethem, you must have been granted the bdr_application role.

There are various possible algorithms for global sequences:

```
Timeshard sequences
```
```
Globally-allocated range sequences
```

Timeshard sequences generate values using an algorithm that does not requireinter-node communication at any point, so is faster and more robust, as wellas having the useful property of recording the timestamp at which they werecreated.Timeshard sequences have the restriction that they work only for 64-bit BIGINTdatatypes and produce values 19 digits long, which may be too long foruse in some host language datatypes such as Javascript Integer types.Globally-allocated sequences allocate a local range of values which canbe replenished as-needed by inter-node consensus, making them suitable foreither BIGINT or INTEGER sequences.

A global sequence can be created using the bdr.alter_sequence_set_kind()function. This function takes a standard PostgreSQL sequence and marks it asa BDR global sequence. It can also convert the sequence back to the standardPostgreSQL sequence (see below).

BDR also provides the configuration variable bdr.default_sequence_kind, whichdetermines what kind of sequence will be created when the CREATE SEQUENCEcommand is executed or when a serial, bigserial orGENERATED BY DEFAULT AS IDENTITY column is created. Valid settings are:

```
`local` (the default) meaning that newly created
```
- sequences are the standard PostgreSQL (local) sequences.

`galloc` which always creates globally-allocated range sequences.

`timeshard` which creates time-sharded global sequences for BIGINT sequences,

but will throw ERRORs when used with INTEGER sequences.

The bdr.sequences view shows information about individual sequence kinds.

currval() and lastval() work correctly for all types of global sequence.

Timeshard Sequences¶

The ids generated by timeshard sequences are loosely time-ordered so they canbe used to get the approximate order of data insertion, like standard PostgreSQLsequences. Values generated within the same millisecond might be out of order,even on one node. The property of loose time-ordering means they are suitablefor use as range partition keys.

Timeshard sequences work on one or more nodes, and do not require any inter-nodecommunication after the node join process completes. So they may continue tobe used even if there’s the risk of extended network partitions, and are notaffected by replication lag or inter-node latency.

Timeshard sequences generate unique ids in a differentway to standard sequences. The algorithm uses 3 components for asequence number. The first component of the sequence is a timestampat the time of sequence number generation. The second component ofthe sequence number is the unique id assigned to each BDR node,which ensures that the ids from different nodes will always bedifferent. Finally, the third component is the number generated bythe local sequence itself.

While adding a unique node id to the sequence number would be enoughto ensure there are no conflicts, we also want to keep another usefulproperty of sequences, which is that the ordering of the sequencenumbers roughly corresponds to the order in which data was insertedinto the table. Putting the timestamp first ensures this.

A few limitations and caveats apply to timeshard sequences.

Timeshard sequences are 64-bits wide and need a bigint or bigserial.Values generated will be at least 19 digits long.There is no practical 32-bit integer version, so cannot be used with serialsequences - use globally-allocated range sequences instead.

There is a limit of 8192 sequence values generated per millisecond on anygiven node for any given sequence. If more than 8192 sequences permillisecond are generated from one sequence on one node, the generatedvalues will wrap around and could collide. There is no check on that forperformance reasons; the value is not reset to 0 at the start of each ms.Collision will usually result in aUNIQUE constraint violation on INSERT or UPDATE. It cannot cause areplication conflict, because sequence values generated on different nodescannot ever collide since they contain the nodeid.

In practice this is harmless; values are not generated fast enoughto trigger this limitation as there will be otherwork being done, rows inserted, indexes updated, etc. Despite that,applications should have a UNIQUE constraint in place where theyabsolutely rely on a lack of collisions.

Perhaps more importantly, the timestamp component will run out of values inthe year 2050, and if used in combination with bigint, the values will wrap tonegative numbers in the year 2033. This means that sequences generated after 2033will have negative values. If you plan to deploy your application beyond thisdate, try one of UUIDs, KSUUIDs and Other Approaches mentioned below, oruse globally-allocated range sequences instead.

The INCREMENT option on a sequence used as input for timeshard sequences iseffectively ignored. This could be relevant for applications that do sequenceID caching, like many object-relational mapper (ORM) tools, notably Hibernate.Because the sequence is time-based, this has little practical effect since thesequence will have advanced to a new non-colliding value by the time theapplication can do anything with the cached values.

Similarly, the START, MINVALUE, MAXVALUE and CACHE settings maybe changed on the underlying sequence, but there is no benefit to doingso. The sequence’s low 14 bits are used and the rest is discarded, sothe value range limits do not affect the function’s result. For the samereason, setval() is not useful for timeshard sequences.

Globally-allocated range Sequences¶

The globally-allocated range (or galloc) sequences allocate ranges (chunks)of values to each node. When the local range is used up, a new range isallocated globally by consensus amongst the other nodes. This uses the keyspace efficiently, but requires that the local node be connected to a majorityof the nodes in the cluster for the sequence generator to progress, when thecurrently assigned local range has been used up.

Unlike timeshard sequences, galloc sequences support all sequence data typesprovided by PostgreSQL - smallint, integer and bigint. This means that gallocsequences can be used in environments where 64-bit sequences are problematic,such as using integers in javascript, since that supports only 53-bitvalues, or when the sequence is displayed on output with limited space.

The range assigned by each voting is currently predetermined based on thedatatype the sequence is using:

```
smallint - 1 000 numbers
```
```
integer - 1 000 000 numbers
```
```
bigint - 1 000 000 000 numbers
```

Each node will allocate two chunks of seq_chunk_size, one for the current useplus a reserved chunk for future usage, so the values generated from any onenode will increase monotonically. However, viewed globally, the valuesgenerated will not be ordered at all. This could cause a loss of performancedue to the effects on b-tree indexes, and will typically mean that generatedvalues will not be useful as range partition keys.

The main downside of the galloc sequences is that once the assigned range isused up, the sequence generator has to ask for consensus about the next rangefor the local node that requires inter-node communication, which couldlead to delays or operational issues if the majority of the BDR group is notaccessible. This may be avoided in later releases.

The CACHE, START, MINVALUE and MAXVALUE options work correctlywith galloc sequences, however you need to set them before transformingthe sequence to galloc kind. The INCREMENT BY option also workscorrectly, however, you cannot assign an increment value which is equalto or more than the above ranges assigned for each sequence datatype.setval() does not reset the global state for galloc sequences andshould not be used.

A few limitations apply to galloc sequences. BDR tracks galloc sequences in aspecial BDR catalog bdr.sequence_alloc. This catalog is required to track thecurrently allocated chunks for the galloc sequences. The sequence name andnamespace is stored in this catalog. Since the sequence chunk allocation ismanaged via Raft whereas any changes to the sequence name/namespace is managedvia replication stream, BDR currently does not support renaming gallocsequences, or moving them to another namespace or renaming the namespace thatcontains a galloc sequence. The user should be mindful of this limitation whiledesigning application schema.

Usage¶

Before transforming a local sequence to galloc, you need to take care of theseprerequisites:

When sequence kind is altered to galloc, it will be rewritten and restart fromthe defined start value of the local sequence. If this happens on an existingsequence in a production database you will need to query the current valuethen set the start value appropriately. To assist with this use case, BDRallows users to pass a starting value with the function bdr.alter_sequence_set_kind().If you are already using offset and you have writes from multiple nodes, youneed to check what is the greatest used value and restart the sequence at leastto the next value.

-- determine highest sequence value across all nodes
SELECT max((x->'response'->0->>'nextval')::bigint)
   *   FROM json_array_elements(
   *       bdr.run_on_all_nodes(
   *           E'SELECT nextval(\'public.sequence\');'
   *           )::jsonb AS x;

-- turn into a galloc sequence
SELECT bdr.alter_sequence_set_kind('public.sequence'::regclass, 'galloc', $MAX+MARGIN);

Since users cannot lock a sequence, you must leave a $MARGIN value to allowoperations to continue while the max() value is queried.

The bdr.sequence_alloc table will give information on the chunk size and whatranges are allocated around the whole cluster.In this example we started our sequence from 333, and we have two nodes in thecluster, we can see that we have a number of allocation 4, that is 2 per nodeand the chunk size is 1000000 that is related to an integer sequence.

SELECT * FROM bdr.sequence_alloc
   *   WHERE seqid = 'public.categories_category_seq'::regclass;
   *         seqid          | seq_chunk_size | seq_allocated_up_to | seq_nallocs |       seq_last_alloc
-------------------------+----------------+---------------------+-------------+-----------------------------
 categories_category_seq |        1000000 |             4000333 |           4 | 2020-05-21 20:02:15.957835+00
(1 row)

To see the ranges currently assigned to a given sequence on each node, usethese queries:

Node `Node1` is using range from `333` to `2000333`.

SELECT last_value AS range_start, log_cnt AS range_end
   *   FROM categories_category_seq WHERE ctid = '(0,2)'; -- first range
 range_start | range_end
-------------+-----------
   *        334 |   1000333
(1 row)

SELECT last_value AS range_start, log_cnt AS range_end
   *   FROM categories_category_seq WHERE ctid = '(0,3)'; -- second range
 range_start | range_end
-------------+-----------
   *    1000334 |   2000333
(1 row)

Node `Node2` is using range from `2000004` to `4000003`.

SELECT last_value AS range_start, log_cnt AS range_end
   *   FROM categories_category_seq WHERE ctid = '(0,2)'; -- first range
 range_start | range_end
-------------+-----------
   *    2000334 |   3000333
(1 row)

SELECT last_value AS range_start, log_cnt AS range_end
   *   FROM categories_category_seq WHERE ctid = '(0,3)'; -- second range
 range_start | range_end
-------------+-----------
   *    3000334 |   4000333

NOTE You can’t combine it to single query (like WHERE ctid IN (‘(0,2)’, ‘(0,3)’))as that will still only show the first range.

When a node finishes a chunk, it will ask a consensus for a new one and get thefirst available; in our case, it will be from 4000334 to 5000333. This will bethe new reserved chunk and it will start to consume the old reserved chunk.

UUIDs, KSUUIDs and Other Approaches¶

There are other ways to generate globally unique ids without using the globalsequences that can be used with BDR. For example:

```
UUIDs, and their BDR variant, KSUUIDs
```

Local sequences with a different offset per node (i.e. manual)

```
An externally co-ordinated natural key
```

Please note that BDR applications cannot use other methods safely:counter-tablebased approaches relying on SELECT ... FOR UPDATE, UPDATE ... RETURNING ...or similar for sequence generation will not work correctly in BDR, because BDRdoes not take row locks between nodes. The same values will be generated onmore than one node. For the same reason, the usual strategies for “gapless”sequence generation do not work with BDR. In most cases the application shouldcoordinate generation of sequences that must be gapless from some externalsource using two-phase commit, or it should only generate them on one node inthe BDR group.

UUIDs and KSUUIDs¶

UUID keys instead avoid sequences entirely anduse 128-bit universal unique identifiers. These are randomor pseudorandom values that are so large that it is nearlyimpossible for the same value to be generated twice. There isno need for nodes to have continuous communication when using UUID keys.

In the incredibly unlikely event of a collision, conflict detection willchoose the newer of the two inserted records to retain. Conflict logging,if enabled, will record such an event, but it isexceptionally unlikely to ever occur, since collisionsonly become practically likely after about 2^64 keys have been generated.

The main downside of UUID keys is that they’re somewhat space- andnetwork inefficient, consuming more space not only as a primary key, butalso where referenced in foreign keys and when transmitted on the wire.Additionally, not all applications cope well with UUID keys.

BDR provides functions for working with a K-Sortable variant of UUID data,known as KSUUID, which generates values that can be stored using PostgreSQL’sstandard UUID data type. A KSUUID value is similar to UUIDv1 in thatit stores both timestamp and random data, following the UUID standard.The difference is that KSUUID is K-Sortable, meaning that it’s weaklysortable by timestamp. This makes it more useful as a database key as it produces more compact btree indexes, which improvesthe effectiveness of search, and allows natural time-sorting of result data. Unlike UUIDv1,KSUUID values do not include the MAC of the computer on which they weregenerated, so there should be no security concerns from using KSUUIDs.

KSUUID v2 is now recommended in all cases. Values generated are directlysortable with regular comparison operators.

There are two versions of KSUUID in BDR, v1 and v2. The legacy KSUUID v1 isnow deprecated but is kept in order to support existing installations and shouldnot be used for new installations.The internal contents of the v1 and v2 are not compatible, and as such thefunctions to manipulate them are also not compatible. The v2 of KSUUID alsono longer stores the UUID version number.

Step & Offset Sequences¶

In offset-step sequences, a normal PostgreSQL sequence is used on each node.Each sequence increments by the same amount and starts at differing offsets.For example with step 1000, node1’s sequence generates 1001, 2001, 3001, andso on, node2’s generates 1002, 2002, 3002, etc. This scheme works welleven if the nodes cannot communicate for extended periods, but the designer must specify a maximum number of nodes when establishing theschema, and it requires per-node configuration. However, mistakes can easily lead tooverlapping sequences.

It is relatively simple to configure this approach with BDR by creating thedesired sequence on one node, like this:

CREATE TABLE some_table (
   *   generated_value bigint primary key
);

CREATE SEQUENCE some_seq INCREMENT 1000 OWNED BY some_table.generated_value;

ALTER TABLE some_table ALTER COLUMN generated_value SET DEFAULT nextval('some_seq');

… then on each node calling setval() to give each node a different offsetstarting value, e.g.:

-- On node 1
SELECT setval('some_seq', 1);

-- On node 2
SELECT setval('some_seq', 2);
   * -- ... etc

You should be sure to allow a large enough INCREMENT to leave room for allthe nodes you may ever want to add, since changing it in future is difficultand disruptive.

If you use bigint values, there is no practical concern about key exhaustion,even if you use offsets of 10000 or more. You’ll need hundreds of years,with hundreds of machines, doing millions of inserts per second, to have anychance of approaching exhaustion.

BDR does not currently offer any automation for configuration of theper-node offsets on such step/offset sequences.

Composite Keys¶

A variant on step/offset sequences is to use a composite key composed ofPRIMARY KEY (node_number, generated_value), where thenode number is usually obtained from a function that returns a differentnumber on each node. Such a function may be created by temporarilydisabling DDL replication and creating a constant SQL function, or by usinga one-row table that is not part of a replication set to store a differentvalue in each node.

Global Sequence Management Interfaces¶

BDR provides an interface for converting between a standard PostgreSQL sequenceand the BDR global sequence.

Note that the following functions are considered to be DDL, so DDL replicationand global locking applies to them.

bdr.alter_sequence_set_kind¶

Allows the owner of a sequence to set the kind of a sequence.Once set, seqkind is only visible via the bdr.sequences view;in all other ways the sequence will appear as a normal sequence.

BDR treats this function as DDL, so DDL replication and global locking applies,if that is currently active. See [DDL Replication].

Synopsis¶

bdr.alter_sequence_set_kind(seqoid regclass, seqkind text)

Parameters¶

`seqoid` - name or Oid of the sequence to be altered

```
`seqkind` - `local` for a standard PostgreSQL sequence, `timeshard` for BDR
```
- global sequence which uses the “time and sharding” based algorithm described in the
- BDR Global Sequences section, or galloc for globally-allocated range
- sequences which use consensus between nodes to assign unique ranges of
- sequence numbers to each node

Notes¶

When changing the sequence kind to galloc, the first allocated range for thatsequence will use the sequence start value as the starting point. When there arealready existing values used by the sequence before it was changed to galloc,it is recommended to move the starting point so that the newly generatedvalues will not conflict with the existing ones using the following command:

ALTER SEQUENCE seq_name START starting_value RESTART

This function uses the same replication mechanism as DDL statements. This meansthat the replication is affected by the ddl filtersconfiguration.

The function will take a global DDL lock. It will also lock the sequence locally.

This function is transactional - the effects can be rolled back with theROLLBACK of the transaction, and the changes are visible to the currenttransaction.

The bdr.alter_sequence_set_kind function can be only executed bythe owner of the sequence, unless bdr.backwards_compatibility isset is set to 30618 or below.

bdr.extract_timestamp_from_timeshard¶

This function extracts the timestamp component of the timeshard sequence.The return value is of type “timestamptz”.

Synopsis¶

bdr.extract_timestamp_from_timeshard(timeshard_seq bigint)

Parameters¶

`timeshard_seq` - value of a timeshard sequence

Notes¶

This function is only executed on the local node.

bdr.extract_nodeid_from_timeshard¶

This function extracts the nodeid component of the timeshard sequence.

Synopsis¶

bdr.extract_nodeid_from_timeshard(timeshard_seq bigint)

Parameters¶

`timeshard_seq` - value of a timeshard sequence

Notes¶

This function is only executed on the local node.

bdr.extract_localseqid_from_timeshard¶

This function extracts the local sequence value component of the timeshard sequence.

Synopsis¶

bdr.extract_localseqid_from_timeshard(timeshard_seq bigint)

Parameters¶

`timeshard_seq` - value of a timeshard sequence

Notes¶

This function is only executed on the local node.

bdr.timestamp_to_timeshard¶

This function converts a timestamp value to a dummy timeshard sequence value.

This is useful for doing indexed searches or comparisons of values in thetimeshard column and for a specific timestamp.

For example, given a table foo with a column id which is using a timeshardsequence, we can get the number of changes since yesterday midnight like this:

SELECT count(1) FROM foo WHERE id > bdr.timestamp_to_timeshard('yesterday')

A query formulated this way will use an index scan on the column id.

Synopsis¶

bdr.timestamp_to_timeshard(ts timestamptz)

Parameters¶

`ts` - timestamp to be used for the timeshard sequence generation

Notes¶

This function is only executed on local node.

KSUUID v2 Functions¶

Functions for working with KSUUID v2 data, K-Sortable UUID data.

bdr.gen_ksuuid_v2¶

This function generates a new KSUUID v2 value, using the value of timestamp passed as anargument or current system time if NULL is passed.If you want to generate KSUUID automatically using system time, pass NULL argument.

The return value is of type “UUID”.

Synopsis¶

bdr.gen_ksuuid_v2(timestamptz)

Notes¶

This function is only executed on the local node.

bdr.ksuuid_v2_cmp¶

This function compares the KSUUID v2 values.

It returns 1 if first value is newer, -1 if second value is lower, or zero if theyare equal.

Synopsis¶

bdr.ksuuid_v2_cmp(uuid, uuid)

Parameters¶

```
`UUID` - `KSUUID` v2 to compare
```

Notes¶

This function is only executed on local node.

bdr.extract_timestamp_from_ksuuid_v2¶

This function extracts the timestamp component of KSUUID v2.The return value is of type “timestamptz”.

Synopsis¶

bdr.extract_timestamp_from_ksuuid_v2(uuid)

Parameters¶

`UUID` - `KSUUID` v2 value to extract timestamp from

Notes¶

This function is only executed on the local node.

KSUUID v1 Functions¶

Functions for working with KSUUID v1 data, K-Sortable UUID data(v1).

bdr.gen_ksuuid¶

This function generates a new KSUUID v1 value, using the current system time.The return value is of type “UUID”.

Synopsis¶

bdr.gen_ksuuid()

Notes¶

This function is only executed on the local node.

bdr.uuid_v1_cmp¶

This function compares the KSUUID v1 values.

It returns 1 if first value is newer, -1 if second value is lower, or zero if theyare equal.

Synopsis¶

bdr.uuid_v1_cmp(uuid, uuid)

Notes¶

This function is only executed on the local node.

Parameters¶

```
`UUID` - `KSUUID` v1 to compare
```

bdr.extract_timestamp_from_ksuuid¶

This function extracts the timestamp component of KSUUID v1 or UUIDv1 values.The return value is of type “timestamptz”.

Synopsis¶

bdr.extract_timestamp_from_ksuuid(uuid)

Parameters¶

`UUID` - `KSUUID` v1 value to extract timestamp from

Notes¶

This function is only executed on the local node.