什么是雪花算法？
在集群高并发情况下如何保证分布式全局唯一ID生成？
分布式ID生成规则硬性要求：
1、全局唯一：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
2、趋势递增：MySQL中InnoDB引擎使用的是聚集索引。多数RDBMS使用Btree的数据结构来存储索引数据，在主键的选择上尽量选择有序的主键保证写入性能。
3、单调递增：保证下一个ID号一定大于上一个。
4、保证安全：ID号需要无规则性，不能让别人根据ID号猜出我们的信息和业务数据量，增加恶意用户扒取数据的难度。
5、含时间戳。
分布式ID生成可用性要求：
1、高可用：发布一个获取分布式ID的请求，服务器就要保证99.999%的情况下给创建一个全局唯一的分布式ID。
2、低延迟：发布一个获取分布式ID的请求，要快，急速。
3、高QPS：假如并发一口气10万个创建分布式ID请求同时杀过来，服务器要顶得住并且成功创建10万个分布式ID。
生成主键方案有哪些：
1、UUID。
2、数据库自增主键。
3、基于Redis生成全局ID策略。
4、雪花算法，Twitter的分布式自增ID算snowflake。
5、百度UidGenerator算法(基于雪花算法实现自定义时间戳)。
6、美团Leaf算法(依赖于数据库，ZK)。
1、UUID的优缺点：
优点：性能非常高，JDK自带本地生成，无网络消耗。
缺点：（1）只保证了唯一性，趋势递增。（2）无序，无法预测他的生成规则，不能生成递增有序的数字。（3）mysql官方推荐主键越短越好，UUID包含32个16位进制的字母数字，每一个都很长。（4）B+树索引的分裂。主键是包含索引的，mysql的索引是通过B+树来实现的，每一次新的UUID数据插入，为了查询优化，因为UUID是无序的，都会对索引底层的B+树进行修改。插入无序，不但会导致一些中间节点产生分裂，也会白白创造很多不饱和的节点，大大降低了数据库插入的性能。
2、数据库自增主键的优缺点：
优点：简单方便易用。
缺点：（1）要设置增长步长，系统水平扩展比较困难。（2）每次获取ID都得读写一次数据库，数据库压力大，非常影响性能，不符合分布式ID里低延迟和高QPS的规则。
3、基于Redis生成全局ID策略优缺点：
优点：满足分布式ID生成要求，并且已有成功落地案例。
缺点：（1）要设置增长步长，同时key一定要设置有效期。（2）为了一个分布式ID，要搞一个Redis集群，维护成本大。
4、雪花算法，Twitter的分布式自增ID算snowflake优缺点：
优点：（1）经测试snowflake每秒能生成26万个自增可排序的ID。（2）snowflake生成的ID结果是一个64bit大小的整数，为一个Long型 （转换成字符串后长度最多19）。（3）分布式系统内不会产生ID碰撞（datacenter和workerId作区分）并且效率高。
雪花算法的几个核心组成：
主要分为 5 个部分：
是 1 个 bit：0，这个是无意义的。
是 41 个 bit：表示的是时间戳。
是 10 个 bit：表示的是机房 id，0000000000，因为我传进去的就是0。
是 12 个 bit：表示的序号，就是某个机房某台机器上这一毫秒内同时生成的 id 的序号，0000 0000 0000。
1 bit，是无意义的：
因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。
41 bit：表示的是时间戳，单位是毫秒。
41 bit 可以表示的数字多达 2^41 – 1，也就是可以标识 2 ^ 41 – 1 个毫秒值，换算成年就是表示 69 年的时间，从1970年到2039年9月7日。
10 bit：记录工作机器 id，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。
但是 10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房里可以代表 2 ^ 5 个机器（32 台机器），这里可以随意拆分，比如拿出4位标识业务号，其他6位作为机器号。可以随意组合。
12 bit：这个是用来记录同一个毫秒内产生的不同 id。
12 bit 可以代表的最大正整数是 2 ^ 12 – 1 = 4096，也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。也就是同一毫秒内同一台机器所生成的最大ID数量为4096
简单来说，你的某个服务假设要生成一个全局唯一 id，那么就可以发送一个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来生成唯一 id。这个 SnowFlake 算法系统首先肯定是知道自己所在的机器号，（这里姑且讲10bit全部作为工作机器ID）接着 SnowFlake 算法系统接收到这个请求之后，首先就会用二进制位运算的方式生成一个 64 bit 的 long 型 id，64 个 bit 中的第一个 bit 是无意义的。接着用当前时间戳（单位到毫秒）占用41 个 bit，然后接着 10 个 bit 设置机器 id。最后再判断一下，当前这台机房的这台机器上这一毫秒内，这是第几个请求，给这次生成 id 的请求累加一个序号，作为最后的 12 个 bit。
雪花算法源码demo：
package com.example.demo; import java.net.Inet4Address; import java.net.UnknownHostException; import java.util.Random; public class SnowflakeIdWorker { /** 时间部分所占长度 */ private static final int TIME_LEN = 41; /** 数据中心id所占长度 */ private static final int DATA_LEN = 5; /** 机器id所占长度 */ private static final int WORK_LEN = 5; /** 毫秒内存序列所占长度 */ private static final int SEQ_LEN = 12; /** 定义起始时间 2015-01-01 00:00:00 */ private static final long START_TIME = 14200041600000L; /** 上次生成ID的时间戳 */ private static long LAST_TIME_STAMP = -1L; /** 时间部分向左移动的位数 22 */ private static final int TIME_LEFT_BIT = 64 - 1 - TIME_LEN; /** 自动获取数据中心id（可以手动定义0-31之间的数） */ private static final long DATA_ID = getDataId(); /** 自动机器id（可以手动定义0-31之间的数） */ private static final long WORK_ID = getWorkId(); /** 数据中心id最大值 31 */ private static final int DATA_MAX_NUM = ~(-1 << DATA_LEN); /** 机器id最大值 31 */ private static final int WORK_MAX_NUM = ~(-1 << WORK_LEN); /** 随机获取数据中心id的参数 32 */ private static final int DATA_RANDOM = DATA_MAX_NUM + 1; /** 随机获取机器id的参数 32 */ private static final int WORK_RANDOM = WORK_MAX_NUM + 1; /** 数据中心id左移位数 17 */ private static final int DATA_LEFT_BIT = TIME_LEFT_BIT - DATA_LEN; /** 机器id左移位数 12 */ private static final int WORK_LEFT_BIT = DATA_LEFT_BIT - WORK_LEN; /** 上一次毫秒内存序列值 */ private static long LAST_SEQ = 0L; /** 毫秒内存列的最大值 4095 */ private static final long SEQ_MAX_NUM = ~(-1 << SEQ_LEN); /** * 获取字符串S的字节数组，然后将数组的元素相加，对（max+1）取余 * @param s 本地机器的hostName/hostAddress * @param max 机房/机器的id最大值 * @return */ private static int getHostId(String s, int max) { byte[] bytes = s.getBytes(); int sums = 0; for (int b : bytes) { sums += b; } return sums % (max + 1); } /** * 根据 host address 取余， 发送异常就返回 0-31 之间的随机数 * @return 机器ID */ private static int getWorkId() { try { return getHostId(Inet4Address.getLocalHost().getHostAddress(), WORK_MAX_NUM); } catch (UnknownHostException e) { return new Random().nextInt(WORK_RANDOM); } } /** * 根据 host name 取余， 发送异常就返回 0-31 之间的随机数 * @return 机房ID（数据中心ID） */ private static int getDataId() { try{ return getHostId(Inet4Address.getLocalHost().getHostName(), DATA_MAX_NUM); }catch(Exception e){ return new Random().nextInt(DATA_RANDOM); } } /** * 获取下一不同毫秒的时间戳 * @param lastMillis * @return 下一毫秒的时间戳 */ private static long nextMillis(long lastMillis) { long now = System.currentTimeMillis(); while (now <= lastMillis) { now = System.currentTimeMillis(); } return now; } /** * 核心算法，需要加锁保证并发安全 * @return 返回唯一ID */ public synchronized static long getUUID() { long now = System.currentTimeMillis(); // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过，此时因抛出异常 if (now < LAST_TIME_STAMP) { throw new RuntimeException(String.format("系统时间错误！ %d 毫秒内拒绝生成雪花ID", START_TIME)); } if (now == LAST_TIME_STAMP) { LAST_SEQ = (LAST_SEQ + 1) & SEQ_MAX_NUM; if (LAST_SEQ == 0) { now = nextMillis(LAST_TIME_STAMP); } } else { LAST_SEQ = 0; } // 上次生成ID的时间戳 LAST_TIME_STAMP = now; return ((now - START_TIME) << TIME_LEFT_BIT | (DATA_ID << DATA_LEFT_BIT) | (WORK_ID << WORK_LEFT_BIT) | LAST_SEQ); } /** * 主函数测试 * @param args */ public static void main(String[] args) { long start = System.currentTimeMillis(); int num = 300000; for (int i = 0; i < num; i++) { System.out.println(getUUID()); } long end = System.currentTimeMillis(); System.out.println("共生成 " + num + " 个ID，用时 " + (end - start) + " 毫秒"); } }
