正文

分布式高并发下全局id生成策略

狂风骤起  狂风骤起  2022-10-21  276

关键词：

数据在分片时，典型的是分库分表，就有一个全局ID生成的问题。
单纯的生成全局ID并不是什么难题，但是生成的ID通常要满足分片的一些要求：
1 不能有单点故障。
2 以时间为序，或者ID里包含时间。这样一是可以少一个索引，二是冷热数据容易分离。
3 可以控制ShardingId。比如某一个用户的文章要放在同一个分片内，这样查询效率高，修改也容易。
4 不要太长，最好64bit。使用long比较好操作，如果是96bit，那就要各种移位相当的不方便，还有可能有些组件不能支持这么大的ID。

一 twitter
twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成机制，于是自己开发了一套全局唯一ID生成服务：Snowflake。
1 41位的时间序列（精确到毫秒，41位的长度可以使用69年）
2 10位的机器标识（10位的长度最多支持部署1024个节点）
3 12位的计数顺序号（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）最高位是符号位，始终为0。
优点：高性能，低延迟；独立的应用；按时间有序。缺点：需要独立的开发和部署。

原理

java 实现代码

public class IdWorker 
 
private final long workerId;
private final static long twepoch = 1288834974657L;
private long sequence = 0L;
private final static long workerIdBits = 4L;
public final static long maxWorkerId = -1L ^ -1L << workerIdBits;
private final static long sequenceBits = 10L;
private final static long workerIdShift = sequenceBits;
private final static long timestampLeftShift = sequenceBits + workerIdBits;
public final static long sequenceMask = -1L ^ -1L << sequenceBits;
private long lastTimestamp = -1L;
public IdWorker(final long workerId) 
super();
if (workerId > this.maxWorkerId || workerId < 0) 
throw new IllegalArgumentException(String.format(
"worker Id can\'t be greater than %d or less than 0",
this.maxWorkerId));
this.workerId = workerId;
public synchronized long nextId() 
long timestamp = this.timeGen();
if (this.lastTimestamp == timestamp) 
this.sequence = (this.sequence + 1) & this.sequenceMask;
if (this.sequence == 0) 
System.out.println("###########" + sequenceMask);
timestamp = this.tilNextMillis(this.lastTimestamp);
 else 
this.sequence = 0;
if (timestamp < this.lastTimestamp) 
try 
throw new Exception(
String.format(
"Clock moved backwards. Refusing to generate id for %d milliseconds",
this.lastTimestamp - timestamp));
 catch (Exception e) 
e.printStackTrace();
 
this.lastTimestamp = timestamp;
long nextId = ((timestamp - twepoch << timestampLeftShift))
| (this.workerId << this.workerIdShift) | (this.sequence);
System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"
+ timestampLeftShift + ",nextId:" + nextId + ",workerId:"
+ workerId + ",sequence:" + sequence);
return nextId;
 
private long tilNextMillis(final long lastTimestamp) 
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) 
timestamp = this.timeGen();
return timestamp;
 
private long timeGen() 
return System.currentTimeMillis();
 
 
public static void main(String[] args)
IdWorker worker2 = new IdWorker(2);
System.out.println(worker2.nextId());
 

2 来自Flicker的解决方案
因为MySQL本身支持auto_increment操作，很自然地，我们会想到借助这个特性来实现这个功能。
Flicker在解决全局ID生成方案里就采用了MySQL自增长ID的机制（auto_increment + replace into + MyISAM）。一个生成64位ID方案具体就是这样的：
先创建单独的数据库(eg:ticket)，然后创建一个表：

CREATE TABLE Tickets64 (
id bigint(20) unsigned NOT NULL auto_increment,
stub char(1) NOT NULL default \'\',
PRIMARY KEY (id),
UNIQUE KEY stub (stub)
) ENGINE=MyISAM

当我们插入记录后，执行SELECT * from Tickets64，查询结果就是这样的：

+-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |
+-------------------+------+
在我们的应用端需要做下面这两个操作，在一个事务会话里提交：

REPLACE INTO Tickets64 (stub) VALUES (\'a\');
SELECT LAST_INSERT_ID();

这样我们就能拿到不断增长且不重复的ID了。
到上面为止，我们只是在单台数据库上生成ID，从高可用角度考虑，接下来就要解决单点故障问题：Flicker启用了两台数据库服务器来生成ID，通过区分auto_increment的起始值和步长来生成奇偶数的ID。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
 
TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

最后，在客户端只需要通过轮询方式取ID就可以了。

优点：充分借助数据库的自增ID机制，提供高可靠性，生成的ID有序。
缺点：占用两个独立的MySQL实例，有些浪费资源，成本较高。

三 UUID

UUID生成的是length=32的16进制格式的字符串，如果回退为byte数组共16个byte元素，即UUID是一个128bit长的数字，
一般用16进制表示。
算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成UUID。
从理论上讲，如果一台机器每秒产生10000000个GUID，则可以保证（概率意义上）3240年不重复
优点：
（1）本地生成ID，不需要进行远程调用，时延低
（2）扩展性好，基本可以认为没有性能上限
缺点：
（1）无法保证趋势递增
（2）uuid过长，往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性）
四基于redis的分布式ID生成器
首先，要知道redis的EVAL，EVALSHA命令：
原理

利用redis的lua脚本执行功能，在每个节点上通过lua脚本生成唯一ID。
生成的ID是64位的：

使用41 bit来存放时间，精确到毫秒，可以使用41年。
使用12 bit来存放逻辑分片ID，最大分片ID是4095
使用10 bit来存放自增长ID，意味着每个节点，每毫秒最多可以生成1024个ID
比如GTM时间 Fri Mar 13 10:00:00 CST 2015 ，它的距1970年的毫秒数是 1426212000000，假定分片ID是53，自增长序列是4，则生成的ID是：

5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41
redis提供了TIME命令，可以取得redis服务器上的秒数和微秒数。因些lua脚本返回的是一个四元组。

second, microSecond, partition, seq
客户端要自己处理，生成最终ID。

((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;
五 MongoDB文档（Document）全局唯一ID

为了考虑分布式，“_id”要求不同的机器都能用全局唯一的同种方法方便的生成它。因此不能使用自增主键（需要多台服务器进行同步，既费时又费力），
因此选用了生成ObjectId对象的方法。

ObjectId使用12字节的存储空间，其生成方式如下：

|0|1|2|3|4|5|6 |7|8|9|10|11|

|时间戳 |机器ID|PID|计数器 |

前四个字节时间戳是从标准纪元开始的时间戳，单位为秒，有如下特性：

1 时间戳与后边5个字节一块，保证秒级别的唯一性；
2 保证插入顺序大致按时间排序；
3 隐含了文档创建时间；
4 时间戳的实际值并不重要，不需要对服务器之间的时间进行同步（因为加上机器ID和进程ID已保证此值唯一，唯一性是ObjectId的最终诉求）。

机器ID是服务器主机标识，通常是机器主机名的散列值。

同一台机器上可以运行多个mongod实例，因此也需要加入进程标识符PID。

前9个字节保证了同一秒钟不同机器不同进程产生的ObjectId的唯一性。后三个字节是一个自动增加的计数器（一个mongod进程需要一个全局的计数器），保证同一秒的ObjectId是唯一的。同一秒钟最多允许每个进程拥有（256^3 = 16777216）个不同的ObjectId。

总结一下：时间戳保证秒级唯一，机器ID保证设计时考虑分布式，避免时钟同步，PID保证同一台服务器运行多个mongod实例时的唯一性，最后的计数器保证同一秒内的唯一性（选用几个字节既要考虑存储的经济性，也要考虑并发性能的上限）。

"_id"既可以在服务器端生成也可以在客户端生成，在客户端生成可以降低服务器端的压力。

分布式id的四种写法，你会吗？(代码片段)

...略。入门学习由于篇幅优先，建议阅读下面的文章内容。分布式id生成需求uuid策略讲解random生成策略snowflake算法讲解开源工具id是一款为java设计常见ID实现策略。让你在日常开发中可以开箱即用，享受提前下班的快乐~创作意图对... 查看详情

七种分布式全局id生成策略，你更爱哪种？(代码片段)

上了微服务之后，很多原本很简单的问题现在都变复杂了，例如全局ID这事！最近工作中刚好用到这块内容，于是调研了市面上几种常见的全局ID生成策略，稍微做了一下对比，供小伙伴们参考。当数据库... 查看详情

七种分布式全局id生成策略，你更爱哪种？(代码片段)

文章目录1.两种思路2.数据库自己搞定2.1修改数据库配置2.2MySQL+MyCat+ZooKeeper3.Java代码处理3.1UUID3.2SNOWFLAKE3.3LEAF3.3.1号段模式3.3.2SNOWFLAKE模式3.4Redis生成3.5Zookeeper处理4.小结上了微服务之后，很多原本很简单的问题现在都变复... 查看详情

架构设计|分布式业务系统中，全局id生成策略(代码片段)

...，仅供参考。二、雪花算法1、概念简介Twitter公司开源的分布式ID生成算法策略，生成的ID遵循时间的顺序。1为位标识，始终为0，不可用；41位时间截，存储时间截的差值（当前时间截-开始时间截)；10位的机器标识，10位的长度... 查看详情

分布式事务,高并发下分布式事务的解决方案

...据库本身保证的。今天，我将介绍一种比较复杂的事务：分布式事务。1、什么是分布式事务分布式事务就是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。以上是... 查看详情

架构设计|分布式业务系统中，全局id生成策略(代码片段)

6大布式唯一id生成策略对比

全局唯一的ID几乎是所有系统都会遇到的刚需。这个id在搜索,存储数据,加快检索速度等等很多方面都有着重要的意义。有多种策略来获取这个全局唯一的id，针对常见的几种场景，我在这里进行简单的总结和对比。简单分... 查看详情

数据存储redis第四章：高并发下实现分布式锁(代码片段)

直接上代码：大部分互联网公司实现分布式锁原理/***分布式锁底层实现原理*@return*/@GetMapping("distributedLock")publicObjectdistributedLock()StringlockKey="distributedLockKey";//给每个线程都设置一个唯一标识，避免出现程序执行的时间超过设置的... 查看详情

数据存储redis第四章：高并发下实现分布式锁(代码片段)

深入理解分布式事务,高并发下分布式事务的解决方案

这两天正在研究微服务架构中分布式事务的处理方案,做一个小小的总结,作为备忘.如有错误,欢迎指正!概念澄清事务补偿机制:在事务链中的任何一个正向事务操作,都必须存在一个完全符合回滚规则的可逆事务.CAP理论:CAP(Consistency... 查看详情

分布式高并发下actor模型(代码片段)

写在开始一般来说有两种策略用来在并发线程中进行通信：共享数据和消息传递。使用共享数据方式的并发编程面临的最大的一个问题就是数据条件竞争。处理各种锁的问题是让人十分头... 查看详情

分布式id生成策略(代码片段)

　　在分布式系统中，肯定避免不了获取全局唯一ID，用于业务主键，本节主要学习分布式ID常用的生成方法。一、UUID　　UUID(UniversallyUniqueIdentifier)，通用唯一识别码。UUID是基于当前时间、计数器（counter）和硬件标识（通常为... 查看详情

java中如何一次请求生成一个日志文件高并发下可用

参考技术Ajava是编程语言里比较难学的一门，如果有心从事编程方向的工作，最好到专业机构学习并有更多的项目实践，更贴近市场，这样更有利于将来的发展。参考技术B日志框架，或写一个切面aop 查看详情

分布式系统唯一id的生成方案讨论(代码片段)

在分布式系统下唯一id问题，就是id咋生成？比如分表分库，因为要是一个表分成多个表之后，每个表的id都是从1开始累加自增长，那是不对的。举个例子，一个表拆分为了2张表，每个表的id都从1开始累加，这个肯定有问题了！... 查看详情

redis场景拓展秒杀问题-全局唯一id生成策略(代码片段)

...ID，那么多张表都会出现相同的ID，不满足业务需求。在分布式系统下全局唯一ID需要满足的特点：唯一性递增性安全性高可用(服务稳定)高性能(生成速度够快)为了提高数据库性能，这里采用Java中的数值类型(Long--8(Byte)字节，64位... 查看详情

七种分布式全局id生成策略，你更爱哪种？(代码片段)

高并发下接口的并发问题

...会员，限制每个帐号只能领取一个有恶意用户刷接口，在高并发下越过限制。原因领取会员流程：1.后端先生成卡卷，将卡号放到消息队列中2.用户扫码请求领取会员接口2-1).先检查用户是否已经领取过该活动会员2-2).领取过return... 查看详情

分布式事务,高并发下分布式事务的解决方案

分布式事务,高并发下分布式事务的解决方案1、什么是分布式事务分布式事务就是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。以上是百度百科的解释，简单的说... 查看详情