SnowFlake唯一ID生成器_春哥大魔王的博客-CSDN博客
写在前面
架构是权衡的结果，架构也是一层层的组件拼接起来的，如果没有好用的组件，架构势必会做阉割，架构的理想态是建立在一堆友好、易用、标准化的组件之上的。在我过去的经验中，有两类组件经常会出现在我的架构方案中，一个是唯一ID生成器，一个是推拉结合配置中心，有了他们我可以解决分布式系统下的时序问题，不会再因数据不一致问题手足无措，推拉结合的数据中心也让架构的事件驱动能力成为可能。
今天简单聊下分布式唯一ID生成器。
SnowFlake最早应该是Twitter提出的。SnowFlake生成一个64bit大小的整数，结构如下：
- 1 位，不用。二进制中最高位为 1 的都是负数，但是我们生成的 id 一般都使用整数，所以这个最高位固定是 0。
- 41 位，用来记录时间戳（毫秒）。41 位可以表示 2^41 个数字；如果只用来表示正整数（计算机中正数包含 0），可以表示的数值范围是：0 至 2^41−1，也就是说 41 位可以表示 2^41 个毫秒的值，转化成单位年则是 2^41 / (1000 60 60 24 365) = 69年。
- 10 位，用来记录工作机器 id，可以部署在 2^10 = 1024个节点，包括 5 位 idcId 和 5 位 workerId ；5 位（bit）可以表示的最大正整数是2^5-1 = 31，即可以用 0、1、2、3、....31 这 32 个数字，来表示不同的 idcId 或 workerId。
- 12 位，序列号，用来记录同毫秒内产生的不同 id。12位（bit）可以表示的最大正整数是 2^12-1 =4095，即可以用 0、1、2、3、....4095 这 4096 个数字，来表示同一机器同一时间段（毫秒）内产生的 4096 个ID序号。
所以SnowFlake可以保证生成的ID按时间趋势递增（不是严格的递增），由于有了idc和worker的区分，整个分布式系统内不会产生重复的id。
在生产环境服务是无状态的，特别是在容器时代，容器指定固定ID不太现实，这是我们可以基于Redis/Tair/MySql等存储生成服务自增的hostid，作为全局的idcId和workerId，因为机器数量普遍较少，对于存储压力不大，运行时根据当前host获取存储的IdcId和workerId，结合SnowFlake生成唯一分布式id。
SnowFlake实现时需要考虑两个问题。
- 时钟回拨问题
机器的时间不是严格一致的，可能会出现几毫秒的差别，如果基于这个错误时间生成的id，可能会出现重复的id。
解决方案是，进程启动之后，我们将当前时间作为分布式id服务的起始时间并记录下来，后续的递增操作是在这个时间片内的递增+1，当到达这个时间窗口最大值时，时间戳+1，到达下一个时间窗口，序号归0，为解决不同容器启动延迟问题，一般的开始时间是采用了延迟10s的处理。
- 机器id分配及回收
前面说了，应用服务是无状态的，每台机器的id都是不一样的，而且在运行时，每台机器都有可能宕机，也可能扩容，如果机器宕了对应生成的id应该怎么处理才能不产生数据问题呢？
方案是前面介绍的，基于MySql、Tair等为每一个host生成一个idcId/workerId，这样服务启动或是宕机其实还是可以把之前生成的id续上的，机器下线不销毁生成的id。维护一个活跃的服务节点队列，节点有值代表节点活跃，则跳过，否则占用此节点，当地址空间满之后调整指针回到头部。这样可以复用已经生成的id，不会浪费掉。
如果自己写一个SnowFlake应该怎么搞呢？
写一个Java版的SnowFlake
核心算法：
public class SnowFlake { /* 起始时间戳 */ private final static long START_TIMESTAMP = 1611573333870L; /* 序号占用的位数 */ private final static long SEQUENCE_BIT = 12; /* 机器标识占用的位数 */ private final static long MACHINE_BIT = 5; /* 数据中心占用的位数 */ private final static long IDC_BIT = 5; /* 数据中心位数最大值 */ private final static long MAX_IDC_NUM = ~(-1L << IDC_BIT); /* 机器标识位数最大值 */ private final static long MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT); /* 序号占用位数最大值 */ private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT); /* 各部分索引 */ private final static long MACHINE_INDEX = SEQUENCE_BIT; private final static long IDC_INDEX = SEQUENCE_BIT + MACHINE_BIT; private final static long TIMESTAMP_INDEX = IDC_INDEX + IDC_BIT; /* 数据中心标识 */ private long idcId; /* 机器标识 */ private long machineId; /* 序列号 */ private long sequence = 0L; /* 上一次时间戳 */ private long lastStamp = -1L; public SnowFlake(long idcId, long machineId) { if (idcId > MAX_IDC_NUM || idcId < 0) { throw new IllegalArgumentException("idcId error"); } if (machineId > MAX_MACHINE_NUM || machineId < 0) { throw new IllegalArgumentException("machineId error"); } this.idcId = idcId; this.machineId = machineId; } /** * ID生成 * * @return */ public synchronized long generateId() { long currentTime = getCurrentTime(); // 时钟回拨，抛异常 if (currentTime < lastStamp) { throw new RuntimeException("clock moved backwards. Refusing to generate id"); } // 同一毫秒内，做自增处理 if (currentTime == lastStamp) { sequence = (sequence + 1) & MAX_SEQUENCE; // 位运算，同一毫秒序列数达到最大 if (sequence == 0L) { currentTime = getNextMillis(); } } else { // 下一毫秒，从0开始 sequence = 0L; } lastStamp = currentTime; // 位或计算 return (currentTime - START_TIMESTAMP) << TIMESTAMP_INDEX // 时间戳部分值 | idcId << IDC_INDEX // 数据中心部分值 | machineId << MACHINE_INDEX // 机器标识部分值 | sequence; // 序号递增部分值 } /** * 获取当前毫秒 * * @return */ private long getCurrentTime(){ return System.currentTimeMillis(); } /** * 获取下一毫秒 * * @return */ private long getNextMillis(){ long millis = getCurrentTime(); while (millis <= lastStamp){ millis = getCurrentTime(); } return millis; }}测试一下：
public class IDTest { private final static ExecutorService bizExecutorService = Executors.newFixedThreadPool(2); public static void main(String[] args) { bizExecutorService.execute(new Runnable() { @Override public void run() { long maxId = 0L; SnowFlake snowFlake = new SnowFlake(2, 10); for (int i = 0; i < 100; i++) { long id = snowFlake.generateId(); System.out.println("id = " + id); if (maxId <= id) { maxId = id; System.out.println("true index = " + i); } } } }); }}输出结果：
id = 20122937106432true index = 0id = 20122941300736true index = 1id = 20122941300737true index = 2id = 20122941300738true index = 3id = 20122941300739true index = 4id = 20122941300740true index = 5id = 20122941300741true index = 6id = 20122941300742true index = 7id = 20122941300743true index = 8id = 20122941300744true index = 9id = 20122941300745true index = 10id = 20122941300746true index = 11id = 20122941300747true index = 12id = 20122941300748true index = 13id = 20122941300749true index = 14id = 20122941300750true index = 15id = 20122941300751true index = 16id = 20122941300752true index = 17id = 20122941300753true index = 18id = 20122941300754true index = 19id = 20122945495040true index = 20id = 20122945495041true index = 21id = 20122945495042true index = 22id = 20122945495043true index = 23id = 20122945495044true index = 24id = 20122945495045true index = 25id = 20122945495046true index = 26id = 20122945495047true index = 27id = 20122945495048true index = 28id = 20122945495049true index = 29id = 20122945495050true index = 30id = 20122945495051true index = 31id = 20122945495052true index = 32id = 20122945495053true index = 33id = 20122945495054true index = 34id = 20122945495055true index = 35id = 20122945495056true index = 36id = 20122945495057true index = 37id = 20122945495058true index = 38id = 20122949689344true index = 39id = 20122949689345true index = 40id = 20122949689346true index = 41id = 20122949689347true index = 42id = 20122949689348true index = 43id = 20122949689349true index = 44id = 20122949689350true index = 45id = 20122949689351true index = 46id = 20122949689352true index = 47id = 20122949689353true index = 48id = 20122949689354true index = 49id = 20122949689355true index = 50id = 20122949689356true index = 51id = 20122949689357true index = 52id = 20122949689358true index = 53id = 20122949689359true index = 54id = 20122949689360true index = 55id = 20122949689361true index = 56id = 20122949689362true index = 57id = 20122949689363true index = 58id = 20122953883648true index = 59id = 20122953883649true index = 60id = 20122953883650true index = 61id = 20122953883651true index = 62id = 20122953883652true index = 63id = 20122953883653true index = 64id = 20122953883654true index = 65id = 20122953883655true index = 66id = 20122953883656true index = 67id = 20122953883657true index = 68id = 20122953883658true index = 69id = 20122953883659true index = 70id = 20122953883660true index = 71id = 20122953883661true index = 72id = 20122953883662true index = 73id = 20122953883663true index = 74id = 20122953883664true index = 75id = 20122953883665true index = 76id = 20122953883666true index = 77id = 20122953883667true index = 78id = 20122958077952true index = 79id = 20122958077953true index = 80id = 20122958077954true index = 81id = 20122958077955true index = 82id = 20122958077956true index = 83id = 20122958077957true index = 84id = 20122958077958true index = 85id = 20122958077959true index = 86id = 20122958077960true index = 87id = 20122958077961true index = 88id = 20122958077962true index = 89id = 20122958077963true index = 90id = 20122958077964true index = 91id = 20122958077965true index = 92id = 20122958077966true index = 93id = 20122958077967true index = 94id = 20122958077968true index = 95id = 20122958077969true index = 96id = 20122962272256true index = 97id = 20122962272257true index = 98id = 20122962272258true index = 99通过输出值看起来是递增的。
推荐阅读：https://my.oschina.net/u/1000241/blog/3048980
原网址: 访问
创建于: 2022-07-11 09:43:40
目录: default
标签: 无
未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到
最新评论