问题描述

在物联网场景的解决方案中，通常需要将设备的信息转换为一个业务事件进行输出。在生成/升级事件的过程往往需要多次的数据库操作，且伴随着异步的逻辑。依靠数据库的自增id作为事件的id容易造成脏数据且会占用大量的数据库资源，所以需要系统内置一个轻量级的id生成器。

常见解决方案

UUID

UUID(universally unique identifier)是基于时间生成的128位随机标识符，算法保证了UUID重复的可能性接近于0，且UUID的生成不依赖中心注册单元，完全是分布式生成的。JAVA自带了生成UUID的类库。

public static void main(String[] args) { 
       String uuid = UUID.randomUUID().toString().replaceAll("-","");
       System.out.println(uuid);
}

优点：
生成足够简单，本地生成无网络消耗，具有唯一性
缺点：
无序的字符串，不具备趋势自增特性
没有具体的业务含义
长度过长16 字节128位，字符串36位，很难作为主键保存。

数据库自增ID

基于数据库的auto_increment自增ID完全可以充当分布式ID，具体实现：需要一个单独的MySQL实例用来生成ID，建表结构如下：

CREATE TABLE SEQUENCE_ID (
    id bigint(20) unsigned NOT NULL auto_increment, 
    tag char(10) NOT NULL default '',
    PRIMARY KEY (id),
) ENGINE=INNODB;

当需要一个ID的时候，向表中插入一条记录返回主键ID.

insert into SEQUENCE_ID(value)  VALUES ('tag');

数据库集群自增ID

由于单个数据库有可能造成单点故障，所以数据库自增还可以基于数据库集群来提供。可以避免因为单点造成的不可用，ID重复的问题可以通过给每个数据库设置不同的起始id和步长进行控制。

MySQL_1 配置：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

MySQL_2 配置：

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

优点：
实现简单，ID单调自增，数值类型查询速度快
缺点：
无法支持高并发场景，单机模式有不可用风险，集群模式后期无法扩容。

号段模式

号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。表结构如下：

CREATE TABLE SEGAMENT_ID (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的步长',
  tag     varchar(8) NOT NULL COMMENT '业务标识',
  version int(20) NOT NULL COMMENT '是一个乐观锁，每次都更新version，保证并发时数据的正确性',
  PRIMARY KEY (`id`)
) 

表里插入初始化的数据，确定步长和id初始值。

insert into SEGAMENT_ID (`max_id`,`step`,`tag`,`version`) values(1,1000,'tag',1);

将(1,1000]放到内存里供系统使用。
等这批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。

update SEGAMENT_ID set max_id = #{max_id+step}, version = version + 1 where version = # {version} and tag ='tag'

优点：
高并发，不会占用大量数据库性能。
缺点：
当吞吐量上去后，依旧存在单点故障问题。

redis自增

基于用redis的 incr命令实现ID的原子性自增，也可视实现uid快速生成。

127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id      // 增加1，并返回递增后的数值
(integer) 2

优点：
支持较大的吞吐量，不会占用大量数据库性能。
缺点：
高并发下占用较大的网络IO资源。id完全自增，有信息安全问题。

snowflake算法

Twitter公司开源的id生成算法，基于机器的时钟服务和节点信息生成id。
Snowflake生成的是Long类型的ID，共占64个比特。
其中：正数位（占1比特）+ 时间戳（占41比特）+ 机器ID（占5比特）+ 数据中心（占5比特）+ 自增值（占12比特）。

第一个bit位（1bit）：Java中long的最高位是符号位代表正负，正数是0，负数是1，一般生成ID都为正数，所以默认为0。
时间戳部分（41bit）：毫秒级的时间，不建议存当前时间戳，而是用（当前时间戳 - 固定开始时间戳）的差值，可以使产生的ID从更小的值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
工作机器id（10bit）：也被叫做workId，这个可以灵活配置，机房或者机器号组合都可以。
序列号部分（12bit），自增值支持同一毫秒内同一个节点可以生成4096个ID。
在使用中，可以根据实际情况对每个部分的占比进行调整。

优点
没有网络IO开销，ID不连续，没有安全问题。
缺点
依赖时钟服务，当时间回调后会出现id重复。

混合使用

以上5种生成方案都有不同的缺点，在实际使用过程中各厂倾向于混合使用几种策略来满足自身的需求。

uid-generator

百度的uid-generator基于snowflake算法。解决了时钟回拨和瞬时高并发的问题。
uid-generator默认workNodeId持久化在数据库中，但也提供了重新实现workNodeId的接口。当时间回拨后，会自动生成新的nodeId，保证uid整体的不重复。
RingBuffer保存了当前可用的所有id序列，tail和cursor表示最新生成id和最新使用id，环状结构保证了序列的填充不用非得在正数时刻进行。由于不依赖时间服务，可以向未来借用时间生成id。解决了瞬时高并发的问题。

Leaf

美团团队根据业务场景提出了基于号段思想的 Leaf-Segment 方案和基于 Snowflake 的 Leaf-Snowflake 方案。出现两种方案的原因是Leaf-Segment并没有满足安全属性要求，容易被猜测。无法用在对外开放的场景（如订单）。Leaf-Snowflake 通过文件系统缓存降低了对 ZooKeeper 的依赖，同时通过对时间的比对和警报来应对 Snowflake 的时间回拨问题。

Seqsvr

微信并没有全局id，但他会为每个用户创建一组id，单个用户的id是顺序且唯一的。由于单个用户的吞吐量有限，该方案没有依赖时间服务，而是基于自增数和号段解决。

场景分析

基于部署成本和运维成本的考虑，事件中心被设计成既可以被集成部署，也可以独立部署的模式。所以在实际的环境中，往往会存在多个事件中心的实例。
这些情况对id生成器提出额外的要求：id的生成不能依赖单一中心组件，比如停车解决方案的数据库挂了，不能影响排水解决方案的id生成。且一个环境多个实例生成的id不能重复。
此外，应用需要在专有云，共有云等多种环境中部署。id生成器不能依赖时间服务。
最后，考虑到物联网的场景下，往往会产生事件风暴。所以id的生成还必须能够支持瞬时高并发。
综上现有的方案并不能100%的满足我们的需求，需要对其进行改造。

最终方案

id结构

基于以上的需求，我们采用snowflak算法作为基础进行了优化。我们依旧把64位分成4部分，其中：1bit符号，30bit时间偏移量，20bit机器id，13bit序列。

30bit的时间偏移量我们使用秒作为单位，可以支持34年使用。
20bit的机器id，支持每秒近50w台机器。
13bit的序列，可以支持8000qps的请求，对于单个解决方案来说足够了。

时间回拨

时间回拨通常有几个思路：
1. 缓存每毫秒的seq记录，当回拨时间时，使用之前没有用的seq创建新id，缺点是有可能会不够用。
2. 等待当前时间到lastTime，缺点是当回拨时间过长时，可用性无法保证。
3. 不再持续获取服务器最新时间，只在启动时获取一次时间，之后每个节点采取自增的方式维护自己的lastTime。当发现时间回拨时，更新一次nodeId。缺点是id中的“时间戳delta”并不代表实际生成的时间的偏移量。
经过评估第三种实现可以比较好的避免时间回拨问题。我们将nodeId持久化保存。每当机器启动时，或发现时间回拨时，在数据库里注册一个新的node记录，将新的id作为nodeId使用.

CREATE TABLE csa_work_node(
    `id` bigint unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
    `host_name` VARCHAR(64) NOT NULL COMMENT 'host name',
    `port` VARCHAR(64) NULL COMMENT 'port',
    `type` INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
    `gmt_modified` datetime  NOT NULL DEFAULT CURRENT_TIMESTAMP  COMMENT 'modified time',
    `gmt_create` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP  COMMENT 'created time',
    `is_deleted` bigint unsigned NOT NULL DEFAULT 0 COMMENT '是否删除0:未删除，1:删除',
    PRIMARY KEY(`id`)
) DEFAULT CHARACTER SET=utf8mb4 COMMENT='WorkNodeId';

由于需要持久化nodeId的信息，就需要考虑单点故障的问题。在这里我们将nodeId分为两部分，5bit的groupId和15bit的workId。“groupId”是由事件中心颁发给各解决方案的的分段标识，用以区分各解决方案产生的事件，“workId”用来标识每个id生成器实例的机器。

每个解决方案维护自己的workId，互相之间不影响。最终的nodeId为groupId+workId%32768。这样可以保证每秒2^15次的重启和时间回拨。

瞬时高并发

由于在解决时间回拨问题时，我们去掉了对时间服务的依赖，由每个实例维护自己的lastTime，所以具备了借用未来时间生成id的可能，在参考了uid-genenrator的实现后，我们这里直接使用uid-generator作为seqId的生成逻辑。

总结

通过上诉的设计，我们实现了不依赖时间服务的id生成器。且在多个实例同时存在的情况下，可以做到互相之间不影响，生成的id不重复。