道客网站建设推广小程序,网站建设合肥,网站优化图片,2008iis添加网站打不开分布式全局id
snowflake 算法是 twitter 开源的分布式 id 生成算法#xff0c;采用 Scala 语言实现#xff0c;是把一个 64 位的 long 型的 id#xff0c;1 个 bit 是不用的#xff0c;用其中的 41 bits 作为毫秒数#xff0c;用 10 bits 作为工作机器 id#xff0c;12 …分布式全局id
snowflake 算法是 twitter 开源的分布式 id 生成算法采用 Scala 语言实现是把一个 64 位的 long 型的 id1 个 bit 是不用的用其中的 41 bits 作为毫秒数用 10 bits 作为工作机器 id12 bits 作为序列号。
1 bit不用为啥呢因为二进制里第一个 bit 为如果是 1那么都是负数但是我们生成的 id 都是正数所以第一个 bit 统一都是 0。41 bits表示的是时间戳单位是毫秒。41 bits 可以表示的数字多达 2^41 - 1 也就是可以标识 2^41 - 1 个毫秒值换算成年就是表示 69 年的时间。10 bits记录工作机器 id代表的是这个服务最多可以部署在 2 ^ 10 台机器上也就是 1024 台机器。但是 10 bits 里 5 个 bits 代表机房 id5 个 bits 代表机器 id。意思就是最多代表 2^5 个机房32 个机房每个机房里可以代表 2^5 个机器32 台机器。12 bits这个是用来记录同一个毫秒内产生的不同 id12 bits 可以代表的最大正整数是 2^12 - 1 4096 也就是说可以用这个 12 bits 代表的数字来区分同一个毫秒内的 4096 个不同的 id。
0 | 0001100 10100010 10111110 10001001 01011100 00 | 10001 | 1 1001 | 0000 00000000:::details 实现不用看有工具实现得更好
public class IdWorker {private long workerId;private long datacenterId;private long sequence;public IdWorker(long workerId, long datacenterId, long sequence) {// sanity check for workerId// 这儿不就检查了一下要求就是你传递进来的机房id和机器id不能超过32不能小于0if (workerId maxWorkerId || workerId 0) {throw new IllegalArgumentException(String.format(worker Id cant be greater than %d or less than 0, maxWorkerId));}if (datacenterId maxDatacenterId || datacenterId 0) {throw new IllegalArgumentException(String.format(datacenter Id cant be greater than %d or less than 0, maxDatacenterId));}System.out.printf(worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d,timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);this.workerId workerId;this.datacenterId datacenterId;this.sequence sequence;}private long twepoch 1288834974657L;private long workerIdBits 5L;private long datacenterIdBits 5L;// 这个是二进制运算就是 5 bit最多只能有31个数字也就是说机器id最多只能是32以内private long maxWorkerId -1L ^ (-1L workerIdBits);// 这个是一个意思就是 5 bit最多只能有31个数字机房id最多只能是32以内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 long getWorkerId() {return workerId;}public long getDatacenterId() {return datacenterId;}public long getTimestamp() {return System.currentTimeMillis();}public synchronized long nextId() {// 这儿就是获取当前时间戳单位是毫秒long timestamp timeGen();if (timestamp lastTimestamp) {System.err.printf(clock is moving backwards. Rejecting requests until %d., lastTimestamp);throw new RuntimeException(String.format(Clock moved backwards. Refusing to generate id for %d milliseconds, lastTimestamp - timestamp));}if (lastTimestamp timestamp) {// 这个意思是说一个毫秒内最多只能有4096个数字// 无论你传递多少进来这个位运算保证始终就是在4096这个范围内避免你自己传递个sequence超过了4096这个范围sequence (sequence 1) sequenceMask;if (sequence 0) {timestamp tilNextMillis(lastTimestamp);}} else {sequence 0;}// 这儿记录一下最近一次生成id的时间戳单位是毫秒lastTimestamp timestamp;// 这儿就是将时间戳左移放到 41 bit那儿// 将机房 id左移放到 5 bit那儿// 将机器id左移放到5 bit那儿将序号放最后12 bit// 最后拼接起来成一个 64 bit的二进制数字转换成 10 进制就是个 long 型return ((timestamp - twepoch) timestampLeftShift) | (datacenterId datacenterIdShift)| (workerId workerIdShift) | sequence;}private long tilNextMillis(long lastTimestamp) {long timestamp timeGen();while (timestamp lastTimestamp) {timestamp timeGen();}return timestamp;}private long timeGen() {return System.currentTimeMillis();}// ---------------测试---------------public static void main(String[] args) {IdWorker worker new IdWorker(1, 1, 1);for (int i 0; i 30; i) {System.out.println(worker.nextId());}}}:::
思考
需要用到雪花算法一般都是大型分布式系统而分布式意味着同一套代码的重复部署所以上面的雪花算法还有两个最重要的问题没有解决。
分布式系统中的workerId/datacenterId 怎么确保强唯一timeStamp 怎么确保系统时钟不回拨
业界大牛的实现
https://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万。 https://tech.meituan.com/2017/04/21/mt-leaf.html 在复杂分布式系统中往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中数据日渐增长对数据分库分表后需要有一个唯一ID来标识一条数据或消息数据库的自增ID显然不能满足需求特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。概括下来那业务系统对ID号的要求有哪些呢 全局唯一性不能出现重复的ID号既然是唯一标识这是最基本的要求。趋势递增在MySQL InnoDB引擎中使用的是聚集索引由于多数RDBMS使用B-tree的数据结构来存储索引数据在主键的选择上面我们应该尽量使用有序的主键保证写入性能。单调递增保证下一个ID一定大于上一个ID例如事务版本号、IM增量消息、排序等特殊需求。信息安全如果ID是连续的恶意用户的扒取工作就非常容易做了直接按照顺序下载指定URL即可如果是订单号就更危险了竞对可以直接知道我们一天的单量。所以在一些应用场景下会需要ID无规则、不规则。
