常见的分布式Id生成器剖析 _分布式

在高并发或者分表分库情况下怎么保证数据id的幂等性呢？
经常用到的解决方案有以下几种。
微软公司通用唯一识别码（UUID）
Twitter公司雪花算法（SnowFlake）
基于数据库的id自增
对id进行缓存
一、SnowFlake算法
snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID 。
其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号，最后还有一个符号位，永远是0 。
snowflake算法所生成的ID结构，如下图：
【常见的分布式Id生成器剖析】

文章插图

整个结构是64位，所以我们在JAVA中可以使用long来进行存储。
该算法实现基本就是二进制操作,单机每秒内理论上最多可以生成1024*(2^12)，也就是409.6万个ID(1024 X 4096 = 4194304)
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
41位时间截(毫秒级) 。注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId
12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号
加起来刚好64位，为一个Long型。
SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高
经测试，SnowFlake每秒能够产生26万ID左右。
snowFlake算法的优点：
生成ID时不依赖于DB，完全在内存生成，高性能高可用。
ID呈趋势递增，后续插入索引树的时候性能较好。
SnowFlake算法的缺点：
依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成ID冲突，或者ID乱序
二、基于数据库的id自增

文章插图

字段说明：
id代表该obj本次set后的maxid
不同业务不同的ID需求可以用obj字段区分，每个obj的ID获取相互隔离，互不影响
step 步长，代表每次获取多长ID段到缓存
基本要求：
全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求
趋势递增：在MySQL InnoDB引擎使用的是聚集索引, 由于多数的RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上应该尽量使用有序的主键保证写入性能
单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求
信息安全：如果ID是联系的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量。所以在这些场景下，会需要ID无规则，不规则。
性能要求：
平均延迟和TP999延迟都要尽可能低
可用性5个9（99.999%）
高QPS
优点：
支持全局唯一、系统唯一、表级别唯一三种形式，绝对不会出现重复ID，且ID整体趋势递增；
大大的降低了数据库的压力，ID生成可以做到每秒生成几万几十万个
一定的高可用，服务采用预分配ID的方案，每次调用分配10000个id到系统缓存集群，即使MySQL宕机，也能容忍一段时间数据不可用；
接入简单，直接通过公司的RPC服务或者HTTP调用即可使用;
缺点：
强依赖数据库，当MySQL服务长时间不可用，那么对公司业务将是一场灾难；
并发性能较低，假设公司业务量急剧增长，idgenerator服务请求并发量增高，而实际上在更新数据库时会触发表锁，可能造成ID获取失败,导致服务不可用;
缺少服务自身监控，无法通过web层的内存数据映射界面实时观测所有号段的下发状态及使用情况
服务仍然是单点
如果服务挂了，服务重启起来之后，继续生成ID可能会不连续，中间出现空洞（服务内存是保存着0,1,2,3,4,5，数据库中max-id是5，分配到3时，服务重启了，下次会从6开始分配，4和5就成了空洞，不过这个问题也不大）