溫馨提示×

Snowflake算法原理及C#實現(xiàn)

c#
小樊
82
2024-09-02 12:41:56
欄目: 編程語言

Snowflake 是 Twitter 開源的一個分布式 ID 生成算法，用于在分布式系統(tǒng)中生成唯一、有序、不重復的 ID。它的設(shè)計目標是在不依賴數(shù)據(jù)庫或其他存儲設(shè)備的情況下生成全局唯一 ID。

Snowflake 算法的原理如下：

  1. 使用 64 位整數(shù)表示 ID，分為以下幾部分：

    • 1 位符號位：始終為 0，表示正數(shù)。
    • 41 位時間戳：表示當前時間與某個固定時間點（如：2021-01-01 00:00:00）的差值，單位是毫秒。這部分可以表示約 69 年的時間。
    • 10 位工作機器 ID：可以分為 5 位數(shù)據(jù)中心 ID 和 5 位工作節(jié)點 ID，用于標識不同的數(shù)據(jù)中心和工作節(jié)點，最多可以支持 1024 個節(jié)點。
    • 12 位序列號：在同一毫秒內(nèi)，同一個工作節(jié)點可以生成的不同 ID 的數(shù)量，最多可以生成 4096 個。

  2. 算法流程：

    • 首先，根據(jù)當前時間計算出時間戳，并將其左移 22 位，得到高 41 位。
    • 然后，將工作機器 ID 左移 12 位，得到中 10 位。
    • 最后，將序列號加 1，得到低 12 位。
    • 將高 41 位、中 10 位和低 12 位拼接起來，得到一個 64 位的整數(shù)，即為生成的全局唯一 ID。

下面是一個簡單的 C# 實現(xiàn)：

public class Snowflake
{
    private const long Twepoch = 1609459200000L; // 2021-01-01 00:00:00
    private const int WorkerIdBits = 5;
    private const int DatacenterIdBits = 5;
    private const int SequenceBits = 12;
    private const long MaxWorkerId = -1L ^ (-1L<< WorkerIdBits);
    private const long MaxDatacenterId = -1L ^ (-1L<< DatacenterIdBits);
    private const int WorkerIdShift = SequenceBits;
    private const int DatacenterIdShift = SequenceBits + WorkerIdBits;
    private const int TimestampLeftShift = SequenceBits + WorkerIdBits + DatacenterIdBits;
    private const long SequenceMask = -1L ^ (-1L << SequenceBits);

    private readonly object _lock = new object();
    private long _sequence;
    private long _lastTimestamp;

    public Snowflake(long workerId, long datacenterId)
    {
        if (workerId > MaxWorkerId || workerId < 0)
            throw new ArgumentException($"Worker Id must be between 0 and {MaxWorkerId}");
        if (datacenterId > MaxDatacenterId || datacenterId < 0)
            throw new ArgumentException($"Datacenter Id must be between 0 and {MaxDatacenterId}");

        WorkerId = workerId;
        DatacenterId = datacenterId;
    }

    public long WorkerId { get; }
    public long DatacenterId { get; }

    public long NextId()
    {
        lock (_lock)
        {
            var timestamp = GetCurrentTimestamp();
            if (timestamp < _lastTimestamp)
                throw new Exception("Invalid system clock");

            if (_lastTimestamp == timestamp)
            {
                _sequence = (_sequence + 1) & SequenceMask;
                if (_sequence == 0)
                    timestamp = WaitNextMillis(_lastTimestamp);
            }
            else
            {
                _sequence = 0;
            }

            _lastTimestamp = timestamp;
            return ((timestamp - Twepoch)<< TimestampLeftShift) |
                   (DatacenterId<< DatacenterIdShift) |
                   (WorkerId<< WorkerIdShift) |
                   _sequence;
        }
    }

    private long GetCurrentTimestamp()
    {
        return (long)(DateTime.UtcNow - new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc)).TotalMilliseconds;
    }

    private long WaitNextMillis(long lastTimestamp)
    {
        var timestamp = GetCurrentTimestamp();
        while (timestamp <= lastTimestamp)
        {
            timestamp = GetCurrentTimestamp();
        }
        return timestamp;
    }
}

使用示例：

var snowflake = new Snowflake(1, 1);
var id = snowflake.NextId();
Console.WriteLine(id);

這個實現(xiàn)是線程安全的，但在高并發(fā)場景下可能會有性能瓶頸。在實際應(yīng)用中，可以根據(jù)需要對其進行優(yōu)化。

0 踩