nats-io / nuid

NATS Unique Identifiers

NUID

A highly performant unique identifier generator.

Installation

Use the go command:

$ go get github.com/nats-io/nuid

Basic Usage

// Utilize the global locked instance
nuid := nuid.Next()

// Create an instance, these are not locked.
n := nuid.New()
nuid = n.Next()

// Generate a new crypto/rand seeded prefix.
// Generally not needed, happens automatically.
n.RandomizePrefix()

Performance

NUID needs to be very fast to generate and be truly unique, all while being entropy pool friendly. NUID uses 12 bytes of crypto generated data (entropy draining), and 10 bytes of pseudo-random sequential data that increments with a pseudo-random increment.

Total length of a NUID string is 22 bytes of base 62 ascii text, so 62^22 or 2707803647802660400290261537185326956544 possibilities.

NUID can generate identifiers as fast as 60ns, or ~16 million per second. There is an associated benchmark you can use to test performance on your own hardware.

License

Unless otherwise noted, the NATS source files are distributed under the Apache Version 2.0 license found in the LICENSE file.

nuid's Issues

Modulo bias in prefix generation

The modulo operation in

nuid/nuid.go

Line 132 in 57049d7

n.pre[i] = digits[int(cbs[i])%base]

causes a bias towards the first 8 digits (0-7). These digits occur with a probability of 5/256 while the rest of the digits occur with a probability of 4/256.

Using a base that is a power of 2 would guarantee a uniform distribution. It would also open up the possibility to exploit power of 2 for mod and div operations.

Prefix may not be properly filled

The RandomizePrefix function seems to be incorrect. The loop is using l as the condition to continue, however, there is no guarantee that l is going to be big enough that the loop will cover all 12 indexes of the prefix array:

https://github.com/nats-io/nuid/blob/master/nuid.go#L111

Actually, since maxPre (36^12) is used as the max for rand.Int(rand.Reader, big.NewInt(maxPre)), it is quite probable. A quick test showed that 2% of runs, i would end-up greater than 0 at the end of the loop. Should the condition had been i? or should maxPre be the minimum acceptable value for r, and therefore rand.Int() should be passed the max int64 value?

seed from crypto/rand, not timestamp

(Nice library!)

Re

https://github.com/nats-io/nuid/blob/master/nuid.go#L49

I've had code reviews from ex-NSA guys who pointed out seeding with the current timestamp is actually pretty non-random, and is not too difficult to reverse engineer.

The alternative: it is simpler and more random to seed from crypto/rand instelf.

Please add tag for current release

Hi,

Could you please add a tag for the current version? It would be useful for packaging and get notifications about new releases :)

LICENSE: please specify copyright owner

Hello!

Would it be possible to specify the copyright owner in the LICENSE file?

Thanks!

Code duplicate

Code in

nuid/nuid.go

Line 71 in 4b96681

globalNUID.RandomizePrefix()

is duplicate as New() has called RandomizePrefix already

nuid/nuid.go

Lines 75 to 83 in 4b96681

	func New() *NUID {
	n := &NUID{
	seq: prand.Int63n(maxSeq),
	inc: minInc + prand.Int63n(maxInc-minInc),
	pre: make([]byte, preLen),
	}
	n.RandomizePrefix()
	return n
	}