Как разбить папки с цифровыми именами в иерархию?

Рейтинг: 0Ответов: 1Опубликовано: 10.04.2015

Данные хранятся в файлах в папках с цифровыми именами, соотв. id объектов. Диапазон чисел от 1 до 3e9. Ещё и со знаком. Сейчас отрицательные и положительные живут отдельно: plus/1234455/ и minus/123456.

Операции сводятся к тому, что есть id, и надо определить, в какой папке лежат его файлы (и на каком сервере, в случае шардинга).

Хочется равномерно разбить их в иерархическую структуру 1-2-3 уровней вложенности, чтобы уменьшить число объектов в одной папке, и с прицелом на как-бы-шардинг.

Стоит ли делать это просто по первым цифрам, или есть более удачный подход?

12/        -> 1/2/
123/       -> 1/2/3/
123456789/ -> 1/2/3456789/

Так получается, что «короткие» папки будут содержать как собственные данные, так и подпапки. Некруто.

Кто знаком с изнанкой всяких MongoDB – как там похожая задача решается?

nosql структуры-данных
Источник: Stack Overflow на русском

Ответы

▲ 1

Собственно для файлов с короткими именами можно сделать отдельный каталог, чтобы они лежали не вместе с подкаталогами длинных имён. Например:

  1  ->  1/_/
  12 ->  1/2/_/
  123 -> 1/2/3/

Или же можно просто дополнить числа нулями слева до длины максимального числа, в этом случае все имена будут одинаковой длины:

   001 -> 0/0/1/
   012 -> 0/1/2/
   123 -> 1/2/3/

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

В этом случае нужно проводить хэширование имени, которое сделает распределение действительно равномерным.

Если есть высокие требования, то стоит использовать производительные хэши, такие как xxhash, например. Он не является криптографическим, но в данном случае это и не нужно.

Скорость различных алгоритмов/реализаций хэширования (64-битные варианты ещё значительно быстрее):

Name            Speed       Q.Score   Author
xxHash          5.4 GB/s     10
MumurHash 3a    2.7 GB/s     10       Austin Appleby
SpookyHash      2.0 GB/s     10       Bob Jenkins
SBox            1.4 GB/s      9       Bret Mulvey
Lookup3         1.2 GB/s      9       Bob Jenkins
CityHash64      1.05 GB/s    10       Pike & Alakuijala
FNV             0.55 GB/s     5       Fowler, Noll, Vo
CRC32           0.43 GB/s     9
MD5-32          0.33 GB/s    10       Ronald L. Rivest
SHA1-32         0.28 GB/s    10

В том случае, если вероятность, что в будущем нужно будет менять распределение имен между узлами (каталогами) или распределение должно быть не равномерно, а на какие-то узлы должно приходиться большее количество имен, можно рассмотреть использование консистентного хэширования (consistent hashing). Оно используется в Cassandra, в Riak, и много ещё где.