8 ms·
NUID – An entropy friendly and highly performant unique identifier generator
- NuSkooler 11y agoWhat's the use case here over a UUID?
- tylertreat 11y agoPerformance mainly, I think. Benchmarking against UUID v4 shows a ~175% speedup.
- derekcollison 11y agoUUID V4 is ~900ns/op, NUID is ~60ns/op, so 15X speedup, or 1500%.
- fweespeech 11y ago> 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 36 ascii text, so 36^22 or 17324272922341479351919144385642496 possibilities. Isn't 22 bytes = 176 bits? UUID = 128 bit Storage performance is more than per-ns on a CPU core, imo.
- sheng 11y agoUUIDs are 120 Bit or less. Depending on the Version you use. But you lose 8 bit on any version because 1 byte is used to decode the UUID version.
- fweespeech 11y agoYes. 128bit is the worst case for UUIDs, I was trying to avoid the claim I was being overly generous by using the smallest size I could get away with. ;)
- JoeAltmaier 11y agoHm. The RFC says 4 bits + 2 bits (variant and variant version) are taken. That leaves 122 bits?
- derekcollison 11y agoYes, but most UUID when moved across networks are translated to hex, so 32 bytes/characters whereas NUID's are 22 bytes, so generally a savings of 10 bytes per when stored as a string.
- deleted 11y ago[deleted]
- tptacek 11y agoThere is no such thing as "entropy draining". If it's higher-performance than other UUID generators, fine, that's a win. But it's not doing anything useful for the system as a whole by sparing the "entropy pool".
- derekcollison 11y agoI disagree, either the entropy is drained and the randomness of what the pool returns (based on OS) is compromised or you get stalled waiting for more of it and decrease performance of the generator. https://www.google.com/webhp?q=draining+entropy+pool https://www.google.com/webhp?q=draining+entropy+pool
- nullc 11y agoIn the immortal words of Timecube: "You have been educated stupid". Fortunately, salvation is readily at hand: http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
- derekcollison 11y agoI think entropy, in however you measure it, does influence something like a UUID generator differently than the cryptographic algorithms. What you are trying to achieve, or more importantly the condition you are trying to avoid, is different.
- tptacek 11y agoA simple thought exercise to show you how false this is: Instantiate AES-128-CTR with a random key. Encrypt 100 megabytes with it. Have you "drained" "key" from AES? No, not in any meaningful sense. If you could, the AES-CTR recommendations would say "don't encrypt more than 100 megabytes with AES-CTR". In practice, people routinely encrypt many gigabytes with it. Every modern OS uses a DRBG for its kernel CSPRNG. You can think of a DRBG as a stream cipher, just like AES-128-CTR, where random events are hashed to form the key, and the output is the raw keystream. Asking for 100 megabytes of additional keystream doesn't "drain" the "key" from the keystream. Linux has a terrible misfeature, born of a failure to understand the crypto primitives they're using in their CSPRNG. /dev/random keeps an "estimator" that tries to determine how much "entropy" has been fed to the CSPRNG, and it decrements that estimator when requests come in for random bytes. Linux claims you can drain its CSPRNG. Linux is wrong; that is not how crypto works. Linux should lose that feature, but they will not. But there's no reason you should have to go along with it; just use urandom, which will not block for the estimator.
- nullc 11y ago"Entropy draining" :(
- jamesrom 11y agoWhy on earth would you care about entropy for a UUID? You can use the most basic PRNG to generate your 128 bits. There's your UUID. Call me when you find a collision.
- wongarsu 11y agoA basic PRNG might not be enough if you care about malicious collisions. There's plenty of cases of UUIDs being used in a context where a CSPRNG is preferable.
- heavenlyhash 11y agoI wrote Yet Another UUID [1] for my own purposes recently as well. Mine's based on Firebase's style UIDs [2] -- they sort roughly chronologically, because operationally, I find that irritates me less. Arbitrary choice? Entirely. Regrets? None. Do I recommend it for use? Also not at all. Unless you feel like it. It's fine. I guess. I've kind of given up on there being any purpose to a One True Spec for UUIDs. Count how many bits of entropy you want. Shove some CSPRNG into it. Call it a day. ¯\_(ツ)_/¯ (This a fine implementation, fwiw. I only mean to share my honest question as to whether there's any real utility to UUIDs-as-a-library.) [1] https://github.com/polydawn/repeatr/blob/dd41ca72421a173b5aa14580f5d7df48df1548d0/lib/guid/guid.go https://github.com/polydawn/repeatr/blob/dd41ca72421a173b5aa... [2] https://www.firebase.com/blog/2015-02-11-firebase-unique-identifiers.html https://www.firebase.com/blog/2015-02-11-firebase-unique-ide...
- derekcollison 11y agoI agree, was simply sharing because it was a need we had, which might be a need someone else had as well. Anyone can feel free to use it or not.