coxx Dec 27 2011 at 14:53

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

3 min

33K

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

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

Ключ должен монотонно увеличиваться
Зачем это нужно:

Автоматическая естественная сортировка (в том числе хронологическая)
Быстрее вставка, чем при случайных ключах

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

Ключ должен формироваться на стороне клиента
Зачем это нужно:

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

Ограничение по размеру ключа (например, только 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:

Hubs:

Website development