27 December 2011

Уникальный ключ в условиях распределенной БД

Website development
В случае если вы разделяете данные по нескольким физическим базам данных,
поддержка глобально-уникальных идентификаторов становится не такой уж тривиальной задачей.
Я попытался собрать вместе возможные варианты и рассмотреть их плюсы и минусы.


Какие требования (кроме уникальности) могут предъявляться к ключам?



Ключ должен монотонно увеличиваться
Зачем это нужно:
  • Автоматическая естественная сортировка (в том числе хронологическая)
  • Быстрее вставка, чем при случайных ключах

Вышесказанное актуально только для индексов с использованием деревьев.

Ключ должен формироваться на стороне клиента
Зачем это нужно:
  • Приложение может сразу обратиться на нужный шард (узел кластера), поскольку уникальный ключ известен еще до сохранения объекта
  • Приложение может сохранять несколько связанных объектов сразу (в одной транзакции или пакетном задании)


Ограничение по размеру ключа (например, только 64 бита)
Зачем это нужно:
  • В некоторых случаях 128- или 160-битные идентификаторы могут быть проблемой. Например, Sphinx search поддерживает только целочисленные идентификаторы документов (64 бита в 64-битной версии).
  • Индекс с 32- или 64-битными ключами теоретически должен работать быстрее, чем с ключами произвольной длины.
  • Индекс с 32- или 64-битными ключами компактнее и, в результате, целиком помещается в память (актуально для больших объемов данных).


Какие существуют способы генерации уникальных ключей?



Генерация ID на стороне приложения (UUID и т.п.)

С UUID все относительно просто — берем библиотеку и генерируем ключи на стороне приложения. UUID широко используется во многих системах. Значение формируется таким образом, что коллизии невозможны.

Минусы:
    • Длина стандартного UUID 128 бит (которые, на самом деле, часто хочется хранить прямо в виде строки шестнадцатеричных цифр, а это уже 32 байта)
    • Как правило, UUID не дает естественной сортировки ключей

Отдельный сервис, для генерации ключей

Такой вариант используют, например, Flick и Twitter.

Минусы:
    • усложнение системы из-за введения дополнительных компонентов
    • потенциально единая точка сбоя, либо требуются дополнительные усилия, чтобы обеспечить высокую доступность генератора ключей

Автоинкремент на стороне базы данных по диапазонам значений

Весь диапазон значений делится на поддиапазоны и каждый шард (узел кластера) отвечает за свой диапазон, например:
    1 - 0        .. 3FFFFFFF,
    2 - 40000000 .. 7FFFFFFF,
    3 - 80000000 .. BFFFFFFF,
    4 - C0000000 .. FFFFFFFF

Минусы:
    • БД должна поддерживать автоинкремент (не применимо для многих NoSQL-хранилищ)
естественная сортировка невозможна
    • Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.
    • Практически невозможно увеличить количество узлов кластера

Aвтоинкремент от Instagram

Об этом решении рассказано в техническом блоге команды Instgram (photo sharing application).

Они используют 64-битный ключ, который формируется на стороне БД (PostgreSQL) и состоит из битовых полей

63                          31                          0
|======|======|======|======|======|======|======|======|
|        CUSTOM TIMESTAMP          | SHARD ID  |  AUTO  |

где
CUSTOM TIMESTAMP (41 бита) — время в миллисекундах от 2011-01-01 00:00:00
SHARD ID (13 бит) — идентификатор логического раздела (число шардов больше, чем число физических узлов)
AUTO (10 бит) — последовательность (sequence), уникальная в пределах логического раздела (шарда)

Плюсы (по сравнению с автоинкрементом по диапазонам):
    • Автоматическая хронологическая сортировка

А вы какие варианты знаете и используете?
Tags: autoincrement uuid sql nosql primary key unique key
Hubs: Website development
+50
24.5k 193
Comments 86
Ads