Способы генерации примерно последовательных идентификаторов (32-битные и 64-битные размеры) в распределенном приложении

Question

Каковы хорошие способы для генерации уникальных "приблизительно" последовательных идентификаторов (32-битные и 64-битные размеры) в распределенном приложении ?

[Примечание: моя БД не предоставляет эту возможность.] Также я не хочу, чтобы использовал 128-битные UUID.

РЕДАКТИРОВАТЬ: Спасибо всем за ваш ответ!
Поскольку некоторые из вас предлагают использовать Mysql db как серверы билетов flickr, я сомневаюсь, что использование нескольких серверов (для устранения единой точки отказа) может нарушить некоторую последовательную природу генерируемых идентификаторов, поскольку некоторые серверы могут отставать от других. Хотя у меня все в порядке с отставанием нескольких Id-последовательностей, но я не могу допустить огромных нарушений в последовательности.

Answer 1

Основываясь на идее @Chris о наличии таблицы для генерирования «следующей» идентичности. Более надежный способ сделать это состоит в том, чтобы иметь два сервера и круговой балансировщик нагрузки. Сервер 1 распределяет нечетные числа, Сервер 2 распределяет четные числа. Если вы потеряете один сервер, вы получите все шансы или все четные, но шоу все еще продолжается.

Flickr использует нечто очень похожее для своей системы идентификации

http://code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

Затем творчески используйте атомарный синтаксис MYSQL REPLACE, как показано ниже:

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

Там, где значение заглушки достаточно для генерации следующего идентификатора атомарным способом.

Обновление с требованиями к хронологии и последовательности операций OP

С помощью Chronology в качестве драйвера ваш выбор меняет буквально - атомарное состояние в SPOF - например, идея Криса в SQL. Это будет узким местом, и его состояние должно быть долговечным, чтобы избежать выдачи дубликатов.

Чтобы достичь хронологии в масштабе с высокой доступностью в распределенной системе, алгоритмы причинно-следственной последовательности - в значительной степени единственный путь - есть несколько:

• метки времени Lamport
• Векторные часы
• Последовательности зависимостей
• Иерархические часы

Шаблон вызова совершенно отличается от стратегии SPOF, он требует, чтобы вы отслеживали и передавали памятку последовательности, метки времени или версии - фактически информацию сеанса для последовательности, которую вы генерируете. Однако они гарантируют причинный порядок для любой заданной последовательности или элемента даже в распределенной системе. В большинстве случаев событие PK будет составной частью идентификатора элемента + идентификатора причинной последовательности.

Answer 2

Поскольку у вас есть база данных, вы можете создать таблицу со значением next . Получение этого значения потребует от вас выбора значения и обновления строки новым следующим значением, где строка имела старое значение, если обновление не затрагивает какие-либо строки, тогда какой-то другой процесс или поток смог получить значение до того, как вы и вам нужно повторить попытку получить следующее значение.

Псевдокод для этого будет выглядеть примерно так

do
  select nextvalue into MyValue from SequenceTable
  update SequenceTable set nextvalue= nextvalue + 1 where nextvalue = MyValue
while rowsaffected = 0

В приведенном выше примере MyValue - это переменная, которая будет содержать nextvalue из таблицы базы данных SequenceTable, а rowsaffected - это показатель, указывающий, сколько строк затронуто последним оператором SQL, который в case является оператором обновления.