分布式ID生成策略

一、分布式ID概述

分布式ID是分布式系统中唯一标识数据的关键，在数据密集型应用中，需要生成全局唯一、有序、高性能的ID。分布式ID生成策略直接影响系统的可用性和数据一致性。

二、ID生成策略对比

2.1 ID生成策略对比

2.2 Snowflake算法结构

三、Snowflake算法实现

3.1 Snowflake算法实现

public class SnowflakeIdGenerator
{
    private readonly long _epoch = 1609459200000L;
    private readonly long _machineId;
    private readonly long _dataCenterId;
    private long _sequence = 0L;
    private long _lastTimestamp = -1L;
    private readonly object _lock = new();
    
    private const long MachineIdBits = 5L;
    private const long DataCenterIdBits = 5L;
    private const long SequenceBits = 12L;
    
    private const long MaxMachineId = -1L ^ (-1L << (int)MachineIdBits);
    private const long MaxDataCenterId = -1L ^ (-1L << (int)DataCenterIdBits);
    
    private const long MachineIdShift = SequenceBits;
    private const long DataCenterIdShift = SequenceBits + MachineIdBits;
    private const long TimestampLeftShift = SequenceBits + MachineIdBits + DataCenterIdBits;
    private const long SequenceMask = -1L ^ (-1L << (int)SequenceBits);
    
    public SnowflakeIdGenerator(long machineId, long dataCenterId)
    {
        if (machineId > MaxMachineId || machineId < 0)
        {
            throw new ArgumentException($"MachineId must be between 0 and {MaxMachineId}");
        }
        
        if (dataCenterId > MaxDataCenterId || dataCenterId < 0)
        {
            throw new ArgumentException($"DataCenterId must be between 0 and {MaxDataCenterId}");
        }
        
        _machineId = machineId;
        _dataCenterId = dataCenterId;
    }
    
    public long GenerateId()
    {
        lock (_lock)
        {
            var timestamp = GetCurrentTimestamp();
            
            if (timestamp < _lastTimestamp)
            {
                throw new InvalidOperationException("时钟回退");
            }
            
            if (timestamp == _lastTimestamp)
            {
                _sequence = (_sequence + 1) & SequenceMask;
                
                if (_sequence == 0)
                {
                    timestamp = WaitNextMillis(_lastTimestamp);
                }
            }
            else
            {
                _sequence = 0L;
            }
            
            _lastTimestamp = timestamp;
            
            return ((timestamp - _epoch) << (int)TimestampLeftShift) |
                   (_dataCenterId << (int)DataCenterIdShift) |
                   (_machineId << (int)MachineIdShift) |
                   _sequence;
        }
    }
    
    private long GetCurrentTimestamp()
    {
        return DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
    }
    
    private long WaitNextMillis(long lastTimestamp)
    {
        var timestamp = GetCurrentTimestamp();
        
        while (timestamp <= lastTimestamp)
        {
            timestamp = GetCurrentTimestamp();
        }
        
        return timestamp;
    }
    
    public (long Timestamp, long DataCenterId, long MachineId, long Sequence) ParseId(long id)
    {
        var timestamp = (id >> (int)TimestampLeftShift) + _epoch;
        var dataCenterId = (id >> (int)DataCenterIdShift) & MaxDataCenterId;
        var machineId = (id >> (int)MachineIdShift) & MaxMachineId;
        var sequence = id & SequenceMask;
        
        return (timestamp, dataCenterId, machineId, sequence);
    }
}

3.2 时钟回退处理

public class ClockSafeSnowflakeGenerator : SnowflakeIdGenerator
{
    private readonly IClockMonitor _clockMonitor;
    private readonly TimeSpan _maxClockDrift = TimeSpan.FromSeconds(5);
    
    public ClockSafeSnowflakeGenerator(long machineId, long dataCenterId, IClockMonitor clockMonitor)
        : base(machineId, dataCenterId)
    {
        _clockMonitor = clockMonitor;
    }
    
    public new long GenerateId()
    {
        var lastTimestamp = GetLastTimestamp();
        var currentTimestamp = GetCurrentTimestamp();
        
        if (currentTimestamp < lastTimestamp)
        {
            var drift = lastTimestamp - currentTimestamp;
            
            if (drift > _maxClockDrift.TotalMilliseconds)
            {
                _clockMonitor.ReportClockDrift(drift);
                
                throw new ClockDriftException($"时钟回退超过 {_maxClockDrift.TotalSeconds} 秒");
            }
            
            Thread.Sleep((int)(lastTimestamp - currentTimestamp + 1));
        }
        
        return base.GenerateId();
    }
}

public interface IClockMonitor
{
    void ReportClockDrift(long driftMilliseconds);
    bool IsClockStable();
}

四、UUID优化

4.1 COMB UUID

public class CombUuidGenerator
{
    public Guid Generate()
    {
        var guid = Guid.NewGuid();
        var timestamp = DateTime.Now.Ticks;
        
        var guidBytes = guid.ToByteArray();
        var timestampBytes = BitConverter.GetBytes(timestamp);
        
        Array.Copy(timestampBytes, 2, guidBytes, 6, 6);
        
        return new Guid(guidBytes);
    }
    
    public Guid GenerateWithDateTime(DateTime dateTime)
    {
        var guid = Guid.NewGuid();
        var timestamp = dateTime.Ticks;
        
        var guidBytes = guid.ToByteArray();
        var timestampBytes = BitConverter.GetBytes(timestamp);
        
        Array.Copy(timestampBytes, 2, guidBytes, 6, 6);
        
        return new Guid(guidBytes);
    }
    
    public DateTime ExtractDateTime(Guid combGuid)
    {
        var guidBytes = combGuid.ToByteArray();
        var timestampBytes = new byte[8];
        
        Array.Copy(guidBytes, 6, timestampBytes, 2, 6);
        
        var timestamp = BitConverter.ToInt64(timestampBytes, 0);
        
        return new DateTime(timestamp);
    }
}

4.2 顺序UUID

public class SequentialUuidGenerator
{
    private readonly object _lock = new();
    private long _lastTimestamp = 0;
    private long _sequence = 0;
    
    public Guid Generate()
    {
        lock (_lock)
        {
            var timestamp = DateTime.UtcNow.Ticks;
            
            if (timestamp == _lastTimestamp)
            {
                _sequence++;
            }
            else
            {
                _sequence = 0;
                _lastTimestamp = timestamp;
            }
            
            var bytes = new byte[16];
            
            var timestampBytes = BitConverter.GetBytes(timestamp);
            Array.Copy(timestampBytes, bytes, 8);
            
            var sequenceBytes = BitConverter.GetBytes(_sequence);
            Array.Copy(sequenceBytes, 0, bytes, 8, 4);
            
            var randomBytes = Guid.NewGuid().ToByteArray();
            Array.Copy(randomBytes, 12, bytes, 12, 4);
            
            return new Guid(bytes);
        }
    }
    
    public string GenerateString()
    {
        return Generate().ToString("N");
    }
}

五、数据库分段ID

5.1 分段ID生成器

public class SegmentIdGenerator
{
    private readonly IDbConnectionFactory _dbConnectionFactory;
    private readonly string _tableName = "id_generator";
    private readonly Dictionary _segments = new();
    private readonly object _lock = new();
    private readonly int _segmentSize = 1000;
    
    public async Task GenerateIdAsync(string businessType)
    {
        if (!_segments.TryGetValue(businessType, out var segment))
        {
            segment = await FetchSegmentAsync(businessType);
            _segments[businessType] = segment;
        }
        
        if (segment.IsExhausted)
        {
            segment = await FetchSegmentAsync(businessType);
            _segments[businessType] = segment;
        }
        
        return segment.GetNextId();
    }
    
    private async Task FetchSegmentAsync(string businessType)
    {
        using var connection = _dbConnectionFactory.CreateConnection();
        await connection.OpenAsync();
        
        using var transaction = await connection.BeginTransactionAsync();
        
        var sql = $@"
            UPDATE {_tableName} 
            SET max_id = max_id + @SegmentSize 
            WHERE business_type = @BusinessType;
            
            SELECT max_id - @SegmentSize + 1 as start_id, max_id as end_id 
            FROM {_tableName} 
            WHERE business_type = @BusinessType;
        ";
        
        var parameters = new { BusinessType = businessType, SegmentSize = _segmentSize };
        
        var result = await connection.QueryFirstAsync(sql, parameters, transaction);
        
        await transaction.CommitAsync();
        
        return new Segment(result.StartId, result.EndId);
    }
    
    public async Task InitializeBusinessTypeAsync(string businessType, long initialValue = 1)
    {
        using var connection = _dbConnectionFactory.CreateConnection();
        await connection.OpenAsync();
        
        var sql = $@"
            INSERT INTO {_tableName} (business_type, max_id) 
            VALUES (@BusinessType, @InitialValue)
            ON DUPLICATE KEY UPDATE max_id = @InitialValue;
        ";
        
        await connection.ExecuteAsync(sql, new { BusinessType = businessType, InitialValue = initialValue });
    }
}

public class Segment
{
    private readonly long _startId;
    private readonly long _endId;
    private long _currentId;
    
    public Segment(long startId, long endId)
    {
        _startId = startId;
        _endId = endId;
        _currentId = startId - 1;
    }
    
    public bool IsExhausted => _currentId >= _endId;
    
    public long GetNextId()
    {
        if (IsExhausted)
        {
            throw new InvalidOperationException("分段已用尽");
        }
        
        return Interlocked.Increment(ref _currentId);
    }
    
    public long Remaining => _endId - _currentId;
}

public class SegmentRange
{
    public long StartId { get; set; }
    public long EndId { get; set; }
}

六、Redis自增ID

6.1 Redis自增ID生成器

public class RedisIdGenerator
{
    private readonly IDistributedCache _cache;
    private readonly string _prefix = "id:";
    private readonly long _defaultStep = 1;
    
    public async Task GenerateIdAsync(string businessType)
    {
        var key = $"{_prefix}{businessType}";
        
        var value = await _cache.StringIncrementAsync(key, _defaultStep);
        
        return value;
    }
    
    public async Task GenerateIdAsync(string businessType, long step)
    {
        var key = $"{_prefix}{businessType}";
        
        var value = await _cache.StringIncrementAsync(key, step);
        
        return value;
    }
    
    public async Task GetCurrentValueAsync(string businessType)
    {
        var key = $"{_prefix}{businessType}";
        
        var value = await _cache.GetStringAsync(key);
        
        return string.IsNullOrEmpty(value) ? 0 : long.Parse(value);
    }
    
    public async Task InitializeAsync(string businessType, long initialValue)
    {
        var key = $"{_prefix}{businessType}";
        
        var exists = await _cache.StringSetAsync(key, initialValue.ToString(), 
            new DistributedCacheEntryOptions(), 
            new DistributedCacheEntryOptions());
        
        return initialValue;
    }
    
    public async Task> GenerateBatchAsync(string businessType, int count)
    {
        var ids = new List();
        
        for (int i = 0; i < count; i++)
        {
            ids.Add(await GenerateIdAsync(businessType));
        }
        
        return ids;
    }
}

七、ID碰撞解决方案

7.1 ID碰撞检测

public class IdCollisionDetector
{
    private readonly HashSet _generatedIds = new();
    private readonly object _lock = new();
    
    public bool IsCollision(long id)
    {
        lock (_lock)
        {
            if (_generatedIds.Contains(id))
            {
                return true;
            }
            
            _generatedIds.Add(id);
            
            if (_generatedIds.Count > 1000000)
            {
                _generatedIds.Clear();
            }
            
            return false;
        }
    }
    
    public async Task IsCollisionAsync(long id, string businessType)
    {
        var key = $"id:collision:{businessType}:{id}";
        
        var exists = await _cache.StringGetAsync(key);
        
        if (exists.HasValue)
        {
            return true;
        }
        
        await _cache.StringSetAsync(key, "1", TimeSpan.FromHours(24));
        
        return false;
    }
    
    public async Task RegisterIdAsync(long id, string businessType)
    {
        var key = $"id:collision:{businessType}:{id}";
        
        await _cache.StringSetAsync(key, "1", TimeSpan.FromHours(24));
    }
}

7.2 ID生成策略选择

7.3 ID生成最佳实践

• 选择合适的ID生成策略
• 考虑ID的有序性
• 处理时钟回退问题
• 避免ID碰撞
• 监控ID生成性能

八、总结

分布式ID生成是分布式系统的基础问题。通过选择合适的ID生成策略（Snowflake、UUID、数据库自增、Redis自增、分段ID），能够满足不同场景的需求。Snowflake算法是高并发场景的首选，具有高性能和有序性的特点。UUID适合不需要有序性的场景。分段ID通过批量获取减少数据库压力。遵循ID生成最佳实践，能够构建稳定可靠的ID生成系统。