详解雪花算法原理
雪花算法
自增主键
一、简介
雪花算法是Twitter公司发明的一种算法，主要目的是解决在分布式环境下，ID怎样生成的问题
分布式ID生成要求：
1、分布式ID生成规则硬性要求：
1.1、全局唯一：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
1.2、趋势递增：MySQL中InnoDB引擎使用的是聚集索引。多数RDBMS使用Btree的数据结构来存储索引数据，在主键的选择上尽量选择有序的主键保证写入性能。
1.3、单调递增：保证下一个ID号一定大于上一个。
1.4、保证安全：ID号需要无规则性，不能让别人根据ID号猜出我们的信息和业务数据量，增加恶意用户扒取数据的难度。
1.5、含时间戳。
2、分布式ID生成可用性要求
高可用：发布一个获取分布式ID的请求，服务器就要保证99.999%的情况下给创建一个全局唯一的分布式ID
低延迟：发布一个获取分布式ID的请求，要快，急速。
高QPS：假如并发一口气10万个创建分布式ID请求同时杀过来，服务器要顶得住并且成功创建10万个分布式ID
3、特点
基于时间戳，所生成的ID按时间递增
能满足高并发分布式系统环境下ID不重复
不依赖第三方的库或者中间件
生成效率极高
二、雪花算法
主要是由64bit的long型生成的全局ID,引入了时间戳和ID保持自增的属性.
64bit分为四个部分:
第一个部分是1bit
首位无效符：不使用,没有意义，第一个 bit 作为符号位，因为我们生成的都是正数，所以第一个 bit 统一都是 0;
第二个部分是41bit
时间戳：占用 41 bit ，精确到毫秒。41位最好可以表示2^41-1毫秒，转化成单位年为 69 年;
第三个部分是10bit
机器编码：占用10bit，其中高位 5 bit 是数据中心 ID，低位 5 bit 是工作节点 ID，最多可以容纳 1024 个节点。
第四部分是12bit
序列号：代表是同一个毫秒类产生不同的ID,区分同一个毫秒内产生的ID，支持每个节点每毫秒产生4096个ID序号，所以最大可以支持单节点差不多四百万的并发量，这个妥妥的够用了。
三、优缺点
优点：
经测试雪花算法(SnowFlake)每秒能生成26万个自增可排序的ID
雪花算法(SnowFlake)生成的ID结果是一个64bit大小的整数，为一个Long型 （转换成字符串后长度最多19）
分布式系统内不会产生ID碰撞（datacenter和workerId作区分）并且效率高
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高，可以根据自身业务分配bit位，非常灵活。
缺点：
依赖机器时钟，如果机器时钟回拨，会导致id重复
四、其他生成主键方案
1、方案
1.1、UUID。
1.2、数据库自增主键。
1.3、基于Redis生成全局ID策略。
1.4、雪花算法，Twitter的分布式自增ID算法snowflake。
1.5、百度UidGenerator算法(基于雪花算法实现自定义时间戳)。
1.6、美团Leaf算法(依赖于数据库，ZK)。
2、详解
2.1、UUID的优缺点：
优点：性能非常高，JDK自带本地生成，无网络消耗。
缺点：（1）只保证了唯一性，趋势递增。（2）无序，无法预测他的生成规则，不能生成递增有序的数字。（3）mysql官方推荐主键越短越好，UUID包含32个16位进制的字母数字，每一个都很长。（4）B+树索引的分裂。主键是包含索引的，mysql的索引是通过B+树来实现的，每一次新的UUID数据插入，为了查询优化，因为UUID是无序的，都会对索引底层的B+树进行修改。插入无序，不但会导致一些中间节点产生分裂，也会白白创造很多不饱和的节点，大大降低了数据库插入的性能。
2.2、数据库自增主键的优缺点：
优点：简单方便易用。
缺点：（1）要设置增长步长，系统水平扩展比较困难。（2）每次获取ID都得读写一次数据库，数据库压力大，非常影响性能，不符合分布式ID里低延迟和高QPS的规则。
2.3、基于Redis生成全局ID策略优缺点：
优点：满足分布式ID生成要求，并且已有成功落地案例。
缺点：（1）要设置增长步长，同时key一定要设置有效期。（2）为了一个分布式ID，要搞一个Redis集群，维护成本大。
2.4、雪花算法，Twitter的分布式自增ID算snowflake优缺点：
优点：（1）经测试snowflake每秒能生成26万个自增可排序的ID。（2）snowflake生成的ID结果是一个64bit大小的整数，为一个Long型 （转换成字符串后长度最多19）。（3）分布式系统内不会产生ID碰撞（datacenter和workerId作区分）并且效率高。（4）不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高，可以根据自身业务分配bit位，非常灵活。
缺点：依赖机器时钟，如果机器时钟回拨，会导致id重复。由于是部署到分布式环境，每台机器上的时钟不可能完全同步，有时候出现不是全局递增的情况。（一般分布式ID只要求趋势递增，并不会严格要求递增，90%的需求只要求趋势递增，可以忽略这个缺点，或者按实际情况进行改进）
推荐：https://www.cnblogs.com/hld123/p/14976414.html
雪花算法是Twitter公司发明的一种算法，主要目的是解决在分布式环境下，ID怎样生成的问题
分布式ID生成要求：
1、分布式ID生成规则硬性要求：
1.1、全局唯一：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
1.2、趋势递增：MySQL中InnoDB引擎使用的是聚集索引。多数RDBMS使用Btree的数据结构来存储索引数据，在主键的选择上尽量选择有序的主键保证写入性能。
1.3、单调递增：保证下一个ID号一定大于上一个。
1.4、保证安全：ID号需要无规则性，不能让别人根据ID号猜出我们的信息和业务数据量，增加恶意用户扒取数据的难度。
1.5、含时间戳。
2、分布式ID生成可用性要求
高可用：发布一个获取分布式ID的请求，服务器就要保证99.999%的情况下给创建一个全局唯一的分布式ID
低延迟：发布一个获取分布式ID的请求，要快，急速。
高QPS：假如并发一口气10万个创建分布式ID请求同时杀过来，服务器要顶得住并且成功创建10万个分布式ID
3、特点
基于时间戳，所生成的ID按时间递增
能满足高并发分布式系统环境下ID不重复
不依赖第三方的库或者中间件
生成效率极高
二、雪花算法
主要是由64bit的long型生成的全局ID,引入了时间戳和ID保持自增的属性.
64bit分为四个部分:
第一个部分是1bit
首位无效符：不使用,没有意义，第一个 bit 作为符号位，因为我们生成的都是正数，所以第一个 bit 统一都是 0;
第二个部分是41bit
时间戳：占用 41 bit ，精确到毫秒。41位最好可以表示2^41-1毫秒，转化成单位年为 69 年;
第三个部分是10bit
机器编码：占用10bit，其中高位 5 bit 是数据中心 ID，低位 5 bit 是工作节点 ID，最多可以容纳 1024 个节点。
第四部分是12bit
序列号：代表是同一个毫秒类产生不同的ID,区分同一个毫秒内产生的ID，支持每个节点每毫秒产生4096个ID序号，所以最大可以支持单节点差不多四百万的并发量，这个妥妥的够用了。
三、优缺点
优点：
经测试雪花算法(SnowFlake)每秒能生成26万个自增可排序的ID
雪花算法(SnowFlake)生成的ID结果是一个64bit大小的整数，为一个Long型 （转换成字符串后长度最多19）
分布式系统内不会产生ID碰撞（datacenter和workerId作区分）并且效率高
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高，可以根据自身业务分配bit位，非常灵活。
缺点：
依赖机器时钟，如果机器时钟回拨，会导致id重复
四、其他生成主键方案
1、方案
1.1、UUID。
1.2、数据库自增主键。
1.3、基于Redis生成全局ID策略。
1.4、雪花算法，Twitter的分布式自增ID算法snowflake。
1.5、百度UidGenerator算法(基于雪花算法实现自定义时间戳)。
1.6、美团Leaf算法(依赖于数据库，ZK)。
2、详解
2.1、UUID的优缺点：
优点：性能非常高，JDK自带本地生成，无网络消耗。
缺点：（1）只保证了唯一性，趋势递增。（2）无序，无法预测他的生成规则，不能生成递增有序的数字。（3）mysql官方推荐主键越短越好，UUID包含32个16位进制的字母数字，每一个都很长。（4）B+树索引的分裂。主键是包含索引的，mysql的索引是通过B+树来实现的，每一次新的UUID数据插入，为了查询优化，因为UUID是无序的，都会对索引底层的B+树进行修改。插入无序，不但会导致一些中间节点产生分裂，也会白白创造很多不饱和的节点，大大降低了数据库插入的性能。
2.2、数据库自增主键的优缺点：
优点：简单方便易用。
缺点：（1）要设置增长步长，系统水平扩展比较困难。（2）每次获取ID都得读写一次数据库，数据库压力大，非常影响性能，不符合分布式ID里低延迟和高QPS的规则。
2.3、基于Redis生成全局ID策略优缺点：
优点：满足分布式ID生成要求，并且已有成功落地案例。
缺点：（1）要设置增长步长，同时key一定要设置有效期。（2）为了一个分布式ID，要搞一个Redis集群，维护成本大。
2.4、雪花算法，Twitter的分布式自增ID算snowflake优缺点：
优点：（1）经测试snowflake每秒能生成26万个自增可排序的ID。（2）snowflake生成的ID结果是一个64bit大小的整数，为一个Long型 （转换成字符串后长度最多19）。（3）分布式系统内不会产生ID碰撞（datacenter和workerId作区分）并且效率高。（4）不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高，可以根据自身业务分配bit位，非常灵活。
缺点：依赖机器时钟，如果机器时钟回拨，会导致id重复。由于是部署到分布式环境，每台机器上的时钟不可能完全同步，有时候出现不是全局递增的情况。（一般分布式ID只要求趋势递增，并不会严格要求递增，90%的需求只要求趋势递增，可以忽略这个缺点，或者按实际情况进行改进）
推荐：https://www.cnblogs.com/hld123/p/14976414.html