文档章节

Twitter-Snowflake 64位自增ID简介

保护单身狗协会理事长
 保护单身狗协会理事长
发布于 2017/09/11 16:39
字数 620
阅读 37
收藏 1

      在系统中,我们需要为每个资源设置一个唯一ID,单表时代,使用数据库的自增ID可以很简单的达到我们的目的,但是在分布式系统、多库多表的情况下,数据库自增ID就不灵了,因此,我们需要另一种算法来实现分布式环境下的唯一ID。

      Snowflake核心算法:

     

      把时间戳、工作id和序列号拼装起来,生成一个64bit的唯一id,符号位不用,其他三组bit可以根据业务需要来进行调整,默认方案下,能使用69年,部署1023台机器,每毫秒能产生4095个自增ID。

      这里的69年,1023台机器,4095个自增ID是怎么算出来的的?

      假设41个bit都是1,那么转换成10进制就是 2**41-1 = 2199023255552毫秒≈69年,机器数量、自增ID数量也是如此计算。

      生成唯一ID的方式很多,为什么是Snowflake?

      1、相对有序,数据库插入性能好。

      2、Long 型存储,相对于guid uuid占用空间小。

 

JAVA 实现:

public class SnowFlake {

    private static final Long workerIdBits = 10L;
    private static final Long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private static final Long sequenceBits = 12L;
    private static final Long maxSequence = -1L ^ (-1L << sequenceBits);

    private static final Long workerIdShift = sequenceBits;
    private static final Long timestampLeftShift = sequenceBits + workerIdBits;

    private final Long workerId;

    private Long sequence = 0L;
    private Long lastTimestamp = -1L;

    private Long since = 0l;

    public SnowFlake(final Long workerId) {
        super();

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

        this.workerId = workerId;

        Calendar calendar = Calendar.getInstance();
        calendar.set(2016, Calendar.NOVEMBER, 3, 0, 0, 0);

        this.since = calendar.getTimeInMillis();
    }

    public synchronized Long nextId() throws Error {
        long timestamp = this.timeGen();

        if (this.lastTimestamp == timestamp) {
            this.sequence = (this.sequence + 1) & this.maxSequence;

            if (this.sequence == 0) {
                timestamp = this.tilNextMillis(this.lastTimestamp);
            }
        } else {
            this.sequence = 0l;
        }

        if (timestamp < this.lastTimestamp) {
            throw new Error(
                    String.format(
                            "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                            this.lastTimestamp - timestamp));
        }

        this.lastTimestamp = timestamp;

        return ((timestamp - since) << timestampLeftShift) | (this.workerId << this.workerIdShift) | (this.sequence);
    }

    private long tilNextMillis(final long lastTimestamp) {
        long timestamp = this.timeGen();

        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }

        return timestamp;
    }

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

}

 

py3实现

# -*- coding: utf-8 -*-
import time

WORKER_ID_BITS = 10
MAX_WORK_ID = -1^(-1<<WORKER_ID_BITS)
SEQUENCE_BITS = 12
MAX_SEQUENCE = -1^(-1<<SEQUENCE_BITS)

TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS+WORKER_ID_BITS
WORKER_ID_SHIFT = SEQUENCE_BITS

class Snowflake(object):
    def __init__(self,workerId):
        self.workerId = workerId
        self.sequence = 0
        self.lastTimestamp = -1
        self.since = 0

    def nextId(self):
        timestamp = self._timestamp()
        if self.lastTimestamp == timestamp:
            self.sequence = (self.sequence + 1) & MAX_SEQUENCE
            if self.sequence == 0:
                timestamp = self._tilNextMillis()
        else:
            self.sequence = 0

        self.lastTimestamp = timestamp

        return (timestamp - self.since) << TIMESTAMP_LEFT_SHIFT | self.workerId << WORKER_ID_SHIFT | self.sequence

    def _timestamp(self):
        return int(round(time.time()*1000))

    def _tilNextMillis(self):
        timestamp=self._timestamp()
        while timestamp<self.lastTimestamp:
            timestamp = self._timestamp()

        return timestamp

 

参考:

1. https://github.com/twitter/snowflake

2. http://www.cnblogs.com/relucent/p/4955340.html

3.http://www.lanindex.com/twitter-snowflake%EF%BC%8C64%E4%BD%8D%E8%87%AA%E5%A2%9Eid%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/

© 著作权归作者所有

共有 人打赏支持
保护单身狗协会理事长
粉丝 20
博文 27
码字总数 10638
作品 0
杭州
程序员
私信 提问
李景枫/sequence

分布式高效ID生产黑科技(sequence) 开源产品介绍(微服务基础设施QQ交流群:191958521) 配置中心(mconf) GITHUB:https://github.com/yu120/mconf 码云:https://git.oschina.net/yu120/mco...

李景枫
2016/07/08
0
0
分布式高效有序 ID 生产--dsequence

高性能(理论QPS > 400w/s)GUID产生算法(sequence),基于Snowflake实现64位自增ID算法。 Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分...

李景枫
2017/04/27
287
0
Twitter的分布式自增ID算法snowflake (Java版)

结构 snowflake的结构如下(每部分用-分开): 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 第一位为未使用,接下来的41位为毫秒级时间(41位的长度可以...

liangxiao
2017/07/04
0
0
对新UUID算法的说明

原来的算法产生36位的字符串类型的UUID,当数据量比较大时有很大可能会成为性能瓶颈。另外算法本身完全基于时间产生的随机数,还是有小概率生成不唯一的ID。基于以上两点原因,我又搜索了一下...

sieg
2015/03/01
4
3
Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版

在分布式系统中,需要生成全局UID的场合还是比较多的,twitter的snowflake解决了这种需求,实现也还是很简单的,除去配置信息,核心代码就是毫秒级时间41位+机器ID 10位+毫秒内序列12位。 该...

真爱2015
2016/05/18
225
0

没有更多内容

加载失败,请刷新页面

加载更多

安卓代码混淆

Proguard是安卓提供的方便开发者对代码和apk进行保护和精简的工具,可在SDK/tools文件夹下找到。 proguard的作用 : 1,代码混淆 2,精简代码,删掉没有用到的代码,减小apk的体积。 使用场景...

whoisliang
13分钟前
0
0
配置Tomcat虚拟主机

12月13日任务 16.4 配置Tomcat监听80端口 16.5/16.6/16.7 配置Tomcat虚拟主机 16.8 Tomcat日志 配置tomcat监听80端口 默认tomcat监听的是8080端口,如果想直接输入ip就访问到网页,就需要进行...

robertt15
19分钟前
1
0
emqtt Qos 0, 1, 2 图解

SimonAt
19分钟前
0
0
基于vue2定义自己的图表echart组件

先安装echarts cnpm i echarts -S,然后定义父组件 <template> <div> <echarts :option="echartOpion"></echarts> </div></template><script> import echarts from './e......

莫沫达
26分钟前
3
0
详解CSS的Flex布局

本文由云+社区发表 Flex是Flexible Box 的缩写,意为"弹性布局",是CSS3的一种布局模式。通过Flex布局,可以很优雅地解决很多CSS布局的问题。下面会分别介绍容器的6个属性和项目的6个属性。每...

腾讯云加社区
38分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部