UUID на основе времени не следует порядку создания согласно реализации RFC 4122 - PullRequest
Новая
       26

UUID на основе времени не следует порядку создания согласно реализации RFC 4122

0 голосов
/ 30 октября 2018

Я создаю собственный алгоритм для встраивания информации в timeUUID . При изучении RFC 4122 . В спецификации UUID версии 1 имеет следующую структуру: 

 0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                          time_low                             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |       time_mid                |         time_hi_and_version   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                         node (2-5)                            |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Я обнаружил, что нижняя часть метки времени (крайняя справа 32 бита) идет перед идентификатором, что делает ее наиболее важной частью при сортировке UUID. Что я не понимаю, так это , как эта спецификация работает таким образом, что при сортировке UUID сортировка будет следовать порядку создания .

Чтобы проиллюстрировать вопрос, найдите два примера здесь, где временная метка t1> t2, но созданный UUID с этой временной меткой будет в обратном порядке. 

 t1 = 137601405637595834 // 0x1e8dbbfd79f92ba
 t2 = 3617559227 // 0xd79f92bb

преобразуются в следующие части 

 t1_low: Uint = 3617559226 // 0xd79f92ba
 t1_mid: Ushort = 56255 // 0xdbbf
 t1_hi: Ushort = 1e8 // 0x1e8

 t2_low: Uint = 3617559226 // 0xd79f92bb
 t2_mid: Ushort = 0 // 0x0
 t2_hi: Ushort = 0 // 0x0

Поскольку в этом случае младшие значащие байты не относятся к порядку, я буду игнорировать это для упрощения.

UUID, сгенерированные с использованием этих временных меток, равны 

 UUID1 = d79f92ba-dbbf-11e8-8808-000000000002
 UUID2 = d79f92bb-0000-1000-a68b-000000000004

Очевидно, что UUID1

Что не так в моем анализе?

1 Ответ

0 голосов
/ 04 ноября 2018

Спецификация UUIDv1 преднамеренно помещает наибольшую энтропию в старшие биты, чтобы ключи делали не сортировку, как вы ожидали; вместо этого они будут казаться случайными, но примерно равномерно распределенными по всему диапазону номеров независимо от порядка создания - точно так же, как UUIDv3 / v4 / v5.

Если вам нужна сортируемая временная метка, добавьте еще один столбец; использование UUID в качестве чего-либо, кроме непрозрачного идентификатора, приведет к тому, что вы будете кусаться позже.

...