布满式唯1ID服务架构

2019-05-03 22:40 来源:未知

简介

这个是根据twitter的snowflake来写的.这里有中文的介绍.

www.weide1946.com 1

如上图所示,一个64位ID,除了最左边的符号位不用(固定为0,以保证生成的ID都是正数),还剩余63位可用.

下面的代码与图中的位数分配略有不同,除了中间部分10bit工作机器id不变,时间戳和序列号的位数是可以根据自己的需求变化的,就是说,你可以把中间的工作机器ID往左挪一挪,或往右挪一挪.

在大型互联网应用中,随着用户数的增加;为了提高应用的性能,我们经常需要对数据库进行分库分表操作。在单表时代我们可以完全依赖于数据库的自增ID来唯一标识一个条数据。但是当我们对数据库进行了分库分表之后,就不能依赖于每个表的自增ID来全局唯一标识这些数据了。因为自增的ID不能在分库分表的场景下准确的路由到正确的数据。

代码

    /// <summary>
    /// 64位ID生成器,最高位为符号位,始终为0,可用位数63.
    /// 实例编号占10位,范围为0-1023
    /// 时间戳和索引共占53位
    /// </summary>
    public sealed class IdCreator
    {
        private static readonly Random r = new Random();
        private static readonly IdCreator _default = new IdCreator();

        private readonly long instanceID;//实例编号
        private readonly int indexBitLength;//索引可用位数
        private readonly long tsMax = 0;//时间戳最大值
        private readonly long indexMax = 0;
        private readonly object m_lock = new object();

        private long timestamp = 0;//当前时间戳
        private long index = 0;//索引/计数器

        /// <summary>
        /// 
        /// </summary>
        /// <param name="instanceID">实例编号(0-1023)</param>
        /// <param name="indexBitLength">索引可用位数(1-32).每秒可生成ID数等于2的indexBitLength次方.大并发情况下,当前秒内ID数达到最大值时,将使用下一秒的时间戳,不影响获取ID.</param>
        /// <param name="initTimestamp">初始化时间戳,精确到秒.当之前同一实例生成ID的timestamp值大于当前时间的时间戳时,
        /// 有可能会产生重复ID(如持续一段时间的大并发请求).设置initTimestamp比最后的时间戳大一些,可避免这种问题</param>
        public IdCreator(int instanceID, int indexBitLength, long? initTimestamp = null)
        {
            if (instanceID < 0)
            {
                //这里给每个实例随机生成个实例编号
                this.instanceID = r.Next(0, 1024);
            }
            else
            {
                this.instanceID = instanceID % 1024;
            }

            if (indexBitLength < 1)
            {
                this.indexBitLength = 1;
            }
            else if (indexBitLength > 32)
            {
                this.indexBitLength = 32;
            }
            else
            {
                this.indexBitLength = indexBitLength;
            }
            tsMax = Convert.ToInt64(new string('1', 53 - indexBitLength), 2);
            indexMax = Convert.ToInt64(new string('1', indexBitLength), 2);

            if (initTimestamp != null)
            {
                this.timestamp = initTimestamp.Value;
            }
        }

        /// <summary>
        /// 默认每实例每秒生成65536个ID,从1970年1月1日起,累计可使用4358年
        /// </summary>
        /// <param name="instanceID">实例编号(0-1023)</param>
        public IdCreator(int instanceID) : this(instanceID, 16)
        {

        }

        /// <summary>
        /// 默认每秒生成65536个ID,从1970年1月1日起,累计可使用4358年
        /// </summary>
        public IdCreator() : this(-1)
        {

        }

        /// <summary>
        /// 生成64位ID
        /// </summary>
        /// <returns></returns>
        public long Create()
        {
            long id = 0;

            lock (m_lock)
            {
                //增加时间戳部分
                long ts = Harry.Common.Utils.GetTimeStamp() / 1000;

                ts = ts % tsMax;  //如果超过时间戳允许的最大值,从0开始
                id = ts << (10   indexBitLength);//腾出后面部分,给实例编号和索引编号使用

                //增加实例部分
                id = id | (instanceID << indexBitLength);

                //获取计数
                if (timestamp < ts)
                {
                    timestamp = ts;
                    index = 0;
                }
                else
                {
                    if (index > indexMax)
                    {
                        timestamp  ;
                        index = 0;
                    }
                }

                id = id | index;

                index  ;
            }

            return id;
        }

        /// <summary>
        /// 获取当前实例的时间戳
        /// </summary>
        public long CurrentTimestamp
        {
            get
            {
                return this.timestamp;
            }
        }

        /// <summary>
        /// 默认每实例每秒生成65536个ID,从1970年1月1日起,累计可使用4358年
        /// </summary>
        public static IdCreator Default
        {
            get
            {
                return _default;
            }
        }
    }

因此我们需要提供一个全局唯一的ID生成策略来支持分库分表的应用环境;这个系统必须满足以下需求:

代码说明

使用时,需要new一个IdCreator的实例,然后调用Create()方法,生成一个ID号.需要把IdCreator的例实赋给一个静态变量,以保证ID号的唯一性.如果是分布式部署,需要给IdCreator的构造函数传递instanceID参数,每一个部署都要有一个不同的值,范围为0-1023.

构造函数中的indexBitLength参数,代表图中最右边的'序列号'的长度,不再固定为12bit,范围为1-32.剩下的可用位,就留给了时间戳.

注意:IdCreator类的时间戳是按秒计的. 如果想改成毫秒,只需要将代码long ts = Harry.Common.Utils.GetTimeStamp() / 1000;改成long ts = Harry.Common.Utils.GetTimeStamp();即可.

  • 全局唯一: 不能出现重复的ID;
  • 高可用: ID生成系统属于基础服务,同时被许多关键系统调用,一旦宕机,会造成严重影响;

示例代码

    IdCreator c=new IdCreator(0,16);
    var id=c.Create();

欢迎加Q群:7957181

1. UUID

UUID是Universally Unique Identifier的缩写,它是在一定范围内(从特定的名字空间到全球)唯一的机器生成的标识符,UUID是16字节128位长的数字,通常以36字节的字符串表示;比如:

UUID经由一定的算法机器生成,为了保证UUID的唯一性,规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。UUID的复杂特性在保证了其唯一性的同时,意味着只能由计算机生成。

优点:
  • 本地生成ID,不需要远程调用、低延时、性能高;
缺点:
  • UUID过长,16字节128位,很多场景不适用;比如用UUID做数据库的索引时,插入数据时数据量越大,插入性能越低;
  • UUID不是有序的,无法保证趋势递增;

2. Flicker方案

该方案主要的思路是采用了MySQL自增长的ID的机制(auto_increment replace into)

--- 数据表CREATE TABLE Tickets64 ( id bigint unsigned NOT NULL auto_increment, stub char NOT NULL default '', PRIMARY KEY , UNIQUE KEY stub ENGINE=MyISAM;

--- 每次业务使用下列sql读写MySQL得到ID号REPLACE INTO Tickets64  VALUES ;SELECT LAST_INSERT_ID();

replace into跟insert功能类似,不同之处在于: replace into 首先尝试插入数据到表中,如果发现表中已经有此行数据则先删除此行数据,然后插入新的数据,否则直接插入新数据;

优点:
  • 充分借助数据库的自增ID机制,可靠性高,生成有序ID
缺点:
  • ID生成性能依赖单台数据库读写性能;
  • 依赖数据库,当数据库异常时整个系统不可用。

3. Twitter-Snowflake方案

Twitter-Snowflake算法产生的背景相当简单,是为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序,并且在分布式系统中不同机器产生的id必须不同。

Snowflake算法核心

时间戳工作机器Id序列号组合在一起。

www.weide1946.com 2www.weide1946.com,Snowflake核心算法

除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,具体看业务需求而定。默认情况下:

  • 41bit的时间戳可以支持该算法使用到2082年;
  • 10bit的工作机器id可以支持1023台机器,
  • 序列号支持1毫秒产生4095个自增序列id。
Snowflake - 时间戳

在这里,时间戳的粒度为毫秒级,具体代码如下:

uint64_t generateStamp() { timeval tv; gettimeofday(&tv, 0); return tv.tv_sec * 1000   tv.tv_usec / 1000;}

默认情况下有41个bit可以使用,那么(1 << 41) / (3600 * 24 * 365 * 1000) = 69.7年

Snowflake - 工作机器Id

严格意义来说工作机器Id可以是进程级的, 机器级的话可以使用MAC地址来唯一标示工作机器,工作进程级可以使用IP Path来区分工作进程。如果工作机器比较少,可以使用配置文件来设置这个id是一个不错的选择,如果机器过多配置文件来维护则是一件灾难性的事情。

Snowflake - 序列号

序列号就是一系列的自增Id,为了处理在同一毫秒内需要给多条消息分配id,若同一毫秒把序列号用完了,则“等待至下一毫秒”

uint64_t waitNextMs(uint64_t lastStamp){ uint64_t cur = 0; do { cur = generateStamp(); } while (cur <= lastStamp); return cur;}

Snowflake参数资料

版权声明:本文由韦德娱乐1946_韦德娱乐1946网页版|韦德国际1946官网发布于网络编程,转载请注明出处:布满式唯1ID服务架构