4 ms·

A problem with this approach is it's not monotonical. Especially if you want to use this thing as an index in a database, you'll run into problems where you tr

A problem with this approach is it's not monotonical. Especially if you want to use this thing as an index in a database, you'll run into problems where you try doing middle insertions frequently, which causes fragmentation. The solution to this problem is making the higher order characters time sorted [1]. You don't need to go all out like uuid, you can have a pretty low resolution. It's more important that new insertions tend to be on the same page. If you have a low frequency insertions then minute resolution is probably good enough. (Minutes since 2000 is an easy calculation). To implement that here, I'd suggest looking at how base64 or 85 encoders work and use that instead of repeated mods. You can then dedicate the upper bits to a time component and the lower bits can remain random. [2] [1] https://vladmihalcea.com/uuid-database-primary-key/ https://vladmihalcea.com/uuid-database-primary-key/ [2] https://github.com/mklemm/base-n-codec-java/blob/master/src/main/java/net/codesup/utilities/basen/AnyBaseEncoder.java https://github.com/mklemm/base-n-codec-java/blob/master/src/...

reissbaker 2y ago
IMO it's nice to have two keys: 1. An auto-incremented 64-bit (unless you have a good reason, in which case 32-bit is fine) primary key, used internally for foreign key relations. This will generally result in less index bloat on associated tables, and fast initial inserts. 2. A public-facing random string ID. Don't use this internally (other than in an index on the table it's defined for), since it's large. But this should be the only key you expose to end-users, to prevent leaking data via the German Tank Problem: https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem Only create the second key if this is data you're exposing to users, of course — for data that's only used internally, just use the 64-bit auto-incremented PK and skip the added index bloat entirely.
- cogman10 2y ago
  For the number 2, I think one issue is that you are going to be semi-frequently whacking the db to do a mapping of that random string id back to the real id. OK for smaller entities but might be a pain if there's a lot of those ids to wrangle. You can throw a secondary index on it, but that will still have some minor fragmentation issues. One benefit of a random id is if you are working with more complex data models it can make creating those easier/faster. Instead of having a centralized location to get new ids from (the DB) you can create ids on the fly from the application which can turn the write into a single action from the application rather than a dance of inserting the main table, getting the new id, then inserting to the normalized tables.
  - caeril 2y ago
    That's why the Good Lord invented caching. In most applications, 90% of your workload will be over ids less than a week old, so your hit rate is likely to be pretty high for this sort of mapping.
    - cogman10 2y ago
      First hit can be a beast. It's workload/entity determinant if caching is enough for this. Not great if you are spending 1 minute on the first lookup just to do the mapping.
      - reissbaker 2y ago
        Although I think it'll be fine even without a cache for most workloads (it's super easily indexed since the cardinality of random data is extremely high), I'm curious what cache setup you've got that it would take a minute to do a KV lookup — Memcached or Redis for example should be single digit milliseconds or better.
  - reissbaker 2y ago
    Assuming you've set up an index on the public ID string, that should be a super fast query even on a table with billions of rows. Beyond billions of rows you're looking at something a lot more custom than a standard SQL DB, but assuming you shard the data, it should still be a very fast query regardless of dataset size. Worst case you can cache, as others have mentioned, but TBH I think you don't need to for a query that simple and should save the cache space for something more complicated. Most SQL DBs are excellent for ready-heavy workloads; it's writes that tend to make them fall over.
- rav 2y ago
  Instead of a random string ID, you can devise a fixed secret key and expose the auto-incremented ID xor the fixed secret key as the public-facing ID. This saves you the separate index but still avoids the German tank problem. But it gives you a new problem, namely a secret that's hard or impossible to rotate.
  - cogman10 2y ago
    This is insecure. Assuming the user can get a few key examples (which, we assume they would be able to if the german tank problem is a problem) then the secret can easily be revealed. [1] [1] https://dev.to/wrongbyte/cryptography-basics-breaking-repeated-key-xor-ciphertext-1fm2 https://dev.to/wrongbyte/cryptography-basics-breaking-repeat...
  - senderista 2y ago
    XOR isn't secure enough, but you're on the right track. Instead, use an actual block cipher.
- WorldMaker 2y ago
  A different approach to solve both 1 and 2 is timestamp-oriented IDs. You can get useful cache locality/less "index bloat"/fast initial inserts if your keys can be easily ordered in time. Sorted by timestamp means very similar behavior to B-Tree appends of a monotonic integer, even sometimes in the worst cases where "same moment" IDs aren't monotonic and rely more on random entropy. I got some great DB cache/index performance from ULIDs with a bit of work to order the ULID timestamp bits in the way the DB's 128-bit column "uuid" sort best supported. Now that UUIDv7 is standardized we should hopefully see good out-of-the-box collation for UUIDv7 in databases sooner rather than later.
  - reissbaker 2y ago
    Yep, that works too as long as the timestamp data isn't sensitive.
- senderista 2y ago
  I don't understand why you need to maintain two separate keys: instead of generating a random key, why not just encrypt the auto-increment key using a secret key? This is the approach used by e.g. cloud providers that use auto-increment keys internally but don't want them to be guessable.
  - cogman10 2y ago
    I think the biggest problem with this approach is it effectively pins you to a encryption key and algorithm (unless you embed some information in the key that lets you version the key, gotta think of that upfront). Imagine, for example, that you picked DES and "kangaroo" as the secret several years back. You are now pinned to an algorithm and key with known security problems and a weak key.
    - Too 2y ago
      Especially since you can try the encryption algorithm. Create 1000 users very quickly in a row and you now have 1000 samples of enc(i) all the way up to enc(i+1000) that can help you break the algorithm. Not saying it will be easy but it surely lowers the guarantees given by the encryption. Someone better at crypto can probably quantify this risk better than me.
  - reissbaker 2y ago
    Sure, that works too. The upside of just storing a random string is you don't ever need to deal with secret management, key rotation, ciphers getting broken, etc — the random string truly has nothing to do with the real underlying ID, so there's just less work involved in hiding it. The downside is some extra bytes and index space.
echelon 2y ago
This is a great technical modification that can be made to work with "Stripe"-alike IDs or tokens. Another hack for advanced active-active situations where you may need to route events before replication completes: encoding the author shard / region in the lower order bytes. There are lots of interesting primary key hacks for dealing with physical or algorithmic complications.
jordanthoms 2y ago
This is dependent on the database you are using - if it's a key-sharded distributed database, you want to have insertions evenly spread across the key space in order to avoid having all the inserts go into a single shard (which could overload it)
- cogman10 2y ago
  This is the great thing about using random bits for the lower bits. Because you are unlikely to use more than say 2^64 database nodes, any sharding algorithm will have to figure out how to spread a key with 64 bits (or however many bits are in your key) across n nodes. Because of the random portion of the key, that means you'll get good distribution so long as the distribution algorithm isn't something stupid like relying solely on the highest order bits.
groestl 2y ago
> A problem with this approach is it's not monotonical Whether or not that's bad fully depends on your platform and the number of writes you do. If you're using a massively distributed database like Datastore, Spanner etc, you want random keys as to avoid hot spots for writes. They produce contention.
- cogman10 2y ago
  Well, you'd still likely want psuedo-random keys. You'd rather not have the underlying database doing extra work to shuffle around records as the pages get jumbled. One solution to that is having more complex keys. For example, in one of our more contentious tables the index includes an account id (32bit int) and then the id of the entity being inserted. This causes inserts for a given account to still be contiguous (resulting in less fragmentation) while not creating a writing hotspot since those writes are distributed across various clients.
  - groestl 2y ago
    Not disagreeing. Point is, you need to know your domain, your technology, your write patterns, your downstream systems, etc to decide if a specific key scheme works to your advantage or not. All the more reason not to use natural keys, as they lock you in in that regard.
    - cogman10 2y ago
      Absolutely agree. I don't know how you can successfully maintain or develop software without developing an understanding of the underlying domain. I've seen devs try that route and the quality of their work has never been high.
hot_gril 2y ago
Depends heavily on what kind of database/index. Going with anything other than a random uuid4 adds complexity; for one, do you want to expose time info? I'd rather default to uuid4 as the client-exposed ID* and only change if there's a solid measured reason to. * not the same as your internal DB row primary keys, which in Postgres should usually be bigserial
- cogman10 2y ago
  Yes but also no. Yes, in that there are DB technologies not built in a fashion where records are stored in a sorted order of some fashion. No, in that they are very much not common technologies. Most databases, relational, non-relational, etc have some form of a B-Tree at their core somewhere.
  - hot_gril 2y ago
    I can see this. Spanner is an example where you don't want this, idk if that's considered common enough. Postgres and MySQL both support hash indexes that are unordered, but the default in both is btree, and Postgres hash indexes used to have some caveats that made them unsuitable (idk about now) so I've gotten in the habit of just using the default. MySQL docs claim that a hash index is much faster if you only need kv lookups, so it seems like uuid4 with hash index would be suitable. Never tried it though, and can't say whether it's faster than using a btree with uuid7. Seems like in theory it would be.
    - cogman10 2y ago
      As always, depends on the implementation. Hash maps should generally always have faster lookups than Btree based structures. However, they'll have slower writes especially when contested. A key issue hash tables have to deal with is what happens when a remapping needs to happen. For example, when 2 keys have the same hash. In that case, locking becomes a lot more messy. For a btree this is simpler. It's built to be able to handle reshuffling and rebalancing in a way that's semi easy to have fine grained locks around.

reissbaker 2y ago

IMO it's nice to have two keys: 1. An auto-incremented 64-bit (unless you have a good reason, in which case 32-bit is fine) primary key, used internally for foreign key relations. This will generally result in less index bloat on associated tables, and fast initial inserts. 2. A public-facing random string ID. Don't use this internally (other than in an index on the table it's defined for), since it's large. But this should be the only key you expose to end-users, to prevent leaking data via the German Tank Problem: https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem Only create the second key if this is data you're exposing to users, of course — for data that's only used internally, just use the 64-bit auto-incremented PK and skip the added index bloat entirely.

cogman10 2y ago
For the number 2, I think one issue is that you are going to be semi-frequently whacking the db to do a mapping of that random string id back to the real id. OK for smaller entities but might be a pain if there's a lot of those ids to wrangle. You can throw a secondary index on it, but that will still have some minor fragmentation issues. One benefit of a random id is if you are working with more complex data models it can make creating those easier/faster. Instead of having a centralized location to get new ids from (the DB) you can create ids on the fly from the application which can turn the write into a single action from the application rather than a dance of inserting the main table, getting the new id, then inserting to the normalized tables.
- caeril 2y ago
  That's why the Good Lord invented caching. In most applications, 90% of your workload will be over ids less than a week old, so your hit rate is likely to be pretty high for this sort of mapping.
  - cogman10 2y ago
    First hit can be a beast. It's workload/entity determinant if caching is enough for this. Not great if you are spending 1 minute on the first lookup just to do the mapping.
    - reissbaker 2y ago
      Although I think it'll be fine even without a cache for most workloads (it's super easily indexed since the cardinality of random data is extremely high), I'm curious what cache setup you've got that it would take a minute to do a KV lookup — Memcached or Redis for example should be single digit milliseconds or better.
- reissbaker 2y ago
  Assuming you've set up an index on the public ID string, that should be a super fast query even on a table with billions of rows. Beyond billions of rows you're looking at something a lot more custom than a standard SQL DB, but assuming you shard the data, it should still be a very fast query regardless of dataset size. Worst case you can cache, as others have mentioned, but TBH I think you don't need to for a query that simple and should save the cache space for something more complicated. Most SQL DBs are excellent for ready-heavy workloads; it's writes that tend to make them fall over.
rav 2y ago
Instead of a random string ID, you can devise a fixed secret key and expose the auto-incremented ID xor the fixed secret key as the public-facing ID. This saves you the separate index but still avoids the German tank problem. But it gives you a new problem, namely a secret that's hard or impossible to rotate.
- cogman10 2y ago
  This is insecure. Assuming the user can get a few key examples (which, we assume they would be able to if the german tank problem is a problem) then the secret can easily be revealed. [1] [1] https://dev.to/wrongbyte/cryptography-basics-breaking-repeated-key-xor-ciphertext-1fm2 https://dev.to/wrongbyte/cryptography-basics-breaking-repeat...
- senderista 2y ago
  XOR isn't secure enough, but you're on the right track. Instead, use an actual block cipher.
WorldMaker 2y ago
A different approach to solve both 1 and 2 is timestamp-oriented IDs. You can get useful cache locality/less "index bloat"/fast initial inserts if your keys can be easily ordered in time. Sorted by timestamp means very similar behavior to B-Tree appends of a monotonic integer, even sometimes in the worst cases where "same moment" IDs aren't monotonic and rely more on random entropy. I got some great DB cache/index performance from ULIDs with a bit of work to order the ULID timestamp bits in the way the DB's 128-bit column "uuid" sort best supported. Now that UUIDv7 is standardized we should hopefully see good out-of-the-box collation for UUIDv7 in databases sooner rather than later.
- reissbaker 2y ago
  Yep, that works too as long as the timestamp data isn't sensitive.
senderista 2y ago
I don't understand why you need to maintain two separate keys: instead of generating a random key, why not just encrypt the auto-increment key using a secret key? This is the approach used by e.g. cloud providers that use auto-increment keys internally but don't want them to be guessable.
- cogman10 2y ago
  I think the biggest problem with this approach is it effectively pins you to a encryption key and algorithm (unless you embed some information in the key that lets you version the key, gotta think of that upfront). Imagine, for example, that you picked DES and "kangaroo" as the secret several years back. You are now pinned to an algorithm and key with known security problems and a weak key.
  - Too 2y ago
    Especially since you can try the encryption algorithm. Create 1000 users very quickly in a row and you now have 1000 samples of enc(i) all the way up to enc(i+1000) that can help you break the algorithm. Not saying it will be easy but it surely lowers the guarantees given by the encryption. Someone better at crypto can probably quantify this risk better than me.
- reissbaker 2y ago
  Sure, that works too. The upside of just storing a random string is you don't ever need to deal with secret management, key rotation, ciphers getting broken, etc — the random string truly has nothing to do with the real underlying ID, so there's just less work involved in hiding it. The downside is some extra bytes and index space.

echelon 2y ago

This is a great technical modification that can be made to work with "Stripe"-alike IDs or tokens. Another hack for advanced active-active situations where you may need to route events before replication completes: encoding the author shard / region in the lower order bytes. There are lots of interesting primary key hacks for dealing with physical or algorithmic complications.

jordanthoms 2y ago

This is dependent on the database you are using - if it's a key-sharded distributed database, you want to have insertions evenly spread across the key space in order to avoid having all the inserts go into a single shard (which could overload it)

cogman10 2y ago
This is the great thing about using random bits for the lower bits. Because you are unlikely to use more than say 2^64 database nodes, any sharding algorithm will have to figure out how to spread a key with 64 bits (or however many bits are in your key) across n nodes. Because of the random portion of the key, that means you'll get good distribution so long as the distribution algorithm isn't something stupid like relying solely on the highest order bits.

groestl 2y ago

> A problem with this approach is it's not monotonical Whether or not that's bad fully depends on your platform and the number of writes you do. If you're using a massively distributed database like Datastore, Spanner etc, you want random keys as to avoid hot spots for writes. They produce contention.

cogman10 2y ago
Well, you'd still likely want psuedo-random keys. You'd rather not have the underlying database doing extra work to shuffle around records as the pages get jumbled. One solution to that is having more complex keys. For example, in one of our more contentious tables the index includes an account id (32bit int) and then the id of the entity being inserted. This causes inserts for a given account to still be contiguous (resulting in less fragmentation) while not creating a writing hotspot since those writes are distributed across various clients.
- groestl 2y ago
  Not disagreeing. Point is, you need to know your domain, your technology, your write patterns, your downstream systems, etc to decide if a specific key scheme works to your advantage or not. All the more reason not to use natural keys, as they lock you in in that regard.
  - cogman10 2y ago
    Absolutely agree. I don't know how you can successfully maintain or develop software without developing an understanding of the underlying domain. I've seen devs try that route and the quality of their work has never been high.

hot_gril 2y ago

Depends heavily on what kind of database/index. Going with anything other than a random uuid4 adds complexity; for one, do you want to expose time info? I'd rather default to uuid4 as the client-exposed ID* and only change if there's a solid measured reason to. * not the same as your internal DB row primary keys, which in Postgres should usually be bigserial

cogman10 2y ago
Yes but also no. Yes, in that there are DB technologies not built in a fashion where records are stored in a sorted order of some fashion. No, in that they are very much not common technologies. Most databases, relational, non-relational, etc have some form of a B-Tree at their core somewhere.
- hot_gril 2y ago
  I can see this. Spanner is an example where you don't want this, idk if that's considered common enough. Postgres and MySQL both support hash indexes that are unordered, but the default in both is btree, and Postgres hash indexes used to have some caveats that made them unsuitable (idk about now) so I've gotten in the habit of just using the default. MySQL docs claim that a hash index is much faster if you only need kv lookups, so it seems like uuid4 with hash index would be suitable. Never tried it though, and can't say whether it's faster than using a btree with uuid7. Seems like in theory it would be.
  - cogman10 2y ago
    As always, depends on the implementation. Hash maps should generally always have faster lookups than Btree based structures. However, they'll have slower writes especially when contested. A key issue hash tables have to deal with is what happens when a remapping needs to happen. For example, when 2 keys have the same hash. In that case, locking becomes a lot more messy. For a btree this is simpler. It's built to be able to handle reshuffling and rebalancing in a way that's semi easy to have fine grained locks around.