当前位置:首页 > 数码 > b-分布式唯一ID生成原理-b-雪花算法详解与Java实现 (分布式怎么理解)

b-分布式唯一ID生成原理-b-雪花算法详解与Java实现 (分布式怎么理解)

admin4周前 (04-25)数码17

概述

SnowFlake 算法是一种开源的分布式 ID 生成算法,其核心思想是使用一个 64 位的 long 型数字作为全局唯一 ID。它在分布式系统中广泛应用,并且 ID 引入了时间戳,基本保持自增。 分布式怎么理解

算法原理

64 位 long 型数字的分配如下: 1 位:不使用(二进制中第一个位为 1 表示负数,而 ID 都是正数) 41 位:毫秒数(可以表示 2^41-1 个毫秒值,约为 69 年) 10 位:工作机器 ID(最多支持部署在 1024 台机器上) 12 位:序列号(同一个毫秒内最多可生成 4096 个 ID)

算法实现

以下是一个 SnowFlake 算法的 Java 代码实现示例: ```java public class IdWorker { private static final long workerId = 12; // 机器 ID private static final long datacenterId = 17; // 机房 ID private static final long twepoch = 1577836800; // 开始时间戳(2020-01-01 00:00:00) private static final long workerIdBits = 5L; private static final long datacenterIdBits = 5L; private static final long sequenceBits = 12L; private static final long maxWorkerId = -1L ^ (-1L << workerIdBits); private static final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); private static final long sequenceMask = -1L ^ (-1L << sequenceBits); private long lastTimestamp = -1L; private long sequence =0L; public long getId() { long timestamp = System.currentTimeMillis(); if (timestamp < lastTimestamp) { throw new IllegalArgumentException("时钟不能回拨"); } if (timestamp == lastTimestamp) { sequence = (sequence + 1) & sequenceMask; if (sequence == 0L) { timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0L; } lastTimestamp = timestamp; // 组成 64 位 ID long id = ((timestamp - twepoch) << (workerIdBits + datacenterIdBits + sequenceBits)) | (datacenterId << (workerIdBits + sequenceBits)) | (workerId << sequenceBits) | sequence; return id; } private long tilNextMillis(long lastTimestamp) { long timestamp = System.currentTimeMillis(); while (timestamp <= lastTimestamp) { timestamp = System.currentTimeMillis(); } return timestamp; } } ```

局限性

SnowFlake 算法的局限性在于其依赖于系统时间的准确性。如果系统时间被回调或改变,可能会导致 ID 冲突或重复。

改进

在实际应用中,我们通常没有那么多机房。因此,我们可以优化算法,将 10 位的工作机器 ID 替换为与业务相关的标识。

结论

SnowFlake 算法是一种简单且有效的分布式 ID 生成算法。它广泛应用于分布式系统中,但需要确保系统时间的准确性。通过优化算法,我们可以使其更加灵活地满足不同的业务需求。

分布式ID生成器

在分布式系统中,往往需要对大量的数据和消息进行唯一标识,此时一个能够生成全局唯一ID的系统是非常必要的,那么业务系统对ID号的要求有哪些呢?

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,示例:5e8c4456-6166-40d6-9b9f-fb37a150bc6e,到目前为止业界一共有5种方式生成UUI,Java标准类库中已经提供了UUID的API。

优点:

缺点:

类snowflake方案

雪花ID生成的是一个64位的二进制正整数,然后转换成10进制的数。64位二进制数由如下部分组成:

41-bit的时间可以表示(1L<<41)/(1000L*3600*24*365)=69年的时间,10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求,还可以将10-bit分5-bit给IDC,分5-bit给工作机器。这样就可以表示32个IDC,每个IDC下可以有32台机器,可以根据自身需求定义。12个自增序列号可以表示2^12个ID,理论上snowflake方案的QPS约为409.6w/s,这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

但是对于绝大部分普通应用程序来说,根本不需要每秒超过400万的ID,机器数量也达不到1024台,所以,我们可以改进一下,使用更短的ID生成方式:53bitID由32bit秒级时间戳+16bit自增+5bit机器标识组成,累积32台机器,每秒可以生成6.5万个序列号。

代码示例

最后,为什么采用最多53位整型,而不是64位整型?这是因为考虑到大部分应用程序是Web应用,如果要和JavaScript打交道,由于JavaScript支持的最大整型就是53位,超过这个位数,JavaScript将丢失精度。因此,使用53位整数可以直接由JavaScript读取,而超过53位时,就必须转换成字符串才能保证JavaScript处理正确,这会给API接口带来额外的复杂度。

参考资料:

生成19位不重复的纯数字随机ID方法之一

在设计随机ID生成方法之前,我通常会考虑这么几个问题: 1、长度多长,是否定长? 2、是否要求纯数字? 3、是否有分布式的要求? 4、业务量是多大?每毫秒至少要求几个序列号? 以上问题是基于常见的随机ID算法提出的,例如UUID,雪花算法等。 随机ID的生成常常会涉及到时间戳,MAC地址,ip地址的提取,因此会有第3问和第4问。 生成随机数的方法有很多,我们需要根据业务场景来设计合适自己的。 本文的业务场景是,线下业务员手动生成订单时,需要随机生成订单号,原先的老系统直接调取了公司统一封装的UUID包,但是做Java改造时发现没有Java版本,所以只能自己设计。 场景具备以下特点: 1、要求与老系统逻辑保持不变,订单号必须是19位定长的纯数字 2、没有专门的自增序列表可以用 3、业务量小。 并发很低 4、不是单机,涉及分布式环境 按照通常的做法,我先取了13 位的currentMillis,再取系统ip,ip保留最后两段共6位,不足6位用0补齐。 这么做的原因是在同一环境下,ip的前两段通常是相同的,保留下来没有太大的意义,而且长度的限制摆在这。 这样算下来,时间戳+ip 刚好19位,同一毫秒只能有一笔订单。 很显然这样的重复几率有点太大了。 但是又不能超过长度,最后我选定的方法是,舍弃时间戳的第一位,留一位用来做序列。 12位的时间戳会在30年左右重复,以当前的业务场景来看是符合要求的。 那么最后这个id的生成方式就变成了 12位时间戳 + 6位ip + 1位自增序列。 虽然是分布式环境,但是序列并没有分布式,而是维护在了本地。 原因很简单,序列的目的是让同一机器同一毫秒下不出现重复订单号即可,因此本地自增是完全可行的。 而且重启后重新从0开始问题也不大。 只要一毫秒落地的订单不超过10笔就完全没问题。 这样的做法显然不是特别优雅,特别是截取一位时间戳的操作可能会被吐槽。 但是在这特定的条件和业务场景下,这也是我能想出的比较好的办法了。 后续有新的想法,我会在这里补充。

免责声明:本文转载或采集自网络,版权归原作者所有。本网站刊发此文旨在传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及版权、内容等问题,请联系本网,我们将在第一时间删除。同时,本网站不对所刊发内容的准确性、真实性、完整性、及时性、原创性等进行保证,请读者仅作参考,并请自行核实相关内容。对于因使用或依赖本文内容所产生的任何直接或间接损失,本网站不承担任何责任。

标签: 雪花算法

“b-分布式唯一ID生成原理-b-雪花算法详解与Java实现 (分布式怎么理解)” 的相关文章

雪花算法与散布式ID生成-粗浅了解其原理-长处与运行 (雪花算法优缺点)

雪花算法与散布式ID生成-粗浅了解其原理-长处与运行 (雪花算法优缺点)

生成全局惟一ID的雪花算法原理 雪花算法是一种用于生成全局惟一ID的算法,最后由开发,用于处置散布式系统中生成ID的疑问。其外围现实是将一个64位的长整型ID划分红多个局部,每个局部用于示意...