今天一定要努力工作
绝对不会浪费时间
在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。比如我们所熟知的美团、饿了么,携程、飞猪等app,它们的支付订单、餐饮、酒店、代金券等产品系统中,随着数据日渐增长,就会产生分表、分库的需求,这样也就需要一个唯一的ID来标识一条数据或消息,数据库的自增ID显然不能满足需求。
分布式系统唯一ID的特点
上述123对应三类不同的场景,3和4需求还是互斥的,无法使用同一个方案满足。同时除了对ID号码自身的要求,业务还对ID号生成系统的可用性要求极高。
由此一个ID生成系统应该做到如下几点:
常见解决方案有UUID,Snowflake,Flicker,Redis,Zookeeper,Leaf等。
1.UUID
UUID 是 通用唯一识别码(Universally Unique Identifier)的缩写,是一种软件建构的标准。其目的,是让分布式系统中的所有元素,都能有唯一的辨识信息,而不需要通过中央控制端来做辨识信息的指定。如此一来,每个人都可以创建不与其它人冲突的UUID。在这样的情况下,就不需考虑数据库创建时的名称重复问题。常见的为一个32位16进制字符串(16字节的128位数据,通常以32位长度的字符串表示)
组成:
优点:
缺点:
我们所熟知的MySQL官方有明确的建议主键要尽量越短越好,并且如果作为数据库主键,在InnoDB引擎下,UUID的无序性可能会引起数据位置频繁变动,严重影响性能。
适用场景:
不需要考虑空间占用,不需要生成有递增趋势的ID,且不在MySQL中存储,或者不需要用UUID做排序的情况。
2.Snowflake
这种方案大致来说是一种以划分命名空间(UUID也算,由于比较常见,所以单独分析)来生成ID的一种算法。是Twitter开源的分布式ID生成算法,结果是一个long型的ID。这种方案把64-bit分别划分成多段,分开来标示机器、时间等,比如在Snowflake中的 64-bit 分别表示如下图(图片来自网络)所示:
组成:
优点:
缺点:
1.强依赖机器时钟。分布式环境,每台机器上的时钟不可能完全同步,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。
本来想看看推特怎么写的,结果github上面写着项目不维护了,这是忧伤
不过它留了一个scala的项目压缩包,可以看看。
下面是模拟这个结构写的一份Snowflake的Java版本代码,仅供参考:
public class SnowflakeIdWorker { // ==============================Fields=========================================== /** 开始时间截 (2015-01-01) */ private final long twepoch = 1420041600000L; /** 机器id所占的位数 */ private final long workerIdBits = 5L; /** 数据标识id所占的位数 */ private final long datacenterIdBits = 5L; /** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); /** 支持的最大数据标识id,结果是31 */ private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); /** 序列在id中占的位数 */ private final long sequenceBits = 12L; /** 机器ID向左移12位 */ private final long workerIdShift = sequenceBits; /** 数据标识id向左移17位(12+5) */ private final long datacenterIdShift = sequenceBits + workerIdBits; /** 时间截向左移22位(5+5+12) */ private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; /** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */ private final long sequenceMask = -1L ^ (-1L << sequenceBits); /** 工作机器ID(0~31) */ private long workerId; /** 数据中心ID(0~31) */ private long datacenterId; /** 毫秒内序列(0~4095) */ private long sequence = 0L; /** 上次生成ID的时间截 */ private long lastTimestamp = -1L; //==============================Constructors===================================== /** * 构造函数 * @param workerId 工作ID (0~31) * @param datacenterId 数据中心ID (0~31) */ public SnowflakeIdWorker(long workerId, long datacenterId) { if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId)); } if (datacenterId > maxDatacenterId || datacenterId < 0) { throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId)); } this.workerId = workerId; this.datacenterId = datacenterId; } // ==============================Methods========================================== /** * 获得下一个ID (该方法是线程安全的) * @return SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常 if (timestamp < lastTimestamp) { throw new RuntimeException( String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } //如果是同一时间生成的,则进行毫秒内序列 if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; //毫秒内序列溢出 if (sequence == 0) { //阻塞到下一个毫秒,获得新的时间戳 timestamp = tilNextMillis(lastTimestamp); } } //时间戳改变,毫秒内序列重置 else { sequence = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID return ((timestamp - twepoch) << timestampLeftShift) // | (datacenterId << datacenterIdShift) // | (workerId << workerIdShift) // | sequence; } /** * 阻塞到下一个毫秒,直到获得新的时间戳 * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * @return 当前时间(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } //==============================Test============================================= /** 测试 */ public static void main(String[] args) { SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); for (int i = 0; i < 1000; i++) { long id = idWorker.nextId(); System.out.println(Long.toBinaryString(id)); System.out.println(id); } } }
应用场景:
要求高性能,可以不连续,数据类型为long型。
思考:如何解决时间回拨的问题?
时间回拨产生的原因:分布式系统中,各机器同步服务器时间,一般每2小时同步一次,在 10ms 以内完成。
百度倒是做了一个简单的处理:
UidGenerator是百度开源的Java语言实现,基于 Snowflake 算法的唯一ID生成器。百度对这些组成部分稍微调整了一下:
传统的雪花算法实现都是通过 System.currentTimeMillis()来获取时间并与上一次时间进行比较,这样的实现严重依赖服务器的时间。而 UidGenerator 的时间类型是AtomicLong,且通过 incrementAndGet() 方法获取下一次的时间,从而脱离了对服务器时间的依赖,也就不会有时钟回拨的问题(这种做法也有一个小问题,即分布式ID中的时间信息可能并不是这个ID真正产生的时间点,例如:获取的某分布式ID的值为3200169789968523265,它的反解析结果为{"timestamp":"2019-05-02 23:26:39","workerId":"21","sequence":"1"},但是这个ID可能并不是在"2019-05-02 23:26:39"这个时间产生的)。
3.MongoDB
官方文档ObjectID可以算作是和snowflake类似方法,通过“时间+机器码+pid+inc”共12个字节,通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。
4.数据库生成
主要思路是涉及单独的库表,利用数据库的自增ID+replace_into,来生成全局ID。
replace into 跟 insert 功能类似,不同点在于:replace into首先尝试插入数据列表中,如果发现表中已经有此行数据(根据主键或唯一索引判断)则先删除,再插入。否则直接插入新数据。
扩展:为解决单点问题,启用多台服务器,如MySQL,利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增(如通过设置起始值与步长,生成奇偶数ID)
优点:
缺点:
适用场景:
数据量不大,并发量不大。
优化:
对于MySQL性能问题,可用如下方案解决:在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。
比如有两台机器。设置步长step为2,TicketServer1 的初始值为1(1,3,5,7,9,11…)、TicketServer2 的初始值为2(2,4,6,8,10…)。这是Flickr团队在2010年撰文介绍的一种主键生成策略(Ticket Servers: Distributed Unique Primary Keys on the Cheap )。如下所示,为了实现上述方案分别设置两台机器对应的参数,TicketServer1 从1开始发号, TicketServer2 从2开始发号,两台机器每次发号之后都递增2。
TicketServer1:
auto-increment-increment = 2 auto-increment-offset = 1 TicketServer2: auto-increment-increment = 2 auto-increment-offset = 2
假设我们要部署N台机器,步长需设置为N,每台的初始值依次为0,1,2…N-1那么整个架构就变成了如下图所示:
这种架构貌似能够满足性能的需求,但有以下几个缺点:
5.Redis
由于 Redis 的所有命令是单线程的,所以可以利用Redis的原子操作 INCR 和 INCRBY ,来生成全局唯一的ID。
比较适合使用 Redis 来生成每天从0开始的流水号。比如订单号=日期+当日自增长号。可以每天在 Redis 中生成一个Key,使用 INCR 进行累加。
扩展:
可以通过集群来提升吞吐量(可以通过为不同Redis节点设置不同的初始值并统一步长,从而利用Redis生成唯一且趋势递增的ID)(其实这个方法和Flicker一致,只是利用到了Redis的一些特性,如原子操作,内存数据库读写快等)(Incrby:将key中储存的数字加上指定的增量值。这是一个“INCR AND GET”的原子操作,业务方可以定义一个自己的key值,通过INCR命令来获取对应的ID)
优点:
缺点:
适用场景:
Redis集群高可用,并发量高。
6.zookeeper生成唯一ID
通过其znode数据版本来生成序列号,可以生成32位和64位的数据版本号,客户端可以使用这个版本号来作为唯一的序列号。
小结:很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper,并且是多步调用API,如果在竞争较大的情况下,需要考虑使用分布式锁。因此,性能在高并发的分布式环境下,也不甚理想。
7.Leaf-segment数据库方案
拓展自第4种方法,因为原方案每次获取ID都得读写一次数据库,造成数据库压力大。改为利用 proxy server 批量获取,每次获取一个 segment ( step 决定大小)号段的值。用完之后再去数据库获取新的号段,可以大大的减轻数据库的压力。 各个业务不同的发号需求用 biz_tag 字段来区分,每个 biz-tag 的 ID 获取相互隔离,互不影响。如果以后有性能需求需要对数据库扩容,不需要上述描述的复杂的扩容操作,只需要对 biz_tag分库分表就行。数据库表设计如下
biz_tag 用来区分业务,max_id 表示该 biz_tag 目前所被分配的ID号段的最大值,step 表示每次分配的号段长度。
原来获取ID每次都需要写数据库,现在只需要把 step 设置得足够大,比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step,大致架构如下图所示:
test_tag 在第一台 Leaf 机器上是1~1000的号段,当这个号段用完时,会去加载另一个长度为step=1000的号段,假设另外两台号段都没有更新,这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的 biz_tag 这条数据的 max_id 会从3000被更新成4000,更新号段的SQL语句如下:
Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxxSELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit
优点:
缺点:
8.双buffer优化
对于第二个缺点,Leaf-segment 做了一些优化,简单的说就是:
Leaf 取号段的时机是在号段消耗完的时候进行的,也就意味着号段临界点的 ID 下发时间取决于下一次从DB取回号段的时间,并且在这期间进来的请求也会因为DB号段没有取回来,导致线程阻塞。如果请求DB的网络和DB的性能稳定,这种情况对系统的影响是不大的,但是假如取 DB 的时候网络发生抖动,或者 DB 发生慢查询就会导致整个系统的响应时间变慢。
为此,我们希望DB取号段的过程能够做到无阻塞,不需要在DB取号段的时候阻塞请求线程,即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。详细实现如下图所示:
采用 双buffer 的方式,Leaf 服务内部有两个号段缓存区segment。当前号段已下发10%时,如果下一个号段未更新,则另启一个更新线程去更新下一个号段。当前号段全部下发完后,如果下个号段准备好了则切换到下个号段为当前 segment 接着下发,循环往复。
每个 biz-tag 都有消费速度监控,通常推荐 segment 长度设置为服务高峰期发号QPS的600倍(10分钟),这样即使DB宕机,Leaf 仍能持续发号10-20分钟不受影响。
每次请求来临时都会判断下个号段的状态,从而更新此号段,所以偶尔的网络抖动不会影响下个号段的更新。
理论总结:
其实除了上述方案外,还有ins等的方案,但总的来看,方案主要分为两种:第一有中心(如数据库,包括 MySQL,Redis 等),其中可以会利用事先的预约来实现集群(起始步长)。第二种就是无中心,通过生成足够散落的数据,来确保无冲突(如UUID等)。站在这两个方向上,来看上述方案的利弊就方便多了。
中心化方案:
优点:
缺点:
非中心化方案:
优点:
缺点:
体悟:
技术是无穷无尽的,我们不仅需要看到其中体现的思想与原则,在学习新技术或方案时,需要明确其中一些特性,优缺点的来源,从而进行有效的总结归纳。
应用角度来说,完全应该根据当前业务场景来选择,毕竟业务场景在当前是确定的。如果业务变动较大(比如发展初期,业务增长很快),那就需要考虑扩展性,便于日后进行该模块的更新与技术方案的替换实现。
本文参考:
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://www.cnblogs.com/Tiancheng-Duan/p/10962704.html
https://youzhixueyuan.com/how-to-generate-distributed-unique-id.html
https://www.cnblogs.com/relucent/p/4955340.html