实现全局唯一ID
一、采用主键自增
最常见的方式。利用数据库,全数据库唯一。
优点:
缺点:
二、UUID
常见的方式。可以利用数据库也可以利用程序生成,一般来说全球唯一。
优点:
缺点:
三、Redis生成ID
当使用数据库来生成ID性能不够要求的时候,我们可以尝试使用Redis来生成ID。这主要依赖于Redis是单线程的,所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY来实现。可以使用Redis集群来获取更高的吞吐量。假如一个集群中有5台Redis。可以初始化每台Redis的值分别是1,2,3,4,5,然后步长都是5。各个Redis生成的ID为:
A:1,6,11,16,21 B:2,7,12,17,22 C:3,8,13,18,23 D:4,9,14,19,24 E:5,10,15,20,25
这个,随便负载到哪个机确定好,未来很难做修改。但是3-5台服务器基本能够满足器上,都可以获得不同的ID。但是步长和初始值一定需要事先需要了。使用Redis集群也可以方式单点故障的问题。另外,比较适合使用Redis来生成每天从0开始的流水号。比如订单号=日期+当日自增长号。可以每天在Redis中生成一个Key,使用INCR进行累加。
优点:
缺点:
四、雪花算法 (snowflake,Java版)
SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图:
1位
,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是041位
,用来记录时间戳(毫秒)。- 41位可以表示$2^{41}-1$个数字,
- 如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至 $2^{41}-1$,减1是因为可表示的数值范围是从0开始算的,而不是1。
- 也就是说41位可以表示$2^{41}-1$个毫秒的值,转化成单位年则是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
10位
,用来记录工作机器id。- 可以部署在$2^{10} = 1024$个节点,包括
5位datacenterId
和5位workerId
5位(bit)
可以表示的最大正整数是$2^{5}-1 = 31$,即可以用0、1、2、3、....31这32个数字,来表示不同的datecenterId或workerId
- 可以部署在$2^{10} = 1024$个节点,包括
12位
,序列号,用来记录同毫秒内产生的不同id。12位(bit)
可以表示的最大正整数是$2^{12}-1 = 4095$,即可以用0、1、2、3、....4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号
由于在Java中64bit的整数是long类型,所以在Java中SnowFlake算法生成的id就是long(18位)来存储的。
优点:
缺点:
美团的Leaf和百度的UidGenerator有相应的解决方案
以下是Twitter官方原版的,用Scala写的:
/** Copyright 2010-2012 Twitter, Inc.*/ package com.twitter.service.snowflake import com.twitter.ostrich.stats.Stats import com.twitter.service.snowflake.gen._ import java.util.Random import com.twitter.logging.Logger /** * An object that generates IDs. * This is broken into a separate class in case * we ever want to support multiple worker threads * per process */ class IdWorker(val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L) extends Snowflake.Iface { private[this] def genCounter(agent: String) = { Stats.incr("ids_generated") Stats.incr("ids_generated_%s".format(agent)) } private[this] val exceptionCounter = Stats.getCounter("exceptions") private[this] val log = Logger.get private[this] val rand = new Random val twepoch = 1288834974657L private[this] val workerIdBits = 5L private[this] val datacenterIdBits = 5L private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits) private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) private[this] val sequenceBits = 12L private[this] val workerIdShift = sequenceBits private[this] val datacenterIdShift = sequenceBits + workerIdBits private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits private[this] val sequenceMask = -1L ^ (-1L << sequenceBits) private[this] var lastTimestamp = -1L // sanity check for workerId if (workerId > maxWorkerId || workerId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId)) } if (datacenterId > maxDatacenterId || datacenterId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId)) } log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId) def get_id(useragent: String): Long = { if (!validUseragent(useragent)) { exceptionCounter.incr(1) throw new InvalidUserAgentError } val id = nextId() genCounter(useragent) reporter.report(new AuditLogEntry(id, useragent, rand.nextLong)) id } def get_worker_id(): Long = workerId def get_datacenter_id(): Long = datacenterId def get_timestamp() = System.currentTimeMillis protected[snowflake] def nextId(): Long = synchronized { var timestamp = timeGen() if (timestamp < lastTimestamp) { exceptionCounter.incr(1) log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp); throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format( lastTimestamp - timestamp)) } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp) } } else { sequence = 0 } lastTimestamp = timestamp ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence } protected def tilNextMillis(lastTimestamp: Long): Long = { var timestamp = timeGen() while (timestamp <= lastTimestamp) { timestamp = timeGen() } timestamp } protected def timeGen(): Long = System.currentTimeMillis() val AgentParser = """([a-zA-Z][a-zA-Z\-0-9]*)""".r def validUseragent(useragent: String): Boolean = useragent match { case AgentParser(_) => true case _ => false } }
使用java:
public class SnowflakeIdWorker { /** * 开始时间截 (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 ^ (-1L << workerIdBits); /** * 支持的最大数据标识id,结果是31 */ private final long maxDatacenterId = -1L ^ (-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 ^ (-1L << sequenceBits); /** * 工作机器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 SnowflakeIdWorker(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; } /** * 获得下一个ID (该方法是线程安全的) * @return SnowflakeId */ public synchronized long nextId() { 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 当前时间戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * @return 当前时间(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } public static void main(String[] args) throws InterruptedException { SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); for (int i = 0; i < 10; i++) { long id = idWorker.nextId(); Thread.sleep(1); System.out.println(id); } } }