Thuật toán Snowflake trong Python

Tạo số nhận dạng duy nhất là một công việc mà tất cả các lập trình viên phải thực hiện tại một số thời điểm trong vòng đời phát triển của ứng dụng. Các ID duy nhất cho phép chúng tôi xác định đúng các đối tượng dữ liệu, duy trì chúng, truy xuất chúng và để chúng tham gia vào các mẫu quan hệ phức tạp.

Nhưng những ID duy nhất này được tạo ra như thế nào và cách tiếp cận nào hoạt động tốt nhất ở các quy mô tải khác nhau? Làm cách nào để ID vẫn duy nhất trong môi trường phân tán nơi nhiều máy tính cạnh tranh để được ID có sẵn tiếp theo?

Snowflake IDs, hoặc snowflakes, là một dạng mã định danh duy nhất được sử dụng trong máy tính phân tán. Định dạng này đã được các công ty bao gồm Discord, Twitter và Instagram phát triển với những phiên bản khác nhau.

Một ứng dụng gọi trình tạo ID để tạo ID mới. Ví dụ: một ứng dụng mạng xã hội gọi trình tạo ID để gán một ID duy nhất cho mỗi bài đăng.

Máy chủ ID đảm nhận việc tạo các ID duy nhất cho cơ sở hạ tầng phân tán của bạn. Theo việc triển khai máy chủ ID của bạn, nó có thể là một máy chủ duy nhất tạo Id hoặc một cụm máy chủ tạo ra số lượng ID cao mỗi giây.

Twitter với trung bình 9000 tweet mỗi giây và cao nhất là 143199 tweet mỗi giây, vì vậy cần một giải pháp không chỉ mở rộng trên cơ sở hạ tầng máy chủ rộng lớn của họ mà còn tạo ra các ID hiệu quả để lưu trữ.

Snowflake là một dịch vụ mạng để tạo số ID duy nhất ở quy mô cao với một số đảm bảo đơn giản.

Giải pháp

import time
import logging


log = logging.getLogger(__name__)


# Tue, 21 Mar 2006 20:50:14.000 GMT
twepoch = 1142974214000L

worker_id_bits = 5L
data_center_id_bits = 5L
max_worker_id = -1L ^ (-1L << worker_id_bits)
max_data_center_id = -1L ^ (-1L << data_center_id_bits)
sequence_bits = 12L
worker_id_shift = sequence_bits
data_center_id_shift = sequence_bits + worker_id_bits
timestamp_left_shift = sequence_bits + worker_id_bits + data_center_id_bits
sequence_mask = -1L ^ (-1L << sequence_bits)


def snowflake_to_timestamp(_id):
    _id = _id >> 22   # strip the lower 22 bits
    _id += twepoch    # adjust for twitter epoch
    _id = _id / 1000  # convert from milliseconds to seconds
    return _id


def generator(worker_id, data_center_id, sleep=lambda x: time.sleep(x/1000.0)):
    assert worker_id >= 0 and worker_id <= max_worker_id
    assert data_center_id >= 0 and data_center_id <= max_data_center_id

    last_timestamp = -1
    sequence = 0

    while True:
        timestamp = long(time.time()*1000)

        if last_timestamp > timestamp:
            log.warning(
                "clock is moving backwards. waiting until %i" % last_timestamp)
            sleep(last_timestamp-timestamp)
            continue

        if last_timestamp == timestamp:
            sequence = (sequence + 1) & sequence_mask
            if sequence == 0:
                log.warning("sequence overrun")
                sequence = -1 & sequence_mask
                sleep(1)
                continue
        else:
            sequence = 0

        last_timestamp = timestamp

        yield (
            ((timestamp-twepoch) << timestamp_left_shift) |
            (data_center_id << data_center_id_shift) |
            (worker_id << worker_id_shift) |
            sequence)

Sử dụng

    >>> import snowflake

    >>> s = snowflake.generator(1, 1)

    >>> s.next()

    1132805160360349696

    >>> s.next()

    1132805164143611904

    >>> s.next()

    1132805168782512128

    # convenience to convert a snowflake to a unix timestamp

    >>> snowflake.snowflake_to_timestamp(1132805168782512128)

    1413056012