Giter VIP home page Giter VIP logo

nulid's Introduction

Logo NUlid

Build Status Nuget version

A .Net ULID implementation

Universally Unique Lexicographically Sortable Identifier

A GUID/UUID can be suboptimal for many use-cases because:

  • It isn't the most character efficient way of encoding 128 bits
  • It provides no other information than randomness

A ULID however:

  • Is compatible with UUID/GUID's
  • 1.21e+24 unique ULIDs per millisecond (1,208,925,819,614,629,174,706,176 to be exact)
  • Lexicographically sortable
  • Canonically encoded as a 26 character string, as opposed to the 36 character UUID
  • Uses Crockford's base32 for better efficiency and readability (5 bits per character)
  • Case insensitive
  • No special characters (URL safe)

Installation

PM> Install-Package NUlid

Or simply use the Nuget package manager GUI in Visual Studio.

Usage

Creating a ULID:

// Create a ULID
var myulid = Ulid.NewUlid();
// Print ULID
Console.WriteLine(myulid);

Output:

01ASB2XFCZJY7WHZ2FNRTMQJCT

Parsing a ULID:

// Parse ULID:
var myulid = Ulid.Parse("01ASB2XFCZJY7WHZ2FNRTMQJCT");
// Print time-part of ULID:
Console.WriteLine(myulid.Time);

Output:

4-8-2016 15:31:59 +00:00

You can also convert from/to GUID/UUID's, get the byte-representation of a ULID, create a ULID with specific timestamp and you can even specify an IUlidRng to use for generating the randomness (by default NUlid uses the CSUlidRng but a SimpleUlidRng is also provided, as well as a MonotonicUlidRng). The ULID is implemented as a struct with (operator) overloads for (in)equality, comparison etc. built-in and is, generally, very much like .Net's native Guid struct. An extensive helpfile is provided in the Nuget package and the testsuite also serves as a (simple) demonstration of NUlid's features.

Specification

Below is the current specification of ULID as implemented in this repository.

 01AN4Z07BY      79KA1307SR9X4MV3
|----------|    |----------------|
 Timestamp          Randomness
  10 chars           16 chars
   48bits             80bits
   base32             base32

Components

Timestamp

  • 48 bit integer
  • UNIX-time in milliseconds
  • Won't run out of space till the year 10895 AD (this .Net specific Ulid implementation limits this to DateTimeOffset.MaxValue).

Randomness

  • 80 (Whenever possible: Cryptographically secure) Random bits

As of v1.4.0 monotonic ULID's are supported (see below).

Monotonicity

When generating a ULID within the same millisecond, it is possible to provide some guarantees regarding sort order (with some caveats). When you use the MonotonicUlidRng and a newly generated ULID in the same millisecond is detected, the random component is incremented by 1 bit in the least significant bit position (with carrying). For example:

// Create monotonic rng
var rng = new MonotonicRng();

// Create ULIDs, assume that these calls occur within the same millisecond:
Console.WriteLine(Ulid.NewUlid(rng)); // 01DBN5W2SG000DCBVYHX4T6MCX
Console.WriteLine(Ulid.NewUlid(rng)); // 01DBN5W2SG000DCBVYHX4T6MCY
Console.WriteLine(Ulid.NewUlid(rng)); // 01DBN5W2SG000DCBVYHX4T6MCZ
Console.WriteLine(Ulid.NewUlid(rng)); // 01DBN5W2SG000DCBVYHX4T6MD0
Console.WriteLine(Ulid.NewUlid(rng)); // 01DBN5W2SG000DCBVYHX4T6MD1
Console.WriteLine(Ulid.NewUlid(rng)); // 01DBN5W2SG000DCBVYHX4T6MD2

By default the most significant bit of the random part is set to zero; this ensures you can generate enough ULID's after the initial one before causing an overflow. Some implementations simply pick a random value for the random part and increment this value, however, there's a (very small) chance that this random part is close to the overflow value. If you then happen to generate a lot of ULID's within the same millisecond there is a risk the you hit the overflow. By our method we ensure there's enough 'room' for new values before 'running out of values' (overflowing). It is, with some effort, even possible to 'resume counting' from any given ULID.

Encoding

Crockford's Base32 is used as shown. This alphabet excludes the letters I, L, O, and U to avoid confusion and abuse.

0123456789ABCDEFGHJKMNPQRSTVWXYZ

Binary Layout and Byte Order

The components are encoded as 16 octets. Each component is encoded with the Most Significant Byte first (network byte order).

0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      32_bit_uint_time_high                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     16_bit_uint_time_low      |       16_bit_uint_random      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

String Representation

ttttttttttrrrrrrrrrrrrrrrr

Where: t is Timestamp r is Randomness

Prior Art

Based on / inspired by alizain/ulid.

Performance

Below measurements are based on an Intel(R) Core(TM) i9-10900X CPU @ 3.70Ghz:

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22621.963)
Intel Core i9-10900X CPU 3.70GHz, 1 CPU, 20 logical and 10 physical cores
.NET SDK=7.0.101
  [Host]     : .NET 7.0.1 (7.0.122.56804), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.1 (7.0.122.56804), X64 RyuJIT AVX2


|                               Method |      Mean |    Error |   StdDev |   Gen0 | Allocated |
|------------------------------------- |----------:|---------:|---------:|-------:|----------:|
|                       Guid.NewGuid() |  58.14 ns | 0.334 ns | 0.296 ns |      - |         - |
|          Ulid.NewUlid(SimpleUlidRng) |  50.32 ns | 0.193 ns | 0.171 ns |      - |         - |
|              Ulid.NewUlid(CSUlidRng) | 117.07 ns | 0.862 ns | 0.720 ns |      - |         - |
| Ulid.NewUlid(SimpleMonotonicUlidRng) |  65.02 ns | 0.124 ns | 0.110 ns |      - |         - |
|     Ulid.NewUlid(CSMonotonicUlidRng) |  65.58 ns | 0.119 ns | 0.099 ns |      - |         - |
|                   Guid.Parse(string) | 193.62 ns | 0.813 ns | 0.721 ns | 0.0095 |      96 B |
|                   Ulid.Parse(string) | 226.54 ns | 0.299 ns | 0.250 ns | 0.0181 |     184 B |
|                      Guid.ToString() | 168.76 ns | 0.597 ns | 0.558 ns | 0.0095 |      96 B |
|                      Ulid.ToString() | 144.66 ns | 0.504 ns | 0.447 ns | 0.0079 |      80 B |
|                   'new Guid(byte[])' |  10.96 ns | 0.031 ns | 0.024 ns | 0.0040 |      40 B |
|                   'new Ulid(byte[])' |  12.55 ns | 0.024 ns | 0.021 ns | 0.0040 |      40 B |
|                   Guid.ToByteArray() |  65.32 ns | 0.183 ns | 0.152 ns | 0.0039 |      40 B |
|                   Ulid.ToByteArray() | 127.23 ns | 0.337 ns | 0.298 ns | 0.0038 |      40 B |
|                        Ulid.ToGuid() | 117.48 ns | 0.434 ns | 0.406 ns |      - |         - |
|                     'new Ulid(Guid)' |  64.26 ns | 0.574 ns | 0.537 ns |      - |         - |

nulid's People

Contributors

crnd avatar cyrusdargahi avatar gfoidl avatar rcollina avatar robthree avatar tsenart avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

nulid's Issues

NuGet Package with Source Files

Hello,
First and foremost, thanks for NUlid!
I'd love to use NUlid in one of our "core" libraries.

Not sure if you're familiar with TinyIoC; it has a "simple inclusion model". You basically get its source files, no assemblies to reference.

Would it be possible to have a "source only" package for NUlid?

Thank you, and apologies in advance if opening an "issue" is not the correct way to open requests.

Rob

Guid conversion doesn't take into account Microsoft's mixed-endian encoding

Hey, thanks for providing this library; it's been very useful to me.

I happened to notice that the Guids that were converted from certain Ulids (and vice-versa) didn't maintain the proper lexicographical sort order that I would have expected. I believe that this is because of Microsoft's screwy way of encoding the byte arrays (https://stackoverflow.com/a/16722909).

I forked and made a commit that appears to fix this at
kdawg14@c5ae7c8

I'm not certain exactly how you like to handle pull requests, or if this was something that was intentionally done the way that it was, so I figured I'd post this here and see if this looks like a good correction or if you maybe have any additional information on the subject.

Thanks!

Is there a way to serialize and maintain ordering?

Is there a means of serializing an NUlid object and still maintaining it's lexicographic ordering? More specifically, is there a way or would it make sense to convert an NUlid object into a representation than can be stored and have it still maintain its order amongst other stored NUlid objects?

Possible improvements from Cysharp/Ulid

Created a pull request with some potential optimizations/code modernisation for Cysharp/Ulidd. Not sure if any changes would apply here, it looks like NUlid and Ulid serialize to Guid in different ways (not 100% sure only glanced at it).

I meant to check if any improvements would apply to NUlid and create a pr, but I've been busy so I'll just dump the work on you ๐Ÿ˜†

ULID from GUID does not always parse

I ran into this issue while trying to convert a GUID to a ULID, but it happened randomly.

The following code should trigger it

for (var i = 0; i < 100_000; i++)
{
    Ulid.Parse(new Ulid(Guid.NewGuid()).ToString());
}

The stack trace:

System.ArgumentOutOfRangeException : Ticks must be between DateTime.MinValue.Ticks and DateTime.MaxValue.Ticks. (Parameter 'ticks')
   at System.DateTime.ThrowTicksOutOfRange()
   at System.DateTimeOffset..ctor(Int64 ticks, TimeSpan offset)
   at NUlid.Ulid.FromUnixTimeMilliseconds(Int64 milliseconds)
   at NUlid.Ulid.ByteArrayToDateTimeOffset(Byte[] value)
   at NUlid.Ulid.Parse(ReadOnlySpan`1 span)

Nuget package do not work for .NET 4.5.2

It is possible to add the nuget package to a .NET 4.5.2 project but since the library is for .NET 4.6 it will not be added to the project references. This is really confusing. I guess it is possible to add some kind of .NET framework compatibility requirement to the package so that projects with < .NET 4.6 can not install the package.

multiple machines for the same time.incrementation

I have seen that the MonotonicUlidRng implements monotonic incrementation within a single machine for the same time. I would like to know if it supports monotonic incrementation across multiple machines for the same time.

Underlying member variable is reference type?

Hi,

As I said in the title, a byte array is used as the member variable to hold the value of ULID struct. I (maybe others) expect ULID struct as a value type has a default value without an initialization which should be 00000000-0000-0000-0000-000000000000 in this case. I examine the source of GUID from corefx repo and I saw value types is used for member variables. https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Guid.cs

I hit this problem when I mess around with ULID and EF Core. EFCore create instances of entities to materialize query results but didn't use constructors and throw null reference exceptions for ULID types used in entity classes.

I changed implementation and use 16 different byte variables instead of byte array and achieve expected behavior (at least by me).

@RobThree Do you consider to change your implementation. I didn't keep my changes but can do it again if you prefer a pull request, because I'm intended to use NUlid on a new project.

Duplicate Ulid generated (serious)

This is not a joke. Here's the setup:

  1. The project is a IIS Asp.net application (WebAPI 2) running on .net 4.6
  2. Recycle app pool (or just restart the site in IIS)
  3. hit a request that uses Ulid.NewUlid() 2 times, (in my case this is primary key generation)

So what's happening is that the 2 requests are blocked until the Startup has finished after AppPool recycle. After startup finishes both requests are let through the gate. I'm unsure about the internal mechanism might be a semaphore.

Both requests call Ulid.NewUlid() at the same millisecond, so the first part is identical. But how come the random part is the same? Is there a data race in this library?

Looking underneath it uses BaseUlidRng.DEFAULTRNG which initalises a static RNGCryptoServiceProvider could this be the data race?

Network byte order

Hello there,

I'm confused regarding the byte order of the time components in the ULID. The original project states the following:

   The components are encoded as 16 octets.
   Each component is encoded with the MSB first (network byte order).

   0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      32_bit_uint_time_low                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     16_bit_uint_time_high     |       16_bit_uint_random      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       32_bit_uint_random                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       32_bit_uint_random                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

What I read from the above would result in the following diff in this function:

diff --git a/NUlid/Ulid.cs b/NUlid/Ulid.cs
index 70fe351..3639faa 100644
--- a/NUlid/Ulid.cs
+++ b/NUlid/Ulid.cs
@@ -147,7 +147,7 @@ namespace NUlid
         private static byte[] DateTimeOffsetToByteArray(DateTimeOffset value)
         {
             var mb = BitConverter.GetBytes(value.ToUnixTimeMilliseconds());
-            return new[] { mb[5], mb[4], mb[3], mb[2], mb[1], mb[0] };                                  // Drop byte 6 & 7
+            return new[] { mb[2], mb[3], mb[4], mb[5], mb[0], mb[1] };                                  // Drop byte 6 & 7
         }

         private static DateTimeOffset ByteArrayToDateTimeOffset(byte[] value)

Can you help me understand this please? Thank you :-)

1.7.0 return error with generated Ulid

Hello!

First, thanks for your job!

When using the latest version 1.7.0 of NUlid, we have this error when generate and then parse NUlid code

Example with this : "01FTX9NB2FVWG9MYN7ZEE03HX0"

'new Ulid("01FTX9NB2FVWG9MYN7ZEE03HX0")' threw an exception of type 'System.ArgumentOutOfRangeException'
ActualValue: null
Data: {System.Collections.ListDictionaryInternal}
HResult: -2146233086
HelpLink: null
InnerException: null
Message: "Index and length must refer to a location within the string.\r\nParameter name: length"
ParamName: "length"
Source: "mscorlib"
StackTrace: " at System.String.Substring(Int32 startIndex, Int32 length)\r\n at NUlid.Ulid.Parse(String s)\r\n at NUlid.Ulid..ctor(String ulid)"
TargetSite: {System.String Substring(Int32, Int32)}

We are using framework .NET 4.7.1 project

Thanks for your help !

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.