Каковы компромиссы при создании уникальных порядковых номеров в распределенной и параллельной среде?

Question

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

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

• Оставайтесь под высокой нагрузкой.
• Разрешить как можно больше одновременных подключений.
• Распределено: распределена нагрузка на несколько машин.
• Производительность: работайте с максимальной скоростью и максимально возможной пропускной способностью.
• Правильность: сгенерированные числа должны:
  1. не повторяется.
  2. быть уникальным для каждого запроса (должен иметь способ разрыва связей, если любые два запроса происходят в одно и то же время).
  3. в (возрастающем) последовательном порядке.
  4. нет пробелов между запросами: 1,2,3,4 ... (фактически счетчик для общего количества # запросов)
• Отказоустойчивость: если один или несколько или все машины вышли из строя, он может вернуться в состояние до сбоя.

Очевидно, что это идеализированная спецификация, и не все ограничения могут быть полностью выполнены. См. CAP Теорема . Тем не менее, я хотел бы услышать ваш анализ о различных ослаблениях ограничений. Какие проблемы мы оставим и какие алгоритмы будем использовать для решения оставшихся проблем. Например, если мы избавимся от ограничения счетчика, тогда проблема станет намного проще: поскольку пропуски разрешены, мы можем просто разбить числовые диапазоны и отобразить их на разных машинах.

Любые ссылки (документы, книги, код) приветствуются. Я также хотел бы сохранить список существующего программного обеспечения (с открытым исходным кодом или нет).

---

Программное обеспечение

• Снежинка : сетевой сервис для генерации уникальных идентификационных номеров в большом масштабе с некоторыми простыми гарантиями.
• пространство ключей : общедоступный, уникальный генератор 128-битных идентификаторов, чьи идентификаторы могут использоваться для любых целей
• Реализации RFC-4122 существуют на многих языках . Спецификация RFC, вероятно, является действительно хорошей основой, поскольку она предотвращает необходимость какой-либо межсистемной координации, UUID являются 128-битными, а при использовании идентификаторов из программного обеспечения, реализующего определенные версии спецификации, они включают часть временного кода, которая возможна сортировка и т. д.

Answer 1

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

Если вы можете допустить наличие двух порядковых номеров - логическийнемедленно вернулся;гарантированно уникальные и упорядоченные, но с пробелами - и отдельный физический, гарантированный в последовательном порядке, без пробелов и доступный через некоторое время - тогда решение кажется простым:

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

Отображение из логического в физическое может произойти по требованию, как только вторая система завершит обработку.

Answer 2

Если вы должны быть последовательными (для каждой машины), но можете отбросить требования к разрыву / счетчику, ищите реализацию UUID версии 1, как указано в RFC 4122 .

Если вы работаете в .NET и можете устранить требования к последовательным и пропускам / счетчикам, просто используйте System.Guid s. Они реализуют RFC 4122 версии 4 и уже являются уникальными (с очень низкой вероятностью коллизий) для машин и запросов. Это может быть легко реализовано как веб-сервис или просто использовано локально.