Распределенная генерация порядковых номеров?

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

например, используя тип Postgres SERIAL http://www.neilconway.org/docs/sequences/

Мне любопытно, как сгенерировать порядковые номера для больших распределенных систем, где нет базы данных. Есть ли у кого-нибудь опыт или предложения по лучшему способу создания порядкового номера потокобезопасным способом для нескольких клиентов?

Хорошо, это очень старый вопрос, который я впервые вижу сейчас.

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

Уникальные идентификаторы - другое дело, есть несколько хороших способов децентрализованно генерировать уникальные идентификаторы:

а) Вы можете использовать сетевой сервис Twitter Snowflake ID . Снежинка - это:

• Сетевая услуга, т. Е. Вы совершаете сетевой вызов, чтобы получить уникальный идентификатор;
• который производит 64-битные уникальные идентификаторы, упорядоченные по времени генерации;
• и сервис хорошо масштабируется и (потенциально) высокодоступен; каждый экземпляр может генерировать много тысяч идентификаторов в секунду, и вы можете запускать несколько экземпляров в своей LAN / WAN;
• написан на Scala, работает на JVM.

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

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

• Следующие 14 или около того битов: счетчик для каждого генератора , который каждый генератор увеличивает на единицу для каждого нового сгенерированного идентификатора. Это гарантирует, что идентификаторы, сгенерированные в один и тот же момент (одинаковые временные метки), не перекрываются.

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

c) Вы можете генерировать идентификаторы клиентов, используя только временную метку и случайное значение. Это позволяет избежать необходимости знать все генераторы и назначать каждому генератору уникальное значение. С другой стороны, не гарантируется , что такие идентификаторы будут глобально уникальными, они будут уникальными только с большой вероятностью . (Чтобы столкнуться, один или несколько генераторов должны будут создать одно и то же случайное значение в одно и то же время.) Что-то вроде:

• Старшие 32 бита: отметка времени, время генерации идентификатора.
• Наименее значимые 32 бита: 32 бита случайности, генерируемые заново для каждого идентификатора.

г) Самый простой выход - использовать UUID / GUID .

Теперь есть еще варианты.

Хотя этот вопрос «старый», я попал сюда, поэтому я думаю, что было бы полезно оставить варианты, о которых я знаю (пока):

• Вы можете попробовать Hazelcast . В версии 1.9 он включает распределенную реализацию java.util.concurrent.AtomicLong
• Вы также можете использовать Zookeeper . Он предоставляет методы для создания узлов последовательности (добавляются к именам znode, хотя я предпочитаю использовать номера версий узлов). Однако будьте осторожны с этим: если вы не хотите, чтобы в вашей последовательности пропущены числа, возможно, это не то, что вам нужно.

Ура

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

Например, узел 1 генерирует последовательность 001-00001 001-00002 001-00003 и т. Д., А узел 5 генерирует 005-00001 005-00002.

Уникальный :-)

В качестве альтернативы, если вам нужна какая-то централизованная система, вы можете подумать о том, чтобы ваш сервер последовательностей выдавался блоками. Это значительно снижает накладные расходы. Например, вместо того, чтобы запрашивать новый идентификатор с центрального сервера для каждого идентификатора, который должен быть назначен, вы запрашиваете идентификаторы блоками по 10 000 с центрального сервера, а затем вам нужно выполнить еще один сетевой запрос, когда они закончатся.

Это можно сделать с помощью Redisson . Он реализует распределенную и масштабируемую версию AtomicLong. Вот пример:

Config config = new Config();
config.addAddress("some.server.com:8291");

Redisson redisson = Redisson.create(config);
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong");
atomicLong.incrementAndGet();

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

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

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

1. есть центральный генератор чисел. это не обязательно должна быть большая база данных. memcachedимеет быстрый атомный счетчик, в подавляющем большинстве случаев его достаточно для всего кластера.
2. разделите целочисленный диапазон для каждого узла (например , ответ Стивена Шлансктера )
3. использовать случайные числа или UUID
4. использовать часть данных вместе с идентификатором узла и хешировать все это (или hmac )

лично я бы склонился к UUID или memcached, если я хочу иметь в основном непрерывное пространство.

Почему бы не использовать (потокобезопасный) генератор UUID?

Я, наверное, должен подробнее остановиться на этом.

Гарантируется, что идентификаторы UUID будут глобально уникальными (если вы избегаете идентификаторов, основанных на случайных числах, где уникальность весьма вероятна).

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

Ваше требование «потокобезопасности» можно удовлетворить, выбрав «потокобезопасные» генераторы UUID.

Предполагается, что ваше требование «порядкового номера» удовлетворяется за счет гарантированной глобальной уникальности каждого UUID.

Обратите внимание, что многие реализации порядковых номеров баз данных (например, Oracle) не гарантируют ни монотонно возрастающих, ни (даже) возрастающих порядковых номеров (для каждого «соединения»). Это связано с тем, что последовательный пакет порядковых номеров выделяется в «кэшированных» блоках для каждого соединения. Это гарантирует глобальную уникальность и поддерживает адекватную скорость. Но фактически назначенные порядковые номера (с течением времени) могут быть беспорядочными, когда они выделяются несколькими соединениями!

Генерацию распределенного идентификатора можно заархивировать с помощью Redis и Lua. Реализация доступна на Github . Он производит распределенные и k-сортируемые уникальные идентификаторы.

Я знаю, что это старый вопрос, но мы также столкнулись с той же проблемой и не смогли найти решение, которое удовлетворяет наши потребности. Наше требование состояло в том, чтобы получить уникальную последовательность (0,1,2,3 ... n) идентификаторов, поэтому снежинка не помогла. Мы создали нашу собственную систему для генерации идентификаторов с помощью Redis. Redis является однопоточным, поэтому его механизм списка / очереди всегда будет выдавать нам по одному запросу за раз.

Что мы делаем: мы создаем буфер идентификаторов. Первоначально в очереди будет от 0 до 20 идентификаторов, которые готовы к отправке по запросу. Несколько клиентов могут запрашивать идентификатор, и redis будет выдавать по одному идентификатору за раз. После каждого всплывающего сообщения слева мы вставляем BUFFER + currentId справа, что поддерживает список буферов. Реализация здесь

Я написал простой сервис, который может генерировать полууникальные непоследовательные 64-битные числа. Его можно развернуть на нескольких машинах для обеспечения избыточности и масштабируемости. Он использует ZeroMQ для обмена сообщениями. Для получения дополнительной информации о том, как это работает, посмотрите страницу github: zUID

Используя базу данных, вы можете достичь более 1000 приращений в секунду с одним ядром. Это довольно просто. Вы можете использовать его собственную базу данных в качестве бэкэнда для генерации этого числа (поскольку это должен быть его собственный агрегат в терминах DDD).

У меня была похожая проблема. У меня было несколько разделов, и я хотел получить счетчик смещения для каждого из них. Я реализовал что-то вроде этого:

CREATE DATABASE example;
USE example;
CREATE TABLE offsets (partition INTEGER, offset LONG, PRIMARY KEY (partition));
INSERT offsets VALUES (1,0);

Затем выполнил следующий оператор:

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE;
UPDATE offsets set offset=@offset+1 WHERE partition=1;

Если ваше приложение позволяет, вы можете выделить блок сразу (в моем случае).

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE;
UPDATE offsets set offset=@offset+100 WHERE partition=1;

Если вам нужна дополнительная пропускная способность и вы не можете заранее выделить смещения, вы можете реализовать свой собственный сервис, используя Flink для обработки в реальном времени. Я смог получить около 100 КБ на раздел.

Надеюсь, поможет!

Проблема похожа на: В мире iscsi, где каждый lun / volume должен быть однозначно идентифицирован инициаторами, работающими на стороне клиента. Стандарт iscsi гласит, что первые несколько битов должны представлять информацию о поставщике / производителе хранилища, а остальные монотонно увеличиваются.

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

Одно из достойных решений - использовать генерацию на основе длительного времени. Это можно сделать с помощью распределенной базы данных.