文档章节

Twitter-Snowflake 64位自增ID简介

保护单身狗协会理事长_退休
 保护单身狗协会理事长_退休
发布于 2017/09/11 16:39
字数 806
阅读 282
收藏 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 final 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 SimpleDateFormat format = new SimpleDateFormat("yyyyMMddHHmmssSSS");

    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(2017, Calendar.NOVEMBER, 3, 0, 0, 0);

        this.since = calendar.getTimeInMillis();
    }

    public synchronized Long nextId() {
        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 RuntimeException(
                    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);
    }


    /**
     * 生成
     * prefix 长度最多3个字符
     * 返回的字符串长度最多26个字符
     *
     * @param prefix
     * @return
     */
    public synchronized String nextSerialNumber(String prefix) {
        prefix = StringUtils.trimToEmpty(prefix);

        if (prefix.length() > 3) throw new BusinessException("prefix长度不能大于3", Error.ILLEGAL_ARGUMENT);

        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 RuntimeException(
                    String.format(
                            "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                            this.lastTimestamp - timestamp));
        }

        this.lastTimestamp = timestamp;

        String time = format.format(new Date());

        return String.format("%s%s%s%6d", prefix, time, workerId, 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/

© 著作权归作者所有

保护单身狗协会理事长_退休
粉丝 21
博文 27
码字总数 10748
作品 0
杭州
程序员
私信 提问
加载中

评论(0)

Twitter-Snowflake:自增ID算法

简介 Twitter 早期用 MySQL 存储数据,随着用户的增长,单一的 MySQL 实例没法承受海量的数据,后来团队就研究如何产生完美的自增ID,以满足两个基本的要求: 每秒能生成几十万条 ID 用于标识...

飞鸿影
2019/10/26
0
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 生成算法 - go-snowflake

:snowflake:️ GO-Snowflake Snowflake简介 在单机系统中我们会使用自增id作为数据的唯一id,自增id在数据库中有利于排序和索引,但是在分布式系统中如果还是利用数据库的自增id会引起冲突,...

GuaiK
01/14
669
2
数据库分库分表(一)常见分布式主键ID生成策略

主键生成策略   系统唯一ID是我们在设计一个系统的时候常常会遇见的问题,下面介绍一些常见的ID生成策略。 Sequence ID UUID GUID COMB Snowflake   最开始的自增ID为了实现分库分别的需...

osc_mo4m2o49
2018/09/10
9
0
Twitter的分布式自增ID算法snowflake(雪花算法) - C#版

概述 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一...

osc_nta49u19
2019/02/18
1
0

没有更多内容

加载失败,请刷新页面

加载更多

QT 执行shell命令

(1)首先包含头文件: #include <QProcess> (2)执行shell命令: QProcess::execute("ls");

悲催的古灵武士
7分钟前
9
0
osgEarth使用笔记3——加载倾斜摄影数据

目录 1. 概述 2. 详论 2.1. 位置 2.2. 着色 2.3. 其他 3. 结果 4. 参考 1. 概述 我在《OSG加载倾斜摄影数据》这篇博文中论述了如何通过OSG生成一个整体的索引文件,通过这个索引文件来正确显...

osc_7oc4d1en
8分钟前
11
0
cesium加载gltf模型点击以及列表点击定位弹窗

前言 cesium 官网的api文档介绍地址cesium官网api,里面详细的介绍 cesium 各个类的介绍,还有就是在线例子:cesium 官网在线例子,这个也是学习 cesium 的好素材。 之前有部分订阅者咨询我,...

osc_cx8uhydz
9分钟前
8
0
思维导图软件如何插入图片?具体步骤?

学习思维导图制作的过程中,会遇到很多没有学过的知识,需要我们不断地去改进和学习,这样增强自己的学习能力,才能更好地掌握制图软件。以后帮助我们快速方便地完成制图,今天我们就要来看看...

深蓝月上
9分钟前
10
0
Notepad++ 列块模式编辑,替换换行符

一、列块模式编辑: 1、数据准备 2、按住 “Alt + 鼠标左键” 选择需要列块模式编辑的区域,可以看到多了一条竖线 3、之后批量可以添加,修改内容 二、替换换行符 上面说了列块模式的编辑,后...

osc_itgved4p
10分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部