Twitter的分布式自增ID算法Snowflake

标签: twitter id 算法 | 发表时间:2015-05-09 03:52 | 作者:yuanhsh
出处:http://www.iteye.com

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

Snowflake算法核心

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

 

snowflake-64bit

 

除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。 默认情况下41bit的时间戳可以支持该算法使用到2082年,10bit的工作机器id可以支持1023台机器,序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

 

Snowflake – 时间戳

这里时间戳的细度是毫秒级,具体代码如下,建议使用64位linux系统机器,因为有 vdso,gettimeofday()在用户态就可以完成操作,减少了进入内核态的损耗。

1
2
3
4
5
6
uint64_t generateStamp()
{
     timeval tv;
     gettimeofday(&tv, 0);
     return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;
}

默认情况下有41个bit可以供使用,那么一共有T(1llu << 41)毫秒供你使用分配,年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用,那么根据同样的算法最后年份 = 17.4年。

Snowflake – 工作机器id

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

这里的解决方案是需要一个工作id分配的进程,可以使用自己编写一个简单进程来记录分配id,或者利用Mysql auto_increment机制也可以达到效果。

snowflake - 工作id

 

工作进程与工作id分配器只是在工作进程启动的时候交互一次,然后工作进程可以自行将分配的id数据落文件,下一次启动直接读取文件里的id使用。

PS:这个工作机器id的bit段也可以进一步拆分,比如用前5个bit标记进程id,后5个bit标记线程id之类:D

Snowflake – 序列号

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

1
2
3
4
5
6
7
8
uint64_t waitNextMs(uint64_t lastStamp)
{
     uint64_t cur = 0;
     do {
         cur = generateStamp();
     } while (cur <= lastStamp);
     return cur;
}

 

总体来说,是一个很高效很方便的GUID产生算法,一个int64_t字段就可以胜任,不像现在主流128bit的GUID算法,即使无法保证严格的id序列性,但是对于特定的业务,比如用做游戏服务器端的GUID产生会很方便。另外,在多线程的环境下,序列号使用atomic可以在代码实现上有效减少锁的密度。

 

结构为:

   0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---0000000000 00

在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。

这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。

 

public class IdWorker {
    private final long        workerId;
    private final static long twepoch            = 1361753741828L;
    private long              sequence           = 0L;
    private final static long workerIdBits       = 4L;
    private final static long maxWorkerId        = -1L ^ -1L << workerIdBits;
    private final static long sequenceBits       = 10L;

    private final static long workerIdShift      = sequenceBits;
    private final static long timestampLeftShift = sequenceBits + workerIdBits;
    private final static long sequenceMask       = -1L ^ -1L << sequenceBits;

    private long              lastTimestamp      = -1L;

    public IdWorker(final long workerId) {
        super();
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format(
                "worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = this.timeGen();
        if (this.lastTimestamp == timestamp) {
            this.sequence = (this.sequence + 1) & sequenceMask;
            if (this.sequence == 0) {
                System.out.println("###########" + sequenceMask);
                timestamp = this.tilNextMillis(this.lastTimestamp);
            }
        } else {
            this.sequence = 0;
        }
        if (timestamp < this.lastTimestamp) {
            try {
                throw new Exception(String.format(
                    "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    this.lastTimestamp - timestamp));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        this.lastTimestamp = timestamp;
        long nextId = ((timestamp - twepoch << timestampLeftShift))
                      | (this.workerId << workerIdShift) | (this.sequence);
        //  System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"
        //       + timestampLeftShift + ",nextId:" + nextId + ",workerId:"
        //       + workerId + ",sequence:" + sequence);
        return nextId;
    }

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

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

    public static void main(String[] args) throws InterruptedException {
        IdWorker worker2 = new IdWorker(2);
        System.out.println(worker2.nextId());
        Thread.sleep(1000L);
        System.out.println(worker2.nextId());
    }
}

 

 

Reference:

http://www.lanindex.com/twitter-snowflake/



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


ITeye推荐



相关 [twitter 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.

产生Id

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

语言学家开发出算法识别Twitter用户性别

- geek2live - Solidot
网民多以假名掩盖身份,雌雄难辩,男扮女女扮男屡见不鲜,然而他们的言语和喜好会暴露他们的身份. Mitre公司的语言学研究人员,在苏格兰举行的自然语言处理实证方法会议上公布了一篇论文(PDF),称他们开发出一种算法能根据Twitter用户的帖子内容识别出其性别,他们的依据是女性所用语言和男性存在相当大的差异.

小米手机ID简介

- miyizs - Billwang 工业设计
      小米手机是小米公司(全称北京小米科技有限责任公司)专为发烧友级手机控打造的 一款高品质智能手机. 下面我们将对其做一个简单的介绍.       小米手机的外观设计走的是简约内敛路线,直板加圆润的边角让其显得简单清爽. 小米手机配置了,1.5GHz双核处理器、1G RAM、4英寸夏普屏、800万像素摄像头以及大容量电池.

id Software发布《狂怒(Rage)》

- ArmadilloCommander - Solidot
id Software发布了容量为21GB的第一人称射击游戏《狂怒(Rage)》. 游戏基于id Tech 5引擎,背景是世界末日后的未来. 目前对它的评价好坏参半,媒体综合评分80左右,玩家评分相似或更低. 在游戏中,玩家将扮演一位小行星Apophis撞击地球后的幸存者. 在灾难发生前,全世界展开合作将包括科学家在内的精英冰冻在地下,以在灾难后重建地球.

标签?ID?还是CLASS?

- - 前端观察
想谈一下几个基本的HTML问题,都是围绕着应该怎样使用HTML. 多用有语义的标签,少用div和span,避免使用没有class的div和span. 设想一下HTML的世界最初只有div和span这两个标签,其实网页依然可以写得出来. 更多标签的出现,其实是为了替代利用率高但不好书写的  <div class="{tagname}"> 和 <span class="{tagname}"> 来的.

Linuxer:制作自己的Linux ID Card吧

- rex - Wow! Ubuntu
Super Boot Manager的作者Alessandro Lanave,又为Linuxer带来了一个web程序,制作Linux ID Card ,Card效果如图. 可以把ID Card做为论坛签名,博客签名,任何你需要的地方. 当然,如果觉得没有自己喜欢的发行版的模板,可以向Alessandro Lanave提交哦,.

两个 Apple ID 是很有必要的

- 闷闲居士 - Page to Page
刚买iPad的时候注册的是中国区的Apple ID,绑定了自己的信用卡. 可当搜索下载Kindle for iPad的时候才觉得,注册一个美国区的Apple ID还是很有必要的,否则很多中国区没有的App无法下载. 大致学习了2篇注册美国区ID的帖子,赶紧动手,可是还是因为疏忽产生了问题,提示我说“我的邮箱地址已经注册了”.