[5z7k9]

**Mireczki, jak generujecie ID(nie chodzi o auto_increment) w bazach NoSQL/rozproszonych bazach danych? ( ͡° ͜ʖ ͡°)**

Podoba mi się Twitter Snowflake(Scala, ale jest wiele implementacji, nawet w PHP): https://github.com/twitter/snowflake/tree/scala_28

Przykładowe ID: 532260564940881920

epoch = 1325376000000 // unsigned long, any timestamp before now, in milliseconds
timestamp = unixTimestamp - epoch // unsigned long, unixTimestamp - current timestamp in milliseconds
machineld = 0 // unsigned short, 0-1023
sequence = 0 // unsigned short, 0-4095, incremented for each timestamp => ID

id = (timestamp << 22)
...... | (machineId << 12)
...... | sequence

Mały przykład dla PHP-owców(działa na 32 bitach z bc_*): http://ideone.com/n8Aa77#li_n8Aa77

- prawdopodobieństwo kolizji bliskie zeru, a przy zastosowaniu oddzielnej usługi(tak jak to się powinno robić) która generuje ID prawdopodobieństwo wynosi 0%,
- wysoka wydajność(Twitter potrzebował 10,000 ID/sekundę i nawet nie wiem czy Scala podołała),
- małe ID - 64 bity(UUID pls!),
- 2^41/1000/60/60/24/365 = ID generowane bez przerwy przez 69 lat,
- możliwość sortowania(każde kolejne ID na pewno będzie większe od poprzedniego),
- złożone tylko z cyfr(według mnie ładnie wygląda, przede wszystkim w linkach, np. jako ID postu),
- ukrywają ilość rekordów w bazie(jeżeli ktoś tego potrzebuje...).

#programowanie #cpp #scala #go #php #algorytmy

[ritter]

UUIDa w wersji 4 zawsze generuję. Nigdy nie doświadczyłem kolizji.

[dupasmoka]

epoch jest const?

[5z7k9]

@dupasmoka: może być, nie ma problemu.

[dupasmoka]

@5z7k9: Bo jak epoch nie jest const to

możliwość sortowania(każde kolejne ID na pewno będzie większe od poprzedniego),

wydaje mi się, że nie jest prawdą.

[5z7k9]

@ritter: ale UUID nie ma wielu z tych zalet: nie jest k-sortable, jest 128-bitowy, nie za bardzo URL friendly, przypuszczam że generowanie UUID jest też mniej wydajne.

[5z7k9]

@dupasmoka: da się sortować(tak, epoch jest zawsze niezmienne, jeżeli o to pytasz), zobacz sobie mój przykład z PHP(jest napisany na maszynę 32-bitową, więc jest dłuższy), tam jest stdout z wykonania skryptu. Zobaczysz, że każde kolejne ID jest większe.

[5z7k9]

@dupasmoka: "każde kolejne", czyli możesz sortować np. od największego ID do najmniejszego i otrzymasz rekordy według "daty" dodania. Oczywiście nie miałem na myśli, że każde kolejne ID jest większe o 1, wtedy to by był auto_increment.

[dupasmoka]

@5z7k9: No to w końcu epoch nie jest stałe, może być stałe, czy musi być stałe?

[5z7k9]

@dupasmoka: TAK, MA BYĆ STAŁE