漫画:什么是SnowFlake算法?



漫画1 漫画2

————— 第二天 —————HCF思考者日记网-束洋洋个人博客

漫画3 漫画4 漫画5 漫画6 漫画7

方法一:UUID

UUID是通用唯一识别码 (Universally Unique Identifier),在其他语言中也叫GUID,可以生成一个长度32位的全局唯一识别码。HCF思考者日记网-束洋洋个人博客

String uuid = UUID.randomUUID().toString()HCF思考者日记网-束洋洋个人博客

结果示例:HCF思考者日记网-束洋洋个人博客

046b6c7f-0b8a-43b9-b35d-6489e6daee91HCF思考者日记网-束洋洋个人博客

漫画8

为什么无序的UUID会导致入库性能变差呢?HCF思考者日记网-束洋洋个人博客

这就涉及到B+树索引的分裂HCF思考者日记网-束洋洋个人博客

B+树索引的分裂

众所周知,关系型数据库的索引大都是B+树的结构,拿ID字段来举例,索引树的每一个节点都存储着若干个ID。HCF思考者日记网-束洋洋个人博客

如果我们的ID按递增的顺序来插入,比如陆续插入8,9,10,新的ID都只会插入到最后一个节点当中。当最后一个节点满了,会裂变出新的节点。这样的插入是性能比较高的插入,因为这样节点的分裂次数最少,而且充分利用了每一个节点的空间。HCF思考者日记网-束洋洋个人博客

B+树索引的分裂2

但是,如果我们的插入完全无序,不但会导致一些中间节点产生分裂,也会白白创造出很多不饱和的节点,这样大大降低了数据库插入的性能。HCF思考者日记网-束洋洋个人博客

漫画9 漫画10

方法二:数据库自增主键

假设名为table的表有如下结构:HCF思考者日记网-束洋洋个人博客

id feild
35 a
36 b

每一次生成ID的时候,访问数据库,执行下面的语句:HCF思考者日记网-束洋洋个人博客

begin;

REPLACE INTO table ( feild )  VALUES ( 'a' );

SELECT LAST_INSERT_ID();

commit;

REPLACE INTO 的含义是插入一条记录,如果表中唯一索引的值遇到冲突,则替换老数据。HCF思考者日记网-束洋洋个人博客

这样一来,每次都可以得到一个递增的ID。HCF思考者日记网-束洋洋个人博客

为了提高性能,在分布式系统中可以用DB proxy请求不同的分库,每个分库设置不同的初始值,步长和分库数量相等:HCF思考者日记网-束洋洋个人博客

DB proxy请求不同的分库

这样一来,DB1生成的ID是1,4,7,10,13....,DB2生成的ID是2,5,8,11,14.....HCF思考者日记网-束洋洋个人博客

漫画11 漫画12 漫画13

————————————HCF思考者日记网-束洋洋个人博客

漫画14 漫画15 漫画16 漫画17 漫画18 漫画19

初识SnowFlake

snowflake算法所生成的ID结构是什么样子呢?我们来看看下图:HCF思考者日记网-束洋洋个人博客

snowflake算法生成的ID结构

SnowFlake所生成的ID一共分成四部分:HCF思考者日记网-束洋洋个人博客

1.第一位

占用1bit,其值始终是0,没有实际作用。HCF思考者日记网-束洋洋个人博客

2.时间戳

占用41bit,精确到毫秒,总共可以容纳约140年的时间。HCF思考者日记网-束洋洋个人博客

3.工作机器id

占用10bit,其中高位5bit是数据中心ID(datacenterId),低位5bit是工作节点ID(workerId),做多可以容纳1024个节点。HCF思考者日记网-束洋洋个人博客

4.序列号

占用12bit,这个值在同一毫秒同一节点上从0开始不断累加,最多可以累加到4095。HCF思考者日记网-束洋洋个人博客

SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢?只需要做一个简单的乘法:HCF思考者日记网-束洋洋个人博客

同一毫秒的ID数量 = 1024 X 4096 = 4194304HCF思考者日记网-束洋洋个人博客

这个数字在绝大多数并发场景下都是够用的。HCF思考者日记网-束洋洋个人博客

SnowFlake的代码实现

漫画20 漫画21

 HCF思考者日记网-束洋洋个人博客

//初始时间截 (2017-01-01)
private static final long INITIAL_TIME_STAMP = 1483200000000L;
//机器id所占的位数
private static final long WORKER_ID_BITS = 5L;
//数据标识id所占的位数
private static final long DATACENTER_ID_BITS = 5L;
//支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);
//支持的最大数据标识id,结果是31
private static final long MAX_DATACENTER_ID = ~(-1L << DATACENTER_ID_BITS);
//序列在id中占的位数
private final long SEQUENCE_BITS = 12L;
//机器ID的偏移量(12)
private final long WORKERID_OFFSET = SEQUENCE_BITS;
//数据中心ID的偏移量(12+5)
private final long DATACENTERID_OFFSET = SEQUENCE_BITS + SEQUENCE_BITS;
//时间截的偏移量(5+5+12)
private final long TIMESTAMP_OFFSET = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS;
//生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)
private final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);
//工作节点ID(0~31)
private long workerId;
//数据中心ID(0~31)
private long datacenterId;
//毫秒内序列(0~4095)
private long sequence = 0L;
//上次生成ID的时间截
private long lastTimestamp = -1L;
/**

 * 构造函数

 *

 * @param workerId     工作ID (0~31)

 * @param datacenterId 数据中心ID (0~31)

 */
public SnowFlakeIdGenerator(long workerId, long datacenterId) {
	if(workerId > MAX_WORKER_ID || workerId < 0){
		throw new IllegalArgumentException(String.format("WorkerID 不能大于 %d 或小于 0", MAX_WORKER_ID));
	}
	if(datacenterId > MAX_DATACENTER_ID || datacenterId < 0){
		throw new IllegalArgumentException(String.format("DataCenterID 不能大于 %d 或小于 0", MAX_DATACENTER_ID));
	}
	this.workerId = workerId;
	this.datacenterId = datacenterId;
}

/**

 * 获得下一个ID (用同步锁保证线程安全)

 *

 * @return SnowflakeId

 */
 public synchronized long nextId(){
	 long timestamp = System.currentTimeMillis();
	 //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
	 if (timestamp < lastTimestamp){
		 throw new RuntimeException("当前时间小于上一次记录的时间戳!");
	 }
	 //如果是同一时间生成的,则进行毫秒内序列
	 if (lastTimestamp == timestamp){
		 sequence = (sequence + 1) & SEQUENCE_MASK;
		 //sequence等于0说明毫秒内序列已经增长到最大值
		 if(sequence == 0){
			 //阻塞到下一个毫秒,获得新的时间戳
			 timestamp = tilNextMillis(lastTimestamp);
		 }
	 }
	 //时间戳改变,毫秒内序列重置
	 else {
		 sequence = 0L;
	 }
	 //上次生成ID的时间截
	 lastTimestamp = timestamp;
	 //移位并通过或运算拼到一起组成64位的ID
	 return (timestamp - INITIAL_TIME_STAMP) << TIMESTAMP_OFFSET)
	 | (datacenterId << DATACENTERID_OFFSET)
	 | (workerId << WORKERID_OFFSET)
	 | sequence;
 }
 
 /**

 * 阻塞到下一个毫秒,直到获得新的时间戳

 *

 * @param lastTimestamp 上次生成ID的时间截

 * @return 当前时间戳

 */
 protected long tilNextMillis(long lastTimestamp){
	 long timestamp = System.currentTimeMillis();
	 while (timestamp <= lastTimestamp){
		 timestamp = System.currentTimeMillis();
	 }
	 return timestamp;
 }
 
 public static void main(String[] args)	{
	 final SnowFlakeIdGenerator idGenerator = new SnowFlakeIdGenerator(1, 1);
	 //线程池并行执行10000次ID生成
	 ExecutorService executorService = Executors.newCachedThreadPool();
	 for(int i = 0;i <10000;i++ ){
		 executorService.execute(new Runnable(){
			 @Override
			 public void run(){
				 long id = idGenerator.nextId();
				 System.out.println(id);
			 }
		 });
	 }
	 executorService.shutdown();
 }

这段代码改写自网上的SnowFlake算法实现,有几点需要解释一下:HCF思考者日记网-束洋洋个人博客

1.获得单一机器的下一个序列号,使用Synchronized控制并发,而非CAS的方式,是因为CAS不适合并发量非常高的场景。HCF思考者日记网-束洋洋个人博客

2.如果当前毫秒在一台机器的序列号已经增长到最大值4095,则使用while循环等待直到下一毫秒。HCF思考者日记网-束洋洋个人博客

3.如果当前时间小于记录的上一个毫秒值,则说明这台机器的时间回拨了,抛出异常。但如果这台机器的系统时间在启动之前回拨过,那么有可能出现ID重复的危险。HCF思考者日记网-束洋洋个人博客

SnowFlake的优势和劣势

漫画22 漫画23

SnowFlake算法的优点:

1.生成ID时不依赖于DB,完全在内存生成,高性能高可用。HCF思考者日记网-束洋洋个人博客

2.ID呈趋势递增,后续插入索引树的时候性能较好。HCF思考者日记网-束洋洋个人博客

SnowFlake算法的缺点:

依赖于系统时钟的一致性。如果某台机器的系统时钟回拨,有可能造成ID冲突,或者ID乱序。HCF思考者日记网-束洋洋个人博客

漫画24

—————END—————HCF思考者日记网-束洋洋个人博客

之前本站也有一篇讲解分布式ID生成方法,和此章互补,可以看下:细聊分布式ID生成方法HCF思考者日记网-束洋洋个人博客

转自:程序员小灰(微信号:chengxuyuanxiaohui)

 

(转载本站文章请注明作者和出处 思考者日记网|束洋洋个人博客 ,请勿用于任何商业用途)

『访问 思考者日记网404页面 寻找遗失儿童』

告知
  •     本站90%以上文章均属原创,部分转载已加上原作者出处。 如需转载本站文章请您务必保留本站出处!
  •     打广告评论者请自重,请为广大网友提供一个健康干净的网络空间。
  •  感谢主机屋提供网站空间;
  •  感谢万网阿里云提供域名解析;
  •  感谢EmpireCMS提供CMS系统;
  •  感谢bootstrap展示本站前端页面;
  •  感谢Glyphicons Halflings提供字体;
  •  感谢大家一直以来对本站的喜爱,感谢大家!
近期文章 建议与反馈

 

网友评论
我也来说两句
点击显示

 

点击显示弹幕