Thuật toán Snowflake trong Java

Chúng tôi thường sử dụng MySQL để lưu trữ hầu hết dữ liệu trực tuyến của mình. Lúc đầu, dữ liệu nằm trong một cá thể cơ sở dữ liệu nhỏ, sau đó trở thành một cá thể cơ sở dữ liệu lớn và cuối cùng là nhiều cụm cơ sở dữ liệu lớn. Vì nhiều lý do khác nhau, chi tiết nào xứng đáng với toàn bộ bài đăng trên blog, chúng tôi đang làm việc để thay thế nhiều hệ thống này bằng cơ sở dữ liệu phân tán Cassandra hoặc MySQL được phân đoạn theo chiều ngang (sử dụng gizzard).

Yêu cầu của chúng tôi đối với hệ thống này khá đơn giản nhưng vẫn đòi hỏi:

• Chúng tôi cần thứ gì đó có thể tạo ra hàng chục nghìn id mỗi giây theo cách có tính khả dụng cao. Điều này tự nhiên khiến chúng tôi chọn một cách tiếp cận không phối hợp.
• Các id này gần như có thể sắp xếp được, nghĩa là nếu các bài A và B được đăng cùng lúc, chúng phải có các id gần nhau.
• Ngoài ra, những con số này phải vừa với 64 bit. Trước đây, chúng tôi đã trải qua một quá trình khó khăn để tăng số lượng bit được sử dụng để lưu trữ id post. Điều đó không có gì đáng ngạc nhiên khi bạn có hơn 100.000 cơ sở mã khác nhau tham gia.

Tùy chọn

Chúng tôi đã xem xét một số cách tiếp cận: Máy chủ bán vé dựa trên MySQL (như sử dụng flickr), nhưng những cách đó không mang lại cho chúng tôi sự đảm bảo về thứ tự mà chúng tôi cần nếu không xây dựng một số loại quy trình đồng bộ hóa lại. Chúng tôi cũng đã xem xét các UUID khác nhau, nhưng tất cả các lược đồ mà chúng tôi có thể tìm thấy đều yêu cầu 128 bit. Sau đó, chúng tôi đã xem xét các nút tuần tự của Zookeeper, nhưng không thể có được các đặc tính hiệu suất mà chúng tôi cần và chúng tôi sợ rằng cách tiếp cận phối hợp sẽ làm giảm tính khả dụng của chúng tôi mà không có lợi nhuận thực sự.

UUID

UUID là số thập lục phân 128 bit là bộ tạo số không trùng trên toàn cầu. Cơ hội của trùng UUID được tạo hai lần là không đáng kể.

Vấn đề với UUID là chúng có kích thước rất lớn và không được lập chỉ mục tốt. Khi tập dữ liệu của bạn tăng lên, kích thước chỉ mục cũng tăng và hiệu suất truy vấn sẽ giảm.

MongoDB ObjectId

Các ObjectID của MongoDB là các số thập lục phân 12 byte (96 bit). Nó nhỏ hơn UUID 128 bit trước đó. Nhưng một lần nữa kích thước tương đối dài hơn những gì chúng ta thường có trong một trường tăng tự động MySQL ID duy nhất (giá trị bigint 64-bit).

Snowflake

Snowflake là một dịch vụ mạng chuyên dụng để tạo ID duy nhất 64-bit ở quy mô lớn. Chỉ 63 bit được sử dụng để vừa với số nguyên có dấu. 41 bit đầu tiền là thời gian Unix với độ chính xác mili giây bắt đầu từ lúc thời gian đã tạo. 10 bit tiếp theo đại diện cho một ID máy, ngăn chặn xung đột. 12 bit nữa đại diện cho số thứ tự của mỗi máy, để cho phép tạo ra nhiều ID trong cùng một phần nghìn giây.

Các ID được tạo bởi snowflake phù hợp với 64 bit và có thể sắp xếp theo thời gian vì chúng dựa trên thời gian chúng được tạo ra.

Các microservices có thể sử dụng Trình tạo trình tự này để tạo ID một cách độc lập.

Giải pháp

package com.nth.snowflake;

import java.net.NetworkInterface;

import java.security.SecureRandom;

import java.time.Instant;

import java.util.Enumeration;

/**

 * Distributed Sequence Generator.

 * This class should be used as a Singleton.

 * Make sure that you create and reuse a Single instance of Snowflake per node in your distributed system cluster.

 */

public class Snowflake {

    private static final int UNUSED_BITS = 1; // Sign bit, Unused (always set to 0)

    private static final int EPOCH_BITS = 41;

    private static final int NODE_ID_BITS = 10;

    private static final int SEQUENCE_BITS = 12;

    private static final long maxNodeId = (1L << NODE_ID_BITS) - 1;

    private static final long maxSequence = (1L << SEQUENCE_BITS) - 1;

    // Custom Epoch (January 1, 2015 Midnight UTC = 2015-01-01T00:00:00Z)

    private static final long DEFAULT_CUSTOM_EPOCH = 1420070400000L;

    private final long nodeId;

    private final long customEpoch;

    private volatile long lastTimestamp = -1L;

    private volatile long sequence = 0L;

    // Create Snowflake with a nodeId and custom epoch

    public Snowflake(long nodeId, long customEpoch) {

        if(nodeId < 0 || nodeId > maxNodeId) {

            throw new IllegalArgumentException(String.format("NodeId must be between %d and %d", 0, maxNodeId));

        }

        this.nodeId = nodeId;

        this.customEpoch = customEpoch;

    }

    // Create Snowflake with a nodeId

    public Snowflake(long nodeId) {

        this(nodeId, DEFAULT_CUSTOM_EPOCH);

    }

    // Let Snowflake generate a nodeId

    public Snowflake() {

        this.nodeId = createNodeId();

        this.customEpoch = DEFAULT_CUSTOM_EPOCH;

    }

    public synchronized long nextId() {

        long currentTimestamp = timestamp();

        if(currentTimestamp < lastTimestamp) {

            throw new IllegalStateException("Invalid System Clock!");

        }

        if (currentTimestamp == lastTimestamp) {

            sequence = (sequence + 1) & maxSequence;

            if(sequence == 0) {

                // Sequence Exhausted, wait till next millisecond.

                currentTimestamp = waitNextMillis(currentTimestamp);

            }

        } else {

            // reset sequence to start with zero for the next millisecond

            sequence = 0;

        }

        lastTimestamp = currentTimestamp;

        long id = currentTimestamp << (NODE_ID_BITS + SEQUENCE_BITS)

                | (nodeId << SEQUENCE_BITS)

                | sequence;

        return id;

    }

    // Get current timestamp in milliseconds, adjust for the custom epoch.

    private long timestamp() {

        return Instant.now().toEpochMilli() - customEpoch;

    }

    // Block and wait till next millisecond

    private long waitNextMillis(long currentTimestamp) {

        while (currentTimestamp == lastTimestamp) {

            currentTimestamp = timestamp();

        }

        return currentTimestamp;

    }

    private long createNodeId() {

        long nodeId;

        try {

            StringBuilder sb = new StringBuilder();

            Enumeration<NetworkInterface> networkInterfaces = NetworkInterface.getNetworkInterfaces();

            while (networkInterfaces.hasMoreElements()) {

                NetworkInterface networkInterface = networkInterfaces.nextElement();

                byte[] mac = networkInterface.getHardwareAddress();

                if (mac != null) {

                    for(byte macPort: mac) {

                        sb.append(String.format("%02X", macPort));

                    }

                }

            }

            nodeId = sb.toString().hashCode();

        } catch (Exception ex) {

            nodeId = (new SecureRandom().nextInt());

        }

        nodeId = nodeId & maxNodeId;

        return nodeId;

    }

    public long[] parse(long id) {

        long maskNodeId = ((1L << NODE_ID_BITS) - 1) << SEQUENCE_BITS;

        long maskSequence = (1L << SEQUENCE_BITS) - 1;

        long timestamp = (id >> (NODE_ID_BITS + SEQUENCE_BITS)) + customEpoch;

        long nodeId = (id & maskNodeId) >> SEQUENCE_BITS;

        long sequence = id & maskSequence;

        return new long[]{timestamp, nodeId, sequence};

    }

    @Override

    public String toString() {

        return "Snowflake Settings [EPOCH_BITS=" + EPOCH_BITS + ", NODE_ID_BITS=" + NODE_ID_BITS

                + ", SEQUENCE_BITS=" + SEQUENCE_BITS + ", CUSTOM_EPOCH=" + customEpoch

                + ", NodeId=" + nodeId + "]";

    }

}