雪花算法的原理场景和解决的问题packagecom.quanyu.algorithm.snowflake;/** * 雪花算法(Snowflake)ID生成器 * * 核心思想 * 1.不依赖数据库/Redis * 2.本地生成高性能 * 3.全局唯一、趋势递增 */publicclassSnowflakeIdGenerator{/** 起始时间戳可自定义例如项目上线时间 * 单位毫秒 * 作用压缩时间戳长度让41位时间戳能用几十年 * 建议设置为系统上线时间 * * */privatefinallongtwepoch1700000000000L;/** 位段划分 * 64位Long的组成部分 * |1bit符合位|41bit时间戳|5bit数据中心|5bit机器|12bit序列号| * *//**机器编号占用的位数(5bit最多32台机器)*/privatefinallongworkerIdBits5L;/**数据中心编号占用的位数(5bit最多32个数据中心)*/privatefinallongdatacenterIdBits5L;/**同一毫秒内自增序列号占用的位数(12bit每毫秒4096个ID)*/privatefinallongsequenceBits12L;/** * 最大取值范围 * 用于校验workerId/datacenterId是否合法 *//**workerId 最大值2^5-1 31 */privatefinallongmaxWorkerId~(-1LworkerIdBits);/**datacenterId最大值2^5-131*/privatefinallongmaxDatacenterId~(-1LdatacenterIdBits);/*** * 位移偏移量 * 决定每一段在64位ID中的位置 *//** workerId左移12位(放在序列号左边) */privatefinallongworkerIdShiftsequenceBits;/** datacenterId左移17位(125) */privatefinallongdatacenterIdShiftsequenceBitsworkerIdBits;/** 时间戳左移22位(1255)*/privatefinallongtimestampShiftsequenceBitsworkerIdBitsdatacenterIdBits;/** 序列号掩码 * 用于限制序列号不超过4095 * 超过则从0重新开始 * * */privatefinallongsequenceMask~(-1LsequenceBits);/** * 运行时状态变量 *//** 机器编号(必须全局唯一)*/privatelongworkerId;/** 数据中心编号(必须全局唯一)*/privatelongdatacenterId;/**当前毫秒内的自增序号*/privatelongsequence0L;/**上一次生成ID的时间戳(用于判断是否同一毫秒)*/privatelonglastTimestamp-1L;/** * 构造函数 * param workerId 机器编号 * param datacenterId 数据中心编号 */publicSnowflakeIdGenerator(longworkerId,longdatacenterId){if(workerIdmaxWorkerId||workerId0){thrownewIllegalArgumentException(workerId 超出范围);}if(datacenterIdmaxDatacenterId||datacenterId0){thrownewIllegalArgumentException(datacenterId 超出范围);}this.workerIdworkerId;this.datacenterIddatacenterId;}/** * 生成下一个全局唯一ID(核心方法) * return 64位 Long 类型ID */publicsynchronizedlongnextId(){longtimestamptimeGen();// 时钟回拨保护// 如果系统时间被回调直接拒绝生成避免ID重复if(timestamplastTimestamp){thrownewRuntimeException(系统时钟回退拒绝生成 ID);}// 同一毫秒内 if(timestamplastTimestamp){//序列号1sequence(sequence1)sequenceMask;//当前毫秒的4096个ID用完了if(sequence0){// 自旋等待下一毫秒timestamptilNextMillis(lastTimestamp);}}else{// 进入新的一毫秒 //序列号重置为0sequence0L;}//记录上一次生成时间lastTimestamptimestamp;/** * 拼接最终的64位ID * * 结构 * |符号位|时间戳差值|数据中心|机器|序列号| */return((timestamp-twepoch)timestampShift)// 337544129309310976 0100 1010 1111 0011 0010 1001 1000 1110 0011 1000 0000 0000 0000 0000 0000 timestampshift22|(datacenterIddatacenterIdShift)//datacenterId1 datacenterId datacenterIdShift131072 对应的二进制0010 0000 0000 0000 0000 位移的位数datacenterIdShift17|(workerIdworkerIdShift)//workId1 workerId workerIdShift4096 对应的二进制 0001 0000 0000 0000 位移的位数workerIdShift12|sequence;//0 对应的字节码 0000 0000 0000 最终结果0100 1010 1111 0011 0010 1001 1000 1110 0011 1000 0010 0001 0000 0000 0000// 0100 1010 1111 0011 0010 1001 1000 1110 0011 1000 0010 0001 0000 0000 0000}/** * 阻塞直到下一毫秒到来 * 防止当前毫秒内ID用尽之后继续生成重复ID * */privatelongtilNextMillis(longlastTimestamp){longtimestamptimeGen();while(timestamplastTimestamp){timestamptimeGen();}returntimestamp;}/** * 获取当前系统时间(毫秒) * return */privatelongtimeGen(){returnSystem.currentTimeMillis();}}绝大多数场景下引入Snowflake算法后就不需要redis/数据库号段这种集中式分布式ID生成器了。这也是它最大的优势-去中心化。但在实际生产中通常需要Snowflake算法加一个简单的分配机制(不一定是Redis)“来配合使用”。1.什么时候可以不用Redis,什么时候还需要Redis、以及为什么你的分库分表场景最适合Snowflake。一、为什么说用了Snowflake就不需要Redis了Snowflake的设计初衷就是为了摆脱对中间件的强依赖。方案是否需要Redis/DB原理缺点Redis自增必须INCR order:id网络开销、Redis挂了全站瘫痪、扩容麻烦数据库号段必须批量取号(如Leaf)数据库压力大、架构重UUID不需要随机生成无序、不适合做数据库主键Snowflake不需要本地内存计算依赖机器时钟核心区别:Redis方案是应用-请求Redis-拿到IDSnowflake方案是应用-直接计算ID(本地CPU算)Snowflake的速度比Redis快一个数量级且没有网络瓶颈。二、那为什么还说用Redis分配WorkerId?这是一个概念混淆代码里面有这两个参数:new SnowflakeIdGenerator(workerId,datacenterId)这里的workerId和datacenterId必须在所有机器上唯一否则会生成重复ID。1.不需要Redis的情况(推荐)如果服务是部署在Kubernetes(K8S)或Docker Swarm里Pod序号(0,1,2…)天然就是唯一的workerId。直接读取环境变量即可完全不需要Redis。2.可能需要Redis/Zookeeper的情况如果是传统物理机部署且机器经常上下线需要一个地方记录哪台机器用了哪个ID。这是可以用Redis/Etcd/Zookeeper只做一次注册而不是每次生成ID都访问它们。注意Redis此时只负责分配身份证号不参与生成ID的过程。三、分库分表场景为什么Snowflake是最佳解回到订单的分库分表long orderId snowflake.nextId(); int tableIndex (int)(orderId % 16);为什么Snowflake完美适配分库分表1.趋势递增(Trend Increasing)MySQL InnoDB引擎的主键是聚簇索引。如果用UUID(完全随机)插入会导致页分裂性能极差。Snowflake生成的ID是随时间变大的插入性能最好。2.无中心化(No SPoF)双十一大促时Redis往往是瓶颈。Snowflake跑在每个应用JVM里机器越多生成能力越强。3.自带业务含义(可选)你可以从ID里反解出: 机房、机器、生成时间。这在排查问题(比如查某笔订单是哪台机器生成的)时非常有用。四、什么时候不能只用Snowflake?(必坑指南)虽然不用Redis生成ID但是必须解决下面几个问题否则会出事故1.时钟回拨问题(最致命)如果服务器时间被NTP同步回退了代码会直接throw new RuntimeException.生产建议改为等待时钟追上或启用备用workerId。2.WorkerId冲突如果两台机器的workerId不小心配成一样的生成重复的订单号。解决一定要有一套自动化分配机制(脚本、配置中心、K8S环境变量)3.时间位数耗尽41位时间戳大约能用69年。对于普通公司足够但别把twepoch设得太早。最终建议(标准答案)针对场景最终架构是应用内嵌Snowflake算法配置中心管理WorkerId具体落地ID生成使用刚才那段Java Snowflake代码(本地生成不用Redis)。WorkerId分配K8S用StatefulSet的Pod序号。物理机用IP地址的后几位或者用Apollo/Nacos配置。分库分表路由直接用orderId % N。总结一句话Snowflake本身就是一种分布式ID生成器。它不需要Redis来生成ID但在部署时你可能需要一个简单的注册表(不一定是Redis)来管理每台机器的编号。
手写雪花算法
雪花算法的原理场景和解决的问题packagecom.quanyu.algorithm.snowflake;/** * 雪花算法(Snowflake)ID生成器 * * 核心思想 * 1.不依赖数据库/Redis * 2.本地生成高性能 * 3.全局唯一、趋势递增 */publicclassSnowflakeIdGenerator{/** 起始时间戳可自定义例如项目上线时间 * 单位毫秒 * 作用压缩时间戳长度让41位时间戳能用几十年 * 建议设置为系统上线时间 * * */privatefinallongtwepoch1700000000000L;/** 位段划分 * 64位Long的组成部分 * |1bit符合位|41bit时间戳|5bit数据中心|5bit机器|12bit序列号| * *//**机器编号占用的位数(5bit最多32台机器)*/privatefinallongworkerIdBits5L;/**数据中心编号占用的位数(5bit最多32个数据中心)*/privatefinallongdatacenterIdBits5L;/**同一毫秒内自增序列号占用的位数(12bit每毫秒4096个ID)*/privatefinallongsequenceBits12L;/** * 最大取值范围 * 用于校验workerId/datacenterId是否合法 *//**workerId 最大值2^5-1 31 */privatefinallongmaxWorkerId~(-1LworkerIdBits);/**datacenterId最大值2^5-131*/privatefinallongmaxDatacenterId~(-1LdatacenterIdBits);/*** * 位移偏移量 * 决定每一段在64位ID中的位置 *//** workerId左移12位(放在序列号左边) */privatefinallongworkerIdShiftsequenceBits;/** datacenterId左移17位(125) */privatefinallongdatacenterIdShiftsequenceBitsworkerIdBits;/** 时间戳左移22位(1255)*/privatefinallongtimestampShiftsequenceBitsworkerIdBitsdatacenterIdBits;/** 序列号掩码 * 用于限制序列号不超过4095 * 超过则从0重新开始 * * */privatefinallongsequenceMask~(-1LsequenceBits);/** * 运行时状态变量 *//** 机器编号(必须全局唯一)*/privatelongworkerId;/** 数据中心编号(必须全局唯一)*/privatelongdatacenterId;/**当前毫秒内的自增序号*/privatelongsequence0L;/**上一次生成ID的时间戳(用于判断是否同一毫秒)*/privatelonglastTimestamp-1L;/** * 构造函数 * param workerId 机器编号 * param datacenterId 数据中心编号 */publicSnowflakeIdGenerator(longworkerId,longdatacenterId){if(workerIdmaxWorkerId||workerId0){thrownewIllegalArgumentException(workerId 超出范围);}if(datacenterIdmaxDatacenterId||datacenterId0){thrownewIllegalArgumentException(datacenterId 超出范围);}this.workerIdworkerId;this.datacenterIddatacenterId;}/** * 生成下一个全局唯一ID(核心方法) * return 64位 Long 类型ID */publicsynchronizedlongnextId(){longtimestamptimeGen();// 时钟回拨保护// 如果系统时间被回调直接拒绝生成避免ID重复if(timestamplastTimestamp){thrownewRuntimeException(系统时钟回退拒绝生成 ID);}// 同一毫秒内 if(timestamplastTimestamp){//序列号1sequence(sequence1)sequenceMask;//当前毫秒的4096个ID用完了if(sequence0){// 自旋等待下一毫秒timestamptilNextMillis(lastTimestamp);}}else{// 进入新的一毫秒 //序列号重置为0sequence0L;}//记录上一次生成时间lastTimestamptimestamp;/** * 拼接最终的64位ID * * 结构 * |符号位|时间戳差值|数据中心|机器|序列号| */return((timestamp-twepoch)timestampShift)// 337544129309310976 0100 1010 1111 0011 0010 1001 1000 1110 0011 1000 0000 0000 0000 0000 0000 timestampshift22|(datacenterIddatacenterIdShift)//datacenterId1 datacenterId datacenterIdShift131072 对应的二进制0010 0000 0000 0000 0000 位移的位数datacenterIdShift17|(workerIdworkerIdShift)//workId1 workerId workerIdShift4096 对应的二进制 0001 0000 0000 0000 位移的位数workerIdShift12|sequence;//0 对应的字节码 0000 0000 0000 最终结果0100 1010 1111 0011 0010 1001 1000 1110 0011 1000 0010 0001 0000 0000 0000// 0100 1010 1111 0011 0010 1001 1000 1110 0011 1000 0010 0001 0000 0000 0000}/** * 阻塞直到下一毫秒到来 * 防止当前毫秒内ID用尽之后继续生成重复ID * */privatelongtilNextMillis(longlastTimestamp){longtimestamptimeGen();while(timestamplastTimestamp){timestamptimeGen();}returntimestamp;}/** * 获取当前系统时间(毫秒) * return */privatelongtimeGen(){returnSystem.currentTimeMillis();}}绝大多数场景下引入Snowflake算法后就不需要redis/数据库号段这种集中式分布式ID生成器了。这也是它最大的优势-去中心化。但在实际生产中通常需要Snowflake算法加一个简单的分配机制(不一定是Redis)“来配合使用”。1.什么时候可以不用Redis,什么时候还需要Redis、以及为什么你的分库分表场景最适合Snowflake。一、为什么说用了Snowflake就不需要Redis了Snowflake的设计初衷就是为了摆脱对中间件的强依赖。方案是否需要Redis/DB原理缺点Redis自增必须INCR order:id网络开销、Redis挂了全站瘫痪、扩容麻烦数据库号段必须批量取号(如Leaf)数据库压力大、架构重UUID不需要随机生成无序、不适合做数据库主键Snowflake不需要本地内存计算依赖机器时钟核心区别:Redis方案是应用-请求Redis-拿到IDSnowflake方案是应用-直接计算ID(本地CPU算)Snowflake的速度比Redis快一个数量级且没有网络瓶颈。二、那为什么还说用Redis分配WorkerId?这是一个概念混淆代码里面有这两个参数:new SnowflakeIdGenerator(workerId,datacenterId)这里的workerId和datacenterId必须在所有机器上唯一否则会生成重复ID。1.不需要Redis的情况(推荐)如果服务是部署在Kubernetes(K8S)或Docker Swarm里Pod序号(0,1,2…)天然就是唯一的workerId。直接读取环境变量即可完全不需要Redis。2.可能需要Redis/Zookeeper的情况如果是传统物理机部署且机器经常上下线需要一个地方记录哪台机器用了哪个ID。这是可以用Redis/Etcd/Zookeeper只做一次注册而不是每次生成ID都访问它们。注意Redis此时只负责分配身份证号不参与生成ID的过程。三、分库分表场景为什么Snowflake是最佳解回到订单的分库分表long orderId snowflake.nextId(); int tableIndex (int)(orderId % 16);为什么Snowflake完美适配分库分表1.趋势递增(Trend Increasing)MySQL InnoDB引擎的主键是聚簇索引。如果用UUID(完全随机)插入会导致页分裂性能极差。Snowflake生成的ID是随时间变大的插入性能最好。2.无中心化(No SPoF)双十一大促时Redis往往是瓶颈。Snowflake跑在每个应用JVM里机器越多生成能力越强。3.自带业务含义(可选)你可以从ID里反解出: 机房、机器、生成时间。这在排查问题(比如查某笔订单是哪台机器生成的)时非常有用。四、什么时候不能只用Snowflake?(必坑指南)虽然不用Redis生成ID但是必须解决下面几个问题否则会出事故1.时钟回拨问题(最致命)如果服务器时间被NTP同步回退了代码会直接throw new RuntimeException.生产建议改为等待时钟追上或启用备用workerId。2.WorkerId冲突如果两台机器的workerId不小心配成一样的生成重复的订单号。解决一定要有一套自动化分配机制(脚本、配置中心、K8S环境变量)3.时间位数耗尽41位时间戳大约能用69年。对于普通公司足够但别把twepoch设得太早。最终建议(标准答案)针对场景最终架构是应用内嵌Snowflake算法配置中心管理WorkerId具体落地ID生成使用刚才那段Java Snowflake代码(本地生成不用Redis)。WorkerId分配K8S用StatefulSet的Pod序号。物理机用IP地址的后几位或者用Apollo/Nacos配置。分库分表路由直接用orderId % N。总结一句话Snowflake本身就是一种分布式ID生成器。它不需要Redis来生成ID但在部署时你可能需要一个简单的注册表(不一定是Redis)来管理每台机器的编号。
