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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

d) Простой выход, использовать UUID / GUID .

Answer 2

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

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

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

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

Answer 3

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

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

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

Приветствия

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Вероятно, мне следует остановиться на этом.

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

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

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

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

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

Answer 8

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

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

Answer 9

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

Answer 10

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