Распределенный уникальный идентификатор простыми словами

распределенный

Зачем нужны распределенные уникальные идентификаторы

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

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

Требования к распределенным уникальным идентификаторам

Требования распределенного уникального идентификатора можно разбить на три уровня:

  1. Не повторяя. Он не требует случайности в природе, а также возможны простые приращения, потому что нет необходимости избегать угадывания. Во многих случаях вместо неповторения используется случайность (случайный алгоритм достаточно хорош, а пул достаточно велик, чтобы в значительной степени избежать коллизий).
  2. Уточнение не повторяет этого требования к однозначности во времени и уникальности в пространстве. Если текущая метка времени просто используется как начальное число, генератор псевдослучайных чисел может получить один и тот же результат в одно и то же время и на разных машинах (причины описаны ниже).
  3. Существует также неявное требование, согласно которому упорядоченный распределенный уникальный идентификатор должен использоваться в качестве столбца индекса, который часто запрашивается. Основным принципом индекса базы данных является дерево B+, которое представляет собой двоичное дерево поиска с большим количеством дочерних узлов, поэтому его необходимо упорядочивать, желательно чистыми числами, что позволяет избежать использования преобразования набора символов при сортировке типов символов.

Истинно случайные и псевдослучайные решения на уровне системы и языка

По сути, ни одно из вычисляемых чисел не является случайным числом. "Настоящая" случайность согласуется со случайностью физического мира. Она исходит из физических движений, таких как атмосферное движение и молекулярное тепловое движение, и мы не можем найти точные законы для предсказания следующего значения в физическом мире. Что касается того, случайны они или нет, то это поднялось на другой уровень, насколько мы понимаем, они действительно случайны. «Псевдо» случайное псевдо может быть вычислено в следующем значении, но правила более сложны и не могут быть рассчитаны, не зная точного «начального числа».

Поскольку он рассчитывается, должна быть формула.Каковы требования этой формулы?

  1. Рассчитывается как рандом, результат должен быть очень сбалансированным, не должно быть чрезмерного соотношения определенных значений.
  2. Это не может быть слишком сложно, это должно быть быстро.
  3. Стоимость обратного угадывания относительно высока.

В настоящее время большинство случайных алгоритмов в языке (некоторые случайные алгоритмы с криптографическими требованиями могут использовать пул энтропии системы) являются псевдослучайными, такими как линейная конгруэнтность, вращение Мерсенна и взятие квадратов, наиболее известным из которых является «метод линейной конгруэнтности» (LCG), формула которого

LCG公式
где НjМы часто говорим, что это начальное число случайных чисел, а A, B и M обычно определяются реализацией языка. В случае определенного начального числа выходная «случайная» последовательность также полностью непротиворечива. Самый простой способ проверки — случайный алгоритм в golang, если начальное число не указано (по умолчанию 1), последовательность, полученная в результате многократных вычислений, одинакова.

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

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

LCG常见参数
Чтобы доказать, что эта «псевдо» случайность на самом деле имеет очевидные законы, кто-то нарисовал две картинки, используя физическую энтропию (атмосферу) и случайные значения, сгенерированные алгоритмом линейной конгруэнтности:

Используя физическую энтропию:

利用物理熵

Линейная конгруэнтность:

线性同余

Криптография делит случайные числа на три типа:

  1. Слабое случайное число: статистическая псевдослучайность, частота 01 в битовом потоке в основном одинакова, например, упомянутая здесь линейная конгруэнтность.
  2. Сильные случайные числа: криптографически безопасная псевдослучайность: «Никакая другая часть последовательности битов не может быть вычислена за полиномиальное время с вероятностью, значительно превышающей 1/2 от данной случайной последовательности», например Trivium, алгоритм SHA-2, будь то Алгоритм случайных чисел — это криптографически безопасный генератор псевдослучайных чисел с набором проверки CSPRNG.
  3. Настоящие случайные числа: невоспроизводимы. Поскольку результат вычисления компьютера детерминирован, он не может быть реализован алгоритмом, только с использованием энтропийного пула.

Для получения истинных случайных чисел чип ЦП имеет встроенный генератор истинных случайных чисел TRNG и генератор псевдослучайных чисел PRNG.TRNG использует тепловой шум схемы усилителя для генерации случайных чисел, в то время как PRNG использует регистр сдвига с линейной обратной связью, который представляет собой аппаратный генератор псевдослучайных чисел, начальное число которого является истинным случайным числом в TRNG.

(Этот абзац находится на рассмотрении, можете обратить внимание на вопрос автора в v2exЯвляется ли /dev/(u)random генератором истинных случайных чисел (TRNG) и генератором псевдослучайных чисел (PRNG) в процессоре? - V2EX) Соответственно, linux реализует два виртуальных устройства, /dev/random и /dev/urandom.Криптографически безопасные алгоритмы на многих языках реализованы путем чтения этих двух устройств, таких как crypto.randombytes в узле. Кроме того, есть статья, утверждающая, что случайность этих двух устройств одинакова (известна в колонке в справочном материале), но более подробной информации, подтверждающей это утверждение, автор не нашел, и я склонен думать, что это утверждение неверно.

Схема классификации

Распределение центрального узла

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

Базы данных, такие как mysql или redis

Распространенным решением является использование самоинкремента и уникальности первичного ключа базы данных для получения первичного ключа в качестве уникального идентификатора до 1605807. Эта схема осуществима, но очевидны и недостатки: она не распределена, и нагрузка на центральный узел будет велика. Риск выхода из строя центрального узла делает его не очень доступным.

Эволюция базы данных

Две типичные эволюционные идеи:

  1. Пакет генерируется пакетами, которые равномерно распределяются по каждому узлу машины, хранятся в их памяти и генерируются после исчерпания.По сути, это также общее решение, принятое всеми алгоритмами, которые могут столкнуться с проблемами эффективности.
  2. Поддерживайте несколько центральных узлов и устанавливайте разные начальные точки с одинаковой продолжительностью синхронизации, чтобы они никогда не повторялись.Например, две машины имеют 135 и 246. Если одна выходит из строя, другая также может взять на себя работу, но КПД низкий.

mysql实现唯一id

совершенно случайно

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

Nuid

Nuid — это более новый алгоритм с очень простым ядром.

Используйте 62 символа (0-9a-zA-Z) для генерации 22-битного результата, где первые 12 бит — это настоящие случайные числа, полученные с помощью TRNG, а последние 10 бит — случайные числа.

// Generate a new prefix from crypto/rand.
// This call *can* drain entropy and will be called automatically when we exhaust the sequential range.
// Will panic if it gets an error from rand.Int()
func (n *NUID) RandomizePrefix() {
  var cb [preLen]byte
  cbs := cb[:]
  if nb, err := rand.Read(cbs); nb != preLen || err != nil {
    panic(fmt.Sprintf("nuid: failed generating crypto random number: %v\n", err))
  }
  
  for i := 0; i < preLen; i++ {
    n.pre[i] = digits[int(cbs[i])%base]
  }
}

// Generate the next NUID string.
func (n *NUID) Next() string {
  // Increment and capture.
  n.seq += n.inc
  if n.seq >= maxSeq {
    n.RandomizePrefix()
   	n.resetSequential()
  }
  seq := n.seq
  
  // Copy prefix
  var b [totalLen]byte
  bs := b[:preLen]
  copy(bs, n.pre)
  
  // copy in the seq in base36.
  for i, l := len(b), seq; i > preLen; l /= base {
    i -= 1
    b[i] = digits[l%base]
  }
  return string(b[:])
}

Его главное преимущество в том, что производительность очень высока, и миллионы идентификаторов могут быть рассчитаны за 1 секунду.

частичная версия uuid и вырожденная версия

Почему здесь они называются частичными версиями и вырожденными версиями?

Большинство людей должны знать, что uuid, uuid и guid на самом деле одно и то же, просто разные имена. uuid — это алгоритм идентификации, определенный стандартом rfc4122. В принципе, он поддерживает распределенные уникальные идентификаторы, но конкретная реализация бывает не всегда, причина в том, что стандарт uuid относительно открыт, и существует пять версий v1-v5 (v2 не имеет конкретной реализации), а некоторые версии, такие как версия v1, не имеют конкретной реализации для поля node.Нет обязательных ограничений на конкретное значение Оно также может вырождаться в псевдослучайные числа. Стоит отметить, что в SQL также есть метод GENERATE_UUID().

uuid格式

Алгоритм генерации uuid всех версий здесь подробно описывать не буду.В качестве примера возьмем реализацию npm-пакета node uuid с 8k+ звезд на github.Узел node использует не mac адрес, а случайное число (на самом деле, большинство реализаций uuid не используют mac-адрес, конкретная причина должна быть проверена):

// rng库的内容是利用crypto.randomBytes从trng熵池读取随机数
var rng = require('./lib/rng');
var bytesToUuid = require('./lib/bytesToUuid');

// **`v1()` - Generate time-based UUID**
//
// Inspired by https://github.com/LiosK/UUID.js
// and http://docs.python.org/library/uuid.html

var _nodeId;
var _clockseq;

// Previous uuid creation time
var _lastMSecs = 0;
var _lastNSecs = 0;

// See https://github.com/broofa/node-uuid for API details
function v1(options, buf, offset) {
  var i = buf && offset || 0;
  var b = buf || [];

  options = options || {};
  var node = options.node || _nodeId;
  var clockseq = options.clockseq !== undefined ? options.clockseq : _clockseq;

  // node and clockseq need to be initialized to random values if they're not
  // specified.  We do this lazily to minimize issues related to insufficient
  // system entropy.  See #189
  if (node == null || clockseq == null) {
    var seedBytes = rng();
    if (node == null) {
      // Per 4.5, create and 48-bit node id, (47 random bits + multicast bit = 1)
      node = _nodeId = [
        seedBytes[0] | 0x01,
        seedBytes[1], seedBytes[2], seedBytes[3], seedBytes[4], seedBytes[5]
      ];
    }
    if (clockseq == null) {
      // Per 4.2.2, randomize (14 bit) clockseq
      clockseq = _clockseq = (seedBytes[6] << 8 | seedBytes[7]) & 0x3fff;
    }
  }

  // UUID timestamps are 100 nano-second units since the Gregorian epoch,
  // (1582-10-15 00:00).  JSNumbers aren't precise enough for this, so
  // time is handled internally as 'msecs' (integer milliseconds) and 'nsecs'
  // (100-nanoseconds offset from msecs) since unix epoch, 1970-01-01 00:00.
  var msecs = options.msecs !== undefined ? options.msecs : new Date().getTime();

  // Per 4.2.1.2, use count of uuid's generated during the current clock
  // cycle to simulate higher resolution clock
  var nsecs = options.nsecs !== undefined ? options.nsecs : _lastNSecs + 1;

  // Time since last uuid creation (in msecs)
  var dt = (msecs - _lastMSecs) + (nsecs - _lastNSecs)/10000;

  // Per 4.2.1.2, Bump clockseq on clock regression
  if (dt < 0 && options.clockseq === undefined) {
    clockseq = clockseq + 1 & 0x3fff;
  }

  // Reset nsecs if clock regresses (new clockseq) or we've moved onto a new
  // time interval
  if ((dt < 0 || msecs > _lastMSecs) && options.nsecs === undefined) {
    nsecs = 0;
  }

  // Per 4.2.1.2 Throw error if too many uuids are requested
  if (nsecs >= 10000) {
    throw new Error('uuid.v1(): Can\'t create more than 10M uuids/sec');
  }

  _lastMSecs = msecs;
  _lastNSecs = nsecs;
  _clockseq = clockseq;

  // Per 4.1.4 - Convert from unix epoch to Gregorian epoch
  msecs += 12219292800000;

  // `time_low`
  var tl = ((msecs & 0xfffffff) * 10000 + nsecs) % 0x100000000;
  b[i++] = tl >>> 24 & 0xff;
  b[i++] = tl >>> 16 & 0xff;
  b[i++] = tl >>> 8 & 0xff;
  b[i++] = tl & 0xff;

  // `time_mid`
  var tmh = (msecs / 0x100000000 * 10000) & 0xfffffff;
  b[i++] = tmh >>> 8 & 0xff;
  b[i++] = tmh & 0xff;

  // `time_high_and_version`
  b[i++] = tmh >>> 24 & 0xf | 0x10; // include version
  b[i++] = tmh >>> 16 & 0xff;

  // `clock_seq_hi_and_reserved` (Per 4.2.2 - include variant)
  b[i++] = clockseq >>> 8 | 0x80;

  // `clock_seq_low`
  b[i++] = clockseq & 0xff;

  // `node`
  for (var n = 0; n < 6; ++n) {
    b[i + n] = node[n];
  }

  return buf ? buf : bytesToUuid(b);
}

module.exports = v1;

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

Узел + время

uuid с версией узла

Поле узла, соответствующее версии v1, использует схему аппаратного адреса, такую ​​как mac-адрес. Здесь он не будет повторяться.

алгоритм снежинка снежинка

Snowflake — это реальный распределенный алгоритм уникальной идентификации, предложенный Twitter.В настоящее время наиболее часто используемыми решениями крупных производителей в отрасли являются преобразование и оптимизация на основе снежинок или снежинок.

snowflake格式

Обратите внимание, что 64 бита здесь — это биты, все 0 или 1, а не 0-10 или буквы.

Первый бит всегда равен 0, потому что 64-битный бит снежинки на самом деле является 64-битным целым числом, первый бит представляет положительное или отрицательное число, а 0 представляет положительное число. Поддержка 41-битной метки времени2^41Число, которое может представлять в общей сложности 69 лет в миллисекундах.Временная метка здесь не традиционная временная метка Unix, а самоопределяемое относительное время, где значение 0 может быть моментом начала бизнеса. 10 битов рабочей машины могут представлять до2^10Для каждой машины этот id также назначается сам по себе, например 0123 по порядку ip. В соответствии с двумя приведенными выше полями мы уже можем определить, что идентификатор на машине не будет повторяться в течение 1 мс.Для поддержки большего параллелизма в течение 1 мс используется 12 бит для представления порядка идентификаторов, сгенерированных в течение 1 мс.Максимум производительность одной машины в течение одной мс составляет2^12Количество создаваемых идентификаторов в секунду также исчисляется миллионами.

Конечным результатом является 64-битное целое число, отвечающее различным требованиям распределенного идентификатора и упорядоченное по времени.

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

эволюция снежинки

Преобразование и оптимизация снежинки отечественными производителями в основном сосредоточены на двух аспектах:

  1. Избегайте поворота часов вспять. Если 41-битное время повторяется, высока вероятность конфликта идентификаторов. Решение Meituan для листьев состоит в том, чтобы добавить ZooKeeper в Snowflake для записи хода часов и активации будильника, если он вызывается обратно. Также существует множество решений для сравнения времени сгенерированного идентификатора с ранее сгенерированным идентификатором и сообщения об ошибке, если он не передан вперед, или по-прежнему использовать повторяющийся временной ряд после обратного вызова + большее значение ряда, которое вряд ли будет использоваться. (ставка не столкнется).

    leaf时钟回拨策略

  2. Повторно разделите 64-битный сегмент кода и его конкретное значение.Например, когда имеется много машин, сегмент кода тактовой последовательности может быть сжат, а сегмент кода идентификатора рабочей машины может быть расширен.

    百度uidgenerator算法

Согласованность распределенных часов

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

Также существуют решения для поддержания согласованности часов различных машин в сети, такие как протокол NTP или часы GPS, но они не могут добиться полной синхронизации (задержки на уровне десятков мс). Что касается логических часов, то они должны иметь мало общего с распределенными уникальными идентификаторами, обсуждаемыми в этой статье.

В заключение

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

использованная литература

Категории