Many times, as a Data Engineer, I have processed data with inconsistent ID systems, which led to duplicated data. Then, it made me wonder, “Is it difficult to implement an ID system?”
So I decided to do a bit of research into this topic, of which I know little about. The logical result is: I should write a blog post about it, then. Maybe there are other Data Engineers out there who are also frustrated with inconsistent ID systems.
First off, let's start with our goal.
The point of generating IDs is more complex than it looks. It's worthy of an entire iceberg just for itself.
In the tip, we see concerns like uniquely identifying entities in an application, which can be distributed or localized.
As you go further down the iceberg, themes of security, observability, and performance will emerge.
This is where the elegance of Computer Science emerges as well.
Let's say you are building a social media app and you'd like to create a unique ID system for your users.
The naive approach would be to simply SHA256 hash the email string. If you're feeling fancy, you can even add some salt to reduce predictability.
There you go, you'd have a safe-looking string. Job done, right? Who'd guess it?
gmnmedeiros@gmail.com1234456 #some salt added
⏬⏬⏬
3c20b40794c4df725eb33a4d6098f3d6aaffec7368786199a5c9e44142bb5c65Well, there are some problems at hand.
First, hashing functions are deterministic by nature. So there's always an intrinsic relation between the email and the ID, especially if the added salt is simple enough.
Second, emails have a small entropic space. Entropy is a measure of the total information in a system. So, to avoid collisions, you'll want a large entropic space. For instance, if a user changes an email, you need measures to avoid collisions if the previous email gets taken again.
These two issues combined allow for brute force attacks with tools like rainbow tables.
What lacks, then? More randomness, a larger entropic space, and less reliance on determinism, so you lessen predictability.
Note that the ideal entropic space is the product of combining non-related info, which decisively reduces the risk of collision drop.
This part of the post is based on this article by Eric Elliott, Identity Crisis: How Modern Applications Generate Unique Ids.
In this post, the author talks about the limitations of some traditional techniques of ID generation.
For instance, database autoincrements are limited by scale nowadays. If you have a distributed application and use autoincrements, your databases may attribute the same number to different entities, which defies the purpose of identification.
But there's a way to make it work.
Instagram has done a good job with its distributed remote ID generation service. Its logic allows their PostgreSQL logical shards to create IDs and avoid collisions independently. Each shard is a schema.
The resulting ID is a 64-bit integer composed of (A) 41 bits of an encoded custom epoch timestamp, (B) 10 bits of the shard ID, and (C) 13 bits of the incremented table ID.
Here's the SQL transaction that accomplishes this:
CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
our_epoch bigint := 1314220021721; -- Custom epoch
seq_id bigint;
now_millis bigint;
shard_id int := 5; -- Logical shard ID for this particular schema
BEGIN
-- Get the next sequence value and constrain it to 10 bits (0-1023)
SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;
-- Get the current timestamp in milliseconds
SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
-- Build the time component (left shift by 23 bits)
result := (now_millis - our_epoch) << 23;
-- Incorporate the shard ID (shifted left by 10 bits)
result := result | (shard_id << 10);
-- Finally, include the sequence number
result := result | (seq_id);
END;
$$ LANGUAGE PLPGSQL;
However, there are two big downsides to this approach:
Each ID generation requires a round-trip to the service, so it's slow.
This doesn't work offline. Upon partition, it's difficult to enforce consistency.
Eric Elliott brings some useful data about how limited the implementations of UUIDs and GUIDs can be. According to him:
Due to a poor pseudo-random algorithm, some older implementations of V4 UUID can’t generate more than 10k ids without generating a collision.
So he advocates for a better version of these IDs: CUID2. Here's the PyPi link for the lib: https://pypi.org/project/cuid2/
According to the docs, here are the features of this lib:
Secure: It's not possible to guess the next ID.
Collision resistant: It's extremely unlikely to generate the same ID twice.
Horizontally scalable: Generate IDs on multiple machines without coordination.
Offline-compatible: Generate IDs without a network connection.
URL and name-friendly: No special characters.
One of its greatest feats is using multiple, independent entropy sources and hashing them with a security-audited, NIST-standard cryptographically secure hashing algorithm (SHA3).
Cuid2 leverages high-resolution timestamps (often at the nanosecond level) to ensure that each ID is timestamped with a value unlikely to repeat, even if two IDs are generated nearly simultaneously.
Also, it uses a better random function than the standard .random(). For that, it uses Python's secrets module.
This is good, because standard random functions are notoriously unreliable. You can check this discussion on PHP's Sec Bug #70014. It discusses the cryptographical security of a method called openssl_random_pseudo_bytes().
If you don't want to rely on CUID2 or want to create your own system, take some principled paths, and it's unlikely you'll end up in a bad spot.
The following steps will use application data rather than database structures, as Instagram's approach does.
There are two common types of high-entropy data: user-independent ones and fingerprints.
User-Independent Data:
High-precision timestamp (e.g., nanosecond resolution where available)
A random number generated with a strong cryptographic random function
A session or local counter (to capture rapid ID generation on the same host)
A fingerprint component:
A derived fingerprint from the application instance or device-specific attributes (ensuring uniqueness among different clients without exposing raw identifiers)
If you're not modelling users, there is other information you can use as a fingerprint component.
For a product
Static Attributes: Use the product's inherent attributes, such as the SKU, manufacturer code, or even a standardized product name.
Category Identifier: If products come from different categories or vendors, include that.
Data Source Identifier: Add a subtle marker representing the system or database where the product is initially listed.
For a comment
Context Identifier: Include an identifier for the thread or post to which the comment belongs.
Content Hash: A quick hash (such as MD5 or a truncated SHA-256) of the comment content can be used—not to reveal the content but to mix it into the entropy pool.
User or System Timestamp: When the comment was posted can also help differentiate it from others in the same thread.
For a photo
File Metadata: Incorporate metadata if available (e.g., camera model, geolocation, or timestamp embedded in the photo’s EXIF data).
Content-Based Hash: Provide an intrinsic signature by using a cryptographic hash of the image content itself (or a resized/thumbnail version to reduce processing cost).
Upload or Creation Timestamp: When the photo was taken or uploaded, to introduce additional entropy.
The result should be concatenated into a canonical string.
After you have your canonical string, simply transform with one-way and non-reversible operations.
Non-Reversible Hashing:
Concatenate the entropy sources into a canonical string and process it with a strong, one-way hash function (e.g., SHA-256). To avoid exposing any patterned structure from the source entropy, apply a one-way hash that outputs a fixed-length digest.Trimming or Encoding:
Encode or trim the hash output to create a shorter and friendlier identifier. Makes it easier to store, and retains collision safety.
Hope you liked this text!
And I hope you, Data Engineer, come to appreciate more the subtle art of ID building, especially when you don't run into inconsistent systems!
Here are some references I've used to write this text.
https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c
https://medium.com/@sandeep4.verma/system-design-distributed-global-unique-id-generation-d6a440cc8e5
Comments
Nothing yet. Say the first thing.
Sign in to join the conversation.