Это 12-й день моего участия в ноябрьском испытании обновлений. Узнайте подробности события:Вызов последнего обновления 2021 г.
какОпять же, сделайте это привычкой. Поиск в WeChat【код] Обратите внимание на этого программиста, который борется в Интернете.
Эта статья включена вОбучение технических специалистов, с моей в немМаршруты обучения, серия статей, банк вопросов для интервью, материалы для самостоятельной работы, электронные книгиЖдать. приветствую звезду⭐️
Привет всем, я ~
Ведь я уже полмесяца не писал статьи, и я весь в одиночестве. Если не напишу, то, наверное, зря. Прихожу с работы и говорю себя, что я должен закончить эту статью, даже если я останусь на ночь.
Выйдя утром и глядя на снег на обочине, я не могу не чувствовать, что зима близко, эй! Так знакомо, не правда ли, это реплика Ван Чжаоцзюня?
Так что я просто поговорю с тобой сегодняАлгоритм снежинки, вы можете узнать это, когда король воскреснет в одном раунде. (умер немного больше)
План этой статьи
Распределенный идентификатор
Прежде чем мы поговорим, давайте поговорим о том, что такое распределенный идентификатор, и поговорим об этом.
Предполагая, что на двух узлах, A и B, развернута система заказов, как сгенерировать идентификаторы заказов на этих двух узлах, и значения идентификаторов не могут повторяться?
То есть в распределенной системе как генерировать уникальные значения ID на разных серверах?
Обычно есть три варианта:
- Используя функцию автоинкремента базы данных, разные узлы напрямую используют идентификатор автоинкремента одной и той же базы данных.
- Сгенерировать значение идентификатора с использованием алгоритма UUID
- Сгенерируйте значение идентификатора, используя алгоритм снежинки
Хотя Java обеспечивает поддержку UUID, используйтеUUID.randomUUID()Этого достаточно, но поскольку UUID представляет собой случайную 36-битную строку, она состоит из 32 строк цифр и букв и 4 символов "-". Длина слишком длинная, читабельность для бизнеса плохая, и ее нельзя увеличить в упорядоченным образом, поэтому обычно нет, алгоритм снежинки используется чаще.
источник
Почему он называется алгоритмом снежинки?
Есть две теории о происхождении алгоритма снежинки:
- Первый: Twitter использовал язык scala для открытия исходного кода алгоритма распределенной генерации идентификаторов, алгоритма SnowFlake, который был переведен в алгоритм Snowflake.
- Второе: поскольку в природе не бывает двух одинаковых снежинок, каждая снежинка имеет свою красивую и неповторимую форму и неповторимость. Алгоритм снежинки также означает, что сгенерированные идентификаторы уникальны, как и снежинки. (Одноклассник спросил, почему это не лист, Мэйтуан зовут Лиф - Лист)
сочинение
Как выглядит идентификатор, сгенерированный алгоритмом Snowflake?
Идентификатор, сгенерированный алгоритмом снежинки, представляет собой64 bitизlongвведите номер и нажмитевозрастающая временная тенденция. Он примерно состоит из первого недопустимого символа, разницы временных меток, машинного кода и серийного номера.
Как показано на рисунке:
- Первый недопустимый символ: первый бит используется как бит знака, потому что мы генерируем положительные числа, поэтому первый бит всегда равен 0.
- Отметка времени: занимает 41 бит с точностью до миллисекунд. 41 бит лучше всего представляет
2^41-1Миллисекунды, преобразованные в единицу года 69 лет. - Машинный код: занимает 10 бит, из которых старшие 5 бит — идентификатор центра обработки данных, а младшие 5 бит — идентификатор рабочего узла, который может вместить до 1024 узлов.
- Серийный номер: занимает 12 бит, и каждый узел начинает накапливать 0 каждую миллисекунду, до 4095, и всего может быть сгенерировано 4096 идентификаторов.
код
Реализация алгоритма, предоставленная Twitter, написана на Scala, а эта статья реализована на Java.
SnowFlake.java
/**
* 雪花算法类
* 一条coding
*/
public class SnowFlake {
//本例将10位机器码看成是“5位datacenterId+5位workerId”
private long workerId;
private long datacenterId;
//每毫秒生产的序列号之从0开始递增；
private long sequence = 0L;
/*
1288834974657L是1970-01-01 00:00:00到2010年11月04日01:42:54所经过的毫秒数；
因为现在二十一世纪的某一时刻减去1288834974657L的值，正好在2^41内。
因此1288834974657L实际上就是为了让时间戳正好在2^41内而凑出来的。
简言之，1288834974657L（即1970-01-01 00:00:00），就是在计算时间戳时用到的“起始时间”。
*/
private long twepoch = 1288834974657L;
private long workerIdBits = 5L;
private long datacenterIdBits = 5L;
private long maxWorkerId = -1L ^ (-1L <<workerIdBits);
private long maxDatacenterId = -1L ^ (-1L <<datacenterIdBits);
private long sequenceBits = 12L;
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L <<sequenceBits);
private long lastTimestamp = -1L;
public SnowFlake(long datacenterId, long workerId) {
if ((datacenterId >maxDatacenterId || datacenterId <0)
||(workerId >maxWorkerId || workerId <0)) {
throw new IllegalArgumentException("datacenterId/workerId值非法");
}
this.datacenterId = datacenterId;
this.workerId = workerId;
}
//通过SnowFlake生成id的核心算法
public synchronized long nextId() {
//获取计算id时刻的时间戳
long timestamp = System.currentTimeMillis();
if (timestamp <lastTimestamp) {
throw new RuntimeException("时间戳值非法");
}
//如果此次生成id的时间戳，与上次的时间戳相同，就通过机器码和序列号区
//分id值（机器码已通过构造方法传入）
if (lastTimestamp == timestamp) {
/*
下一条语句的作用是：通过位运算保证sequence不会超出序列号所能容纳的最大值。
例如，本程序产生的12位sequence值依次是：1、2、3、4、...、4094、4095
（4095是2的12次方的最大值，也是本sequence的最大值）
那么此时如果再增加一个sequence值（即sequence + 1），下条语句就会
使sequence恢复到0。
即如果sequence==0，就表示sequence已满。
*/
sequence = (sequence + 1) &sequenceMask;
//如果sequence已满，就无法再通过sequence区分id值；因此需要切换到
//下一个时间戳重新计算。
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
//如果此次生成id的时间戳，与上次的时间戳不同，就已经可以根据时间戳区分id值
sequence = 0L;
}
//更新最近一次生成id的时间戳
lastTimestamp = timestamp;
/*
假设此刻的值是（二进制表示）：
41位时间戳的值是：00101011110101011101011101010101111101011
5位datacenterId（机器码的前5位）的值是：01101
5位workerId（机器码的后5位）的值是：11001
sequence的值是：01001
那么最终生成的id值，就需要：
1.将41位时间戳左移动22位（即移动到snowflake值中时间戳应该出现的位置）；
2.将5位datacenterId向左移动17位，并将5位workerId向左移动12位
（即移动到snowflake值中机器码应该出现的位置）；
3.sequence本来就在最低位，因此不需要移动。
以下<<和|运算，实际就是将时间戳、机器码和序列号移动到snowflake中相应的位置。
*/
return ((timestamp - twepoch) <<timestampLeftShift)
| (datacenterId <<datacenterIdShift) | (workerId <<workerIdShift)
| sequence;
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp = System.currentTimeMillis();
/*
如果当前时刻的时间戳<=上一次生成id的时间戳，就重新生成当前时间。
即确保当前时刻的时间戳，与上一次的时间戳不会重复。
*/
while (timestamp <= lastTimestamp) {
timestamp = System.currentTimeMillis();
}
return timestamp;
}
}
TestSnowFlake.java
/**
* 测试类
* 一条coding
*/
public class TestSnowFlake {
//测试1秒能够生成的id个数
public static void generateIdsInOneSecond() {
SnowFlake idWorker = new SnowFlake(1, 1);
long start = System.currentTimeMillis();
int i = 0;
for (; System.currentTimeMillis() - start <1000; i++) {
idWorker.nextId();
}
long end = System.currentTimeMillis();
System.out.println("耗时："+ (end - start));
System.out.println("生成id个数："+ i);
}
public static void main(String[] args) {
generateIdsInOneSecond();
}
}
Результаты теста
сомневаться
Есть ли недостатки у алгоритма Snowflake?
- Должен ли идентификатор, сгенерированный алгоритмом Snowflake, быть уникальным?
- Машинный код может вмещать до 1024 узлов, а если больше 1024?
- Почему идентификатор автоинкремента базы данных не использует алгоритм снежинки?
Не паникуйте, я расскажу вам об этих проблемах в следующем выпуске.
нажмитеПолучите маршрут Java Manucing и 100 электронных книг, участвуйте в технологии вместе, введите большой завод, а поболтать о жизни!