分布式ID神器之雪花算法简介

一、简介

　　雪花算法这一在分布式架构中很常见的玩意，但一般也不需要怎么去深入了解，一方面一般个人项目用不到分布式之类的大型架构，另一方面，就算要用到，市面上很多ID生成器也帮我们完成了这项工作。

二、分布式ID的特点

全局唯一性

　　　　不能出现有重复的ID标识，这是基本要求。

递增性

　　　　确保生成ID对于用户或业务是递增的。

高可用性

　　　　确保任何时候都能生成正确的ID。

高性能性

　　　　在高并发的环境下依然表现良好。

三、分布式ID的常见解决方案

3.1 UUID

　　Java自带的生成一串唯一随机36位字符串（32个字符串+4个“-”）的算法。它可以保证唯一性，且据说够用N亿年，但是其业务可读性差，无法有序递增。

3.2 SnowFlake

今天的主角雪花算法，它是Twitter开源的由64位整数组成分布式ID，性能较高，并且在单机上递增。具体参考：https://github.com/twitter-archive/snowflake

3.3 UidGenerator

UidGenerator是百度开源的分布式ID生成器，其基于雪花算法实现。具体参考：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

3.4 Leaf

Leaf是美团开源的分布式ID生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper等中间件。具体参考：https://tech.meituan.com/MT_Leaf.html

四、雪花算法

4.1 简介

　　SnowFlake是Twitter公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的ID。

4.2 组成部分（64bit）

　　1、第一位占用1bit，其值始终是0，没有实际作用。

　　2、时间戳占用41bit，精确到毫秒，总共可以容纳约69年的时间。

　　3、工作机器id 占用10bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID，做多可以容纳1024个节点。 4.序列号占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生4096个ID。

　　SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢：：同一毫秒的ID数量 = 1024 X 4096 = 4194304。

4.3 雪花算法的实现

　　雪花算法的实现主要依赖于数据中心ID和数据节点ID这两个参数，具体实现如下。

4.3.1 头文件Snowflake.h

　　源码如下：

  1 /*
  2 *
  3 * 文件名称：Snowflake.h
  4 * 文件标识：
  5 * 摘    要：通过SnowFlake算法生成一个64位大小的分布式自增长id
  6 *
  7 */
  8  
  9 #ifndef __SNOWFLAKE_H__
 10 #define __SNOWFLAKE_H__
 11  
 12 #include <mutex>
 13 #include <atomic>
 14  
 15 //#define SNOWFLAKE_ID_WORKER_NO_LOCK
 16 typedef unsigned int UInt;
 17 typedef unsigned long UInt64;
 18  
 19 #ifdef SNOWFLAKE_ID_WORKER_NO_LOCK
 20 typedef std::atomic<UInt> AtomicUInt;
 21 typedef std::atomic<UInt64> AtomicUInt64;
 22 #else
 23 typedef UInt AtomicUInt;
 24 typedef UInt64 AtomicUInt64;
 25 #endif
 26  
 27 namespace service{
 28     class Snowflake
 29     {
 30     public:
 31         Snowflake(void);
 32         ~Snowflake(void);
 33  
 34         void setHostId(UInt HostId)
 35         {
 36             m_HostId = HostId;
 37         }
 38         void setWorkerId(UInt workerId)
 39         {
 40             m_WorkerId = workerId;
 41         }
 42         UInt64 GetId()
 43         {
 44             return GetDistributedId();
 45         }
 46  
 47     private:
 48         UInt64 GetTimeStamp();
 49         UInt64 tilNextMillis(UInt64 lastTimestamp);
 50         UInt64 GetDistributedId();
 51  
 52     private:
 53  
 54 #ifndef SNOWFLAKE_ID_WORKER_NO_LOCK
 55         std::mutex mutex;
 56 #endif
 57  
 58         /**
 59         * 开始时间截 (2019-09-30 00:00:00.000)
 60         */
 61         const UInt64 twepoch = 1569772800000;
 62  
 63         /**
 64         * worker进程映射id所占的位数
 65         */
 66         const UInt workerIdBits = 5;
 67  
 68         /**
 69         * 服务器id所占的位数
 70         */
 71         const UInt hostIdBits = 5;
 72  
 73         /**
 74         * 序列所占的位数
 75         */
 76         const UInt sequenceBits = 12;
 77  
 78         /**
 79         * worker进程映射ID向左移12位
 80         */
 81         const UInt workerIdShift = sequenceBits;
 82  
 83         /**
 84         * 服务器id向左移17位
 85         */
 86         const UInt hostIdShift = workerIdShift + workerIdBits;
 87  
 88         /**
 89         * 时间截向左移22位
 90         */
 91         const UInt timestampLeftShift = hostIdShift + hostIdBits;
 92  
 93         /**
 94         * 支持的worker进程映射id，结果是31
 95         */
 96         const UInt maxWorkerId = -1 ^ (-1 << workerIdBits);
 97  
 98         /**
 99         * 支持的服务器id，结果是31
100         */
101         const UInt maxHostId = -1 ^ (-1 << hostIdBits);
102  
103         /**
104         * 生成序列的掩码，这里为4095
105         */
106         const UInt sequenceMask = -1 ^ (-1 << sequenceBits);
107  
108         /**
109         * worker进程映射id(0~31)
110         */
111         UInt m_WorkerId;
112  
113         /**
114         * 服务器id(0~31)
115         */
116         UInt m_HostId;
117  
118         /**
119         * 毫秒内序列(0~4095)
120         */
121         AtomicUInt sequence{ 0 };
122  
123         /**
124         * 上次生成ID的时间截
125         */
126         AtomicUInt64 lastTimestamp{ 0 };
127     };
128 }
129 #endif

View Code

4.3.2 头文件Snowflake.cpp

　　源码如下：

 1 #include "Snowflake.h"
 2 #include <chrono>
 3 #include <exception>
 4 #include <sstream>
 5  
 6 namespace service
 7 {
 8     Snowflake::Snowflake(void)
 9     {
10         m_HostId = 0;
11         m_WorkerId = 0;
12         sequence = 0;
13         lastTimestamp = 0;
14     }
15  
16     Snowflake::~Snowflake(void)
17     {
18     }
19  
20     UInt64 Snowflake::GetTimeStamp()
21     {
22         auto t = std::chrono::time_point_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now());
23         return t.time_since_epoch().count();
24     }
25  
26     UInt64 Snowflake::tilNextMillis(UInt64 lastTimestamp)
27     {
28         UInt64 timestamp = GetTimeStamp();
29         while (timestamp <= lastTimestamp) {
30             timestamp = GetTimeStamp();
31         }
32         return timestamp;
33     }
34  
35     UInt64 Snowflake::GetDistributedId()
36     {
37 #ifndef SNOWFLAKE_ID_WORKER_NO_LOCK
38         std::unique_lock<std::mutex> lock{ mutex };
39         AtomicUInt64 timestamp{ 0 };
40 #else
41         static AtomicUInt64 timestamp{ 0 };
42 #endif
43  
44         timestamp = GetTimeStamp();
45         // 如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
46         if (timestamp < lastTimestamp) {
47             std::ostringstream s;
48             s << "clock moved backwards.  Refusing to generate id for " << lastTimestamp - timestamp << " milliseconds";
49             throw std::exception(std::runtime_error(s.str()));
50         }
51  
52         if (lastTimestamp == timestamp) {
53             // 如果是同一时间生成的，则进行毫秒内序列
54             sequence = (sequence + 1) & sequenceMask;
55             if (0 == sequence) {
56                 // 毫秒内序列溢出, 阻塞到下一个毫秒,获得新的时间戳
57                 timestamp = tilNextMillis(lastTimestamp);
58             }
59         }
60         else {
61             sequence = 0;
62         }
63  
64 #ifndef SNOWFLAKE_ID_WORKER_NO_LOCK
65         lastTimestamp = timestamp;
66 #else
67         lastTimestamp = timestamp.load();
68 #endif
69  
70         // 移位并通过或运算拼到一起组成64位的ID
71         return ((timestamp - twepoch) << timestampLeftShift)
72             | (m_HostId << hostIdShift)
73             | (m_WorkerId << workerIdShift)
74             | sequence;
75     }
76 }

View Code

五、参考文章

https://www.cnblogs.com/ForestCherry/p/13217802.html

https://zhuanlan.zhihu.com/p/85837641

本文来自博客园，作者：Mr-xxx，转载请注明原文链接：https://www.cnblogs.com/MrLiuZF/p/15171384.html