Universally Unique Lexicographically Sortable Identifiers (ULIDs)

In my previous post, I talked about time-based universally unique identifiers – UUID v7 for short. An alternative to UUIDs (especially to version 4) is the ULID, which stands for Universally unique Lexicographically sortable IDentifier. These are similar with UUIDs, they have the same 128 bit length, but offer several advantages. Let’s see what these are and how ULIDs can be used.

Overview of ULIDs

There are several similarities between ULID and UUID:

• they both have 128-bits
• their string encoding is case insensitive

With UUID v7 it shares more similarities:

• the most significant 48 bits are the UNIX time in milliseconds, the rest of the 80 bits are random
• monotonic sort order

Other characteristics of ULIDs are:

• 1.21e+24 unique ULIDs per millisecond
• canonically encoded as a 26 character string (without any dashes as in the case of UUID)
• no special characters used
• Uses Crockford’s base32 for better efficiency and readability (5 bits per character)

Examples of ULID:

• R29AT090TEA6XYY0ZXR0W3CD60
• 4xx3ns5am83hwsbmkkbaw3cd60

A C++ Implementation

ULIDs can be implemented in C++ in different ways. Such a possible implementation is show below.

struct ulid_t
{
public:
   static ulid_t generate()
   {
      ulid_t ulid;

      uint64_t ts = now_ms();
      ulid.data[0] = (ts >> 40) & 0xFF;
      ulid.data[1] = (ts >> 32) & 0xFF;
      ulid.data[2] = (ts >> 24) & 0xFF;
      ulid.data[3] = (ts >> 16) & 0xFF;
      ulid.data[4] = (ts >> 8) & 0xFF;
      ulid.data[5] = (ts >> 0) & 0xFF;

      static thread_local std::mt19937 rng{ std::random_device{}() };
      for (size_t i = 6; i < 16; ++i) 
      {
         ulid.data[i] = static_cast<uint8_t>(rng());
      }

      return ulid;
   }

   std::string string() const 
   {
      return encode_base32(data);
   }

   explicit operator std::string() const 
   {
      return encode_base32(data);
   }

private:
   std::array<uint8_t, 16> data{};

   static uint64_t now_ms() 
   {
      using namespace std::chrono;
      return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
   }

   // Crockford Base32
   static constexpr char ENCODING[32] = 
   {
       '0','1','2','3','4','5','6','7','8','9',
       'A','B','C','D','E','F','G','H','J','K',
       'M','N','P','Q','R','S','T','V','W','X',
       'Y','Z'
   };

   // Extracts 26 * 5-bit groups (LSB-first) from the 16 bytes
   static std::string encode_base32(const std::array<uint8_t, 16>& bytes)
   {
      std::string out(26, '0');

      // ULID has 128 bits, but encoding requires 130 bits, pad zero bits at start
      uint32_t bitpos = 128 + 2;  // pretend we have 130 bits

      for (int i = 0; i < 26; ++i)
      {
         bitpos -= 5;

         uint32_t value = extract_5bits(bytes, bitpos);
         out[i] = ENCODING[value];
      }

      return out;
   }

   // Extract exactly 5 bits from an arbitrary bit offset
   static uint32_t extract_5bits(const std::array<uint8_t, 16>& bytes, uint32_t bitpos)
   {
      // byte index and bit offset in that byte
      uint32_t byteIndex = bitpos >> 3;
      uint32_t startBit = bitpos & 7;

      // Read 16 bits starting at byteIndex
      uint32_t v = (bytes[byteIndex] << 8) |
         (byteIndex + 1 < 16 ? bytes[byteIndex + 1] : 0);

      // Shift to get a 5-bit window
      v >>= (11 - startBit); // from the 16-bit window

      return v & 0x1F;       // last 5 bits
   }
};

This can be use as follows:

ulid_t ulid = ulid_t::generate();
std::println("{}", static_cast<std::string>(ulid));

Libraries

The above implementation is a simplistic proof of concept. However, there is a plethora of libraries for all major programming languages, including C++, C#, Java, JavaScript, Go, Python, Rust. You can find a list of such libraries here.

See also

You can read more about ULIDs in these articles:

• ULID specifications
• What is ULID and why should you start using it?
• Lexicographically Sortable Identifiers Using ULID