同步操作将从 turnon/blog 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
title: 分布式 ID 基本原理
date: 2019-07-24 11:55:00
categories:
- 分布式
- 分布式调度
tags:
- 分布式
- 数据调度
- 分布式ID
permalink: /pages/3ae455/
传统数据库软件开发中,主键自动生成技术是基本需求。而各个数据库对于该需求也提供了相应的支持,比如 MySQL 的自增键,Oracle 的自增序列等。
数据分片后,不同数据节点生成全局唯一主键是非常棘手的问题。同一个逻辑表内的不同实际表之间的自增键由于无法互相感知而产生重复主键。 虽然可通过约束自增主键初始值和步长的方式避免碰撞,但需引入额外的运维规则,使解决方案缺乏完整性和可扩展性。
为此,需要使用分布式 ID 来解决此问题。本文总结业界常用的分布式 ID 解决方案。
首先,分布式 ID 应该具备哪些特性呢?
UUID 是最简单的分布式 ID 方案。
UUID 是通用唯一识别码(Universally Unique Identifier)的缩写,开放软件基金会(OSF)规范定义了包括网卡 MAC 地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素。利用这些元素来生成 UUID。
UUID 是由 128 位二进制组成,一般转换成十六进制,然后用 String 表示。在 java 中有个 UUID 类,在他的注释中我们看见这里有 4 种不同的 UUID 的生成策略:
String id = UUID.randomUUID().toString();
public static UUID getTimeBasedUuid() {
long time = System.currentTimeMillis() * 10000L + 122192928000000000L + (long)(COUNT.incrementAndGet() % 10000);
long timeLow = (time & 4294967295L) << 32;
long timeMid = (time & 281470681743360L) >> 16;
long timeHi = (time & 1152640029630136320L) >> 48;
long most = timeLow | timeMid | 4096L | timeHi;
return new UUID(most, LEAST);
}
DCE security - DCE 安全的 UUID。
name-based - 基于名字的 UUID,通过计算名字和名字空间的 MD5 来计算 UUID。
UUID 的适用场景可以为不需要担心过多的空间占用,以及不需要生成有递增趋势的数字。在 Log4j 里 UuidPatternConverter
中加入了 UUID 来标识每一条日志。
提到自增键,最先想到的肯定是直接使用数据库自增键。各数据库对于该需求也提供了相应的支持,比如 MySQL 的自增键,Oracle 的自增序列等。
当然,也可以考虑是用 Redis 这样的 Nosql,甚至 ZooKeeper 去生成键
雪花算法(Snowflake)是由 Twitter 公布的分布式主键生成算法,它会生成一个 64 bit
的整数,可以保证不同进程主键的不重复性,以及相同进程主键的有序性。
在同一个进程中,它首先是通过时间位保证不重复,如果时间相同则是通过序列位保证。 同时由于时间位是单调递增的,且各个服务器如果大体做了时间同步,那么生成的主键在分布式环境可以认为是总体有序的,这就保证了对索引字段的插入的高效性。
使用雪花算法生成的主键,二进制表示形式包含 4 部分,从高位到低位分表为:1bit 符号位、41bit 时间戳位、10bit 工作进程位以及 12bit 序列号位。
预留的符号位,恒为零。
41 位的时间戳可以容纳的毫秒数是 2 的 41 次幂,一年所使用的毫秒数是:365 * 24 * 60 * 60 * 1000
。通过计算可知:
Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L);
结果约等于 69.73 年。ShardingSphere 的雪花算法的时间纪元从 2016 年 11 月 1 日零点开始,可以使用到 2086 年,相信能满足绝大部分系统的要求。
该标志在 Java 进程内是唯一的,如果是分布式应用部署应保证每个工作进程的 id 是不同的。该值默认为 0,可通过属性设置。
该序列是用来在同一个毫秒内生成不同的 ID。如果在这个毫秒内生成的数量超过 4096(2 的 12 次幂),那么生成器会等待到下个毫秒继续生成。
雪花算法主键的详细结构见下图:
服务器时钟回拨会导致产生重复序列,因此默认分布式主键生成器提供了一个最大容忍的时钟回拨毫秒数。 如果时钟回拨的时间超过最大容忍的毫秒数阈值,则程序报错;如果在可容忍的范围内,默认分布式主键生成器会等待时钟同步到最后一次主键生成的时间后再继续工作。 最大容忍的时钟回拨毫秒数的默认值为 0,可通过属性设置。
上面只是一个将 64bit
划分的标准,当然也不一定这么做,可以根据不同业务的具体场景来划分,比如下面给出一个业务场景:
这个时候我们根据上面的场景可以再次合理的划分 62bit,QPS 几年之内会发展到百万,那么每毫秒就是千级的请求,目前 10 台机器那么每台机器承担百级的请求,为了保证扩展,后面的循环位可以限制到 1024,也就是 2^10,那么循环位 10 位就足够了。
机器三地部署我们可以用 3bit 总共 8 来表示机房位置,当前的机器 10 台,为了保证扩展到百台那么可以用 7bit 128 来表示,时间位依然是 41bit,那么还剩下 64-10-3-7-41-1 = 2bit,还剩下 2bit 可以用来进行扩展。
当我们需要无序不能被猜测的 ID,并且需要一定高性能,且需要 long 型,那么就可以使用我们雪花算法。比如常见的订单 ID,用雪花算法别人就无法猜测你每天的订单量是多少。
雪花算法是强依赖于时间的,而如果机器时间发生回拨,有可能会生成重复的 ID。
我们可以针对算法做一些优化,来防止时钟回拨生成重复 ID。
用当前时间和上一次的时间进行判断,如果当前时间小于上一次的时间那么肯定是发生了回拨。普通的算法会直接抛出异常,这里我们可以对其进行优化,一般分为两个情况:
5ms
以内,那么可以直接等待一定的时间,让机器的时间追上来。美团提供了一种分布式 ID 解决方案 Leaf,其本质可以视为数据库分段+服务缓存 ID。
详情可以参考 Leaf——美团点评分布式 ID 生成系统
使用数据库生成 ID,但是做了如下改进:
原方案每次获取 ID 都得读写一次数据库,造成数据库压力大。改为利用 proxy server 批量获取,每次获取一个 segment(step 决定大小)号段的值。用完之后再去数据库获取新的号段,可以大大的减轻数据库的压力。 - 各个业务不同的发号需求用 biz_tag 字段来区分,每个 biz-tag 的 ID 获取相互隔离,互不影响。如果以后有性能需求需要对数据库扩容,不需要上述描述的复杂的扩容操作,只需要对 biz_tag 分库分表就行。
数据库表设计如下:
+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field | Type | Null | Key | Default | Extra |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag | varchar(128) | NO | PRI | | |
| max_id | bigint(20) | NO | | 1 | |
| step | int(11) | NO | | NULL | |
| desc | varchar(256) | YES | | NULL | |
| update_time | timestamp | NO | | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+
重要字段说明:
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=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit
需要趋势递增,并且 ID 大小可控制的,可以使用这套方案。
当然这个方案也可以通过一些手段避免被人猜测,把 ID 变成是无序的,比如把我们生成的数据是一个递增的 long 型,把这个 Long 分成几个部分,比如可以分成几组三位数,几组四位数,然后在建立一个映射表,将我们的数据变成无序。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。