每秒生成一千万个,常见布满式主键ID生成战术

二零一八年做了二个出品,会时常导入导出大量的外部数据,那几个数据的ID有的是GUID类型,有的是字符串,也诸多自增。GUID类型未有各种,结果要排序得仰仗其他业务字段,全体查询成效比极低;字符串ID本来是用来改动GUID的或许数字ID的,结果有个别字符串ID不符合标准,平常有特出数据供给管理;自增主键ID的数目导入合并常常有冲突。

主键生成战略

系统唯壹ID是大家在设计三个系统的时候时不时会境遇的难题,下边介绍部分常见的ID生成计策。

  • Sequence ID
  • UUID
  • GUID
  • COMB
  • Snowflake

最开端的自增ID为了兑现分库分别的须要,会在自增的前提下,使用区别幅度(举例DB①生成1,4,7,10,DB2生成二,五,捌,1一,DB三生成3,陆,九,1二),但须求做数据库举办时,极其麻烦。
  比较自增ID,UUID生成唯一主键特别有益(数据量不小的状态下,存在重复的只怕),但出于UUID的严节性,品质不及自增ID,字符串积累,积累空间大,查询成效低。
  COMB相对于UUID,扩充了生成ID的有序性,插入与查询功用都有所升高。见Integer
GUID和Comb做主键的频率测试(Delphi+access)(三)
  Sonwflake是Facebook主键生成计谋,能够用作是COMB的壹种创新,用614位的长整型代替1二十10个人的字符串。ID构成:第四人0

  • 4壹人的小时前缀 + 1三位的节点标记 +
    10个人的sequence幸免并发的数字。见Instagram-Snowflake(陆拾壹人遍及式ID算法)分析与JAVA达成

缘何布满式系统须求用到ID生成系统

在千头万绪遍布式系统中,往往必要对多量的数额和新闻实行唯壹标记。如在美团点评的财经、支付、餐饮、商旅、猫眼电影等制品的类别中,数据日渐加强,对数据库的分库分表后需求有三个唯1ID来标志一条数据或音信,数据库的自增ID鲜明不能够满足急需;尤其一点的如订单、骑手、减价券也都亟待有唯壹ID做标志。此时2个能力所能达到生成全局唯1ID的系统是尤其要求的。

包含下来,业务系统对ID号的渴求有啥呢?

 

为了防止GUID主键的“索引页分化”难点,进步查询功用,同时为了减轻分布式情状下的数额导入合并难题,强烈必要壹种遍及式的,有序的ID生成方案。笔者参考了鹅毛大雪ID(Twitter-Snowflake,陆拾三人自增ID算法)达成方案,设计二个更易于肉眼观望数值再而三有序的分布式ID方案。

1. Sequence ID

数据库自拉长连串或字段,最普及的不2秘诀。由数据库维护,数据库唯1。

ID生成系统的急需

一.全局唯壹性:无法出现重复的ID,最主题的渴求。
二.势头递增:MySQL
InnoDB引擎使用的是集中索引,由于大部分OdysseyDBMS使用B-tree的数据结构来存款和储蓄索引数据,在主键的取舍方面大家应尽量利用有序的主键保险写入质量。
三.枯燥递增:保障下二个ID一定大于上一个ID。
四.音信安全:若是ID是一连递增的,恶意用户就足以很轻松的发掘订单号的条条框框,从而猜出下一个订单号,假设是竞争对手,就足以平素了然大家1天的订单量。所以在好几场景下,供给ID无规则。

第二、4两个需假设排斥的,不可能同时满意。

同时,在大型布满式网址架构中,除了须要满意ID生成自个儿的须求外,还亟需ID生成系统可用性相当高。想象以下,假诺ID生成系统瘫痪,那么任何业务不能开始展览下去,那将是二次不幸。
为此,计算ID生成系统还亟需满足如下的急需:
壹.高可用,可用性到达多少个玖或四个⑨。
二.高QPS,品质还是不可能太差,不然轻巧形成线程堵塞。
3.平分延迟和TP99九(保证9九.玖%的呼吁都能学有所成的最低延迟)延迟都要尽只怕低。

转自 布满式系统唯壹ID生成方案汇总

 

系统唯壹ID是大家在规划一个连串的时候平时会遇见的主题素材,也时不时为这几个标题而纠结。生成ID的艺术有过多,适应分化的气象、须求以及品质要求。所以有个别比较复杂的体系会有八个ID生成的计谋。下边就介绍部分宽广的ID生成计谋。

一. 数据库自增进种类或字段

最普遍的章程。利用数据库,全体据库唯一。

优点:

壹)轻松,代码方便,品质能够承受。

二)数字ID天然排序,对分页也许必要排序的结果很有支持。

 

缺点:

一)分化数据库语法和得以落成差别,数据库迁移的时候或半数以上据库版本援救的时候需求管理。

贰)在单个数据库或读写分离或1主多从的情事下,唯有叁个主库能够调换。有单点故障的风险。

3)在质量达不到须求的情景下,相比难于扩展。

4)假如遇见两个种类须要联合大概关联到多少迁移会一定优伤。

伍)分表分库的时候会有麻烦。

优化方案:

壹)针对主库单点,若是有多少个Master库,则种种Master库设置的原初数字不一致,步长同样,能够是Master的个数。比方:Master壹生成的是 一,四,柒,拾,Master二生成的是二,五,八,11 Master3生成的是
3,6,玖,1贰。那样就能够有效生成集群中的唯壹ID,也足以大大降低ID生成数据库操作的负荷。

 

2. UUID

广阔的措施。能够行使数据库也足以行使程序生成,一般的话全世界唯1。

优点:

一)简单,代码方便。

二)生成ID性能格外好,基本不会有总体性难题。

3)满世界唯1,在境遇数据迁移,系统数据统一,也许数据库退换等情状下,能够从容应对。

 

缺点:

壹)未有排序,无法担保趋势递增。

二)UUID往往是利用字符串存储,查询的频率非常的低。

三)存款和储蓄空间比十分的大,假若是海量数据库,就需求思量存款和储蓄量的标题。

4)传输数据量大

5)不可读。

 

3. UUID的变种

一)为了消除UUID不可读,能够应用UUID to Int64的办法。及

亚洲必赢官网 1

/// <summary>
/// 根据GUID获取唯一数字序列
/// </summary>
public static long GuidToInt64()
{
    byte[] bytes = Guid.NewGuid().ToByteArray();
    return BitConverter.ToInt64(bytes, 0);
}

亚洲必赢官网 2

1
  

二)为了消除UUID冬天的标题,NHibernate在其主键生成方式中提供了Comb算法(combined
guid/timestamp)。保留GUID的十三个字节,用另伍个字节表示GUID生成的岁月(DateTime)。

亚洲必赢官网 3

/// <summary> 
/// Generate a new <see cref="Guid"/> using the comb algorithm. 
/// </summary> 
private Guid GenerateComb()
{
    byte[] guidArray = Guid.NewGuid().ToByteArray();

    DateTime baseDate = new DateTime(1900, 1, 1);
    DateTime now = DateTime.Now;

    // Get the days and milliseconds which will be used to build    
    //the byte string    
    TimeSpan days = new TimeSpan(now.Ticks - baseDate.Ticks);
    TimeSpan msecs = now.TimeOfDay;

    // Convert to a byte array        
    // Note that SQL Server is accurate to 1/300th of a    
    // millisecond so we divide by 3.333333    
    byte[] daysArray = BitConverter.GetBytes(days.Days);
    byte[] msecsArray = BitConverter.GetBytes((long)
      (msecs.TotalMilliseconds / 3.333333));

    // Reverse the bytes to match SQL Servers ordering    
    Array.Reverse(daysArray);
    Array.Reverse(msecsArray);

    // Copy the bytes into the guid    
    Array.Copy(daysArray, daysArray.Length - 2, guidArray,
      guidArray.Length - 6, 2);
    Array.Copy(msecsArray, msecsArray.Length - 4, guidArray,
      guidArray.Length - 4, 4);

    return new Guid(guidArray);
}

亚洲必赢官网 4

 

用地点的算法测试一下,获得如下的结果:作为相比较,前边1个是行使COMB算法得出的结果,最后11个字符串是时间序(统一皮秒生成的二个UUID),过段时间假如重新转移,则10个字符串会比图示的要大。前面三个是一贯生成的GUID。

亚洲必赢官网 5

1旦想把日子序放在目前,能够改变后更换1二个字符串的地点,也能够修改算法类的结尾七个Array.Copy。

 

 

 

 

4. Redis生成ID

当使用数据库来生成ID质量不够需要的时候,大家得以尝尝利用Redis来生成ID。那首要注重于Redis是单线程的,所以也足以用生成全局唯一的ID。能够用Redis的原子操作
INC卡宴和INCRBY来促成。

能够采取Redis集群来获得更加高的吞吐量。假若一个集群中有五台Redis。能够伊始化每台Redis的值分别是一,二,三,四,5,然后步长都以5。各个Redis生成的ID为:

A:1,6,11,16,21

每秒生成一千万个,常见布满式主键ID生成战术。B:2,7,12,17,22

C:3,8,13,18,23

D:4,9,14,19,24

E:5,10,15,20,25

本条,随便负载到哪些机分明好,以往很难做修改。可是三-5台服务器基本能够满意器上,都能够获得不一致的ID。然则增长幅度和早先值一定需求事先须要了。使用Redis集群也足以格局单点故障的主题素材。

其它,相比较符合利用Redis来变化每一日从0起首的流水号。比方订单号=日期+当日自拉长号。能够每日在Redis中生成一个Key,使用INC纳瓦拉实行增添。

 

优点:

一)不借助于数据库,灵活方便,且质量优于数据库。

2)数字ID天然排序,对分页或然须要排序的结果很有援助。

缺点:

一)要是系统中并未有Redis,还须求引进新的组件,增添系统复杂度。

二)供给编码和配置的职业量一点都不小。

 

5. Twitter的snowflake算法

snowflake是Facebook开源的遍及式ID生成算法,结果是二个long型的ID。其宗旨境想是:使用四一bit看作皮秒数,10bit看成机器的ID(八个bit是数码基本,4个bit的机器ID),1贰bit当做阿秒内的流水号(意味着各个节点在每阿秒能够产生40九陆 个
ID),最终还有1个符号位,永久是0。具体达成的代码能够参照。

C#代码如下:

亚洲必赢官网 6

/// <summary>
    /// From: https://github.com/twitter/snowflake
    /// An object that generates IDs.
    /// This is broken into a separate class in case
    /// we ever want to support multiple worker threads
    /// per process
    /// </summary>
    public class IdWorker
    {
        private long workerId;
        private long datacenterId;
        private long sequence = 0L;

        private static long twepoch = 1288834974657L;

        private static long workerIdBits = 5L;
        private static long datacenterIdBits = 5L;
        private static long maxWorkerId = -1L ^ (-1L << (int)workerIdBits);
        private static long maxDatacenterId = -1L ^ (-1L << (int)datacenterIdBits);
        private static long sequenceBits = 12L;

        private long workerIdShift = sequenceBits;
        private long datacenterIdShift = sequenceBits + workerIdBits;
        private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
        private long sequenceMask = -1L ^ (-1L << (int)sequenceBits);

        private long lastTimestamp = -1L;
        private static object syncRoot = new object();

        public IdWorker(long workerId, long datacenterId)
        {

            // sanity check for workerId
            if (workerId > maxWorkerId || workerId < 0)
            {
                throw new ArgumentException(string.Format("worker Id can't be greater than %d or less than 0", maxWorkerId));
            }
            if (datacenterId > maxDatacenterId || datacenterId < 0)
            {
                throw new ArgumentException(string.Format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
            }
            this.workerId = workerId;
            this.datacenterId = datacenterId;
        }

        public long nextId()
        {
            lock (syncRoot)
            {
                long timestamp = timeGen();

                if (timestamp < lastTimestamp)
                {
                    throw new ApplicationException(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;
                }

                lastTimestamp = timestamp;

                return ((timestamp - twepoch) << (int)timestampLeftShift) | (datacenterId << (int)datacenterIdShift) | (workerId << (int)workerIdShift) | sequence;
            }
        }

        protected long tilNextMillis(long lastTimestamp)
        {
            long timestamp = timeGen();
            while (timestamp <= lastTimestamp)
            {
                timestamp = timeGen();
            }
            return timestamp;
        }

        protected long timeGen()
        {
            return (long)(DateTime.UtcNow - new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc)).TotalMilliseconds;
        }
    }

亚洲必赢官网 7

 

测试代码如下:

亚洲必赢官网 8

private static void TestIdWorker()
        {
            HashSet<long> set = new HashSet<long>();
            IdWorker idWorker1 = new IdWorker(0, 0);
            IdWorker idWorker2 = new IdWorker(1, 0);
            Thread t1 = new Thread(() => DoTestIdWoker(idWorker1, set));
            Thread t2 = new Thread(() => DoTestIdWoker(idWorker2, set));
            t1.IsBackground = true;
            t2.IsBackground = true;

            t1.Start();
            t2.Start();
            try
            {
                Thread.Sleep(30000);
                t1.Abort();
                t2.Abort();
            }
            catch (Exception e)
            {
            }

            Console.WriteLine("done");
        }

        private static void DoTestIdWoker(IdWorker idWorker, HashSet<long> set)
        {
            while (true)
            {
                long id = idWorker.nextId();
                if (!set.Add(id))
                {
                    Console.WriteLine("duplicate:" + id);
                }

                Thread.Sleep(1);
            }
        }

亚洲必赢官网 9

 

 

snowflake算法能够依照我项目标须要开始展览一定的改造。比方揣测未来的数码基本个数,每一个数据基本的机器数以及统一纳秒能够能的并发数来调度在算法中所供给的bit数。

优点:

壹)不正视于数据库,灵活方便,且品质优越数据库。

二)ID根据时间在单机上是比比皆是的。

缺点:

1)在单机上是多如牛毛的,可是出于涉及到布满式景况,每台机器上的时钟不容许完全同步,大概有时候也会并发不是大局递增的事态。

 

6. 用到zookeeper生成唯一ID

 

zookeeper主要通过其znode数据版本来生成序列号,可以生成32位和64位的数据版本号,客户端可以使用这个版本号来作为唯一的序列号。

很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper,并且是多步调用API,如果在竞争较大的情况下,需要考虑使用分布式锁。因此,性能在高并发的分布式环境下,也不甚理想。

 

7. MongoDB的ObjectId

MongoDB的ObjectId和snowflake算法类似。它设计成轻量型的,不同的机器都能用全局唯一的同种方法方便地生成它。MongoDB 从一开始就设计用来作为分布式数据库,处理多个节点是一个核心要求。使其在分片环境中要容易生成得多。

其格式如下:

亚洲必赢官网 10

 

前4 个字节是从规范纪元初始的时日戳,单位为秒。时间戳,与随着的6个字节组合起来,提供了秒级其他唯1性。由于时日戳在前,那意味ObjectId
大约会按照插入的顺序排列。那对于一些方面很有用,如将其视作目录提升作用。那五个字节也蕴藏了文书档案创立的年月。绝大许多客户端类库都会当面贰个格局从ObjectId
获取这几个消息。 
接下去的三字节是所在主机的当世无双标记符。经常是机器主机名的散列值。这样就能够有限支撑差别主机生成区别的ObjectId,不发生争论。 
为了保障在一样台机器上现身的四个经过发生的ObjectId
是独一无二的,接下去的两字节来自发生ObjectId 的长河标记符(PID)。 
前玖 字节保障了一样分钟分歧机器不一致进度产生的ObjectId 是不二法门的。后三字节正是2个活动增添的计数器,确认保证同等进度同壹秒发生的ObjectId
也是不雷同的。同1分钟最多允许各种进度具有256三(1六 777
21陆)个不等的ObjectId。

得以达成的源码能够到MongoDB官方网址下载。

跟雪花ID方案同样,都以采用时间数额做为生成ID的基础,差别的在于对数据的有血有肉管理情势。此外,为了确认保证每台机器ID的两样,能够配备钦定此ID,在应用程序配置文件中如下配置:

优点:

  1. 轻巧,代码方便,质量能够承受。
  2. 数字ID天然排序,对分页或许须要排序的结果很有援助。

ID生成系统的档次

<!--分布式ID标识,3位整数,范围101-999 大小--> 
<add key="SOD_MachineID" value="101"/>

缺点:

  1. 今非昔比数据库语法和达成差异,数据库迁移的时候或大部据库版本扶助的时候要求管理。
  2. 在单个数据库或读写分离或一主多从的情景下,唯有一个主库能够改动。有单点故障的高风险。
  3. 在性质达不到供给的景色下,比较难于扩展。
  4. 壹旦遇见多个连串须要统一也许关联到数码迁移会一定痛心。
  5. 分表分库的时候会有麻烦。

UUID

UUID是指在一台机械在同权且间中变化的数字在有着机器中都是并世无双的。遵照开放软件基金会(OSF)制定的科班测算,用到了以太网卡地址、阿秒级时间、芯片ID码和不知凡几只怕的数字
UUID由以下几片段的结缘:
(一)当前几天子和岁月。
(二)石英钟序列。
(3)全局唯1的IEEE机器度和胆识别号,假设有网卡,从网卡MAC地址得到,未有网卡以其它艺术赢得。
标准的UUID格式为:xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
(8-肆-四-四-1②),以连字号分为五段格局的三十八个字符,示例:550e8400-e2九b-肆一d四-a716-446655460000
Java标准类库中早已提供了UUID的API。

UUID.randomUUID()

优点

  • 属性相当高:本地转移,未有互联网消耗。

缺点

  • 不错存款和储蓄:UUID太长,1陆字节127个人,平日以3陆长短的字符串表示,诸多处境不适用。
  • 音信不安全:基于MAC地址生成UUID的算法可能会形成MAC地址败露,这么些漏洞曾被用于寻觅梅Lisa病毒的制作者地点。
  • ID作为主键时在一定的条件会设有有的标题,比方做DB主键的光景下,UUID就老大不适用。

假使不安插布满式ID,暗中认可将根据近期机械IP随机生成3位布满式机器ID。

优化方案:

  1. 本着主库单点,假诺有八个Master库,则每一个Master库设置的苗子数字不雷同,步长同样,能够是Master的个数。
    例如:Master一 生成的是 一,四,7,十,Master2生成的是二,伍,八,11
    Master三生成的是
    三,陆,九,1二。那样就能够使得生成集群中的唯1ID,也能够大大下降ID生成数据库操作的负载。

  2. UUID


广阔的章程,127人。能够动用数据库也足以动用程序生成,一般的话整个世界唯壹。

SnowFlake雪花算法

雪花ID生成的是3个63位的二进制正整数,然后转产生十进制的数。6十位贰进制数由如下一些构成:

亚洲必赢官网 11

snowflake id生成规则

  • 1个人标记符:始终是0,由于long基本项目在Java中是带符号的,最高位是符号位,正数是0,负数是一,所以id一般是正数,最高位是0。
  • 四一位时间戳:44个人时间截不是累积当前时刻的年月截,而是存款和储蓄时间截的差值(超过天子截 –
    早先时间截
    )获得的值,这里的的伊始时间截,一般是大家的id生成器开首运用的时刻,由大家先后来钦命的。
  • 拾1个人机器标记码:能够配备在十二四个节点,借使机器分机房(IDC)布置,那十位能够由
    5位机房ID + 5位机器ID 组成。
  • 12位序列:纳秒内的计数,九个人的计数顺序号援救各类节点每阿秒(同一机器,同暂时间截)爆发40九四个ID序号

优点

  • 简短火速,生成速度快。
  • 光阴戳在高位,自增体系在未有,整个ID是样子递增的,依照时间不改变递增。
  • 灵活度高,能够依照专门的学业需求,调解bit位的细分,满足差异的须求。

缺点

  • 依赖机器的石英钟,假设服务器石英钟回拨,会造成重复ID生成。
  • 在分布式遭受上,每一个服务器的石英电子手表不只怕完全同步,有时会并发不是全局递增的动静。

snowflake Java实现

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
 * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
 * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。
 * 41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位,为一个Long型。<br>
 * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,
 * 经测试,SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (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;

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @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;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个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();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

该算法的落到实处比雪花算法简单不少,详细的不多说,先直接看代码:

优点:

  1. 大概,代码方便。
  2. 普天之下唯1,在遇到数据迁移,系统数据统一,恐怕数据库改动等情状下,能够从容应对。

数据库自增ID机制

重视思路是行使数据库自增ID + replace_into达成唯①ID的取得。

create table t_global_id(
    id bigint(20) unsigned not null auto_increment,
    stub char(1) not null default '',
    primary key (id),
    unique key stub (stub)
) engine=MyISAM;

# 每次业务可以使用以下SQL读写MySQL得到ID号
replace into t_golbal_id(stub) values('a');
select last_insert_id();

replace into跟insert功用类似,分裂点在于:replace
into首先尝试插入数据列表中,借使开采表中已经有此行数据(依据主键或唯一索引推断)则先删除,再插入。不然直接插入新数据。
当然为了幸免数据库的单点故障,最少必要五个数据库实例,通过区分auto_increment的开始值和宽度来生成奇偶数的ID。如下:

Server1:
auto-increment-increment = 2
auto-increment-offset = 1

Server2:
auto-increment-increment = 2
auto-increment-offset = 2

优点

  • 简易。充足借助数据库的自增ID机制,可信赖性高,生成有序的ID。

缺点

  • ID生成正视数据库单机的读写质量。
  • 依赖数据库,当数据库卓殊时整个体系不可用。

对此MySQL的个性难点,能够用如下方案搞定
在遍布式遭遇中,我们能够安插N台数据库实例,每台设置成差别的启幕值,自增长幅度度为机械的台数。每台的开首值分别为1,二,三…N,步长为N。

亚洲必赢官网 12

MySQL数据库自增ID多机图

上述方案就算缓和了品质难题,不过也设有不小的局限性:

  • 系统水平扩大体量困难:系统定义好步长之后,增添机械之后调解幅度困难。假使要抬高机器如何是好?尽管以往唯有一台机械发号是壹,2,三,4,伍(步长是一),这一年供给扩大体积机器一台。能够这么做:把第二台机器的初叶值设置得比第二台超越许多,比如14(若是在扩大体量时间之内第3台不容许发到14),同时安装步长为2,那么那台机械发出的号子都是1肆从此的偶数。然后摘掉第二台,把ID值保留为奇数,比如七,然后修改第3台的增进率为二。让它符合大家定义的号段标准,对于那么些例子来讲就是让第贰台将来只可以发出奇数。扩大体积方案看起来复杂呢?貌似万幸,今后想象一下比方大家线上有100台机械,那个时候要扩大体量该如何做?几乎是惊恐不已的梦。
  • 数据库压力大:每一遍获得四个ID都不可能不读写三次数据库。当然对于那种主题材料,也有对应的缓和方案,正是历次获得ID时都批量赢得三个区间的号段到内部存款和储蓄器中,用完之后再来获取。数据库的品质提升了多少个量级。
        /// <summary>
        /// 获取一个新的有序GUID整数
        /// </summary>
        /// <param name="dt">当前时间</param>
        /// <param name="haveMs">是否包含毫秒,如果不包含,将使用3位随机数代替</param>
        /// <returns></returns>
        protected internal static long InnerNewSequenceGUID(DateTime dt, bool haveMs)
        {
            //线程安全的自增并且不超过最大值10000
            int countNum = System.Threading.Interlocked.Increment(ref SeqNum);
            if (countNum >= 10000)
            {
                while (Interlocked.Exchange(ref signal, 1) != 0)//加自旋锁
                {
                    //黑魔法
                }
                //进入临界区
                if (SeqNum >= 10000)
                {
                    SeqNum = 0;
                    //达到1万个数后,延迟10毫秒,重新取系统时间,避免重复
                    Thread.Sleep(10);
                    dt = DateTime.Now;
                }
                countNum = System.Threading.Interlocked.Increment(ref SeqNum);
                //离开临界区
                Interlocked.Exchange(ref signal, 0);  //释放锁
            }

            //日期以 2017.3.1日为基准,计算当前日期距离基准日期相差的天数,可以使用20年。
            //日期部分使用4位数字表示
            int days = (int)dt.Subtract(baseDate).TotalDays;
            //时间部分表示一天中所有的秒数,最大为 86400秒,共5位
            //日期时间总位数= 4(日期)+5(时间)+3(毫秒)=12
            int times = dt.Second + dt.Minute * 60 + dt.Hour * 3600;
            //long 类型最大值 9223 3720 3685 4775 807
            //可用随机位数= 19-12=7
            long datePart = ((long)days + 1000) * 1000 * 1000 * 1000 * 100;
            long timePart = (long)times * 1000 * 1000;
            long msPart = 0;
            if (haveMs)
            {
                msPart = (long)dt.Millisecond ;
            }
            else

            {
                msPart = new Random().Next(100, 1000);
            }
            long dateTiePart = (datePart + timePart + msPart*1000) * 10000;

            int mid = MachineID * 10000;
            //得到总数= 4(日期)+5(时间)+3(毫秒)+7(GUID)
            long seq = dateTiePart + mid;

            return seq + countNum; ;
        }

缺点:

  1. 从未排序,无法担保趋势递增。
  2. UUID往往是行使字符串存款和储蓄,查询的频率异常低。
  3. 仓库储存空间相当的大,假如是海量数据库,就要求思虑存款和储蓄量的标题。
  4. 传输数据量大
  5. 不可读。

其叁方软件生成(Redis)

Redis达成了1个原子操作INCMurano和INCRBY达成递增的操作。当使用数据库质量不够时,能够利用Redis来取代,同时接纳Redis集群来压实吞吐量。能够开首化每台Redis的伊始值为壹,二,三,四,伍,然后步长为伍。各种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

优点

  • 不依赖于数据库,灵活方便,且品质优于数据库。
  • 数字ID天然排序,对分页可能须求排序的结果很有帮忙。

缺点:

  • 比如系统中向来不Redis,还索要引进新的机件,扩大系统复杂度。
  • 急需编码和布局的专业量很大。那么些都不是最大的难点。

关于分布式全局唯1ID的浮动,各类网络厂商有众多兑现方案,比方美团点评的Leaf-snowflake,用zookeeper化解了逐条服务器石英钟回拨的主题素材,弱依赖zookeeper。以及Leaf-segment类似上边数据库批量ID获取的方案。

注意:上面运用了三个效仿的自旋锁,用来在最终的顺序号当先二万的时候归零重新计算,并且睡眠十阿秒从而根本上杜绝重新ID。

优化方案:

  1. 为了消除UUID不可读,能够使用UUID to Int6四的法门。

  2. GUID


GUID:是微软对UUID这么些职业的达成。UUID还有其余各个完毕,不止GUID1种。优缺点同UUID。

参考

  • 推文(Tweet)的布满式自增ID算法snowflake
    (Java版)
  • Leaf——美团点评分布式ID生成系统

亚洲必赢官网 13

亚洲必赢官网 14

每秒不重复ID生成数:

从地点的程序代码中,得知 ID总的数量=
二位(日期)+5个人(时间)+4人(微秒)+六人(GUID)。
中间,五个人(GUID)中,除去前二位的布满式机器ID,剩余二人不变数字,能够代表1万个数字。
为此,该地点每皮秒最大能够调换一万个不另行的ID数,每秒最大能够更动一千万个不重复ID。
理所当然这是理论大小,实际上受到当前机械的测算才能限制。

该方式开始展览了重复卷入,用于在不一致情形下各自选择:

      /// <summary>
       /// 生成一个新的在秒级别有序的长整形“GUID”,在一秒内,数据比较随机,线程安全,
       /// 但不如NewUniqueSequenceGUID 方法结果更有序(不包含毫秒部分)
       /// </summary>
       /// <returns></returns>
       public static long NewSequenceGUID()
       {
           return UniqueSequenceGUID.InnerNewSequenceGUID(DateTime.Now,false);
       }

       /// <summary>
       /// 生成一个唯一的更加有序的GUID形式的长整数,在一秒内,一千万个不重复ID,线程安全。可用于严格有序增长的ID
       /// </summary>
       /// <returns></returns>
       public static long NewUniqueSequenceGUID()
       {
           return UniqueId.NewID();
       }

        /// <summary>
        /// 当前机器ID,可以作为分布式ID,如果需要指定此ID,请在应用程序配置文件配置 SOD_MachineID 的值,范围大于100,小于1000.
        /// </summary>
        /// <returns></returns>
        public static int CurrentMachineID()
        {
            return UniqueSequenceGUID.GetCurrentMachineID();
        }

提起底,像下边那样使用即可:

        Console.WriteLine("当前机器的分布式ID:{0}",CommonUtil.CurrentMachineID());
            Console.WriteLine("测试分布式ID:秒级有序");
            for (int i= 0; i < 50; i++)
            {
                Console.Write(CommonUtil.NewSequenceGUID());
                Console.Write(",");
            }
            Console.WriteLine();
            Console.WriteLine("测试分布式ID:唯一且有序");
            for (int i = 0; i < 50; i++)
            {
                Console.Write(CommonUtil.NewUniqueSequenceGUID());
                Console.Write(",");
            }
            Console.WriteLine();

下边是调换的ID数字示例:

当前机器的分布式ID:832

测试遍及式ID:秒级有序
1460532991258320201,1460532991258320202,1460532991258320203,1460532991258320204,1460532991258320205,
1460532991258320206,1460532991258320207,1460532991258320208,1460532991258320209,1460532991258320210,
1460532991258320211,1460532991258320212,1460532991258320213,1460532991258320214,1460532991258320215,
1460532991258320216,1460532991258320217,1460532991258320218,1460532991258320219,1460532991258320220,
1460532991258320221,1460532994488320222,1460532994488320223,1460532994488320224,1460532994488320225,
1460532994488320226,1460532994488320227,1460532994488320228,1460532994488320229,1460532994488320230,
1460532994488320231,1460532994488320232,1460532994488320233,1460532994488320234,1460532994488320235,
亚洲必赢官网 ,1460532994488320236,1460532994488320237,1460532994488320238,1460532994488320239,1460532994488320240,
1460532994488320241,1460532994488320242,1460532994488320243,1460532994488320244,1460532994488320245,
1460532994488320246,1460532994488320247,1460532994488320248,1460532993018320249,1460532993018320250,

测试分布式ID:唯1且有序
1460532997708320251,1460532997708320252,1460532997718320253,1460532997718320254,1460532997718320255,
1460532997728320256,1460532997728320257,1460532997728320258,1460532997738320259,1460532997738320260,
1460532997788320261,1460532997788320262,1460532997788320263,1460532997838320264,1460532997838320265,
1460532997838320266,1460532997838320267,1460532997858320268,1460532997858320269,1460532997858320270,
1460532997858320271,1460532997868320272,1460532997868320273,1460532997868320274,1460532997878320275,
1460532997878320276,1460532997878320277,1460532997878320278,1460532997888320279,1460532997888320280,
1460532997888320281,1460532997888320282,1460532997898320283,1460532997908320284,1460532997918320285,
1460532997918320286,1460532997918320287,1460532997918320288,1460532997928320289,1460532997928320290,
1460532997928320291,1460532997928320292,1460532997938320293,1460532997938320294,1460532997948320295,
1460532997948320296,1460532997948320297,1460532998028320298,1460532998028320299,1460532998068320300,

 

 

注:本文生成ID的不二等秘书诀已经在产品中山大学量选择,运营状态理想。

要选取本程序,你能够Nuget 下载SOD的顺序包(援救.NET
二.0品种),然后像本文示例那样使用就可以:

Install-Package PDF.NET.SOD.Core

获取SOD的源码,请Fork我们的Github:

源码地方在  目录下。

有问号,请加QQ群154224970 咨询,感激我们协助SOD框架!

 

4. COMB

COMB(combine)型是数据库特有的1种设计观念,能够领略为一种革新的GUID,它经过整合GUID和种类时间,以使其在目录和找寻事有更优的性质。
  数据库中从未COMB类型,它是吉姆my Nilsson在他的“The Cost of GUIDs as
Primary Keys”一文中设计出来的。
  COMB数据类型的核心陈设思路是如此的:既然UniqueIdentifier数据因并非规律可言产生索引效用低下,影响了系统的属性,那么我们能否经过整合的不二秘技,保留UniqueIdentifier的前十二个字节,用后5个字节表示GUID生成的小时(DateTime),那样我们将时刻音信与UniqueIdentifier组合起来,在保留UniqueIdentifier的唯1性的同时增添了有序性,以此来增长索引功用。

优点:

  1. 竭泽而渔UUID冬日的标题,在其主键生成方式中提供了Comb算法(combined
    guid/timestamp)。保留GUID的十一个字节,用另陆个字节表示GUID生成的岁月(DateTime)。
  2. 品质优于UUID。

  3. Twitter的snowflake算法


snowflake是Twitter开源的布满式ID生成算法,结果是3个long型的ID。其核心情想是:使用四一bit看作飞秒数,十bit看成机器的ID(四个bit是数码基本,五个bit的机器ID),12bit当做皮秒内的流水号(意味着每一个节点在每皮秒能够生出
40玖陆 个
ID),最终还有多少个标记位,永久是0。snowflake算法能够依附本身项目的急需开始展览自然的修改。比方估量以往的数据基本个数,每一种数据基本的机器数以及统一皮秒能够能的并发数来调动在算法中所供给的bit数。

优点:

  1. 不借助于于数据库,灵活方便,且品质优越数据库。
  2. ID依照时间在单机上是俯十皆是的。

缺点:

  1. 在单机上是一日千里的,可是出于涉及到分布式情况,每台机器上的原子钟不可能完全同步,大概有时候也会冒出不是全局递增的景况。

参考:

  1. 布满式系统唯一ID生成方案汇总
  2. UUID 、GUID、COMB
    的界别与联系
  3. UUID 和 GUID
    的区别
  4. The Cost of GUIDs as Primary
    Keys
  5. Integer
    GUID和Comb做主键的频率测试(Delphi+access)(三)
  6. 照片墙-Snowflake项目地址(Tags:snowflake-20拾)
  7. 什么在高并发布满式系统中变化全局唯一Id
  8. 推特-Snowflake(陆15位布满式ID算法)分析与JAVA达成

转发阐明出处,小编就不和您争论。
by Donney Young
http://www.jianshu.com/p/a0a3aa888a49

网站地图xml地图