一位工作4年的小伙伴，去某东面试时被问到这样一道题，说请你简述一下雪花算法的实现原理。屏幕前的小伙伴，如果你遇到这个问题，你会怎么回答？
今天，我给大家分享一下我的理解。
1、什么是雪花算法
雪花算法英文翻译为 Snow Flake 算法，它是由Twitter开源的分布式 ID生成算法。主要应用于分库分表场景中的全局ID作为业务主键，或者生成全局唯一的订单号。
那为什么要叫雪花算法呢？据相关研究表示，一般的雪花大约由10的19次方个水分子组成。在雪花形成过程中，会形成不同的结构分支，所以说大自然中不存在两片完全一样的雪花，每一片雪花都拥有自己独特的形状。雪花算法的意思是表示生成的ID如雪花一般独一无二。
其实，单单解决唯一ID这个问题有很多的解决方法，比如UUID、系统时间戳、Redis原子递增、数据库全局表自增ID等等。但是在实际应用中，我们需要的ID除了唯一性以外，还需要满足以下特征：
1）、单调递增：保证下一个ID号一定大于上一个。
2）、保证安全：ID号需要无规则性，不能让别人根据ID号猜出我们的信息和业务数据量，增加恶意用户扒取数据的难度。
3）、含时间戳：需要记录系统时间戳
4）、高可用：发布一个获取分布式ID的请求，服务器至少要保证99.999%的情况下给创建一个全局唯一的分布式ID。
5）、低延迟：发布一个获取分布式ID的请求，要快，急速。
6）、高QPS：假如并发一口气10万个创建分布式ID请求同时杀过来，服务器要顶得住并且成功创建10万个分布式ID。
雪花算法就是一个比较符合这类特征的全局唯一算法。在很多大厂的全局ID组件中，都有用到，比如百度的UidGenerator、美团的Leaf算法等等。
2、实现原理
雪花算法那是一个由64个Bit(比特)位组成的long类型的数字。如图所示，它分为四个部分。
第一部分，用1个bit（比特）位来表示1个符号位，因为ID一般不会是负数，所以一般情况下就是0。
第二部分，用41个bit(比特)位来表示系统时间戳，这个时间戳就是系统时间记录的毫秒数。41个bit可以表示的最大数字为2的41次方减1毫秒，换算成时间为69年。
第三部分，用10个bit（比特）位来技术工作机器的ID，用来保证多个服务器上生成ID的唯一性。如果存在跨机房部署的情况，还可以把这10个比特位拆分为两组，每组5个bit（比特）位。前面的5个bit（比特）表示机房ID，后面5个bit（比特）表示机器ID。10个比特位最大值是2的10次方，也就是最多1024台机器。
第四部分，用12个比特位来表示递增序列，用来记录同一毫秒内产生不同ID的能力。它的最大值为2的12次方减1，也就是4096。
雪花算法就是根据这四个部分的组成规则，生成对应Bit位的数据，然后组装到一起生成一个全局唯一ID。
3、雪花算法的优缺点
雪花算法主要有以下优点：
1）、分布式系统内不会产生ID碰撞，效率高。
2）、不需要依赖数据库等第三方系统，稳定性更高，可以根据自身业务分配bit位，非常灵活。
3）、生成ID的性能也非常高，每秒能生成26万个自增可排序的ID。
当然，雪花算法那也有缺点，因为它依赖机器时钟，如果机器时钟回拨，可能会导致ID重复。如果再分布式环境下，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况。当然，大部分情况下可以忽略这一缺点。
其实雪花算法，本身并不复杂。我们只要把它的设计理念和思想讲明白，就能够获得面试官的认可，以上就是我对雪花算法的理解。最后，我用Java代码实现了一个雪花算法，有兴趣的小伙伴可以在评论区留言获取，加深一下理解。
public class SnowFlake { /** * 开始时间截 (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 << workerIdBits); /** * 支持的最大数据标识id，结果是31 */ private final long maxDataCenterId = ~(-1L << dataCenterIdBits); /** * 序列在id中占的位数 */ private final long sequenceBits = 12L; /** * 机器ID向左移12位 */ private final long workerIdShift = sequenceBits; /** * 数据标识id向左移17位(12+5) */ private final long dataCenterIdShift = sequenceBits + workerIdBits; /** * 时间截向左移22位(5+5+12) */ private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits; /** * * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */ private final long sequenceMask = ~(-1L << sequenceBits); /** * 工作机器ID(0~31) */ private volatile long workerId; /** * 数据中心ID(0~31) */ private volatile long dataCenterId; /** * 毫秒内序列(0~4095) */ private volatile long sequence = 0L; /** * 上次生成ID的时间截 */ private volatile long lastTimestamp = -1L; //==============================Constructors===================================== /** * 构造函数 * * @param workerId 工作ID (0~31) * @param dataCenterId 数据中心ID (0~31) */ public SnowFlake(long workerId, long dataCenterId) { if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId)); } if (dataCenterId > maxDataCenterId || dataCenterId < 0) { 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 (该方法是线程安全的) * 如果一个线程反复获取Synchronized锁，那么synchronized锁将变成偏向锁。 * @return SnowflakeId */ public synchronized long nextId() throws RuntimeException { long timestamp = timeGen(); //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常 if (timestamp < lastTimestamp) { throw new RuntimeException((String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp))); } //如果是同一时间生成的，则进行毫秒内序列 if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; //毫秒内序列溢出 if (sequence == 0) { //阻塞到下一个毫秒,获得新的时间戳 timestamp = tilNextMillis(lastTimestamp); } } //时间戳改变，毫秒内序列重置 else { sequence = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID return ((timestamp - twepoch) << timestampLeftShift) | (dataCenterId << dataCenterIdShift) | (workerId << workerIdShift) | sequence; } /** * 阻塞到下一个毫秒，直到获得新的时间戳 * * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */ private long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * * @return 当前时间(毫秒) */ private long timeGen() { return System.currentTimeMillis(); } }
我是被编程耽误的文艺Tom，关注我，面试不再难！
完整版面试资料和答案以及PDF文档 ：
