задний план
В приложениях часто требуется глобальный уникальный идентификатор в качестве первичного ключа базы данных.
Какой генератор идентификаторов нам нужен
- Высокая производительность -> 1. Высокая производительность генерации 2. Высокая производительность вставки 3. Высокая производительность индексации
- Высокая доступность -> 1. Меньшая зависимость от промежуточного ПО 2. Избегайте проблем с одним узлом
- Неповторяющийся -> 1. Глобальный неповторяющийся в кластере
- Простота использования -> 1. Легкий доступ 2. Нулевая стоимость обучения
- Semantic -> 1.ID с некоторой дополнительной информацией
Как выполнить эти требования
- Выполнение высокого поколения -> Большинство времени - распределение памяти, уменьшить IO, уменьшить замок
- Высокая производительность вставки -> глобальное приращение, чтобы избежать разделения страниц
- Высокая производительность индекса -> числовой тип
- Глобальное отсутствие дублирования -> распределенная согласованность
- Высокая доступность сервисов -> снижение зависимости от промежуточного ПО и сокращение времени взаимодействия с промежуточным ПО.
Общие характеристики
- глобальное приращение
- Тип номера
- глобально уникальный
- параллелизм без блокировки
- выделение памяти
- Автономные сборки (в большинстве случаев)
SnowFlake
Twitter перенес систему хранения данных с MySQL на Cassandra.Поскольку у Cassandra нет механизма последовательной генерации идентификаторов, компания разработала такой глобально уникальный сервис генерации идентификаторов. Основная идея Рэя происходит от SnowFlake и решает некоторые проблемы в SnowFlake.
Как сделать так, чтобы одномашинный инкремент не повторялся
Простейшая идея: отметка времени + серийный номер Поддельный код:
If 当前时间 > 上次ID生成时间 -> 当前时间+序列号0
If 当前时间 = 上次ID生成时间 -> 当前时间 + 上次序列号+1
If 当前时间 < 上次ID生成时间 -> 是否存在这种情况
Как обеспечить глобальное отсутствие дублирования
Как узнать, являются ли два идентификатора дубликатами? Мы считаем, что два идентификатора повторяются, если повторяется каждый бит.
Если два повторяющихся значения объединяются с разными значениями, последние два значения не совпадают, например:
1111 и 1111, заклинание 1 и 2 соответственно
Тогда 1111-1 и 1111-2 не одно и то же
Раньше мы добивались неповторяемости в одной машине через отметку времени + серийный номер
Затем нам нужно только убедиться, что идентификатор, который не повторяется на одной машине, + идентификатор экземпляра (workId), который не повторяется, могут гарантировать, что окончательный сгенерированный идентификатор не будет повторяться.
Как убедиться, что workId не повторяется
Это проблема распределенной согласованности
Это может использовать распределенные блокировки для достижения эксклюзивного workId для каждого экземпляра.
и это зависит только от промежуточного программного обеспечения при запуске и обновлении
Даже если зависимое промежуточное ПО временно недоступно, а новый сервис использовать нельзя, старый — нормально
Сценический секс
- Глобальное приращение (отметка времени идет с глобальным приращением) -> вставка, высокая производительность индекса
- Распределение памяти (без ввода-вывода при выделении) -> генерировать высокую производительность
- Генерация на одной машине (сильно зависит только от промежуточного программного обеспечения при запуске) -> высокая доступность
Проблемы со Снежинкой
проблема с перекосом часов
Современные компьютеры имеют по крайней мере два разных типа часов: часы и монотонные часы. Хотя они оба измеряют время, важно различать их, потому что они служат разным целям.
Часы
Возвращает текущую дату и время по некоторому календарю. Например: System.currentTimeMillis() в Java возвращается с эпохи (1 января 1970 г. Количество секунд (или миллисекунд) с полуночи по Гринвичу, по григорианскому календарю, без дополнительных секунд.
монотонные часы
Подходит для измерения длительности (интервала времени), например, System.nanoTime() в Java — это монотонные часы. Название происходит от того, что они обещают всегда двигаться вперед.
проблема
Проблема с часами заключается в том, что, хотя они выглядят простыми и удобными в использовании, у них есть удивительные недостатки: в сутках может быть не ровно 86 400 секунд, часы могут прыгать туда-сюда, а время на одном узле может отличаться от этого. в др. время совсем другое. Если время набирается вперед, мы не можем гарантировать, что идентификатор, сгенерированный отметкой времени + серийным номером, уникален на одной машине.
Верхний предел количества спаунов в миллисекундах
Количество идентификаторов, генерируемых SnowFlake в миллисекундах, не может превышать 12 последовательных битов.
краткое изложение проблемы
Другими словами, SnowFlake сильно зависит от текущей временной метки и может обрабатывать только случай, когда текущая временная метка больше или равна последней временной метке, и не может обрабатывать случай, когда текущая временная метка меньше последней временной метки.
Решение проблем с перекосом часов
If 当前时间 > 上次ID生成时间 -> 当前时间+序列号0
If 当前时间 = 上次ID生成时间 -> 当前时间 + 上次序列号+1
If 当前时间 < 上次ID生成时间 ->上次ID生成时间 + 上次序列号 +1
Часы смещены, и временной скачок фактически эквивалентен текущему времени
Как записать время последней генерации идентификатора
Сначала в память текущего экземпляра записывается время последней генерации ID. Если обратный вызов часов происходит при перезагрузке, последняя запись времени генерации идентификатора будет потеряна. В этот момент новый экземпляр получает свой workId, а временная метка новой машины будет иметь повторяющиеся ранее идентификаторы. Следовательно, необходимо периодически синхронизировать глобальную максимальную метку времени с промежуточным ПО в фоновом режиме и синхронизировать метку времени перед выходом и запуском экземпляра.
бесконечные серийные номера
Почему у SnowFlake серийный номер состоит всего из 4096 бит? 1. Битов ровно столько, их можно выделить из машинных битов 2. Нет места для переноса, только текущая временная метка >= последняя временная метка Ray поддерживает текущее время
Ray
Ray относится к дизайну SnowFlake, решает проблему недостаточного обратного вызова часов и серийного номера и обеспечивает лучшую параллельную производительность. Адрес на гитхабе:GitHub.com/KE Шон ван/…