背景
在分布式系统中, 经常需要对大量的数据, 消息, http 请求等进行唯一标识, 例如: 对于分布式系统, 服务间相互调用需要唯一标识, 调用链路分析的时候需要使用这个唯一标识. 这个时候数据库自增主键已经不能满足需求, 需要一个能够生成全局唯一 ID 的系统, 这个系统需要满足以下需求:
全局唯一: 不能出现重复 ID.
高可用: ID 生成系统是基础系统, 被许多关键系统调用, 一旦宕机, 会造成严重影响.
经典方案介绍
1. UUID
UUID 是 Universally Unique Identifier 的缩写, 它是在一定的范围内 (从特定的名字空间到全球) 唯一的机器生成的标识符, UUID 是 16 字节 128 位长的数字, 通常以 36 字节的字符串表示, 比如: 3F2504E0-4F89-11D3-9A0C-0305E82C3301.
UUID 经由一定的算法机器生成, 为了保证 UUID 的唯一性, 规范定义了包括网卡 Mac 地址, 时间戳, 名字空间(Namespace), 随机或伪随机数, 时序等元素, 以及从这些元素生成 UUID 的算法. UUID 的复杂特性在保证了其唯一性的同时, 意味着只能由计算机生成.
优点:
本地生成 ID, 不需要进行远程调用, 时延低, 性能高.
缺点:
UUID 过长, 16 字节 128 位, 通常以 36 长度的字符串表示, 很多场景不适用, 比如用 UUID 做数据库索引字段.
没有排序, 无法保证趋势递增.
2. Flicker 方案
这个方案是由 Flickr 团队提出, 主要思路采用了 MySQL 自增长 ID 的机制(auto_increment + replace into)
replace into 跟 insert 功能类似, 不同点在于: replace into 首先尝试插入数据到表中, 如果发现表中已经有此行数据 (根据主键或者唯 - 索引判断) 则先删除此行数据, 然后插入新的数据, 否则直接插入新数据.
为了避免单点故障, 最少需要两个数据库实例, 通过区分 auto_increment 的起始值和步长来生成奇偶数的 ID.
优点:
充分借助数据库的自增 ID 机制, 可靠性高, 生成有序的 ID.
缺点:
ID 生成性能依赖单台数据库读写性能.
依赖数据库, 当数据库异常时整个系统不可用.
对于依赖 MySQL 性能问题, 可用如下方案解决:
在分布式环境中我们可以部署多台, 每台设置不同的初始值, 并且步长为机器台数, 比如部署 N 台, 每台的初始值就为 0,1,2,3...N-1, 步长为 N.
以上方案虽然解决了性能问题, 但是也存在很大的局限性:
系统扩容困难: 系统定义好步长之后, 增加机器之后调整步长困难.
数据库压力大: 每次获取一个 ID 都必须读写一次数据库.
3. 类 snowflake 方案
这种方案生成一个 64bit 的数字, 64bit 被划分成多个段, 分别表示时间戳, 机器编码, 序号.
ID 为 64bit 的 long 数字, 由三部分组成:
41 位的时间序列(精确到毫秒, 41 位的长度可以使用 69 年).
10 位的机器标识(10 位的长度最多支持部署 1024 个节点).
12 位的计数顺序号(12 位的计数顺序号支持每个节点每毫秒产生 4096 个 ID 序号).
优点:
时间戳在高位, 自增序列在低位, 整个 ID 是趋势递增的, 按照时间有序.
性能高, 每秒可生成几百万 ID.
可以根据自身业务需求灵活调整 bit 位划分, 满足不同需求.
缺点:
依赖机器时钟, 如果机器时钟回拨, 会导致重复 ID 生成.
在单机上是递增的, 但是由于涉及到分布式环境, 每台机器上的时钟不可能完全同步, 有时候会出现不是全局递增的情况.
4. TDDL 序列生成方式
TDDL 是阿里的分库分表中间件, 它里面包含了全局数据库 ID 的生成方式, 主要思路:
使用数据库同步 ID 信息.
每次批量取一定数量的可用 ID 在内存中, 使用完后, 再请求数据库重新获取下一批可用 ID, 每次获取的可用 ID 数量由步长控制, 实际业务中可根据使用速度进行配置.
每个业务可以给自己的序列起个唯一的名字, 隔离各个业务系统的 ID.
优点:
相比 flicker 方案, 大大降低数据库写压力, 数据库不再是性能瓶颈.
相比 flicker 方案, 生成 ID 性能大幅度提高, 因为获取一个可用号段后在内存中直接分配, 相对于每次读取数据库性能提高了几个量级.
不同业务不同的 ID 需求可以用 seqName 字段区分, 每个 seqName 的 ID 获取相互隔离, 互不影响.
缺点:
强依赖数据库, 当数据库异常时整个系统不可用.
发号器实现方案
综合对比以上四种实现方案, 以及我们的业务需求, 最后决定采用第三种方案.
主要原因:
业务需求: 业务要求生成的 ID 要有递增趋势, 全局唯一, 并且为数字.
系统考虑: 第三种方案性能高, 稳定性高, 对外部资源依赖少.
依据实际业务需求和系统规划, 对算法进行局部调整, 实现了发号器 snowflake 方案.
发号器 snowflake 方案
发号器 snowflake 方案中对 bit 的划分做了如下调整:
36 bit 时间戳, 使用时间秒
5 bit 机器编码
22 bit 序号
机器编码维护:
机器编码是不同机器之间产生唯一 ID 的重要依据, 不能重复, 一旦重复, 就会导致有相同机器编码的服务器生成的 ID 大量重复. 如果部署的机器只是少量的, 可以人工维护, 如果大量, 手动维护成本高, 考虑到自动部署, 运维等等问题, 机器编码最好由系统自动维护, 有以下两个方案可供选择:
使用 MySQL 自增 ID 特性, 用数据表, 存储机器的 Mac 地址或者 ip 来维护.
使用 ZooKeeper 持久顺序节点的特性.
这里我们使用 ZooKeeper 持久顺序节点特性来配置维护 WORKID. 发号器的启动顺序如下:
启动发号器服务, 连接 ZooKeeper, 检查根节点 id_generator 是否存在, 如果不存在就创建系统根节点.
检查根节点下当前机器是否已经注册过(是否有该顺序子节点).
如果有注册, 直接取回自己的 WORKID. 如果没注册, 在根节点下创建一个持久顺序节点, 取回顺序号做 WORKID.
一旦取回 WORKID, 缓存在本地文件中, 后续直接使用, 不再与 ZooKeeper 进行任何交互, 此方案对 ZooKeeper 依赖极小.
时钟问题:
snowflake 方案依赖系统时钟, 如果机器时钟回拨, 就有可能生成重复 ID, 为了保证 ID 唯一性, 必须解决时钟回拨问题.
可以采取以下几种方案解决时钟问题:
关闭系统 NTP 同步, 这样就不会产生时钟调整.
系统做出判断, 在时钟回拨这段时间, 不生成 ID, 直接返回 ERROR_CODE, 直到时钟追上, 恢复服务.
系统做出判断, 如果遇到超过容忍限度的回拨, 上报报警系统, 并把自身从集群节点中摘除
系统做兼容处理, 由于 nfp 网络回拨都是几十毫秒到几百毫秒, 极少数到秒级别, 这种回拨会产生以下几种结果:
系统中缓存最近几秒内最后的发号序号(具体范围请根据实际需要确定), 存储格式为: 时间秒 - 序号.
当前秒数不变: 当前是 8:30 秒 100 毫秒, ntp 回拨 50 毫秒, 当前时间变成 8:30 秒 50 毫秒, 这个时候秒数没变, 我们算法的时间戳部分不会产生重复, 就不影响系统继续发号
当前秒数向前: 当前是 8:30 秒 800 毫秒, ntp 向前调整 300 毫秒, 当前时间变成 8:31 秒 100 毫秒, 由于这个时间还没发过号, 不会生成重复的 ID
当前秒数向后: 当前是 8:30 秒 100 毫秒, ntp 回拨 150 毫秒, 当前时间变成 8:29 秒 950 毫秒, 这个时候秒发生回退, 就可能产生重复 ID. 产生重复的原因在于秒回退后, 算法的时间戳部分使用了已经用过的时间戳, 但是算法的序号部分, 并没有回退到 29 秒那个时间对应的序号, 依然使用当前的序号, 如果序号也同时回退到 29 秒时间戳所对应的最后序号, 就不会重复发号. 解决方案如下:
闰秒处理:
闰秒, 是指为保持协调世界时接近于世界时时刻, 由国际计量局统一规定在年底或年中 (也可能在季末) 对协调世界时增加或减少 1 秒的调整. 由于地球自转的不均匀性和长期变慢性 (主要由潮汐摩擦引起的), 会使世界时(民用时) 和原子时之间相差超过到 ±0.9 秒时, 就把协调世界时向前拨 1 秒 (负闰秒, 最后一分钟为 59 秒) 或向后拨 1 秒(正闰秒, 最后一分钟为 61 秒), 闰秒一般加在公历年末或公历六月末.
在闰秒产生的时候系统会出现秒级时间调整, 下面我们来分析闰秒对发号器的影响:
负闰秒: 当前 23:59:58 的下一秒就是第二天的 00:00:00,00:00:00 这个时间我们还没产生过 ID, 不会产生重复的, 对发号器没影响.
正闰秒: 当天 23:59:59 的下一秒当记为 23:59:60, 然后才是第二天的 00:00:00. 由于我们系统时间戳部分取的从某个时间点 (1970 年 1 月 1 日) 到现在的秒数, 是一个数字, 只要这个数字不重复, 就不会产生重复的 ID. 如果在闰秒发生一段时间后 ntp 时间同步(为了规避闰秒风险, 很多公司闰秒前关闭 ntp 同步, 闰秒后打开 ntp 同步), 这个时候系统时钟回拨, 可以使用解决时钟回拨的方案进行处理.
服务部署优化
部署结构
为了实现高可用, 避免单点故障, 系统部署采用集群水平部署, 前置使用 nginx 做负载均衡, 发号器使用 springboot 框架, web 服务器使用 springboot 内嵌 tomcat, 发号器和 nginx 之间进行心跳检测.
tomcat 调优
使用 APR
Tomcat 支持三种接收请求的处理方式: BIO,NIO,APR, 性能 BIO<NIO<APR.APR 简单理解, 就是从操作系统级别解决异步 IO 问题, 大幅度的提高服务器的处理和响应性能, 也是 Tomcat 运行高并发应用的首选模式. 使用 APR 首先要安装系统依赖库, 参考 APR 安装
在 springBoot 程序中增加 apr 配置开启 APR(这里有一个配置变量来控制是否开启)
开发中遇到的问题
整个开发过程都非常顺利, 测试的时候 tps 也很高, 心情很愉快, 世界很美好, 突然一个意外出现, 发现存在 full gc 现象, 有内存溢出? 于是分析了好几遍程序, 也没找到明显的线索, 只能开始 jvm 调试旅程.
pingpoint 监控图:
(上图中红色部署表示 full gc)
JVM 调试最直接的就是获取 full gc 时的 jvm dump 文件, 以及 gc log 进行分析:
为了获取 dump 文件, 在 jvm 参数中加上:
参数介绍:
配置上面的虚拟机参数后, 虚拟机 gc 的时候会把 gc 相关信息输出到文件 gc.log 中, full gc 前后, 会生成当时虚拟机的内存 dump 文件. 从 pingpoint 监控图中可以看出 full gc 是发生在持久区域.
使用 jmap 工具, 获取 JVM 堆内存信息如下:
jmap -heap pid
从上图可以看出, 使用的堆内存很少, 总的堆内存只有 0.84% 使用, 其它使用指标也都在正常范围, 系统装载的类也不多, 没有内存泄露.
继续分析 gc log:
从 gc log 中寻找线索:
这里发现了以下线索:
从 [Full GC (Metadata GC Threshold)看出, 的确产生了 full gc, 原因 Metadata GC Threshold.
[Metaspace: 34773K->34773K(1081344K)] full gc 前后 metaspace 的 size 没有变化说明此区域已经满了, 释放不出内存.
仔细分析 gc log, 发现 2 次 full gc 记录, 第一次 full gc [Metaspace: 20897K->20897K(1069056K), 这个值比第 2 次的要小很多.
两次 full gc 原因都是 Metadata GC Threshold 类型, 说明 pingpoint 监控到的 full gc 是元空间引发的 full gc, 并非内存泄露引起, 但是这个值才 34m, 距离最大值 1081m, 还有很大空间, 为什么会 full gc?
经过查阅官方资料, 发现 MetaspaceSize 的默认大小是 21807104b, 也就是 21296k, 而发生 GC 的时候, 元空间已经使用了 34722K, 从而产生 full gc.
方法区:
方法区也是所有线程共享. 主要用于存储类的信息, 常量池, 方法数据, 方法代码等. 方法区逻辑上属于堆的一部分, 但是为了与堆进行区分, 通常又叫 "非堆". 其实, 移除永久代的工作从 JDK1.7 就开始了. JDK1.7 中, 存储在永久代的部分数据就已经转移到了 Java Heap 或者是 Native Heap. 但永久代仍存在于 JDK1.7 中, 并没完全移除, 譬如符号引用 (Symbols) 转移到了 native heap, 字符串常量转移到了 java heap, 类的静态变量 (class statics) 转移到了 java heap.
在 JDK8 中, classe metadata(the virtual machines internal presentation of Java class), 被存储在叫做 Metaspace 的 native memory. 一些新的 flags 被加入:-XX:MetaspaceSize,class metadata 的初始空间配额, 以 bytes 为单位, 达到该值就会触发垃圾收集进行类型卸载, 同时 GC 会对该值进行调整: 如果释放了大量的空间, 就适当的降低该值; 如果释放了很少的空间, 就会在不超过 MaxMetaspaceSize(如果设置了的话)的情况下, 适当的提高该值.
在虚拟机参数中增加 MetaspaceSize 初始化大小,-XX:MetaspaceSize=128m, 重新启动项目, 不再有 full gc 出现.
总结
发号器 - 达达分布式 ID 生成系统, 是以 snowflake 算法为基础, 实现了生成 全局唯一 ID 的功能, 解决了在分布式系统唯一 ID 生成问题. 在实现 高可用 性方面, 采用水平集群部署, 心跳检测等方案为系统保驾护航. 该系统目前已在达达商城等项目中使用, 每天提供大量服务.
参考
- Snowflake (https://github.com/twitter/snowflake)
- TDDL
来源: http://www.tuicool.com/articles/BNRVzqm