🪴qql1's digital garden

雪花算法

6分钟阅读

梗概

雪花算法（Snowflake Algorithm）是一种用于生成唯一ID的算法，常用于分布式系统中。由Twitter开发，旨在为高并发环境下的数据生成全局唯一的ID。

主要特点如下：

  1. 结构化ID：雪花算法生成的ID通常是64位的整数，由多个部分组成，包括时间戳、机器ID、数据中心ID和序列号等。这种结构化的ID有助于保证唯一性和排序性。
  2. 高性能：算法设计考虑了高并发环境，能够在短时间内生成大量唯一ID。
  3. 时间排序：生成的ID按时间顺序递增，这使得数据在时间维度上可以进行排序。
  4. 容错性：通过包含机器ID和数据中心ID，可以在分布式环境中实现容错和负载均衡。
  5. 简单性：算法实现相对简单，并且不依赖于外部系统或服务，这降低了系统的复杂度。

结构

雪花算法的ID结构通常如下：

  • 1位：符号位（通常固定为0）
  • 41位：时间戳（毫秒级别，表示从一个特定的时间点开始的时间，通常为41位）
  • 10位：机器ID和数据中心ID（用于标识生成ID的机器和数据中心）
  • 12位：序列号（每毫秒内生成的ID序列号，用于处理同一时间内的多个ID生成） 这种设计使得雪花算法可以在分布式系统中有效地生成唯一的ID，同时保证高性能和高可用性。

示例

在实际应用中，雪花算法被广泛用于生成唯一的ID。例如，它在以下场景中很有用：

  1. 分布式系统中的唯一标识符：
    • 在分布式数据库或微服务架构中，雪花算法生成的唯一ID可以用作记录的主键，确保在不同节点和服务之间的唯一性。
  2. 高并发应用中的订单号：
    • 电商平台常用雪花算法生成订单号，以确保每个订单都能获得一个唯一且按时间排序的ID。
  3. 日志记录和追踪：
    • 在大规模分布式系统中，雪花算法生成的ID可以用于唯一标识日志条目或追踪请求，以方便问题排查和分析。

实际应用示例

假设你在开发一个电商平台，需要为用户生成唯一的订单号。你可以使用雪花算法来生成这些订单号。以下是一个实际应用的例子，展示如何集成雪花算法生成订单号。

示例代码（Python）

import time
import threading
# 雪花算法配置
EPOCH = 1609459200000  # 自定义起始时间戳
WORKER_ID_BITS = 5
DATACENTER_ID_BITS = 5
SEQUENCE_BITS = 12
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)
MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS)
SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)
WORKER_ID_SHIFT = SEQUENCE_BITS
DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS
class SnowflakeIDGenerator:
    def __init__(self, worker_id, datacenter_id):
        if worker_id > MAX_WORKER_ID or worker_id < 0:
            raise ValueError(f"Worker ID should be between 0 and {MAX_WORKER_ID}")
        if datacenter_id > MAX_DATACENTER_ID or datacenter_id < 0:
            raise ValueError(f"Datacenter ID should be between 0 and {MAX_DATACENTER_ID}")
        self.worker_id = worker_id
        self.datacenter_id = datacenter_id
        self.sequence = 0
        self.last_timestamp = -1
        self.lock = threading.Lock()
    def _wait_for_next_timestamp(self, last_timestamp):
        timestamp = self._current_timestamp()
        while timestamp <= last_timestamp:
            timestamp = self._current_timestamp()
        return timestamp
    def _current_timestamp(self):
        return int(time.time() * 1000)
    def generate_id(self):
        with self.lock:
            timestamp = self._current_timestamp()
            if timestamp < self.last_timestamp:
                raise RuntimeError("Clock moved backwards. Refusing to generate id")
            if timestamp == self.last_timestamp:
                self.sequence = (self.sequence + 1) & SEQUENCE_MASK
                if self.sequence == 0:
                    timestamp = self._wait_for_next_timestamp(self.last_timestamp)
            else:
                self.sequence = 0
            self.last_timestamp = timestamp
            id = ((timestamp - EPOCH) << TIMESTAMP_SHIFT) | (self.datacenter_id << DATACENTER_ID_SHIFT) | (self.worker_id << WORKER_ID_SHIFT) | self.sequence
            return id
# 示例：为电商平台生成订单号
class OrderService:
    def __init__(self, worker_id, datacenter_id):
        self.id_generator = SnowflakeIDGenerator(worker_id, datacenter_id)
    def create_order(self, order_details):
        order_id = self.id_generator.generate_id()
        # 假设将订单信息存入数据库
        print(f"Creating order with ID: {order_id}")
        # 这里可以添加更多业务逻辑，如保存订单详情
        return order_id
# 使用示例
order_service = OrderService(worker_id=1, datacenter_id=1)
order_id = order_service.create_order({"product_id": 123, "quantity": 2})
print(f"Generated Order ID: {order_id}")

解释：

  • SnowflakeIDGenerator：实现了雪花算法，用于生成唯一ID。
  • OrderService：模拟电商平台的订单服务，利用SnowflakeIDGenerator生成唯一的订单号。
  • create_order：创建订单并生成唯一ID，实际业务中可能会将订单信息保存到数据库中。 通过这种方式，你可以确保每个订单都有一个唯一且按时间排序的ID，这对于高并发环境中的数据管理至关重要。

关系图谱

反向链接