The rise of distributed data stores and the general decomposition of systems into smaller pieces means that coordination between each server, service, or function is less available. In my first applications, unique ID generation meant setting auto_increment=True on a column in the SQL database. Easy, done, no problem. Today, each microservice has its own data source(s) and NoSQL stores are common. Every NoSQL DB is "NoSQL" in its own way, but they usually eschew coordinated and single-writer solutions in the name of reliability/performance/both. You can't have an auto-increment column without implementing the coordination client-side.

Using numbers as identifiers also creates problems. Auto-incrementing can lead to enumeration-based attacks. Fields can have fixed sizes. These issues can go unrealized until you overflow the uint32 field, and now your logs are a pile of ID conflict errors. Instead of integers, we can use a different kind of fixed-length field and make it non-sequential so that different hosts can generate IDs without a central coordinating point.

UUID's are an improvement and avoid collisions in distributed settings, but being strictly random you don't have a way to easily sort them or determine rough order. Segment blogged a while ago about one replacement for UUIDs with the KSUID (K-Sortable Universal ID) but it has limitations and uses a strange 14e8 offset to avoid running out of epoch time in the next 100 years.

Enter the Unique Lexicographically Sortable Identifier (ULID). These are sortable, high-entropy identifiers that we can generate anywhere in our pipeline without coordination and have confidence that there won't be collisions. A ULID looks like 01E5TZRCM5WZYPB2BH7KMYR5HT, and the first 10 characters are a timestamp, and the next 16 characters are random.

What About UUID?

I came across the need for ULID / KSUID when working with S3 objects that needed to be named, but I also wanted to be able to query for recent objects. Typically, when I need a random identifier, I reach for UUID-v4. Why v4?

• UUID v1 and v2 contain MAC addresses based on the host that generates them. This isn't really a security issue since an L2 address won't help you much on the public internet. However, it does mean if my UUIDs are generated in Lambdas, the MAC addresses have no semantic value. I can't SSH into my Lambda and look up the MAC or otherwise use that information.
• UUID v3 requires a seed, and I would just be using random.randint() or the equivalent to pick my seed value. Any system that requires a seed means that I have to think about what to use as a seed, how that impacts the randomness, and how that might impact security or collisions.
• UUID v4 is random, but because it is entirely random, it provides no semantic overloading.

Why would I want to semantically overload the UUID in my system? I took a cue from the Wizard of Semantic Overloading himself, Rick Houlihan. I've spent time on single-table DynamoDB designs and that way of thinking spilled over into the design of my S3 storage system.

ULIDs to Enable S3 Time Queries

Index-based thinking can be illuminating, especially since IT is full of intrinsically sorted storage systems. S3 sorts your object keys and prefixes when returning them, no matter what order they were added in.

Keys are selected for listing by bucket and prefix. For example, consider a bucket named "dictionary" that contains a key for every English word. You might make a call to list all the keys in that bucket that start with the letter "q". List results are always returned in UTF-8 binary order.

— AWS S3 documentation

What does this mean for our application? It means if we provide sortable keys to S3 and sort them in the order we actually want to receive items in, then we will be able to get our objects in order without having to do any sort client-side. Using a ULID in an object name (or better, splitting a ULID with a prefix) lets us avoid collisions and also prevent enumeration-related attacks on our objects.

Using ULIDs in Python is simple. First, you need to install the ulid-py library, then you can import ulid and start generating identifiers:

This would upload an object with just a ULID as the name, with the contents abc. Then when we list objects in the CLI or in any other app, they're sorted by the time they were created even if there were several new objects in a single millisecond.

$ aws --profile personal s3 ls s3://t10-blog-ulids
2020-04-13 21:17:53          3 01E5V474WE4DE0N63ZWT7P6YWH
2020-04-13 21:17:54          3 01E5V475QFRCEHXKJAS3BRS6BV
2020-04-13 21:24:51          3 01E5V4KXFTP52C9M5DVPQ2XR8T
2020-04-13 21:48:33          3 01E5V5Z9J0GX72VFSENBCKMHF0

Automatic sorting is helpful, and of course, ULIDs can be formatted in different ways depending on your needs.

>>> import ulid
>>> u = ulid.new()
>>> u.str
'01E5V7GWA9CHP337PB8SR18ZP4'
>>> u.bytes
b'\x01qvxqIdl1\x9e\xcbFp\x14~\xc4'
>>> u.int
1918360407572615930874316424782053060
>>> u.uuid
UUID('01717a42-cde2-b5be-eed8-55222c867b58')
>>> u.float
1.918360407572616e+36
>>> bin(u.int)
'0b1011100010111011001111000011100010100100101100100011011000011000110011110110010110100011001110000000101000111111011000100'

Especially useful is the u.uuid type that allows you to replace existing UUIDs in your system with ULIDs without changing the value format. This means you can start benefitting from the ordering properties of ULIDs in existing systems.

Decentralized Generation

Because the ULID format of 48-bit timestamp + 100-bit randomness means that we get 100 bits per millisecond which almost eliminates the chance of collisions*. Contrast this with our auto-incrementing numeric column. The incrementation causes us to have to centralize managing that number in the database to avoid ID conflicts. With ULIDs, we can generate IDs in any of our Lambdas, containers, or EC2 instances.

Because the IDs are timestamped natively, we can tolerate partitions and delays. Inserting late data doesn't cause ordering problems because the items are timestamped when the ID is generated, and we can always add another timestamp field at ingestion if needed. The IDs allow us to maintain order and insert data late without having to add a separate ingestion process.

Distributed generation does mean that there is no "true clock" that allows us to perfectly order the items we put ULIDs on. This trade-off between a central synchronization point (for ordering) and greater reliability/resiliency is common in systems of any size and becomes nearly-required at scale.

Further, you may choose to go off-spec and use the 2 most-significant bits of the ULID that our encoding gives us. This is possible because there are 150 bits available in text representation, minus 148 used by the timestamp and randomness in the spec. You can get 4 sub-types of ULID in the same spirit of descriptive IDs like i-0123456789 and AKIAXNMVN by making the ID itself contain an encoded type.

* If you are Amazon Retail, don't follow this advice, one in a million things happen a couple times an hour at sufficient scale.

ULIDs in DynamoDB

The new trend in DynamoDB is single-table designs. Using a single table with a design allowing different GSIs to serve multiple queries. Rick tweeted this real-world example from the Kindle Collection Rights service that serves 9 queries with 4 GSIs.

These single-table designs rely on using properties that are sortable to enable queries, typically by combining Hash&Range in novel ways for each type of object. For example, you might create a key like Hash=Org#Trek10 Range=Post#2020-04-03#ca21477c-5693-4f2d-92e5-068102b24be9 which is composed of a type, org name, create time, and UUIDv4. Instead, with a ULID, you would be able to obviate the timestamp and ID combination and use a range key of Range=Post#01E5WF8AERWH9F8PDTQ5K4GW7R. This is a more efficient representation which also lets you use that same ID as a foreign key.

ULIDs can also be used to associate similar items that are created at the same time by manipulating the randomness values to be monotonic.

Take this NodeJS example that creates a ULID then uses the randomness from that ULID to create a series of related items that will lexically sort together:

> const monotonicFactory = require('ulid').monotonicFactory;
> const ulid = monotonicFactory()
> ulid(1586872590191)
'01E5WFM7VFPWCNF4DM76ADV80W'
> ulid(1586872590191)
'01E5WFM7VFPWCNF4DM76ADV80X'
> ulid(1586872590191)
'01E5WFM7VFPWCNF4DM76ADV80Y'
> ulid(1586872590191)
'01E5WFM7VFPWCNF4DM76ADV80Z'
> ulid(1586872590191)
'01E5WFM7VFPWCNF4DM76ADV810'

These ULIDs can be used to associate actions and events or to group activity from a particular task or host.

Going Plaid in S3

Let's return to our earlier S3 example for a moment. When looking for data in a specific time range, you can reduce the number of objects returned by ListObjects significantly. The Delimiter argument lets you narrow the range of your search in 5-bit increments. A ULID has 10 leading characters that represent a 48-bit timestamp with millisecond precision, with each character encoding 5 bits of the number.

48-bit millisecond epoch timestamps will run out of space in 10889 AD, mark your calendar. The astute reader will also note that a 48-bit timestamp value doesn't evenly encode to 50 bits available in a Crockford Base32 string, so the highest timestamp that will ever be representable is actually 7ZZZZZZZZZ not ZZZZZZZZZZ.

t = time character
r = randomness character
ttttttttttrrrrrrrrrrrrrrrr

How long is the range per character? Well, here are some orders of magnitude of the least significant bit representable in each.

• 1st character: 407226 days
• 2nd character: 12725 days
• 3rd character: 397 days
• 4th character: 12 days, 10 hours
• 5th character: 9 hours, 19 minutes
• 6th character: 17 minutes, 28 seconds
• 7th character: 32 seconds
• 8th character: 1 second
• 9th character: 30 milliseconds
• 10th character: 1 millisecond

This means that with S3's ListObjectsV2 API and the Delimiter parameter, you can grab 17-minute spans of your written data by using the 6th character of the ULID as your Delimiter. Take these objects:

2020-04-13 21:17:54          3 01E5V475QFRCEHXKJAS3BRS6BV
2020-04-13 21:24:51          3 01E5V4KXFTP52C9M5DVPQ2XR8T
2020-04-13 21:48:33          3 01E5V5Z9J0GX72VFSENBCKMHF0

We can slice between the 01E5V5Z... span with the following code:

>>> [k['Key'] for k in s3.list_objects_v2(
    Bucket='t10-blog-ulids',
    Delimiter='4',
    Prefix='01E5V4'
)['Contents']]
['01E5V475QFRCEHXKJAS3BRS6BV', '01E5V4KXFTP52C9M5DVPQ2XR8T']
​
​
>>> [k['Key'] for k in s3.list_objects_v2(
    Bucket='t10-blog-ulids',
    Delimiter='5',
    Prefix='01E5V5'
)['Contents']]
['01E5V5Z9J0GX72VFSENBCKMHF0']

As expected, the keys are ordered when they are returned and we can use bitwise operators (a.k.a. magic) to shift whatever time stamp or range we want into an S3 prefixed query. This lets us do time-range based filters without listing every object in the bucket or using an external job like S3 Inventory to list all the object names and timestamps.

Wrapping Up

In this post, we've touched on a couple of ways that semantically-charged identifiers can be useful in your storage layer. Overall, ULIDs and similar specs for sortable identifiers are an improvement on the standard fully-random UUID. They can make your app faster while still avoiding collisions and enumeration attacks, and also can be stored more efficiently (26 characters vs. 36).