помещение
Snowflake(снежинка) даTwitterВысокая производительность с открытым исходным кодомIDГенерировать алгоритмы (сервисы).
Картинка вышеSnowflakeизGithubсклад,masterв филиалеREAEMDEПримечание в файле: исходная версия была2010выпущен в 2018 году на основеApache Thrift,Раньше чемFinagle(здесьFinagleдаTwitterиспользуется наRPCсервисные строительные блоки) публикуются, аTwitterиспользуется внутриSnowflakeполностью переписанная программа, которая сильно зависит отTwitterработать на существующей инфраструктуре.
а также2010первое изданиеSnowflakeиспользуется исходный кодScalaнаписано на языке, архивировано по адресуscala_28филиал. Другими словами,В настоящее время все используютSnowflakeПервоначальная или улучшенная версия алгоритма была десять лет назад (в настоящее время2020лет), я должен сказать, что этот алгоритм действительно мощный.scala_28В ветке есть мотивы и требования по внедрению алгоритма, вот краткая выдержка:
мотивация:
-
Cassandraнет порядка сборки вIDИнструмент,TwitterиспользованMySQLперейти к использованиюCassandraкогда новый способ генерироватьID(Это доказывает, что архитектура не спроектирована, а итеративно основана на бизнес-сценариях).
Требовать:
- Высокая производительность: каждый процесс производит не менее одного в секунду
10KиндивидуальныйID, плюс скорость отклика сетевой задержки должна быть в2msВнутри. - Последовательный: он имеет тенденцию к самовозрастанию во времени и может быть отсортирован напрямую.
- Компактность: продолжайте генерировать
IDдлина в64 bitили короче. - Высокая доступность:
IDСхема генерации должна быть такой же высокодоступной, как и служба хранения.
нижеSnowflakeИсходный код анализирует его принцип реализации.
Краткий обзор решения Snowflake
SnowflakeПервоначальная схема проектирования:
- время:
41 bitдлина с точностью до миллисекунды, с пользовательскимepoch, то можно использовать приблизительно69год. - Конфигурируемая машина
ID:10 bitдлина, может удовлетворить1024использование машины. - серийный номер:
12 bitдлина, может быть4096Случайным образом брать значение среди чисел, тем самым предотвращая1 msВнутри генерируются повторяющиеся серийные номера.
Но в фактической реализации исходного кодаSnowflakeПучок10 bitнастраиваемая машинаIDразделить на5 bitизWorker ID(Это можно понимать как оригинальную машинуID)и5 bitизData Center ID(Дата центрID), видетьIdWorker.scala:
То есть поддерживаемая конфигурация является наиболее32машиныIDи до32Дата центрID:
Так как алгоритмScalaязык, зависит отJVMязык, вернулсяIDзначениеLongтипа, то есть64 bitЦелые числа, используемые в исходном алгоритме только для генерации последовательности63 bitДлина, которая должна быть возвращена, представляет собой число без знака, поэтому добавьте единицу в старшем порядке.0(занимать1 bit), затем складываем всеIDДлина64 bit:
в:
-
41 bitДиапазон значений временных меток миллисекундного уровня:[0, 2^41 - 1]=>0 ~ 2199023255551, в общей сложности2199023255552числа. -
5 bitмашинаIDДиапазон значений:[0, 2^5 - 1]=>0 ~ 31, в общей сложности32числа. -
5 bitДата центрIDДиапазон значений:[0, 2^5 - 1]=>0 ~ 31, в общей сложности32числа. -
12 bitДиапазон значений серийного номера:[0, 2^12 - 1]=>0 ~ 4095, в общей сложности4096числа.
Тогда теоретически его можно сгенерировать2199023255552 * 32 * 32 * 4096полностью отличаетсяIDценность.
SnowflakeАлгоритм также имеет отличительную особенность:Зависит от системных часов.41 bitВремя в миллисекундах выводится из системной метки времени, поэтому необходимо убедиться, что системное время опережает время и не может произойти.часы назад(Как правило, невозможно создать несколько одинаковых временных меток одновременно или создать прошлые временные метки). Как только происходит откат часов,Snowflakeоткажется генерировать следующийID.
Дополнительные знания о битовых операциях
SnowflakeВ алгоритме используется множество битовых операций. Поскольку дополнение целых чисел является формой хранения в компьютере,JavaилиScalaЦелые числа в представлены дополнительным кодом, здесь небольшое упоминание о знании исходного кода и дополнительного кода.
- Исходный код используется для чтения, а дополнительный код используется для вычисления.
- Дополнение положительного числа совпадает с его исходным кодом.
- Дополнением отрицательного числа является инверсия всех битов, кроме самого старшего бита, а затем добавление
1(обратный код плюс1), и с помощью этого метода дополнение отрицательных чисел восстанавливается до исходного кода. -
+0Оригинальный код0000 0000,а также-0Оригинальный код1000 0000, дополнение только одно0значение, с0000 0000Указывает, что это важно, дополнение0Нет никакой двусмысленности.
Простыми словами это выглядит так:
* [+ 11] 原码 = [0000 1011] 补码 = [0000 1011]
* [- 11] 原码 = [1000 1011] 补码 = [1111 0101]
* [- 11]的补码计算过程：
原码 1000 1011
除了最高位其他位取反 1111 0100
加1 1111 0101 （补码）
При использовании исходного кода и инверсного кода результат расчета не обязательно точен, но при использовании дополнительного кода результат расчета правильный.Просто запомните этот вывод, и я не буду приводить здесь пример. потому чтоSnowflakeизIDВ схеме генерации, за исключением самого старшего бита, остальные четыре части представляют собой целые числа без знака, поэтому целые числа четырех частей равныИспользование дополнения для битовых операций будет более эффективным, и только таким образом оно сможет соответствовать первоначальному замыслу высокопроизводительного дизайна Snowflake..SnowflakeВ алгоритме используется несколько побитовых операций: XOR (^), побитовое И (&), побитовое ИЛИ (|) и сдвиг влево со знаком (<<).
исключающее ИЛИ
Правила операции XOR:0^0=0 0^1=1 1^0=1 1^1=0, то есть если биты разные, результат равен 1, а если биты одинаковые, результат равен 0. Основные функции:
- Конкретный битовый флип, т. е. число и
NОба1XOR количество , что соответствуетNБиты переворачиваются, например.0100 & 1111, Результат1011. - а также
0XOR условия, результат будет таким же, как исходное значение. - Значение взаимодействия двух чисел:
a=a^bb=b^aa=a^b, после выполнения этих трех операцийaа такжеbзначение для завершения обмена.
Вот краткое изложение последнего:
* [+ 11] 原码 = [0000 1011] 补码 = [0000 1011] a
* [- 11] 原码 = [1000 1011] 补码 = [1111 0101] b
a=a^b 0000 1011
1111 0101
---------^
1111 1110
b=b^a 1111 0101
---------^
0000 1011 （十进制数：11） b
a=a^b 1111 1110
---------^
1111 0101 （十进制数：-11） a
побитовое И
Правила побитового И:0&0=0 0&1=0 1&0=0 1&1=1, результат вычисления равен 1 только тогда, когда все соответствующие биты равны 1, а результат вычисления в других случаях равен 0. Основные функции:
- Очистить, если вы хотите очистить число, суммируйте все биты как
0Можно выполнить побитовое И чисел. - Возьмите указанный бит в числе, например, чтобы взять
Xсредний низкий4немного, просто нужно иzzzz...1111Можно выполнить побитовое И, например, взять1111 0110низкий4немного, тогда11110110 & 00001111может получить00000110.
побитовое ИЛИ
Правила побитового И:0|0=0 0|1=1 1|0=1 1|1=1, пока в одном из битов есть 1, результат вычисления равен 1, а результат вычисления равен 0 только тогда, когда оба бита равны 0 одновременно. Основные функции:
- Присвоить часть числа
1, только соответствующие биты должны быть все0Достаточно выполнить побитовую операцию ИЛИ над числами, например1011 0000если низкий4Биты хотят, чтобы все были назначены как1,Так10110000 | 00001111может получить1011 1111.
Знак левого сдвига
Оператор для сдвига влево со знаком<<, общий формат:M << n. Эффект следующий:
-
MДвоичное число (дополнение) сдвинуто влевоnнемного. - Левая часть (высокое положение) выдвигается, а часть непосредственно отбрасывается, а правая часть (нижнее положение) перемещается, чтобы компенсировать это.
0. - Результат сдвига: эквивалентно
Mзначение, умноженное на2изnстепень и 0, положительные и отрицательные числа являются общими. - Количество сдвинутых битов превышает максимальное количество битов типа, тогда компилятор выполнит по модулю количество сдвинутых битов, например
intсдвиг33немного, на самом деле только переехал33 % 2 = 1немного.
Процесс дедукции выглядит следующим образом (при условии, чтоn = 2):
* [+ 11] 原码 = [0000 1011] 补码 = [0000 1011]
* [- 11] 原码 = [1000 1011] 补码 = [1111 0101]
* [+ 11 << 2]的计算过程
补码 0000 1011
左移2位 0000 1011
舍高补低 0010 1100
十进制数 2^2 + 2^3 + 2^5 = 44
* [- 11 << 2]的计算过程
补码 1111 0101
左移2位 1111 0101
舍高补低 1101 0100
原码 1010 1100 （补码除最高位其他所有位取反再加1）
十进制数 - (2^2 + 2^3 + 2^5) = -44
могу написатьmainМетод проверки:
public static void main(String[] args) {
System.out.println(-11 << 2); // -44
System.out.println(11 << 2); // 44
}
Комбинированные навыки
Использование трех упомянутых выше побитовых операторов в сочетании друг с другом позволяет реализовать некоторые эффективные схемы вычислений.
Вычислите максимальное значение, которое могут представлять n битов:
SnowflakeВ алгоритме есть такой код:
// 机器ID的位长度
private val workerIdBits = 5L;
// 最大机器ID -> 31
private val maxWorkerId = -1L ^ (-1L << workerIdBits);
Оператор здесь-1L ^ (-1L << 5L), разберитесь в порядке операторов, а затем используйте64 bitПроцесс вычисления вычета двоичного числа выглядит следующим образом:
* [-1] 的补码 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
左移5位 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
[-1] 的补码 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
异或 ----------------------------------------------------------------------- ^
结果的补码 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111 （十进制数 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31）
Это будет вычислять5 bitМаксимальное значение, которое может быть представленоn,nявляется целым числом и0 <= n <= 31,Сейчас0、1、2、3...31.Worker IDа такжеData Center IDЧастичный максимум получается с помощью этой комбинаторной операции.
Используйте максимальное значение фиксированного бита в качестве маски, чтобы избежать переполнения:
SnowflakeВ алгоритме есть такой код:
var sequence = 0L
......
private val sequenceBits = 12L
// 这里得到的是sequence的最大值4095
private val sequenceMask = -1L ^ (-1L << sequenceBits)
......
sequence = (sequence + 1) & sequenceMask
Последний оператор на самом делеsequence = (sequence + 1) & 4095, предполагаяsequenceТекущее значение4095, вывести процесс вычисления:
* [4095] 的补码 00000000 00000000 00000000 00000000 00000000 00000000 00000111 11111111
[sequence + 1] 的补码 00000000 00000000 00000000 00000000 00000000 00000000 00001000 00000000
按位与 ----------------------------------------------------------------------- &
计算结果 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 （十进制数：0）
могу написатьmainМетод проверки:
public static void main(String[] args) {
int mask = 4095;
System.out.println(0 & mask); // 0
System.out.println(1 & mask); // 1
System.out.println(2 & mask); // 2
System.out.println(4095 & mask); // 4095
System.out.println(4096 & mask); // 0
System.out.println(4097 & mask); // 1
}
то естьx = (x + 1) & (-1L ^ (-1L << N))гарантированный финалxзначение не превыситN, который использует преимущество "побитовой" функции побитового И.
Анализ исходного кода реализации алгоритма Snowflake
SnowflakeХотя с помощьюScalaязык письма, грамматика факт иJavaпочти какJavaКод можно прочитать так: при чтении кода ниже будет пропущена некоторая логика логирования и статистики метрик. Первый взглядIdWorker.scalaСтоимость свойства:
// 定义基准纪元值，这个值是北京时间2010-11-04 09:42:54，估计就是2010年初版提交代码时候定义的一个时间戳
val twepoch = 1288834974657L
// 初始化序列号为0
var sequence = 0L //TODO after 2.8 make this a constructor param with a default of 0
// 机器ID的最大位长度为5
private val workerIdBits = 5L
// 数据中心ID的最大位长度为5
private val datacenterIdBits = 5L
// 最大的机器ID值，十进制数为为31
private val maxWorkerId = -1L ^ (-1L << workerIdBits)
// 最大的数据中心ID值，十进制数为为31
private val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)
// 序列号的最大位长度为12
private val sequenceBits = 12L
// 机器ID需要左移的位数12
private val workerIdShift = sequenceBits
// 数据中心ID需要左移的位数 = 12 + 5
private val datacenterIdShift = sequenceBits + workerIdBits
// 时间戳需要左移的位数 = 12 + 5 + 5
private val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
// 序列号的掩码，十进制数为4095
private val sequenceMask = -1L ^ (-1L << sequenceBits)
// 初始化上一个时间戳快照值为-1
private var lastTimestamp = -1L
// 下面的代码块为参数校验和初始化日志打印，这里不做分析
if (workerId > maxWorkerId || workerId < 0) {
exceptionCounter.incr(1)
throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId))
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
exceptionCounter.incr(1)
throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId))
}
log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
Затем посмотрите на основную логику кода алгоритма:
// 同步方法，其实就是protected synchronized long nextId(){ ...... }
protected[snowflake] def nextId(): Long = synchronized {
// 获取系统时间戳（毫秒）
var timestamp = timeGen()
// 高并发场景，同一毫秒内生成多个ID
if (lastTimestamp == timestamp) {
// 确保sequence + 1之后不会溢出，最大值为4095，其实也就是保证1毫秒内最多生成4096个ID值
sequence = (sequence + 1) & sequenceMask
// 如果sequence溢出则变为0，说明1毫秒内并发生成的ID数量超过了4096个，这个时候同1毫秒的第4097个生成的ID必须等待下一毫秒
if (sequence == 0) {
// 死循环等待下一个毫秒值，直到比lastTimestamp大
timestamp = tilNextMillis(lastTimestamp)
}
} else {
// 低并发场景，不同毫秒中生成ID
// 不同毫秒的情况下，由于外层方法保证了timestamp大于或者小于lastTimestamp，而小于的情况是发生了时钟回拨，下面会抛出异常，所以不用考虑
// 也就是只需要考虑一种情况：timestamp > lastTimestamp，也就是当前生成的ID所在的毫秒数比上一个ID大
// 所以如果时间戳部分增大，可以确定整数值一定变大，所以序列号其实可以不用计算，这里直接赋值为0
sequence = 0
}
// 获取到的时间戳比上一个保存的时间戳小，说明时钟回拨，这种情况下直接抛出异常，拒绝生成ID
// 个人认为，这个方法应该可以提前到var timestamp = timeGen()这段代码之后
if (timestamp < lastTimestamp) {
exceptionCounter.incr(1)
log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format(lastTimestamp - timestamp));
}
// lastTimestamp保存当前时间戳，作为方法下次被调用的上一个时间戳的快照
lastTimestamp = timestamp
// 度量统计，生成的ID计数器加1
genCounter.incr()
// X = (系统时间戳 - 自定义的纪元值) 然后左移22位
// Y = (数据中心ID左移17位)
// Z = (机器ID左移12位)
// 最后ID = X | Y | Z | 计算出来的序列号sequence
((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence
}
// 辅助方法：获取系统当前的时间戳（毫秒）
protected def timeGen(): Long = System.currentTimeMillis()
// 辅助方法：获取系统当前的时间戳（毫秒），用死循环保证比传入的lastTimestamp大，也就是获取下一个比lastTimestamp大的毫秒数
protected def tilNextMillis(lastTimestamp: Long): Long = {
var timestamp = timeGen()
while (timestamp <= lastTimestamp) {
timestamp = timeGen()
}
timestamp
}
Последняя часть логики имеет больше битовых операций, но если вы умеете использовать операторы битовых операций, логика не сложная.Здесь вы можете нарисовать диаграмму, чтобы вывести ее:
После того, как целое число, состоящее из четырех частей, будет сдвинуто влево, будут добавлены младшие биты вакансии.0, согласно характеристике побитового ИЛИ, все младшие биты существуют до тех пор, пока1, то соответствующий бит будет заполнен1, так как биты четырех частей не будут выделяться за пределы, суть здесь такова:После того, как четыре части смещены влево, добавляется итоговое число..
Улучшение алгоритма снежинки
SnowflakeЕсть несколько больших проблем с алгоритмом:
- В сценариях с низким уровнем параллелизма генерируются последовательные четные числа, поскольку системные часы в сценариях с низким уровнем параллелизма всегда переходят к следующему значению в миллисекундах, что приводит к сбросу порядкового номера на
0. - Зависит от системных часов, обратный вызов часов откажется генерировать новые
ID(выдает исключение напрямую). -
Woker IDа такжеData Center IDЭто более проблематично в управлении, особенно разные узлы кластера одной и той же службы должны гарантировать, что каждый узелWoker IDа такжеData Center IDУникальное сочетание.
Эти три вопроса открыты Meituan.LeafПри условии решения следующий снимок экрана взят изcom.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl:
Соответствующее решение (без глубокого анализа исходного кода, вы можете прочитать следующее, если вам интересноLeafисходный код):
- Генерация порядкового номера добавляет случайный источник, что немного уменьшает максимальное количество, которое может быть сгенерировано за ту же миллисекунду.
IDколичество. - Часы настроены на ожидание в течение определенного периода времени.
- использовать
Zookeeperкеш и управлениеWoker IDа такжеData Center ID.
Woker IDа такжеData Center IDКонфигурация чрезвычайно важна, для нескольких узлов кластера одного и того же сервиса (например, платежного сервиса) необходимо настроить разные машины.IDи дата-центрIDили тот же дата-центрIDи разные машиныID(Проще говоря, убедитесьWoker IDа такжеData Center IDСочетание глобально уникально), в противном случае в сценарии с высокой степенью параллелизма, когда системные часы непротиворечивы, легко сгенерировать один и тот жеIDvalue, поэтому общая архитектура развертывания выглядит следующим образом:
управлять обоимиIDЕсть много способов, или какLeafТакая структура с открытым исходным кодом вводит распределенные кеши для управления.Например, небольшая команда предпринимателей, в которой работает автор, производит мало услуг, поэтому мы напрямую помещаемWoker IDа такжеData Center IDЖестко запрограммирован в сценарии запуска службы, а затем используется всеми службами.Woker IDа такжеData Center IDЕдиная регистрация во внутренней базе знаний команды.
Самореализующаяся упрощенная версия Snowflake
Если вы вообще не учитываете производительность и не рассматриваете такие вопросы, как обратный вызов часов, генерация серийных номеров и т. д., вы можете поставитьSnowflakeБитовые операции и части обработки исключенийLong.toBinaryString()метод объединения строк в соответствии сSnowflakeИдеи алгоритмов сращены64 bitдвоичное число, затем передатьLong.parseLong()метод вLongТипы. НапишиmainМетоды, как показано ниже:
public class Main {
private static final String HIGH = "0";
/**
* 2020-08-01 00:00:00
*/
private static final long EPOCH = 1596211200000L;
public static void main(String[] args) {
long workerId = 1L;
long dataCenterId = 1L;
long seq = 4095;
String timestampString = leftPadding(Long.toBinaryString(System.currentTimeMillis() - EPOCH), 41);
String workerIdString = leftPadding(Long.toBinaryString(workerId), 5);
String dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5);
String seqString = leftPadding(Long.toBinaryString(seq), 12);
String value = HIGH + timestampString + workerIdString + dataCenterIdString + seqString;
long num = Long.parseLong(value, 2);
System.out.println(num); // 某个时刻输出为3125927076831231
}
private static String leftPadding(String value, int maxLength) {
int diff = maxLength - value.length();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < diff; i++) {
builder.append("0");
}
builder.append(value);
return builder.toString();
}
}
Затем стандартизируйте код и напишите короткую версию.SnowflakeИнженерный код для реализации алгоритма:
// 主键生成器接口
public interface PrimaryKeyGenerator {
long generate();
}
// 简易Snowflake实现
public class SimpleSnowflake implements PrimaryKeyGenerator {
private static final String HIGH = "0";
private static final long MAX_WORKER_ID = 31;
private static final long MIN_WORKER_ID = 0;
private static final long MAX_DC_ID = 31;
private static final long MIN_DC_ID = 0;
private static final long MAX_SEQUENCE = 4095;
/**
* 机器ID
*/
private final long workerId;
/**
* 数据中心ID
*/
private final long dataCenterId;
/**
* 基准纪元值
*/
private final long epoch;
private long sequence = 0L;
private long lastTimestamp = -1L;
public SimpleSnowflake(long workerId, long dataCenterId, long epoch) {
this.workerId = workerId;
this.dataCenterId = dataCenterId;
this.epoch = epoch;
checkArgs();
}
private void checkArgs() {
if (!(MIN_WORKER_ID <= workerId && workerId <= MAX_WORKER_ID)) {
throw new IllegalArgumentException("Worker id must be in [0,31]");
}
if (!(MIN_DC_ID <= dataCenterId && dataCenterId <= MAX_DC_ID)) {
throw new IllegalArgumentException("Data center id must be in [0,31]");
}
}
@Override
public synchronized long generate() {
long timestamp = System.currentTimeMillis();
// 时钟回拨
if (timestamp < lastTimestamp) {
throw new IllegalStateException("Clock moved backwards");
}
// 同一毫秒内并发
if (lastTimestamp == timestamp) {
sequence = sequence + 1;
if (sequence == MAX_SEQUENCE) {
timestamp = untilNextMillis(lastTimestamp);
sequence = 0L;
}
} else {
// 下一毫秒重置sequence为0
sequence = 0L;
}
lastTimestamp = timestamp;
// 41位时间戳字符串，不够位数左边补"0"
String timestampString = leftPadding(Long.toBinaryString(timestamp - epoch), 41);
// 5位机器ID字符串，不够位数左边补"0"
String workerIdString = leftPadding(Long.toBinaryString(workerId), 5);
// 5位数据中心ID字符串，不够位数左边补"0"
String dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5);
// 12位序列号字符串，不够位数左边补"0"
String seqString = leftPadding(Long.toBinaryString(sequence), 12);
String value = HIGH + timestampString + workerIdString + dataCenterIdString + seqString;
return Long.parseLong(value, 2);
}
private long untilNextMillis(long lastTimestamp) {
long timestamp;
do {
timestamp = System.currentTimeMillis();
} while (timestamp <= lastTimestamp);
return timestamp;
}
private static String leftPadding(String value, int maxLength) {
int diff = maxLength - value.length();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < diff; i++) {
builder.append("0");
}
builder.append(value);
return builder.toString();
}
public static void main(String[] args) {
long epoch = LocalDateTime.of(1970, 1, 1, 0, 0, 0, 0)
.toInstant(ZoneOffset.of("+8")).toEpochMilli();
PrimaryKeyGenerator generator = new SimpleSnowflake(1L, 1L, epoch);
for (int i = 0; i < 5; i++) {
System.out.println(String.format("第%s个生成的ID: %d", i + 1, generator.generate()));
}
}
}
// 某个时刻输出如下
第1个生成的ID: 6698247966366502912
第2个生成的ID: 6698248027448152064
第3个生成的ID: 6698248032162549760
第4个生成的ID: 6698248033076908032
第5个生成的ID: 6698248033827688448
Хотя метод записи сращивания строк неэффективен, читабельность будет относительно высокой, а код после инженерной обработки может быть указан непосредственно во время создания экземпляра.Worker IDа такжеData Center IDэквивалентно, и это простоSnowflakeРеализация не имеет зависимостей от сторонних библиотек и может запускаться сразу после копирования. Вышеупомянутый метод с конкатенацией строк выглядит относительно низкоуровневым, на самом деле это побитовое ИЛИ последней части,может быть полностью преобразован в дополнение:
public class Main {
/**
* 2020-08-01 00:00:00
*/
private static final long EPOCH = 1596211200000L;
public static void main(String[] args) {
long workerId = 1L;
long dataCenterId = 1L;
long seq = 4095;
long timestampDiff = System.currentTimeMillis() - EPOCH;
long num = (long) (timestampDiff * Math.pow(2, 22)) + (long) (dataCenterId * Math.pow(2, 17)) + (long) (workerId * Math.pow(2, 12)) + seq;
System.out.println(num); // 某个时刻输出为3248473482862591
}
}
Кажется, что весь алгоритм становится простым, но здесь задействована экспоненциальная операция и операция сложения, и эффективность будет относительно низкой.
резюме
SnowflakeАлгоритм представляет собой алгоритм с высокой производительностью в качестве основной цели.Основываясь на этой цели, гениально используются битовые операции.Эта статья поместилаSnowflakeБитовая операция и конкретная реализация исходного кода, используемые при анализе, тщательно анализируются. Наконец, на основанииTwitterОфициальныйSnowflakeИсходный код алгоритма, исправленная версияJavaРеализуйте версию и примените упомянутые выше улучшения, чтобы устранить проблему, из-за которой в сценариях с низким параллелизмом генерируются только четные числа.и используется в производстве в течение некоторого времени, репозиторий кода выглядит следующим образом (код не имеет зависимостей от сторонних библиотек и доступен напрямую при копировании):
-
Github:https://github.com/zjcscut/framework-mesh/tree/master/java-snowflake
Использованная литература:
(Обложка c-3-d e-a-20200809 в конце этой статьи взята из Guoman «Ling Cage»)