SnowFlake 分布式ID生成算法Java实现

标签: snowflake 分布 id | 发表时间:2016-12-27 11:45 | 作者:
出处:http://www.iteye.com

SnowFlake 分布式ID生成Java实现

SnowFlake不依赖第三方介质,不像基于ZK,Redis等,每次用完一个区间还得通过网络去获取下一个区间,效率较低,基于SnowFlake的分布式ID生成是目前我见过的最快的

 

SnowFlake生成的是一个64位的数字,其中42位时间戳,接下来10位是自定义的数,其作用就是区分集群中的所有机器,最后12位是毫秒内序列,集群内每个机器能够在1毫秒内生成2^12 - 1个ID

 

 

/**
* 基于SnowFlake的序列号生成实现, 64位ID (42(毫秒)+5(机器ID)+5(业务编码)+12(重复累加))
*/
static class Generator {

		private final static long TWEPOCH = 1288834974657L;

		// 机器标识位数
		private final static long WORKER_ID_BITS = 5L;

		// 数据中心标识位数
		private final static long DATA_CENTER_ID_BITS = 5L;

		// 机器ID最大值 31
		private final static long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);

		// 数据中心ID最大值 31
		private final static long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);

		// 毫秒内自增位
		private final static long SEQUENCE_BITS = 12L;

		// 机器ID偏左移12位
		private final static long WORKER_ID_SHIFT = SEQUENCE_BITS;

		private final static long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;

		// 时间毫秒左移22位
		private final static long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;

		private final static long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS);

		private long lastTimestamp = -1L;

		private long sequence = 0L;
		private final long workerId;
		private final long dataCenterId;
		
		//private final AtomicBoolean lock = new AtomicBoolean(false);
		
		Generator(long workerId, long dataCenterId) {
			if (workerId > MAX_WORKER_ID || workerId < 0) {
				throw new IllegalArgumentException(String.format("%s must range from %d to %d", K_WORK_ID, 0,
						MAX_WORKER_ID));
			}

			if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
				throw new IllegalArgumentException(String.format("%s must range from %d to %d", K_DC_ID, 0,
						MAX_DATA_CENTER_ID));
			}

			this.workerId = workerId;
			this.dataCenterId = dataCenterId;
		}

		synchronized long nextValue() throws SequenceException {
			long timestamp = time();
			if (timestamp < lastTimestamp) {
				throw new SequenceException("Clock moved backwards, refuse to generate id for "
						+ (lastTimestamp - timestamp) + " milliseconds");
			}

			if (lastTimestamp == timestamp) {
				// 当前毫秒内,则+1
				sequence = (sequence + 1) & SEQUENCE_MASK;
				if (sequence == 0) {
					// 当前毫秒内计数满了,则等待下一秒
					timestamp = tilNextMillis(lastTimestamp);
				}
			} else {
				sequence = 0;
			}
			lastTimestamp = timestamp;
			
			// ID偏移组合生成最终的ID,并返回ID
			long nextId = ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT)
					| (dataCenterId << DATA_CENTER_ID_SHIFT) | (workerId << WORKER_ID_SHIFT) | sequence;

			return nextId;
		}

		private long tilNextMillis(final long lastTimestamp) {
			long timestamp = this.time();
			while (timestamp <= lastTimestamp) {
				timestamp = this.time();
			}
			return timestamp;
		}

		private long time() {
			return System.currentTimeMillis();
		}

	}

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [snowflake 分布 id] 推荐:

Twitter的分布式自增ID算法Snowflake

- - 企业架构 - ITeye博客
Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同. Snowflake算法核心. 把 时间戳, 工作机器id, 序列号组合在一起.

SnowFlake 分布式ID生成算法Java实现

- - ITeye博客
SnowFlake 分布式ID生成Java实现. SnowFlake不依赖第三方介质,不像基于ZK,Redis等,每次用完一个区间还得通过网络去获取下一个区间,效率较低,基于SnowFlake的分布式ID生成是目前我见过的最快的. SnowFlake生成的是一个64位的数字,其中42位时间戳,接下来10位是自定义的数,其作用就是区分集群中的所有机器,最后12位是毫秒内序列,集群内每个机器能够在1毫秒内生成2^12 - 1个ID.

忘掉 Snowflake,感受一下性能高出 587 倍的全局唯一 ID 生成算法

- - SegmentFault 最新的文章
今天我们来拆解 Snowflake 算法,同时领略百度、美团、腾讯等大厂在全局唯一 ID 服务方面做的设计,接着根据具体需求设计一款全新的全局唯一 ID 生成算法. 这还不够,我们会讨论到全局唯一 ID 服务的分布式 CAP 选择与性能瓶颈. 已经熟悉 Snowflake 的朋友可以先去看大厂的设计和权衡.

分布式高可用id服务器设计实现

- - C++博客-首页原创精华区
服务端/后台开发中如何生成id是每个开发者都会遇到的问题,在电商、游戏领域尤其突出. 如何保证生成id的唯一性、可靠性、高可用性,如何组织id的格式,在不同的应用场景和限制下实现方式也不尽相同. 我们的应用场景类似电商,在一个订单的生命周期内,有多个逻辑需要生成各自的id,还要考虑到可读性和灵活性,我们决定实现一个独立的id服务.

Leaf——美团点评分布式ID生成系统

- - 美团点评技术团队
在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识. 如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一个唯一ID来标识一条数据或消息,数据库的自增ID显然不能满足需求;特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识. 此时一个能够生成全局唯一ID的系统是非常必要的.

分布式系统中唯一 ID 的生成方法

- - 文章 – 伯乐在线
本文主要介绍在一个分布式系统中, 怎么样生成全局唯一的 ID. 在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现..

雪花算法 Snowflake & Sonyflake

- - 掘金后端
唯一ID算法 Snowflake相信大家都不墨生,他是Twitter公司提出来的算法. 非常广泛的应用在各种业务系统里. 也因为 Snowflake的灵活性和缺点,对他的改造层出不穷,比百度的 UidGenerator、美团的 Leaf、索尼的 Sonyflake等等. 这篇帖子主要是讲一下原生的 Snowflake算法、缺点及改造方案,并分析索尼的 Sonyflake源码对原生 Snowflake的改造,.

分布式系统中, 怎么样生成全局唯一的 ID

- - zzm
在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.. 但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:.

产生Id

- - 研发管理 - ITeye博客
// worker编号最大值,决定支持的部署节点数量. // 毫秒内自增位数,每毫秒最大序号支持65535. // worker编号偏移量. // 毫秒基线:2015-01-01 00:00:00. * 从环境变量中获取worker编号,每个部署环境编号不能重复. * 每个部署环境编号不能重复. * @param workerId Worker编号.