雪花算法snowflake是一种优秀的分布式ID生成方案，其优点突出：它能生成全局唯一且递增的ID，确保了数据的一致性和准确性；同时，该算法灵活性强，可自定义各部分bit位，满足不同业务场景的需求；此外，雪花算法生成ID的速度快，效率高，能有效应对高并发场景，是分布式系统中不可或缺的组件。

在分布式系统的复杂环境下，数据量的持续激增对数据库架构提出了新的挑战。

传统的垂直与水平分库分表策略虽然能有效应对数据存储和扩展的问题，但却引出了一个新的需求：需要一个全局唯一标识符（ID）来标定每条数据或消息队列（MQ）中的消息。

在这种情况下，依赖数据库自身的ID自增功能显然已经无法满足需求，因此，必须设计出符合以下要求的分布式ID生成策略：

1、全局唯一性，所生成的ID必须在全局范围内是独一无二的，以确保数据的精准标识，避免任何可能的ID冲突。

2、趋势递增，鉴于多数关系型数据库管理系统（RDBMS）如MySQL的InnoDB引擎使用B树结构来存储索引数据，并依赖聚集索引进行优化，最好择有序的ID以保证高效的写入性能，因此生成的ID应具备整体递增的趋势。

3、单调递增，在特定场景下，如分布式事务的版本控制、即时通讯的增量消息传递或数据排序等，需要确保每个新生成的ID都严格大于前一个ID，从而实现数据的线性顺序增长。

4、信息安全，针对某些敏感业务，如订单处理等，生成的分布式ID必须是无规则的，以防止外部通过解析ID获取到流量信息或其他商业机密，这就需要ID生成策略在保持唯一性和递增性的同时，还要具备足够的信息隐匿性。

在分布ID生成的领域，目前市面上主要流行几种算法，这些算法也是众多开源项目进行优化和实现的基础：

1、UUID方式，UUID由于是在本地生成，因此具有极高的性能，然而，它生成的ID长度较长，达到16字节128位，通常需要使用字符串类型进行存储。

此外，UUID是无序的，这使得它在许多场景中并不适用，尤其是在作为MySQL数据库的主键和索引时。MySQL官方建议主键应尽可能短，而对于InnoDB引擎来说，索引的无序性可能会导致数据位置频繁变动，从而严重影响性能。

2、数据库自增ID方式，这种方法的缺点是每次获取ID都需要进行数据库IO操作，给数据库带来较大压力，且性能较低。如果数据库发生宕机，对依赖其服务的外部系统将是毁灭性的打击。

尽管可以通过部署数据库集群来提高可用性，但问题并未从根本上解决。

3、数据库号段算法，这是对数据库自增ID的一种优化方法。通过每次获取一个号段的值，可以大大减少与数据库的交互次数，从而显著降低数据库的压力。号段越长，性能越高。即使数据库发生宕机，只要号段未用完，系统仍能在短时间内继续提供服务。

美团的Leaf和滴滴的TinyId就是采用这种算法的典型例子。

4、雪花算法，Twitter开源的snowflake算法，以时间戳、机器标识和递增序列为基础生成ID。这种算法生成的ID基本呈趋势递增，且性能很高。然而，由于它强烈依赖于机器时钟，因此需要考虑时钟回拨问题。即当机器上的时间因校正而发生倒退时，可能会导致生成的ID重复。

目前，百度的uid-generator和美团的Leaf也都在使用或优化这种算法。

Snowflake算法的原理相对直观，它负责生成一个64位（long型）的全局唯一ID，这个ID的构成包括：1位无用的符号位、41位的时间戳、10位的机器ID以及12位的序列号，除了固定的1位符号位之外，其余的三个部分都可以根据实际需求进行调整：

1、41位时间戳：这部分能够表示的时间跨度为（1L if (workerId > maxWorkerId || workerId throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId)); } this.workerId = workerId; this.datacenterId = datacenterId; } // ==============================Methods========================================== /** * 获得下一个ID (该方法是线程安全的) * @return SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常 if (timestamp sequence = (sequence + 1) & sequenceMask; //毫秒内序列溢出 if (sequence == 0) { //阻塞到下一个毫秒,获得新的时间戳 timestamp = tilNextMillis(lastTimestamp); } } //时间戳改变，毫秒内序列重置 else { sequence = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID return ((timestamp - twepoch) timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * @return 当前时间(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } //==============================Test============================================= /** 测试 */ public static void main(String[] args) { SnowflakeIdWorkerV1 idWorker = new SnowflakeIdWorkerV1(0, 0); for (int i = 0; i // ==============================Fields=========================================== /** 开始时间截 (2015-01-01) */ private final long twepoch = 1420041600000L; /** 机器id所占的位数 */ private final long workerIdBits = 5L; /** 数据标识id所占的位数 */ private final long datacenterIdBits = 5L; /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */ private final long maxWorkerId = -1L ^ (-1L throw new IllegalArgumentException( String.format("worker Id can't be greater than %d or less than 0", maxWorkerId)); } if (datacenterId > maxDatacenterId || datacenterId long sequenceTmp = sequence; sequence = (sequence + 1) & sequenceMask; if (sequence == 0 && sequenceTmp >= 0) { // sequence自增到最大了，时间戳自增1 startTimestamp += 1; } // 移位并通过或运算拼到一起组成64位的ID return ((startTimestamp - twepoch) SnowflakeIdWorkerV2 idWorker = new SnowflakeIdWorkerV2(0, 0, timeGen()); for (int i = 0; i return id & ~(-1L return id >> DATA_CENTER_ID_SHIFT & ~(-1L return (id > (TOTAL_BITS - SEQUENCE_BITS); } /** * 通过移位解析出workerId，workerId有效位为[13,17], 左右两边都有无效位 * 先向左移 41+5+1，移除掉41bit-时间，5bit-IDC、1bit-sign， * 然后右移回去41+5+1+12，从而移除掉12bit-序列号 * @param id * @return */ public long getWorkerId2(long id) { return (id > (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS); } /** * 通过移位解析出IDC_ID，dataCenterId有效位为[18,23]，左边两边都有无效位 * 先左移41+1，移除掉41bit-时间和1bit-sign * 然后右移回去41+1+5+12，移除掉右边的5bit-workerId和12bit-序列号 * @param id * @return */ public long getDataCenterId2(long id) { return (id > (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS); } /** * 41bit-时间，左边1bit-sign为0，可以忽略，不用左移，所以只需要右移，并加上起始时间twepoch即可。 * @param id * @return */ public long getGenerateDateTime2(long id) { return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch; } ID生成器使用方式

在分布式ID生成的策略中，通常采用两种方式：一是基于发号器的方案，二是本地生成方案。

1、发号器方案

该方案将雪花算法ID的生成逻辑封装成一个独立的服务，并部署在多个服务器上，外部系统通过请求发号器服务来获取ID，此方案的优势在于，无需部署大量的服务器，仅需确保服务器数量满足需求即可，默认的1024台已经足够。

但是，由于ID的获取涉及到远程请求，因此会受到网络波动的影响，其性能自然无法与直接从本地生成相比，同时，发号器服务的稳定性至关重要，一旦服务出现故障，将影响到许多依赖其的外部服务。为了确保发号器的高可用性，需要采取多实例部署、异地容灾等策略。

此外，发号器在设计时还可以考虑一次性发布一段时间内的ID供服务本地缓存，这样既能提升性能，减少对发号器的频繁请求，也能在一定程度上降低发号器故障所带来的风险。

2、本地生成方案

在此方案中，ID是在本地直接生成的，因此不存在网络延迟问题，性能极高。但是，为了确保生成的ID具有全局唯一性，需要依赖机器ID来进行区分。因此每台机器以及机器上部署的每个服务都需要分配不同的机器ID。

此外，服务重启后也需要重新分配新的机器ID，这种特性使得机器ID具有“用后即弃”的性质，为了满足对大量机器ID的需求，不得不减少时间戳和序列号的位数，这样做虽然会牺牲一部分ID的丰富性，但却是保证本地生成方案可行性的必要妥协。

"&"表示按位与操作，它用于操作整数类型的位模式，并将每个操作数中的每一位进行与操作，它会将两个整数的二进制表示进行按位与运算，只有当两个数的相应位都为1时，结果的相应位才为1，否则为0。这种运算符通常用于低级位操作，如设置、清除或翻转二进制位。

"|"表示按位或操作，它用于操作整数类型的位模式，并将每个操作数中的每一位进行或操作，它会将两个整数的二进制表示进行按位或运算，只要两个数的相应位中有一个为1，结果的相应位就为1，否则为0。

运算符“^”表示按位异或（XOR）操作，它是一个二元运算符，用于对两个整数的二进制位进行异或运算，异或运算的规则是：如果两个相应的二进制位相同，则结果为0；如果两个相应的二进制位不同，则结果为1。

按位异或运算符“^”通常用于处理整数的位级操作，当对两个整数进行异或运算时，它们的每一个二进制位都会根据异或规则进行运算，生成一个新的整数作为结果。

除了整数类型，按位异或运算符也可以应用于布尔类型。在布尔上下文中，运算符“^”表示逻辑异或操作。当应用于两个布尔值时，如果两个值不同，则结果为true；如果两个值相同，则结果为false。

在这个示例中，整数a和b的二进制表示分别为0000 1111和0000 1000，对它们进行按位异或运算后，得到的结果为0000 0111，即十进制数7。

这段Java代码定义了一个用于生成唯一ID的方法nextId2()，该方法不依赖于机器时钟，从而彻底解决了时钟回拨问题。代码中包含两个关键变量：sequence和startTimestamp。

sequence初始化为-1，这是为了避免浪费sequence+1=0这一序列号。在每次生成ID时，sequence会自增，并通过与SEQUENCE_MASK进行位与操作来确保其在有效范围内循环。当sequence自增到最大值并回绕到0时，如果之前的sequenceTmp（即sequence自增前的值）是非负的，那么说明不是初始情况下的自增，此时会将startTimestamp时间戳自增1，以确保生成的ID的唯一性。

startTimestamp是一个初始时间戳，可以在构造器中指定，也可以使用默认值。该时间戳用于与twepoch（一个预设的常量值，表示时间起点）相减，从而得到一个相对时间差，这个相对时间差与序列号结合使用，通过allocate()方法生成最终的唯一ID。

这种方法的优点在于，它完全摆脱了机器时钟的限制，因此不会受到时钟回拨问题的影响。

同时，由于时间戳的自增是由程序自己控制的，因此可以充分利用未来时间，预先生成一些ID并存储在缓存中。

这样，外部系统可以直接从缓存中获取ID，而无需等待ID的生成过程，从而大大提高了性能。

此外，该方法还确保了每一毫秒内可以生成多达4096个序列号（范围从0到4095），且没有浪费。

*然而，这种方法也存在一个明显的缺点，即生成的ID中的时间戳并不是真实的时间。*如果系统的流量较小，那么时间戳可能会滞后很多。

因此，如果对从ID中解析出来的时间戳有特定的利用需求（例如用于记录事件发生的时间），那么这个缺点可能会成为问题。但如果时间戳的利用意义不大，那么这个缺点也就可以忽略不计了。

这里缓存了2000ms的序列号，如果发生时钟回拨，且回拨范围在2000ms内，就从缓存中取序列号自增，超过2000ms回拨，就抛异常，故障转移，将请求分配到正常机器。

等待时钟自己校正来解决时钟回拨问题，适用于回拨幅度小的场景。

比如回拨时长小于500ms，那就睡眠500ms，等时间恢复到正常，如果这个过程中又发生了时钟回拨，不可能一直等它校正，实际生产中可限定校正的次数，超过最大校正次数，那就抛异常吧，这属于极端情况。

小结

解决时钟回拨问题的方法还有很多，无非就是避免和缓解。

每种方式有各自的特点和适用场景，可以两两结合使用，比如时钟回拨幅度小，就休眠校正，回拨幅度大或者出现多次回拨，也不抛异常，获取缓存sequence对外提供服务，也可以当发生时钟回拨时，用备用机器id生成ID等。

1、在分布式系统中生成全局唯一的ID至关重要，目前，业界广泛采用的方案包括数据库号段算法和雪花算法，这些算法不仅在大厂中得到了广泛应用，还催生了诸多开源项目，例如百度的uid-generator、美团的Leaf以及滴滴的TinyId等。

2、雪花算法以其简单高效而著称，其核心在于结合时间戳、机器ID和序列号来生成64位的唯一ID，该算法生成的ID整体上呈递增趋势，确保了全局唯一性，同时性能表现优异。雪花算法提供了高度的灵活性，允许根据实际需求自定义各个组成部分的bit位数，若需提升QPS（每秒查询率），可适当增加序列号所占的bit位数。

3、尽管雪花算法具有诸多优点，但它对机器时钟的强依赖性也带来了时钟回拨问题，为应对这一问题，开发者们提出了多种解决方案，主要分为避免和缓解两大类。*常见的方法包括使时间戳自增以摆脱对机器时钟的依赖、利用缓存来存储序列号，或等待时钟自行校正等。*每种方法都有其独特之处，只有正确利用它们的优点，才能最大限度地提升系统性能。

4、雪花算法ID生成器的使用方式灵活多样，其中远程发号器和本地直接生成ID是两种主要方式。*远程发号器需要确保高可用性，以满足分布式系统中的需求；而本地直接生成ID则省去了远程请求的开销，因此在性能上更具优势。*然而，本地生成方式也带来了机器ID管理的挑战，因为一旦某个机器ID被使用，它就不能再被其他机器重复使用。为了应对这一挑战，开发者们通常利用MySQL或ZooKeeper等工具来进行机器ID的管理和分配。

END! END! END!

深度思考：总结SOA、WSDL、SOAP、REST、UDDI之间的关系

Spring揭秘：@import注解应用场景及实现原理！

Java并发基础：原子类之AtomicMarkableReference全面解析！

Java并发基础：concurrent Flow API全面解析

Java并发基础：CopyOnWriteArraySet全面解析