UUID的弊端以及雪花算法

　　一、问题
　　为什么需要分布式全局唯一ID以及分布式ID的业务需求
　　在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识如在美团点评的金融、支付、餐饮、酒店；猫眼电影等产品的系统中数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。
　　此时一个能够生成全局唯一ID的系统是非常必要的
　　ID生成规则部分硬性要求
　　全局唯一
　　即不能出现重复ID号
　　趋势递增
　　在Mysql的InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用的是BTree的数据结构作为存储索引数据，在主键的选择上我们应该尽量使用有序的主键保证写入性能
　　单调递增
　　保证下一个ID一定大于上一个ID，如事务版本号、排序等特殊要求
　　信息安全
　　如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可：如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，需要ID无规则不规则，让竞争对手不好猜
　　含时间戳
　　在开发中能快速了解这个分布式id生成的时间
　　ID号生成系统的可用性要求
　　高可用
　　发一个获取分布式ID的请求，服务器要保证99。999的情况下能给我返回一个分布式ID
　　低延迟
　　返回的速度要快
　　高QPS（抵抗高访问）
　　比如一秒内10万个，需要服务器能抵抗住并且生成10万个分布式ID
　　二、一般通用方案
　　（一）UUID
　　jdk自带，生成36位字符，形式为844412，包含4个连号，对于单体式仅需满足唯一的话可以使用好处：性能高，本地生成，无网络消耗坏处：无序且字符串长，存入数据库会增大数据库压力，入数据库性能差。mysql官方推荐主键越短越好
　　索引，B树索引的分裂
　　既然分布式id是主键，然后主键是包含索引的，然后mysql的索引是通过b树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的b树进行修改，因为UUID数据是无序的。
　　所以每一次UUID数据的插入都会对主键地的b树进行很大的修改，这一点很不好。插入完全无序，不但会导致一些中间节点产生分裂，也会白白创造出很多不饱和的节点，这样大大降低了数据库插入的性能
　　（二）数据库自增主键
　　数据库自增主键实现原理：数据库自增id和replaceinto实现的
　　REPLACEINTO的含义是插入一条记录，如果表中唯一索引的值遇到冲突，则替换老数据
　　那数据库自增ID机制适合作分布式ID吗？答案是不太适合系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是1，2。3。4。5（步长是1），这个时候需要扩容机器一台。可以这样做，把第二台机器的初始值设置得比第一台超过很多，貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。所以系统水平扩展方案复杂难以实现。数据库压力还是很大，每次获取ID都得读写一次数据库，非常影响性能，不符合分布式ID里面的延迟低和要高QPS的规则（在高并发下，如果都去数据库里面获取id，那是非常影响性能的）
　　（三）Redis生成全局id策略
　　因为Redis是单线的天生保证原子性，可以使用原子操作INCR和INCRBY来实现
　　注意：在Redis集群情况下，同样和MySQL一样需要设置不同的增长步长，同时key一定要设置有效期
　　可以使用Redis集群来获取更高的吞吐量。
　　假如一个集群中有5台Redis。可以初始化每台Redis的值分别是1，2，3，4，5，然后步长都是5。
　　各个Redis生成的ID为：A：1，6，11，16，21B：2，7，12，17，22C：3，8，13，18，23D：4，9，14，19，24E：5，10，15，20，25
　　三、snowflake
　　（一）概述
　　官网：
　　https：github。comtwitterarchivesnowflake
　　Twitter的分布式自增ID算法
　　特点：
　　能够按照时间有序生成
　　Snowflake算法生成id的结果是一个64bit大小的整数，为一个Long型，转化为字符串最多19位
　　分布式系统内不会产生ID碰撞（由datacenter和workerld作区分）并且效率较高。
　　（二）结构
　　bit表示，id一般为正，所以固定为0
　　时间戳位范围为0241次方，大概是可以使用69年（从1970算起）
　　工作进程位最多为210，即1024个节点，包括5位datacenter和5位workerld作区分
　　12bit序列号，序列号，用来记录同毫秒内产生的不同id。12位（bit）可以表示的最大正整数是21214059
　　（三）代码TwitterSnowflake
　　SnowFlake的结构如下（每部分用分开）：
　　0000000000000000000000000000000000000000000000000000000000000000
　　1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
　　41位时间截（毫秒级），注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截开始时间截）得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T（1L41）（1000L606024365）69
　　10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId
　　12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒（同一机器，同一时间截）产生4096个ID序号
　　加起来刚好64位，为一个Long型。
　　SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由数据中心ID和机器ID作区分），并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。publicclassSnowflakeIdWorker｛Fields开始时间截（20200828）privatefinallongtwepoch1598598185157L；机器id所占的位数privatefinallongworkerIdBits5L；数据标识id所占的位数privatefinallongdatacenterIdBits5L；支持的最大机器id，结果是31（这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数）privatefinallongmaxWorkerId1L（1LworkerIdBits）；支持的最大数据标识id，结果是31privatefinallongmaxDatacenterId1L（1LdatacenterIdBits）；序列在id中占的位数privatefinallongsequenceBits12L；机器ID向左移12位privatefinallongworkerIdShiftsequenceBits；数据标识id向左移17位（125）privatefinallongdatacenterIdShiftsequenceBitsworkerIdBits；时间截向左移22位（5512）privatefinallongtimestampLeftShiftsequenceBitsworkerIdBitsdatacenterIdBits；生成序列的掩码，这里为4095（0b1111111111110xfff4095）privatefinallongsequenceMask1L（1LsequenceBits）；工作机器ID（031）privatelongworkerId；数据中心ID（031）privatelongdatacenterId；毫秒内序列（04095）privatelongsequence0L；上次生成ID的时间截privatelonglastTimestamp1L；Constructors构造函数paramworkerId工作ID（031）paramdatacenterId数据中心ID（031）此方法是判断传入的机房号和机器号是否超过了最大值，即31，或者小于0publicSnowflakeIdWorker（longworkerId，longdatacenterId）｛if（workerIdmaxWorkerIdworkerId0）｛thrownewIllegalArgumentException（String。format（workerIdcantbegreaterthandorlessthan0，maxWorkerId））；｝if（datacenterIdmaxDatacenterIddatacenterId0）｛thrownewIllegalArgumentException（String。format（datacenterIdcantbegreaterthandorlessthan0，maxDatacenterId））；｝this。workerIdworkerId；this。datacenterIddatacenterId；｝Methods核心方法获得下一个ID（该方法是线程安全的）returnSnowflakeIdpublicsynchronizedlongnextId（）｛1。获取当前的系统时间longtimestamptimeGen（）；如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常if（timestamplastTimestamp）｛thrownewRuntimeException（String。format（Clockmovedbackwards。Refusingtogenerateidfordmilliseconds，lastTimestamptimestamp））；｝如果是同一时间生成的，则进行毫秒内序列if（lastTimestamptimestamp）｛sequence要增1，但要预防sequence超过最大值4095，所以要与SEQUENCEMASK按位求与即如果此时sequence等于4095，加1后为4096，再和4095按位与后，结果为0sequence（sequence1）sequenceMask；毫秒内序列溢出if（sequence0）｛阻塞到下一个毫秒，获得新的时间戳timestamptilNextMillis（lastTimestamp）；｝｝时间戳改变，毫秒内序列重置else｛sequence0L；｝上次生成ID的时间截把当前时间赋值给lastTime，以便下一次判断是否处在同一个毫秒内lastTimestamptimestamp；移位并通过或运算拼到一起组成64位的IDlongid（（timestamptwepoch）timestampLeftShift）时间戳减去默认时间再左移22位与运算（datacenterIddatacenterIdShift）机房号左移17位与运算（workerIdworkerIdShift）机器号左移12位与运算sequence；序列号无需左移直接进行与运算returnid；｝阻塞到下一个毫秒，直到获得新的时间戳paramlastTimestamp上次生成ID的时间截return当前时间戳protectedlongtilNextMillis（longlastTimestamp）｛longtimestamptimeGen（）；while（timestamplastTimestamp）｛timestamptimeGen（）；｝returntimestamp；｝返回以毫秒为单位的当前时间return当前时间（毫秒）protectedlongtimeGen（）｛returnSystem。currentTimeMillis（）；｝Test测试publicstaticvoidmain（String〔〕args）｛SnowflakeIdWorkeridWorkernewSnowflakeIdWorker（0，0）；for（inti0；i1000；i）｛longididWorker。nextId（）；System。out。println（id）；｝｝｝
　　（四）优缺点
　　优点：
　　毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。可以根据自身业务特性分配bit位，非常灵活。
　　缺点：
　　依赖机器时钟，如果机器时钟回拨，会导致重复ID生成在单机上是递增的，但是由于设计到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况（此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会亚格要求递增，90的需求都只要求趋势递增）
　　缺点的解决方案
　　可以参照以下两个来进行机器时钟的同步百度开源的分布式唯一ID生成器UidGeneratorLeaf美团点评分布式ID生成系统