[转载]雪花算法简介

转载信息

作者：Jeffrey
发表时间：2019-10-09 22:05
原始链接：# 分布式ID神器之雪花算法简介

雪花算法这一在分布式架构中很常见的玩意，但一般也不需要怎么去深入了解，一方面一般个人项目用不到分布式之类的大型架构，另一方面，就算要用到，市面上很多ID生成器也帮我们完成了这项工作。

分布式 ID 的特点

全局唯一性：不能出现有重复的 ID 标识，这是基本要求。
递增性：确保生成 ID 对于用户或业务是递增的。
高可用性：确保任何时候都能生成正确的 ID
高性能：在高并发的环境下依然表现良好

分布式ID的常见解决方案

UUID

生成一串唯一随机 36 位字符串（32个字符串+4个“-”）的算法。它可以保证唯一性，但是其业务可读性差，无法有序递增。

SnowFlake

今天的主角雪花算法，它是 Twitter 开源的由 64 位整数组成分布式 ID，性能较高，并且在单机上递增。具体参考：twitter-archive/snowflake

UidGenerator

UidGenerator 是百度开源的分布式 ID 生成器，其基于雪花算法实现。具体参考：baidu/uid-generator

Leaf

Leaf 是美团开源的分布式 ID 生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper 等中间件。具体参考：Leaf——美团点评分布式ID生成系统

雪花算法的概要

SnowFlake 是 Twitter 公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的 ID。

组成部分（64bit）

第一位：占用 1 bit，其值始终是 0，没有实际作用
时间戳：占用 41 bit，精确到毫秒，总共可以容纳约 69 年的时间
工作机器id：占用 10 bit，其中高位 5 bit 是数据中心 ID，低位 5 bit 是工作节点 ID，最多可以容纳 1024 个节点。
序列号：占用 12 bit，每个节点每毫秒 0 开始不断累加，最多可以累加到 4095，一共可以产生 4096 个 ID。

SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一 ID 呢？ 同一毫秒的ID数量 = 1024 X 4096 = 4194304

雪花算法的实现

雪花算法的实现主要依赖于数据中心ID和数据节点ID这两个参数，具体实现如下。

Python 实现

# coding: utf-8
import time


class InvalidSystemClock(Exception):
    """
    时钟回拨异常
    """
    pass

# 64位ID的划分
WORKER_ID_BITS = 5
DATACENTER_ID_BITS = 5
SEQUENCE_BITS = 12

# 最大取值计算
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)  # 2**5-1 0b11111
MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS)

# 移位偏移计算
WOKER_ID_SHIFT = SEQUENCE_BITS
DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS

# 序号循环掩码
SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)

# 开始时间截 (2015-01-01)
TWEPOCH = 1420041600000


class IdWorker(object):
    """
    用于生成IDs
    """
    def __init__(self, datacenter_id, worker_id, sequence=0):
        """
        初始化
        :param datacenter_id: 数据中心（机器区域）ID
        :param worker_id: 机器ID
        :param sequence: 其实序号
        """
        # sanity check
        if worker_id > MAX_WORKER_ID or worker_id < 0:
            raise ValueError('worker_id值越界')

        if datacenter_id > MAX_DATACENTER_ID or datacenter_id < 0:
            raise ValueError('datacenter_id值越界')

        self.worker_id = worker_id
        self.datacenter_id = datacenter_id
        self.sequence = sequence

        self.last_timestamp = -1  # 上次计算的时间戳

    def _gen_timestamp(self):
        """
        生成整数时间戳
        :return:int timestamp
        """
        return int(time.time() * 1000)

    def get_id(self):
        """
        获取新ID
        :return:
        """
        timestamp = self._gen_timestamp()

        # 时钟回拨
        if timestamp < self.last_timestamp:
            raise InvalidSystemClock

        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & SEQUENCE_MASK
            if self.sequence == 0:
                timestamp = self._til_next_millis(self.last_timestamp)
        else:
            self.sequence = 0

        self.last_timestamp = timestamp

        new_id = ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | (self.datacenter_id << DATACENTER_ID_SHIFT) | \
                 (self.worker_id << WOKER_ID_SHIFT) | self.sequence
        return new_id

    def _til_next_millis(self, last_timestamp):
        """
        等到下一毫秒
        """
        timestamp = self._gen_timestamp()
        while timestamp <= last_timestamp:
            timestamp = self._gen_timestamp()
        return timestamp


if __name__ == '__main__':
    worker = IdWorker(0, 0)
    print(worker.get_id())

A/B

雪花算法