3 ms·

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 fo

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.

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.