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

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

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

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

Очевидно, это - идеализированная спецификация, и не все ограничения может быть удовлетворен полностью. Посмотрите Теорему ОГРАНИЧЕНИЯ. Однако я хотел бы услышать Ваш анализ различной релаксации ограничений. Какие проблемы будут, мы уехали с и что алгоритмы будут мы использовать для решения остающихся проблем. Например, если мы избавляем от встречного ограничения, затем проблема становится намного легче: так как разрывы позволяются, мы можем просто разделить числовые диапазоны и отобразить их на различные машины.

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

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

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