main

Трудности выбора - 2

Бывают моменты, когда твоё внимание фиксируется на какой-то незначительной вещи и стопорит весь процесс. В этот раз в фокус внимания попал алгоритм генерации uuid'ов для файлов.

Вариант "отвлечься" - в моём случае не помогает. Попробуйю изложить в текстовом виде, авось голова прояснится.

Итак, требования к идентификатору:

  • количество - должно работать на 2^32, без значительной просадки производительности при генерации и работе с ними.
  • длина - естественно, как можно меньше
  • сводимость к bigint
  • возможность его запомнить

В принципе всё это стандартно и наиболее разумным вариантом напрашивается bigint с возможным представлением в hex-записи.

Далее, возможные способы генерации:

  • простой счётчик
  • генерация uuid на основе свойств файла и его содержимого
  • полностью берём нужное число байт из /dev/random'а и представляем unsigned int'ом
  • комбинации предыдущих вариантов

Разберу по пунктам:

  • Достоинств - масса, например автоинкремент нас полностью избавляет от необходимости продумывать алгоритм генерации с минимальным количеством коллизий. Минимальный размер идентификатора из всех возможных. Недостаток - при переносе между машинами - потребуется менять идентификаторы у всех или части файлов 1.
  • Достоинства - практически халявная дедупликация при использовании чексумм для всего файла или его части. Недостатки - ресурсоёмкость, в случае частичных чексумм - ложные срабатывания (на некоторых наборах файлов, возможно - массовые)
  • Достоинства - простота генерации, не зависит ни от чего вообще. Но нужен достаточно длинный идентификатор, для минимизации числа коллизий.
  • По сравнению с двумя предыдущими - нет ни одного из их достоинств, зато есть все их недостатки.

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


  1. именно на это я напоролся при выпуске версии 0.2 ↩