предисловие
Привет всем, меня зовут этн, это моя двенадцатая статья, и сегодня я познакомим вас с алгоритмом снежинка. Введение алгоритма снежинки является вторичным, потому что каждый с ним слишком знаком, главная цель - порекомендовать мою новую серию. Сегодня, на прихоти, я хотел создать новую серию. Эта серия в основном хранит алгоритмы, используемые в нашей ежедневной разработке работ, таких как алгоритм снежинки, хэш-алгоритм и так далее. В Интернете все еще много знаний об этих алгоритмах, но это очень сложно. Нелегко найти алгоритм, и вы должны прочитать все виды блога. Поэтому наша текущая идея состоит в том, чтобы сортировать эти алгоритмы вместе и использовать их все
goРеализация с подробными документами, такими как базовые знания и описания кода, так что, когда мы хотим изучить новый алгоритм, мы можем найти его здесь, если нет, мы можем отправить егоissuesИдеальный кусок. В настоящее время он только начался, и сейчас есть только кодовый документ алгоритма снежинки, который в дальнейшем будет постепенно улучшаться.Заинтересованные друзья могут присоединиться, и мы будем совершенствоваться вместе. Подробности смотрите в описании на github:GitHub.com/Assong2020/…
Фон алгоритма снежинки
Фон, сгенерированный алгоритмом снежинки, конечно же,twitterНеобходимость генерации уникальных идентификаторов в среде с высокой степенью параллелизма выигрывает отtwitterВнутренняя превосходная технология, алгоритм снежинки, может быть распространена и по сей день и широко используется, поскольку имеет несколько характеристик.
- Он может соответствовать требованиям неповторяющихся идентификаторов в распределенной системной среде с высокой степенью параллелизма.
- Высокая эффективность генерации
- Базовые упорядоченные приращения могут быть гарантированы на основе временных меток.
- Отсутствие зависимости от сторонних библиотек или промежуточного ПО
- Сгенерировано
idСвоевременность и уникальность
Принцип алгоритма снега
Давайте сначала посмотрим на картинку из Интернета:
Из рисунка мы видим, чтоsnowFlake IDСтруктура 64-битнаяintтип данных.
- 1-й бит
Самый высокий бит в двоичном - 1, указывающий на отрицательный, потому что мы используемidДолжны быть все целые числа, поэтому старший бит здесь должен быть равен 0.
- 41-битная метка времени
41 бит может представлять2^41-1Число, если оно используется только для представления положительных целых чисел, диапазон значений, которые могут быть представлены, составляет: 0 - (2 ^ 41 -1), причина вычитания 1 здесь заключается в том, что диапазон значений рассчитывается от 0, а не от 1 из.
Единицей здесь являются миллисекунды, поэтому 41 бит может представлять2^41-1значение миллисекунды, поэтому преобразованное в единицу года равно (2^41-1)/(1000 * 60 * 60 * 24 * 365) = 69
- 10bit - рабочая машина ID
Вот идентификатор, используемый для записи рабочих машин.2^10=1024Указывает, что текущее правило допускает максимальное количество распределенных узлов, равное 1024 узлам. В том числе 5workerIDи 5-битныйdataCenterID, здесь на самом деле нет различия, но мой код ниже делает различие.
- 12-битный серийный номер
Используется для записи различных идентификаторов, сгенерированных в течение одной миллисекунды. Наибольшее положительное целое число, которое может представлять 12 бит, равно2^12-1=4095, который можно использовать0,1,2,3,......4094Этот4095Число, представляющее 4095 идентификационных серийных номеров, сгенерированных в пределах одной временной метки (миллисекунды) одним и тем же компьютером.
Принцип выше, сложностей нет, посмотрим как реализован код:
Go реализует алгоритм снежинки
1. Определите основные константы
Давайте сначала посмотрим на код, и мы представим его по очереди:
const (
workerIDBits = uint64(5) // 10bit 工作机器ID中的 5bit workerID
dataCenterIDBits = uint64(5) // 10 bit 工作机器ID中的 5bit dataCenterID
sequenceBits = uint64(12)
maxWorkerID = int64(-1) ^ (int64(-1) << workerIDBits) //节点ID的最大值 用于防止溢出
maxDataCenterID = int64(-1) ^ (int64(-1) << dataCenterIDBits)
maxSequence = int64(-1) ^ (int64(-1) << sequenceBits)
timeLeft = uint8(22) // timeLeft = workerIDBits + sequenceBits // 时间戳向左偏移量
dataLeft = uint8(17) // dataLeft = dataCenterIDBits + sequenceBits
workLeft = uint8(12) // workLeft = sequenceBits // 节点IDx向左偏移量
// 2020-05-20 08:00:00 +0800 CST
twepoch = int64(1589923200000) // 常量时间戳(毫秒)
)
Каждая из констант этого кода объясняется ниже:
-
worerIDBits: Вот соответствующий 10-битный идентификатор машины на рисунке выше, я разделяю здесь. Это одна 5-битная``woreridbits` -
dataCenterIDBits: Вот идентификатор 10-битной рабочей машины, соответствующий изображению выше, я разделил его здесь. это 5битdataCenterIDBits -
sequenceBits: Соответствует 12-битному серийному номеру на картинке выше. -
maxWorkerID: Здесь максимум, но мы используем метод XOR, потому что двоичное представление -1 является дополнением до 1. Говоря более популярно, вот на самом деле2^5-1, Студенты, которые еще не знают, вы можете проверить это сами -
maxDataCenterID: Принцип тот же, что и выше -
maxSequence: Принцип тот же, что и выше -
timeLeft: Отметка времени смещена влево, так что вы можете не понять.Глядя на картинку выше, смещение влево равно 22. Вы понимаете? -
dataLeft: Принцип тот же, что и выше, и смещение также рассчитывается -
workLeft: Принцип тот же, что и выше; -
twepoch: 41-битная временная метка в миллисекундах, здесь я выбираю время2020-05-20 08:00:00 +0800 CST, этот идентификатор не следует изменять после его создания, иначе будет сгенерирован тот же идентификатор.
2. Определенияworkerрабочий узел
Поскольку это алгоритм генерации идентификатора, используемый в распределенной среде, нам нужно сгенерировать несколькоworkerТак что абстрактные параметры узла.
type Worker struct {
mu sync.Mutex
LastStamp int64 // 记录上一次ID的时间戳
WorkerID int64 // 该节点的ID
DataCenterID int64 // 该节点的 数据中心ID
Sequence int64 // 当前毫秒已经生成的ID序列号(从0 开始累加) 1毫秒内最多生成4096个ID
}
Объяснение кода:
-
mu sync.Mutex: добавьте мьютекс для обеспечения безопасности параллелизма. -
LastStamp int64: запись временной метки последнего поколения ID -
WorkerID int64: идентификатор рабочего узла имеет значение для 5-битного идентификатора рабочего узла на приведенном выше рисунке. -
DataCenterID int64: тот же принцип, что и выше -
Sequence int64: порядковый номер идентификатора, который был сгенерирован за текущую миллисекунду (начиная с 0). Максимум 4096 идентификаторов генерируется в течение 1 миллисекунды.
3. Создайтеworkerобъект
//分布式情况下,我们应通过外部配置文件或其他方式为每台机器分配独立的id
func NewWorker(workerID,dataCenterID int64) *Worker {
return &Worker{
WorkerID: workerID,
LastStamp: 0,
Sequence: 0,
DataCenterID: dataCenterID,
}
}
Здесь нечего объяснять.
4. Сгенерировать идентификатор
Сначала посмотрите на код:
func (w *Worker) getMilliSeconds() int64 {
return time.Now().UnixNano() / 1e6
}
func (w *Worker)NextID() (uint64,error) {
w.mu.Lock()
defer w.mu.Unlock()
return w.nextID()
}
func (w *Worker)nextID() (uint64,error) {
timeStamp := w.getMilliSeconds()
if timeStamp < w.LastStamp{
return 0,errors.New("time is moving backwards,waiting until")
}
if w.LastStamp == timeStamp{
w.Sequence = (w.Sequence + 1) & maxSequence
if w.Sequence == 0 {
for timeStamp <= w.LastStamp {
timeStamp = w.getMilliSeconds()
}
}
}else {
w.Sequence = 0
}
w.LastStamp = timeStamp
id := ((timeStamp - twepoch) << timeLeft) |
(w.DataCenterID << dataLeft) |
(w.WorkerID << workLeft) |
w.Sequence
return uint64(id),nil
}
Код немного длинный, поэтому позвольте мне объяснить его по очереди:
-
getMilliSeconds(): метод, инкапсулированный для получения текущего значения миллисекунды. func (w *Worker)NextID() (uint64,error)
Содержимое этого кода ничего не значит, конкретный алгоритм идентификатора поколения инкапсулирован вfunc (w *Worker)nextID() (uint64,error)Здесь это просто для понимания эффекта сцепления, кстати, есть особенно важное место, блокировка и снятие блокировки, этот шаг очень важен.
func (w *Worker)nextID() (uint64,error)
Вот фактически сгенерированный идентификационный код. Делится на несколько шагов:
- Получите текущую временную метку и оцените.Убедитесь, что текущее значение временной метки больше, чем временная метка последнего поколения идентификатора, иначе будут дубликаты.
- Если вы хотите подождать, сначала получите порядковый номер идентификатора, который был сгенерирован текущей миллисекундой. Вы можете не понять здесь, на самом деле он эквивалентен
if w.sequence++ > maxSequence
, Если порядковый номер идентификатора, сгенерированный в текущей миллисекунде, переполняется, вам нужно подождать следующую миллисекунду. Если вы не дождетесь, это вызовет много повторений.
-
мы будем в другом
w.sequenceОн установлен равным нулю. Объясните здесь. Если текущее время не соответствует последнему времени, когда идентификатор был сгенерирован рабочим узлом, серийный номер идентификатора, сгенерированного рабочим узлом, необходимо сбросить. -
Последний шаг, который является более важным, использует операцию ИЛИ. Цель здесь состоит в том, чтобы вернуть биты каждой части и интегрировать их с помощью операции побитового ИЛИ (то есть этого '|').
<<Это функция смещения влево для возврата в исходное положение, и|Расчет для интеграции. Может быть вы не поняли, посмотрите на картинку ниже:
Откуда, ты знаешь, что это значит?
5. Тест
Письменный код, мы должны тестировать его, а вот я согласующуюся 10000goroutineГенерируем ID, сохраняем в карту и проверяем, нет ли дубликатов, смотрим на код:
var wg sync.WaitGroup
func main() {
w := idgen.NewWorker(5,5)
ch := make(chan uint64,10000)
count := 10000
wg.Add(count)
defer close(ch)
//并发 count个goroutine 进行 snowFlake ID 生成
for i:=0 ; i < count ; i++ {
go func() {
defer wg.Done()
id,_ := w.NextID()
ch <- id
}()
}
wg.Wait()
m := make(map[uint64]int)
for i := 0; i < count; i++ {
id := <- ch
// 如果 map 中存在为 id 的 key, 说明生成的 snowflake ID 有重复
_, ok := m[id]
if ok {
fmt.Printf("repeat id %d\n",id)
return
}
// 将 id 作为 key 存入 map
m[id] = i
}
// 成功生成 snowflake ID
fmt.Println("All", len(m), "snowflake ID Get successed!")
}
Результаты проверки:
All 10000 snowflake ID Get successed!
Суммировать
На этом статья заканчивается. Алгоритм снежинки не так сложен, как мы думаем, но его все равно очень легко реализовать. Вы его изучили? Неважно, если вы его не изучили, скачайте исходный код и посмотрите еще раз, для вас это не проблема~~~.
Гитхаб:GitHub.com/Assong2020/…Добро пожаловать, звезда, спасибо всем ~~~
Друзья, помните, что я сказал в начале? Желающие могут присоединиться, давайте развиваться вместе.
Напоследок дам небольшое пособие.Недавно читаю книгу [Паттерны проектирования архитектуры микросервисов], очень хорошая.Также собрал PDF.Кому нужно,могут скачать сами. Как получить: Подпишитесь на официальный аккаунт: [Golang DreamWorks], ответ за кулисами: [Microservice], вы можете его получить.
Я перевел документ GIN на китайский язык, который будет регулярно обновляться. Если он вам нужен, вы можете загрузить его, ответив на [gin] в фоновом режиме.
Я Асонг, обычный программист, дайте мне стать сильнее вместе. Я построил один самgolangГруппа для общения, нуждающиеся друзья добавляйте меняvx, я тяну вас в группу. Приветствую всеобщее внимание, увидимся в следующем выпуске~~~
Рекомендуемая последующая статья:
-
Для подробного объяснения пакета Context достаточно этой статьи! ! !
-
Для начала работы с go-ElasticSearch достаточно прочитать эту статью (1)
-
Интервьюер: Вы использовали for-range в го? Можете ли вы объяснить причины этих вопросов?
-
На самом деле так просто научиться внедрению зависимостей проводов и запланированным задачам cron!
-
Я слышал, что ты не знаешь jwt и swagger-meal, я даже не ем его, и я приду с практическим проектом.
-
Освойте эти особенности языка го, ваш уровень повысится на N баллов (2)
-
босс: Этот ребенок не будет использовать библиотеку валидатора для проверки данных, откройте ее~~~