Unique ids in CrateDB

Introduction

CrateDB in 5.10.2 (and in most versions) uses three different kinds [1] of unique IDs:

• ElasticFlakes
• UUID4
• DirtyUUID.

ElasticFlakes

This implementation is inherited from the Open Source days of Elasticsearch [2] they are a time-based id optimized for Apache Lucene, the underlining library in which both CrateDB and Elasticsearch base their storage.

The elasticflake, is used to generate a column named _id [3] for every row, and for the scalar function gen_random_text_uuid() [4].

Structure

An elasticflake has 120 bits and is divided in 15 octets or bytes.

It's composed of a sequence + timestamp + mac address, divided in six groups:

Structured as follows:

The id is then converted to base64 using an alphabet that is URL safe, resulting in a string that has 20 characters.

        
>>> select gen_random_text_uuid();
b8V2a5sBnHiLIAB_yCXG
      

Sortability

Since they’re time-based ids, one would expect that you could sort and filter on them, but they aren’t.

One can naively check this:

        
create table t
(
    real_pos    INTEGER,
    uuid        TEXT      DEFAULT gen_random_text_uuid(),
    inserted_at TIMESTAMP DEFAULT now()
)
      

Then insert several values:

        
insert into t (real_pos)
values (1) -- up to n
      

Trying to filter by _id, and uuid have different results than ordering by inserted_at:

        
select _id, *
from t
order by _id
limit 10
      

Notice how everything seems sorted but the row with real_pos 10. There will always be some order maintained within small buckets of ids, this is because the first group (sequence_a) is a sequence. However, this sequence resets every time the int overflows or every time you restart the node. The sequence will also be different if another node generates the id. Since they all hold different sequences.

        
select _id, * from t
order by inserted_at
limit 10
      

inserted_at returns the correct results, this is also observable in filtering as expected.

Additionally, Base64 doesn’t preserve lexicographical order for encoded strings, because of the alphabet it uses, by chance some buckets of elements can maintain orderability if the range of the alphabet's character is ordered. To dive deeper into this see How to make a sortable BASE64 encoding

Recap

• The Elasticflake is a time-based 120 bit wide unique id that is encoded into a url-safe base64 resulting in a 20 character string.
• It does not maintain lexicographical order, only in small buckets.

Furthermore:

• base32hex and a custom base64 are lexicographically sortable on uuid7 but base64 is not. [5]
• Elasticflake is still not lexicographically sortable in base32hex. [6]

UUID4

A random UUID4 as per RFC 4122 (2005), in url safe Base64 encoding.

This unique id is not exposed to the user and is used in internal database operations.

DirtyUUID

It is just two random integers cobbled up together, not following the UUID RFC format.

This is also not exposed to the user, it is used in internal database operations and is more efficient to generate than the UUID4.

References