Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

github.com

Post reply on HN
Print view View original

141–150 of 236 posts

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#141

Post by klabb3 »

dloreto wrote: post #134
klabb3 wrote: post #120

A couple of suggestions: Lock down the prefix string now before it’s too late and document it. I see in Go that it’s lowercase ascii, which seems fine except for compound types (like “article-comment”). May be worth looking at allowing a single separator given that many complex projects (and ORMs) can’t avoid them. The Go implementation has no tests. This is very unit-testable. Add tests goddammit! For Go, I’d align…

Thanks for the feedback! We have tests for the base32 encoding which is the most complicated part of the implementation ( https://github.com/jetpack-io/typeid-go/blob/main/base32/bas... ) but your point stands. We'll add a more rigorous test suite (particularly as the number of implementations across different languages grows, and we want to make sure all the implementations are compatible with each other) Re: prefix…

> We have tests for the base32 encoding which is the most complicated part of the implementation

I didn’t look into it much but it seems like a great encoding even outside of this project. Predictable length, reasonable density, “double clickable” etc. I’ve been annoyed with both hex and base64 for a while so it’s pretty cool just by itself.

> Re: prefix, is the concern that I haven't defined the allowed character set as part of the spec?

Yeah, the worry is almost entirely “subtle deviations across stacks”, which is usually due to ambiguous specs. It’s so annoying when there’s minor differences, compatibility options etc (like base64 which has another “URL-friendly” encoding - ugh).

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#142

Post by armchairhacker »

onlypositive wrote: post #139

> Compare to entirely random global ids, like UUIDv4, that generally suffer from poor database locality. What does this mean in more words?

Because the bytes are all random, UUIDv4 is sorted randomly. So whenever you insert a database entry with a new UUID, it ends up getting put in some random memory location.

In practice, you often want to select database entries which were inserted near each other in time. Ex: you would like to select the most recent entries or entries within a time frame. Even when selecting entries by other information, entries inserted closer to each other in time are generally more likely to be related.

Fetching entries near each other in memory is faster, so it would be nice to insert entries sequentially in time; we want entries inserted near each other in time to be located near each other in memory.

This is what counter-based indexing does: the database has a counter which increments on each insertion, and the current value becomes the inserted entry's id. But the problem with counters is when the database is distributed and insertions are happening in parallel, and you definitely don't want to sync the counter because that's way too slow.

UUIDv7 combines a sort of counter (Unix time) with a randomly-generated number. The counter bytes are first, so they determine the sort order; but in case 2 entries get inserted at the same time, the randomly-generated number keeps them distinct and totally ordered.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#143

Post by aftbit »

klabb3 wrote: post #141
dloreto wrote: post #134

Earlier quoted context omitted.

Thanks for the feedback! We have tests for the base32 encoding which is the most complicated part of the implementation ( https://github.com/jetpack-io/typeid-go/blob/main/base32/bas... ) but your point stands. We'll add a more rigorous test suite (particularly as the number of implementations across different languages grows, and we want to make sure all the implementations are compatible with each other) Re: prefix…

> We have tests for the base32 encoding which is the most complicated part of the implementation I didn’t look into it much but it seems like a great encoding even outside of this project. Predictable length, reasonable density, “double clickable” etc. I’ve been annoyed with both hex and base64 for a while so it’s pretty cool just by itself. > Re: prefix, is the concern that I haven't defined the allowed character se…

My personal favorite encoding is base58 aka Bitcoin address encoding. It uses characters [A-Za-z0-9] except for [0OIl]. It is almost as dense as base64, "double clickable", but not (as) predictable in length as base32.

It was chosen to avoid a number of the most annoying ambiguous letter shapes for hand-entry of long address strings.

https://en.bitcoin.it/wiki/Base58Check_encoding

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#144

Post by namtab00 »

jabbany wrote: post #126
mtlmtlmtlmtl wrote: post #111

Earlier quoted context omitted.

A vaguely related historical tangent is that V and U used to be just two ways of writing the same letter in Early Modern English. Which I imagine is why W is named as "double U" in speaking.

This is also interesting since in French (and I think Spanish?) W is (correctly) called "double V"

In Romanian and Italian too.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#146

Post by sokoloff »

michaelt wrote: post #106
sokoloff wrote: post #100

Earlier quoted context omitted.

> base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in. We had “analrita” as an autogenerated password that resulted in a complaint many years ago. Might consider adding ‘a’ as an excluded letter.

Presumably base 32 means 26 letters + 10 digits - 4 banned letters So adding an excluded letter is not easy.

Why not use base-31 and (optionally) more characters? (Or go upper and lower or add a symbol if you had to stay with a fixed-size and base-32 for some reason)

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#147

Post by Merad »

iillexial wrote: post #59

I didn't get the "type-safe" part. How would it work in Go? Let's say I have structs: type User struct { ID TypeID } type Post struct { ID TypeID } How can I ensure the correct type is used in each of the structs?

I don't know go, but in C# I'd probably do something like the code below. The object really only needs to carry the uuid/guid, let the language type system worry about the difference between a user and post id. We just need a generic mechanism to ensure that UserId object can only be constructed from a valid type id string with type = user. For production use you'd obviously need more methods to construct it from a database tuple (mentioned elsewhere in the comments), etc.

    interface ITypeIdPrefix
    {
        static abstract string Prefix { get; }
    }

    abstract class TypeId
        where T : TypeId, ITypeIdPrefix, new()
    {
        public Guid Id { get; private init; }

        public override string ToString() => $"{T.Prefix}_{Id.ToBase32String()}";
        // Override GetHashcode(), Equals(), etc.

        public static bool TryParse(string s, out T? result)
        {
            if (!s.StartsWith(T.Prefix) || !TrySplitStringAndParseBase32ToGuid(s, out var id))
            {
                result = default;
                return false;
            }

            result = new T { Id = id };
            return true;
        }
    }

    class UserId : TypeId, ITypeIdPrefix
    {
        public static string Prefix => "user";
    }

    class PostId : TypeId, ITypeIdPrefix
    {
        public static string Prefix => "post";
    }

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#148

Post by Aeolun »

rbera wrote: post #76
titanomachy wrote: post #70

Earlier quoted context omitted.

Wow I didn't know HN even had obscenity filters, and I've been here for many years. Guess that's a credit to the general civility of the community. EDIT: It appears that other people in this thread are freely using profanity, so either your comment was targeted by automation due to the unusual density of banned words, or it's a joke that went over my head :)

That explains it, I was very confused by what I assumed was self-censoring, since the comment didn’t actually clarify anything. I wish there was an accepted way to disambiguate asterisks from server side filters.

But we know there are no server side filters here. At least I never had any profanity censored by anything other than the Mk 1 brain.

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#149

Post by beyonddream »

This looks really interesting! Tangentially related if anyone is interested, I recently wrote[1] a pure C (no external dependency) version of coordination free, k-ordered 128-bit UUID Generator library which is inspired by snowflake but has bigger key space and few nifty features to protect against clock skew etc. The 128 bits are split into

  {timestamp:64, worker_id:48, seq: 16}
where the seq is incremented if the unique id is requested within the same millisecond.

[1] - https://github.com/beyonddream/snowid

Re: Type-safe, K-sortable, globally unique identifier inspired by Stripe IDs

#150

Post by manquer »

sokoloff wrote: post #100
aartav wrote: post #95

I've been doing this kind of thing for years with two notable differences: 1. I don't believe people actually hand type-in these values, so I'm not really concerned about the 'l' vs '1' issue. I do base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in. 2. I add two base-32 characters as a checksum (salted of course). This is prevents having to go look at the datastore when the valu…

> base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in. We had “analrita” as an autogenerated password that resulted in a complaint many years ago. Might consider adding ‘a’ as an excluded letter.

Wouldn’t that be excluded because i is already removed ?
Post reply on HN