分布式id生成器方案详细介绍

　　问题描述
　　在物联网场景的解决方案中，通常需要将设备的信息转换为一个业务事件进行输出。在生成升级事件的过程往往需要多次的数据库操作，且伴随着异步的逻辑。依靠数据库的自增id作为事件的id容易造成脏数据且会占用大量的数据库资源，所以需要系统内置一个轻量级的id生成器。常见解决方案
　　UUID
　　UUID（universallyuniqueidentifier）是基于时间生成的128位随机标识符，算法保证了UUID重复的可能性接近于0，且UUID的生成不依赖中心注册单元，完全是分布式生成的。JAVA自带了生成UUID的类库。publicstaticvoidmain（String〔〕args）｛StringuuidUUID。randomUUID（）。toString（）。replaceAll（，）；System。out。println（uuid）；｝
　　优点：
　　生成足够简单，本地生成无网络消耗，具有唯一性
　　缺点：
　　无序的字符串，不具备趋势自增特性
　　没有具体的业务含义
　　长度过长16字节128位，字符串36位，很难作为主键保存。数据库自增ID
　　基于数据库的autoincrement自增ID完全可以充当分布式ID，具体实现：需要一个单独的MySQL实例用来生成ID，建表结构如下：CREATETABLESEQUENCEID（idbigint（20）unsignedNOTNULLautoincrement，tagchar（10）NOTNULLdefault，PRIMARYKEY（id），）ENGINEINNODB；
　　当需要一个ID的时候，向表中插入一条记录返回主键ID。insertintoSEQUENCEID（value）VALUES（tag）；数据库集群自增ID
　　由于单个数据库有可能造成单点故障，所以数据库自增还可以基于数据库集群来提供。可以避免因为单点造成的不可用，ID重复的问题可以通过给每个数据库设置不同的起始id和步长进行控制。
　　MySQL1配置：setautoincrementoffset1；起始值setautoincrementincrement2；步长
　　MySQL2配置：setautoincrementoffset2；起始值setautoincrementincrement2；步长
　　优点：
　　实现简单，ID单调自增，数值类型查询速度快
　　缺点：
　　无法支持高并发场景，单机模式有不可用风险，集群模式后期无法扩容。号段模式
　　号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如（1，1000〕代表1000个ID，具体的业务服务将本号段，生成11000的自增ID并加载到内存。表结构如下：CREATETABLESEGAMENTID（idint（10）NOTNULL，maxidbigint（20）NOTNULLCOMMENT当前最大id，stepint（20）NOTNULLCOMMENT号段的步长，tagvarchar（8）NOTNULLCOMMENT业务标识，versionint（20）NOTNULLCOMMENT是一个乐观锁，每次都更新version，保证并发时数据的正确性，PRIMARYKEY（id））
　　表里插入初始化的数据，确定步长和id初始值。insertintoSEGAMENTID（maxid，step，tag，version）values（1，1000，tag，1）；
　　将（1，1000〕放到内存里供系统使用。
　　等这批号段ID用完，再次向数据库申请新号段，对maxid字段做一次update操作，maxidmaxidstep，update成功则说明新号段获取成功，新的号段范围是（maxid，maxidstep〕。updateSEGAMENTIDsetmaxid｛maxidstep｝，versionversion1whereversion｛version｝andtagtag
　　优点：
　　高并发，不会占用大量数据库性能。
　　缺点：
　　当吞吐量上去后，依旧存在单点故障问题。redis自增
　　基于用redis的incr命令实现ID的原子性自增，也可视实现uid快速生成。127。0。0。1：6379setseqid1初始化自增ID为1OK127。0。0。1：6379incrseqid增加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年，（1L41）（1000L606024365）69年
　　工作机器id（10bit）：也被叫做workId，这个可以灵活配置，机房或者机器号组合都可以。
　　序列号部分（12bit），自增值支持同一毫秒内同一个节点可以生成4096个ID。
　　在使用中，可以根据实际情况对每个部分的占比进行调整。
　　优点
　　没有网络IO开销，ID不连续，没有安全问题。
　　缺点
　　依赖时钟服务，当时间回调后会出现id重复。混合使用
　　以上5种生成方案都有不同的缺点，在实际使用过程中各厂倾向于混合使用几种策略来满足自身的需求。uidgenerator
　　百度的uidgenerator基于snowflake算法。解决了时钟回拨和瞬时高并发的问题。
　　uidgenerator默认workNodeId持久化在数据库中，但也提供了重新实现workNodeId的接口。当时间回拨后，会自动生成新的nodeId，保证uid整体的不重复。
　　RingBuffer保存了当前可用的所有id序列，tail和cursor表示最新生成id和最新使用id，环状结构保证了序列的填充不用非得在正数时刻进行。由于不依赖时间服务，可以向未来借用时间生成id。解决了瞬时高并发的问题。
　　Leaf
　　美团团队根据业务场景提出了基于号段思想的LeafSegment方案和基于Snowflake的LeafSnowflake方案。出现两种方案的原因是LeafSegment并没有满足安全属性要求，容易被猜测。无法用在对外开放的场景（如订单）。LeafSnowflake通过文件系统缓存降低了对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使用。CREATETABLEcsaworknode（idbigintunsignedNOTNULLAUTOINCREMENTCOMMENT主键，hostnameVARCHAR（64）NOTNULLCOMMENThostname，portVARCHAR（64）NULLCOMMENTport，typeINTNOTNULLCOMMENTnodetype：ACTUALorCONTAINER，gmtmodifieddatetimeNOTNULLDEFAULTCURRENTTIMESTAMPCOMMENTmodifiedtime，gmtcreatedatetimeNOTNULLDEFAULTCURRENTTIMESTAMPonupdateCURRENTTIMESTAMPCOMMENTcreatedtime，isdeletedbigintunsignedNOTNULLDEFAULT0COMMENT是否删除0：未删除，1：删除，PRIMARYKEY（id））DEFAULTCHARACTERSETutf8mb4COMMENTWorkNodeId；
　　由于需要持久化nodeId的信息，就需要考虑单点故障的问题。在这里我们将nodeId分为两部分，5bit的groupId和15bit的workId。groupId是由事件中心颁发给各解决方案的的分段标识，用以区分各解决方案产生的事件，workId用来标识每个id生成器实例的机器。
　　每个解决方案维护自己的workId，互相之间不影响。最终的nodeId为groupIdworkId32768。这样可以保证每秒215次的重启和时间回拨。
　　瞬时高并发
　　由于在解决时间回拨问题时，我们去掉了对时间服务的依赖，由每个实例维护自己的lastTime，所以具备了借用未来时间生成id的可能，在参考了uidgenenrator的实现后，我们这里直接使用uidgenerator作为seqId的生成逻辑。总结
　　通过上诉的设计，我们实现了不依赖时间服务的id生成器。且在多个实例同时存在的情况下，可以做到互相之间不影响，生成的id不重复。