3 ms·

This is quite an interesting point. In data engineering, compression is a key goal -- yet random identifiers are often used. Part of the reason is, presumably,

This is quite an interesting point. In data engineering, compression is a key goal -- yet random identifiers are often used. Part of the reason is, presumably, that over a distributed system it's hard to coordinate choosing a deterministic globally unique identifier without a performance cost. Does any one have any thoughts on implementing a globally unique identifier in a compressible/deterministic way? My initial guess is choose some low-collision probability random part, and then glue on timestamp?

drran 5y ago
Assign pool of ID's to servers in blocks, e.g. 0..9999, 10000..19999. Then, when ID block is near to exhaustion, ask for new one.
- derekperkins 5y ago
  That's pretty close to how Vitess handles sequences (distributed auto-increment)
thanksforfish 5y ago
Snowflake IDs may compress well. https://en.m.wikipedia.org/wiki/Snowflake_ID https://en.m.wikipedia.org/wiki/Snowflake_ID
smitty1e 5y ago
The first comment on the article referenced this article on slightly un-unique identifiers => https://news.ycombinator.com/item?id=28088213 https://news.ycombinator.com/item?id=28088213
edflsafoiewq 5y ago
Twitter uses timestamp + machine ID + sequence number. https://en.wikipedia.org/wiki/Snowflake_ID https://en.wikipedia.org/wiki/Snowflake_ID
willis936 5y ago
Computer index (top 32 bits) + entry index (bottom 32 bits) Adding more things such as time stamp just adds entropy without being useful. The indexes should start at 0 and count up. The computer index is something that should be handed out once every time a computer is brought in.
- mjburgess 5y ago
  > " First, most of the existing UUID versions such as UUIDv4 have poor database index locality. Meaning new values created in succession are not close to each other in the index and thus require inserts to be performed at random locations. The negative performance effects of which on common structures used for this (B-tree and its variants) can be dramatic. As such newly inserted values SHOULD be time-ordered to address this." -- https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...
  - willis936 5y ago
    Then why not map timestamps into a chronological index either on-the-fly or some time later?
bbirk 5y ago
Snowflake has been mentioned here, there is another way to achieve this although I've never seen it used in practice. Imagine, in the DBMS the identifier column would be sequential, but whenever the rows are queried, the identifiers are ran through AES. The server would have a single AES key that is used throughout it's lifetime. To the user the identifiers would seemingly be random, but on the server side they are sequential and thus highly compressible. In addition, when querying the rows and putting a condition on the identifier column, AES decryption would have to be used. For example "select user_id, first_name from user where user_id = 6744073709551615;" would decrypt 6744073709551615 into the sequential number, like 103 (if it's the number 103' inserted row), and then use 103 to query the table. There would certainly be a performance overhead when returning large result sets where lots of identifiers need to be encrypted. On the other hand, modern cpus have specific AES instructions which are really fast, and in addition, when the identifiers are compressed to something like 1.5 bits on average, you can fit a lot more in the cpu cache which may offset some or even all of the performance loss. If you have only a single master DBMS server, then 64-bit integers should be sufficient when using this strategy. Otherwise, if you are using multi-master in a distributed environment, you could achieve lock/communication-free identifier generation by instead using a 128 bit integer and for example include the server identifier inside those 128 bits, similarly to snowflake, before encrypting it and exposing it to the user. Side note, since the identifiers are sequential there is anther benefit in that, like snowflake, when you order by (created_date, user_id), it wouldn't incur any performance cost over just ordering by user_id. If anyone knows anyone who uses this or why it would be a bad idea I would love to know.

drran 5y ago

Assign pool of ID's to servers in blocks, e.g. 0..9999, 10000..19999. Then, when ID block is near to exhaustion, ask for new one.

derekperkins 5y ago
That's pretty close to how Vitess handles sequences (distributed auto-increment)

thanksforfish 5y ago

Snowflake IDs may compress well. https://en.m.wikipedia.org/wiki/Snowflake_ID https://en.m.wikipedia.org/wiki/Snowflake_ID

smitty1e 5y ago

The first comment on the article referenced this article on slightly un-unique identifiers => https://news.ycombinator.com/item?id=28088213 https://news.ycombinator.com/item?id=28088213

edflsafoiewq 5y ago

Twitter uses timestamp + machine ID + sequence number. https://en.wikipedia.org/wiki/Snowflake_ID https://en.wikipedia.org/wiki/Snowflake_ID

willis936 5y ago

Computer index (top 32 bits) + entry index (bottom 32 bits) Adding more things such as time stamp just adds entropy without being useful. The indexes should start at 0 and count up. The computer index is something that should be handed out once every time a computer is brought in.

mjburgess 5y ago
> " First, most of the existing UUID versions such as UUIDv4 have poor database index locality. Meaning new values created in succession are not close to each other in the index and thus require inserts to be performed at random locations. The negative performance effects of which on common structures used for this (B-tree and its variants) can be dramatic. As such newly inserted values SHOULD be time-ordered to address this." -- https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...
- willis936 5y ago
  Then why not map timestamps into a chronological index either on-the-fly or some time later?

bbirk 5y ago

Snowflake has been mentioned here, there is another way to achieve this although I've never seen it used in practice. Imagine, in the DBMS the identifier column would be sequential, but whenever the rows are queried, the identifiers are ran through AES. The server would have a single AES key that is used throughout it's lifetime. To the user the identifiers would seemingly be random, but on the server side they are sequential and thus highly compressible. In addition, when querying the rows and putting a condition on the identifier column, AES decryption would have to be used. For example "select user_id, first_name from user where user_id = 6744073709551615;" would decrypt 6744073709551615 into the sequential number, like 103 (if it's the number 103' inserted row), and then use 103 to query the table. There would certainly be a performance overhead when returning large result sets where lots of identifiers need to be encrypted. On the other hand, modern cpus have specific AES instructions which are really fast, and in addition, when the identifiers are compressed to something like 1.5 bits on average, you can fit a lot more in the cpu cache which may offset some or even all of the performance loss. If you have only a single master DBMS server, then 64-bit integers should be sufficient when using this strategy. Otherwise, if you are using multi-master in a distributed environment, you could achieve lock/communication-free identifier generation by instead using a 128 bit integer and for example include the server identifier inside those 128 bits, similarly to snowflake, before encrypting it and exposing it to the user. Side note, since the identifiers are sequential there is anther benefit in that, like snowflake, when you order by (created_date, user_id), it wouldn't incur any performance cost over just ordering by user_id. If anyone knows anyone who uses this or why it would be a bad idea I would love to know.