手机搭建网站软件,个人网页的内容模板设计,微信网站下载,网站可视化后台#x1f4dd;个人主页#xff1a;五敷有你 #x1f525;系列专栏#xff1a;算法分析与设计
⛺️稳中求进#xff0c;晒太阳 算法具体介绍
雪花算法是 64 位 的二进制#xff0c;一共包含了四部分#xff1a;
1位是符号位#xff0c;也就是最高位#xff0c;… 个人主页五敷有你 系列专栏算法分析与设计
⛺️稳中求进晒太阳 算法具体介绍
雪花算法是 64 位 的二进制一共包含了四部分
1位是符号位也就是最高位始终是0没有任何意义因为要是唯一计算机二进制补码中就是负数0才是正数。41位是时间戳具体到毫秒41位的二进制可以使用69年因为时间理论上永恒递增所以根据这个排序是可以的。10位是机器标识可以全部用作机器ID也可以用来标识机房ID 机器ID10位最多可以表示1024台机器。12位是计数序列号也就是同一台机器上同一时间理论上还可以同时生成不同的ID12位的序列号能够区分出4096个ID。 优化
由于41位是时间戳我们的时间计算是从1970年开始的只能使用69年为了不浪费其实我们可以用时间的相对值也就是以项目开始的时间为基准时间往后可以使用69年。获取唯一ID的服务对处理速度要求比较高所以我们全部使用位运算以及位移操作获取当前时间可以使用System.currentTimeMillis()。
时间回拨问题
在获取时间的时候可能会出现时间回拨的问题什么是时间回拨问题呢就是服务器上的时间突然倒退到之前的时间。
人为原因把系统环境的时间改了。有时候不同的机器上需要同步时间可能不同机器之间存在误差那么可能会出现时间回拨问题。
解决方案
回拨时间小的时候不生成 ID循环等待到时间点到达。上面的方案只适合时钟回拨较小的如果间隔过大阻塞等待肯定是不可取的因此要么超过一定大小的回拨直接报错拒绝服务或者有一种方案是利用拓展位回拨之后在拓展位上加1就可以了这样ID依然可以保持唯一。但是这个要求我们提前预留出位数要么从机器id中要么从序列号中腾出一定的位在时间回拨的时候这个位置 1。
由于时间回拨导致的生产重复的ID的问题其实百度和美团都有自己的解决方案了有兴趣可以去看看下面不是它们官网文档的信息
百度UIDGeneratorhttps://github.com/baidu/uid-generator/blob/master/README.zh_cn.md UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。美团Leaf:https://tech.meituan.com/2019/03/07/open-source-project-leaf.html leaf-segment 方案 优化双buffer 预分配容灾Mysql DB 一主两从异地机房半同步方式缺点如果用segment号段式方案id是递增可计算的不适用于订单ID生成场景比如竞对在两天中午12点分别下单通过订单id号相减就能大致计算出公司一天的订单量这个是不能忍受的。 leaf-snowflake方案 使用Zookeeper持久顺序节点的特性自动对snowflake节点配置workerID 1.启动Leaf-snowflake服务连接Zookeeper在leaf_forever父节点下检查自己是否已经注册过是否有该顺序子节点。2.如果有注册过直接取回自己的workerIDzk顺序节点生成的int类型ID号启动服务。3.如果没有注册过就在该父节点下面创建一个持久顺序节点创建成功后取回顺序号当做自己的workerID号启动服务。 缓存workerID减少第三方组件的依赖由于强依赖时钟对时间的要求比较敏感在机器工作时NTP同步也会造成秒级别的回退建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE等时钟追上即可。或者做一层重试然后上报报警系统更或者是发现有时钟回拨之后自动摘除本身节点并报警
