1. 首页
  2. IT资讯

分布式id生成器

“u003Cdivu003Eu003Cpu003E作者:CoderZSu003Cu002Fpu003Eu003Cpu003E链接:https:u002Fu002Fjuejin.imu002Fpostu002F5d8882d8f265da03e369c063u003Cu002Fpu003Eu003Cpu003E来源:掘金u003Cu002Fpu003Eu003Cpu003E在高并发或者分表分库情况下怎么保证数据id的幂等性呢u003Cu002Fpu003Eu003Cpu003E经常用到的解决方案有以下几种。u003Cu002Fpu003Eu003Cblockquoteu003Eu003Cpu003E微软公司通用唯一识别码(UUID)u003Cu002Fpu003Eu003Cpu003ETwitter公司雪花算法(SnowFlake) u003Cu002Fpu003Eu003Cpu003E基于数据库的id自增 u003Cu002Fpu003Eu003Cpu003E对id进行缓存u003Cu002Fpu003Eu003Cu002Fblockquoteu003Eu003Cpu003E这里我们要谈到snowflake算法了u003Cu002Fpu003Eu003Cblockquoteu003Eu003Cpu003Esnowflake是Twitter开源的分布式ID生成算法,结果是一个long型的ID。其核心思想是:使用41bit作为毫秒数,10bit作为机器的ID(5个bit是数据中心,5个bit的机器ID),12bit作为毫秒内的流水号,最后还有一个符号位,永远是0。 u003Cstrongu003Esnowflake算法所生成的ID结构u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cu002Fblockquoteu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002Ffff84031ff774796bef0525f7baa7a01″ img_width=”1021″ img_height=”346″ alt=”分布式id生成器” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cblockquoteu003Eu003Cpu003E整个结构是64位,所以我们在Java中可以使用long来进行存储。 该算法实现基本就是二进制操作,单机每秒内理论上最多可以生成1024*(2^12),也就是409.6万个ID(1024 X 4096 = 4194304)u003Cu002Fpu003Eu003Cu002Fblockquoteu003Eu003Cpreu003E u003Cbru003E * 0 – 0000000000 0000000000 0000000000 0000000000 0 – 00000 – 00000 – 000000000000 u003Cbru003E * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>u003Cbru003E * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 – 开始时间截)u003Cbru003E * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) u002F (1000L * 60 * 60 * 24 * 365) = 69<br>u003Cbru003E * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>u003Cbru003E * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>u003Cbru003E * 加起来刚好64位,为一个Long型。<br>u003Cbru003E * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。u003Cbru003E复制代码u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003EsnowFlake算法的优点:u003Cu002Fpu003Eu003Cblockquoteu003Eu003Cpu003E1.生成ID时不依赖于DB,完全在内存生成,高性能高可用。 2.ID呈趋势递增,后续插入索引树的时候性能较好。u003Cu002Fpu003Eu003Cu002Fblockquoteu003Eu003Cpu003ESnowFlake算法的缺点:u003Cu002Fpu003Eu003Cblockquoteu003Eu003Cpu003E依赖于系统时钟的一致性。如果某台机器的系统时钟回拨,有可能造成ID冲突,或者ID乱序u003Cu002Fpu003Eu003Cu002Fblockquoteu003Eu003Cpu003E算法代码如下u003Cu002Fpu003Eu003Cpreu003Epublic class SnowflakeIdWorker {u003Cbru003E u002Fu002F ==============================Fields==================u003Cbru003E u002F** 开始时间截 (2019-08-06) *u002Fu003Cbru003E private final long twepoch = 1565020800000L;u003Cbru003E u002F** 机器id所占的位数 *u002Fu003Cbru003E private final long workerIdBits = 5L;u003Cbru003E u002F** 数据标识id所占的位数 *u002Fu003Cbru003E private final long datacenterIdBits = 5L;u003Cbru003E u002F** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) *u002Fu003Cbru003E private final long maxWorkerId = -1L ^ (-1L << workerIdBits);u003Cbru003E u002F** 支持的最大数据标识id,结果是31 *u002Fu003Cbru003E private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);u003Cbru003E u002F** 序列在id中占的位数 *u002Fu003Cbru003E private final long sequenceBits = 12L;u003Cbru003E u002F** 机器ID向左移12位 *u002Fu003Cbru003E private final long workerIdShift = sequenceBits;u003Cbru003E u002F** 数据标识id向左移17位(12+5) *u002Fu003Cbru003E private final long datacenterIdShift = sequenceBits + workerIdBits;u003Cbru003E u002F** 时间截向左移22位(5+5+12) *u002Fu003Cbru003E private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;u003Cbru003E u002F** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) *u002Fu003Cbru003E private final long sequenceMask = -1L ^ (-1L << sequenceBits);u003Cbru003E u002F** 工作机器ID(0~31) *u002Fu003Cbru003E private long workerId;u003Cbru003E u002F** 数据中心ID(0~31) *u002Fu003Cbru003E private long datacenterId;u003Cbru003E u002F** 毫秒内序列(0~4095) *u002Fu003Cbru003E private long sequence = 0L;u003Cbru003E u002F** 上次生成ID的时间截 *u002Fu003Cbru003E private long lastTimestamp = -1L;u003Cbru003E u002Fu002F==============================Constructors====================u003Cbru003E u002F**u003Cbru003E * 构造函数u003Cbru003E * @param workerId 工作ID (0~31)u003Cbru003E * @param datacenterId 数据中心ID (0~31)u003Cbru003E *u002Fu003Cbru003E public SnowflakeIdWorker(long workerId, long datacenterId) {u003Cbru003E if (workerId > maxWorkerId || workerId < 0) {u003Cbru003E throw new IllegalArgumentException(String.format(“worker Id can’t be greater than %d or less than 0”, maxWorkerId));u003Cbru003E }u003Cbru003E if (datacenterId > maxDatacenterId || datacenterId < 0) {u003Cbru003E throw new IllegalArgumentException(String.format(“datacenter Id can’t be greater than %d or less than 0”, maxDatacenterId));u003Cbru003E }u003Cbru003E this.workerId = workerId;u003Cbru003E this.datacenterId = datacenterId;u003Cbru003E }u003Cbru003E u002Fu002F ==============================Methods=================================u003Cbru003E u002F**u003Cbru003E * 获得下一个ID (该方法是线程安全的)u003Cbru003E * @return SnowflakeIdu003Cbru003E *u002Fu003Cbru003E public synchronized long nextId() {u003Cbru003E long timestamp = timeGen();u003Cbru003E u002Fu002F如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常u003Cbru003E if (timestamp < lastTimestamp) {u003Cbru003E throw new RuntimeException(u003Cbru003E String.format(“Clock moved backwards. Refusing to generate id for %d milliseconds”, lastTimestamp – timestamp));u003Cbru003E }u003Cbru003E u002Fu002F如果是同一时间生成的,则进行毫秒内序列u003Cbru003E if (lastTimestamp == timestamp) {u003Cbru003E sequence = (sequence + 1) & sequenceMask;u003Cbru003E u002Fu002F毫秒内序列溢出u003Cbru003E if (sequence == 0) {u003Cbru003E u002Fu002F阻塞到下一个毫秒,获得新的时间戳u003Cbru003E timestamp = tilNextMillis(lastTimestamp);u003Cbru003E }u003Cbru003E }u003Cbru003E u002Fu002F时间戳改变,毫秒内序列重置u003Cbru003E else {u003Cbru003E sequence = 0L;u003Cbru003E }u003Cbru003E u002Fu002F上次生成ID的时间截u003Cbru003E lastTimestamp = timestamp;u003Cbru003E u002Fu002F移位并通过或运算拼到一起组成64位的IDu003Cbru003E return ((timestamp – twepoch) << timestampLeftShift) u002Fu002Fu003Cbru003E | (datacenterId << datacenterIdShift) u002Fu002Fu003Cbru003E | (workerId << workerIdShift) u002Fu002Fu003Cbru003E | sequence;u003Cbru003E }u003Cbru003E u002F**u003Cbru003E * 阻塞到下一个毫秒,直到获得新的时间戳u003Cbru003E * @param lastTimestamp 上次生成ID的时间截u003Cbru003E * @return 当前时间戳u003Cbru003E *u002Fu003Cbru003E protected long tilNextMillis(long lastTimestamp) {u003Cbru003E long timestamp = timeGen();u003Cbru003E while (timestamp <= lastTimestamp) {u003Cbru003E timestamp = timeGen();u003Cbru003E }u003Cbru003E return timestamp;u003Cbru003E }u003Cbru003E u002F**u003Cbru003E * 返回以毫秒为单位的当前时间u003Cbru003E * @return 当前时间(毫秒)u003Cbru003E *u002Fu003Cbru003E protected long timeGen() {u003Cbru003E return System.currentTimeMillis();u003Cbru003E }u003Cbru003E u002Fu002F==============================Test=============================================u003Cbru003E u002F** 测试 *u002Fu003Cbru003E public static void main(String[] args) {u003Cbru003E SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);u003Cbru003E for (int i = 0; i < 1000; i++) {u003Cbru003E long id = idWorker.nextId();u003Cbru003E System.out.println(Long.toBinaryString(id));u003Cbru003E System.out.println(id);u003Cbru003E }u003Cbru003E }u003Cbru003E}u003Cbru003E复制代码u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E快速使用snowflake算法只需以下几步u003Cu002Fpu003Eu003Cpu003E引入hutool依赖u003Cu002Fpu003Eu003Cpreu003E<dependency>u003Cbru003E <groupId>cn.hutool<u002FgroupId>u003Cbru003E <artifactId>hutool-captcha<u002FartifactId>u003Cbru003E <version>${hutool.version}<u002Fversion>u003Cbru003E<u002Fdependency>u003Cbru003E复制代码u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003EID 生成器u003Cu002Fpu003Eu003Cpreu003Epublic class IdGenerator {u003Cbru003E private long workerId = 0;u003Cbru003E @PostConstructu003Cbru003E void init() {u003Cbru003E try {u003Cbru003E workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());u003Cbru003E log.info(“当前机器 workerId: {}”, workerId);u003Cbru003E } catch (Exception e) {u003Cbru003E log.warn(“获取机器 ID 失败”, e);u003Cbru003E workerId = NetUtil.getLocalhost().hashCode();u003Cbru003E log.info(“当前机器 workerId: {}”, workerId);u003Cbru003E }u003Cbru003E }u003Cbru003E u002F**u003Cbru003E * 获取一个批次号,形如 2019071015301361000101237u003Cbru003E * <p>u003Cbru003E * 数据库使用 char(25) 存储u003Cbru003E *u003Cbru003E * @param tenantId 租户ID,5 位u003Cbru003E * @param module 业务模块ID,2 位u003Cbru003E * @return 返回批次号u003Cbru003E *u002Fu003Cbru003E public synchronized String batchId(int tenantId, int module) {u003Cbru003E String prefix = DateTime.now().toString(DatePattern.PURE_DATETIME_MS_PATTERN);u003Cbru003E return prefix + tenantId + module + RandomUtil.randomNumbers(3);u003Cbru003E }u003Cbru003E @Deprecatedu003Cbru003E public synchronized String getBatchId(int tenantId, int module) {u003Cbru003E return batchId(tenantId, module);u003Cbru003E }u003Cbru003E u002F**u003Cbru003E * 生成的是不带-的字符串,类似于:b17f24ff026d40949c85a24f4f375d42u003Cbru003E *u003Cbru003E * @returnu003Cbru003E *u002Fu003Cbru003E public String simpleUUID() {u003Cbru003E return IdUtil.simpleUUID();u003Cbru003E }u003Cbru003E u002F**u003Cbru003E * 生成的UUID是带-的字符串,类似于:a5c8a5e8-df2b-4706-bea4-08d0939410e3u003Cbru003E *u003Cbru003E * @returnu003Cbru003E *u002Fu003Cbru003E public String randomUUID() {u003Cbru003E return IdUtil.randomUUID();u003Cbru003E }u003Cbru003E private Snowflake snowflake = IdUtil.createSnowflake(workerId, 1);u003Cbru003E public synchronized long snowflakeId() {u003Cbru003E return snowflake.nextId();u003Cbru003E }u003Cbru003E public synchronized long snowflakeId(long workerId, long dataCenterId) {u003Cbru003E Snowflake snowflake = IdUtil.createSnowflake(workerId, dataCenterId);u003Cbru003E return snowflake.nextId();u003Cbru003E }u003Cbru003E u002F**u003Cbru003E * 生成类似:5b9e306a4df4f8c54a39fb0cu003Cbru003E * <p>u003Cbru003E * ObjectId 是 MongoDB 数据库的一种唯一 ID 生成策略,u003Cbru003E * 是 UUID version1 的变种,详细介绍可见:服务化框架-分布式 Unique ID 的生成方法一览。u003Cbru003E *u003Cbru003E * @returnu003Cbru003E *u002Fu003Cbru003E public String objectId() {u003Cbru003E return ObjectId.next();u003Cbru003E }u003Cbru003E}u003Cbru003E复制代码u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E测试类u003Cu002Fpu003Eu003Cpreu003Epublic class IdGeneratorTest {u003Cbru003E @Autowiredu003Cbru003E private IdGenerator idGenerator;u003Cbru003E @Testu003Cbru003E public void testBatchId() {u003Cbru003E for (int i = 0; i < 100; i++) {u003Cbru003E String batchId = idGenerator.batchId(1001, 100);u003Cbru003E log.info(“批次号: {}”, batchId);u003Cbru003E }u003Cbru003E }u003Cbru003E @Testu003Cbru003E public void testSimpleUUID() {u003Cbru003E for (int i = 0; i < 100; i++) {u003Cbru003E String simpleUUID = idGenerator.simpleUUID();u003Cbru003E log.info(“simpleUUID: {}”, simpleUUID);u003Cbru003E }u003Cbru003E }u003Cbru003E @Testu003Cbru003E public void testRandomUUID() {u003Cbru003E for (int i = 0; i < 100; i++) {u003Cbru003E String randomUUID = idGenerator.randomUUID();u003Cbru003E log.info(“randomUUID: {}”, randomUUID);u003Cbru003E }u003Cbru003E }u003Cbru003E @Testu003Cbru003E public void testObjectID() {u003Cbru003E for (int i = 0; i < 100; i++) {u003Cbru003E String objectId = idGenerator.objectId();u003Cbru003E log.info(“objectId: {}”, objectId);u003Cbru003E }u003Cbru003E }u003Cbru003E @Testu003Cbru003E public void testSnowflakeId() {u003Cbru003E ExecutorService executorService = Executors.newFixedThreadPool(20);u003Cbru003E for (int i = 0; i < 20; i++) {u003Cbru003E executorService.execute(() -> {u003Cbru003E log.info(“分布式 ID: {}”, idGenerator.snowflakeId());u003Cbru003E });u003Cbru003E }u003Cbru003E executorService.shutdown();u003Cbru003E }u003Cbru003E}u003Cbru003E复制代码u003Cbru003Eu003Cu002Fpreu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002Fd579d35a41f04d97a0445b6cee6e575e” img_width=”538″ img_height=”313″ alt=”分布式id生成器” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E在项目中我们只需要注入 @Autowired private IdGenerator idGenerator;即可u003Cu002Fpu003Eu003Cpu003E然后设置id order.setId(idGenerator.snowflakeId() + “”);u003Cu002Fpu003Eu003Cu002Fdivu003E”

原文始发于:分布式id生成器

主题测试文章,只做测试使用。发布者:逗乐男神i,转转请注明出处:http://www.cxybcw.com/26522.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code