Skip to content

Instantly share code, notes, and snippets.

@jacking75
Last active April 3, 2025 06:47
Show Gist options
  • Save jacking75/5fa1e9178c866a8c26af4480f1503528 to your computer and use it in GitHub Desktop.
Save jacking75/5fa1e9178c866a8c26af4480f1503528 to your computer and use it in GitHub Desktop.
Randflake ID C# 버전

설명

출처: https://news.hada.io/topic?id=18189
Introducing Randflake ID: a distributed, uniform, unpredictable, unique random ID generator
Randflake ID는 분산 환경에서 사용할 수 있는 64비트 고유 식별자 생성 시스템이다.

주요 특징

  • 예측 불가능성: 블록 암호를 사용하여 다음/이전 ID 예측이 불가능
  • 고유성 보장: 타임스탬프, 노드 ID, 시퀀스 번호를 조합
  • 분산 환경 지원: 최대 131,072개의 노드 지원
  • 높은 처리량: 초당 최대 17,179,869,184개의 ID 생성 가능

구조

  • 타임스탬프: 30비트
  • 노드 ID: 17비트
  • 시퀀스: 17비트

장점

  • 데이터베이스 조회 없이 고유 ID 생성
  • 균일한 분포로 샤딩 키로 활용 가능
  • 내부 추적 기능 제공 (비밀키 보유자에 한정)

활용

  • 임대 기반의 노드 ID 조정 메커니즘을 통해 분산 시스템에서 효율적으로 운영 가능하며, 글로벌 규모의 애플리케이션에서 활용하기에 적합다.
using System;
using System.Threading;
namespace Randflake
{
public class Generator
{
private const long RANDFLAKE_EPOCH_OFFSET = 1730000000; // Sunday, October 27, 2024 3:33:20 AM UTC
private const int RANDFLAKE_TIMESTAMP_BITS = 30; // 30 bits for timestamp (lifetime of 34 years)
private const int RANDFLAKE_NODE_BITS = 17; // 17 bits for node id (max 131072 nodes)
private const int RANDFLAKE_SEQUENCE_BITS = 17; // 17 bits for sequence (max 131072 sequences)
private const long RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1L << RANDFLAKE_TIMESTAMP_BITS) - 1;
private const long RANDFLAKE_MAX_NODE = (1L << RANDFLAKE_NODE_BITS) - 1;
private const long RANDFLAKE_MAX_SEQUENCE = (1L << RANDFLAKE_SEQUENCE_BITS) - 1;
private readonly long _leaseStart;
private long _leaseEnd;
private readonly long _nodeId;
private long _sequence;
private long _rollover;
private readonly Sparx64 _sbox;
private readonly Func<long> _timeSource;
public Generator(long nodeId, long leaseStart, long leaseEnd, byte[] secret, Func<long> timeSource = null)
{
if (leaseEnd < leaseStart)
throw new ArgumentException("Invalid lease, lease expired or not started yet");
if (nodeId < 0 || nodeId > RANDFLAKE_MAX_NODE)
throw new ArgumentException("Invalid node id, node id must be between 0 and 131071");
if (leaseStart < RANDFLAKE_EPOCH_OFFSET)
throw new ArgumentException("Invalid lease, lease expired or not started yet");
if (leaseEnd > RANDFLAKE_MAX_TIMESTAMP)
throw new ArgumentException("Randflake is dead after 34 years of lifetime");
if (secret == null || secret.Length != 16)
throw new ArgumentException("Invalid secret, secret must be 16 bytes long");
_leaseStart = leaseStart;
_leaseEnd = leaseEnd;
_nodeId = nodeId;
_sequence = 0;
_rollover = leaseStart;
_sbox = new Sparx64(secret);
_timeSource = timeSource ?? (() => DateTimeOffset.UtcNow.ToUnixTimeSeconds());
}
public bool UpdateLease(long leaseStart, long leaseEnd)
{
if (leaseStart != _leaseStart)
return false;
if (leaseEnd < leaseStart)
return false;
if (leaseEnd > RANDFLAKE_MAX_TIMESTAMP)
return false;
var current = Interlocked.Read(ref _leaseEnd);
if (current < leaseEnd)
{
return Interlocked.CompareExchange(ref _leaseEnd, leaseEnd, current) == current;
}
return false;
}
private long NewRaw()
{
while (true)
{
var now = _timeSource();
if (now < _leaseStart)
throw new InvalidOperationException("Invalid lease, lease expired or not started yet");
if (now > Interlocked.Read(ref _leaseEnd))
throw new InvalidOperationException("Invalid lease, lease expired or not started yet");
var ctr = Interlocked.Increment(ref _sequence) - 1;
if (ctr > RANDFLAKE_MAX_SEQUENCE)
{
var lastRollover = Interlocked.Read(ref _rollover);
if (now > lastRollover)
{
if (Interlocked.CompareExchange(ref _rollover, now, lastRollover) != lastRollover)
continue;
Interlocked.Exchange(ref _sequence, 0);
ctr = 0;
}
else
{
if (now < lastRollover)
throw new InvalidOperationException("Timestamp consistency violation");
throw new InvalidOperationException("Resource exhausted");
}
}
var timestamp = now - RANDFLAKE_EPOCH_OFFSET;
return ((timestamp << (RANDFLAKE_NODE_BITS + RANDFLAKE_SEQUENCE_BITS)) |
(_nodeId << RANDFLAKE_SEQUENCE_BITS) |
ctr);
}
}
public long Generate()
{
var id = NewRaw();
var bytes = BitConverter.GetBytes(id);
var encryptedBytes = _sbox.Encrypt(bytes);
return BitConverter.ToInt64(encryptedBytes, 0);
}
public (long timestamp, long nodeId, long sequence) Inspect(long id)
{
var bytes = BitConverter.GetBytes(id);
// Decrypt 결과를 새로운 변수에 할당받아야 합니다.
var decryptedBytes = _sbox.Decrypt(bytes);
// 복호화된 바이트 배열을 사용하여 long 값을 만듭니다.
id = BitConverter.ToInt64(decryptedBytes, 0);
// 이 검사는 원본 ID 구조상 음수가 나올 수 있는 후반부 타임스탬프에서 발생할 수 있으나,
// "Invalid lease" 메시지는 오해의 소지가 있습니다.
// 이 검사의 의도를 명확히 하거나 제거하는 것을 고려해볼 수 있습니다.
if (id < 0)
{
throw new InvalidOperationException("Decrypted ID resulted in negative value, potentially invalid structure"); // 메시지 변경 제안
}
var timestamp = (id >> (RANDFLAKE_NODE_BITS + RANDFLAKE_SEQUENCE_BITS)) + RANDFLAKE_EPOCH_OFFSET;
var nodeId = (id >> RANDFLAKE_SEQUENCE_BITS) & RANDFLAKE_MAX_NODE;
var sequence = id & RANDFLAKE_MAX_SEQUENCE;
return (timestamp, nodeId, sequence);
}
}
}
/*
잠재적 문제 및 개선점:
1. Generator.Inspect의 if (id < 0) 검사:
- 원본 ID 구조(timestamp | nodeId | sequence)에서 timestamp 부분이 충분히 커지면 (대략 17년 후) 전체 long 값의 최상위 비트(부호 비트)가 1이 되어 음수가 될 수 있습니다.
- 현재 코드에서는 이 경우 "Invalid lease" 예외를 발생시키는데, 이는 ID 값 자체가 음수인 것과 Lease(임대 기간) 유효성은 직접적인 관련이 없으므로 오해의 소지가 있습니다. 복호화 후 구조적으로 예상치 못한 값이 나왔음을 알리는 더 명확한 메시지로 변경하거나, 이 검사가 꼭 필요한지 재검토하는 것이 좋습니다.
2. Generator.UpdateLease의 제약 조건:
- UpdateLease 메소드는 leaseStart 값이 기존 _leaseStart와 정확히 일치해야만 _leaseEnd를 갱신하도록 되어 있습니다. 이는 Lease 기간을 단순히 연장하는 시나리오만 지원합니다. 만약 Lease 시작 시간이 변경되는 경우(예: 갱신 시점 변경)를 지원해야 한다면 이 로직 수정이 필요합니다. 현재 설계가 의도된 것이라면 문제는 없습니다.
3.Sparx64의 비트 연산:
- KeySchedule, ARXBox, InverseARXBox 등에서 & 0xFFFFFFFF 연산은 C#의 uint 타입에서는 불필요합니다. uint는 이미 32비트 부호 없는 정수이므로 연산 결과가 자동으로 32비트로 제한됩니다. 코드를 간결하게 하기 위해 제거할 수 있습니다 (성능 영향은 거의 없음).
4.스레드 안전성:
- Generator 클래스는 Interlocked 연산을 사용하여 _sequence, _rollover, _leaseEnd 필드를 스레드 안전하게 관리하고 있습니다. 이 부분은 올바르게 구현된 것으로 보입니다.
- _nodeId와 _leaseStart는 readonly이므로 스레드 안전합니다.
- _sbox는 상태를 가지지 않고 입력에 따라 출력을 결정하므로(라운드 키는 생성자에서 고정됨), 여러 스레드에서 동시에 Encrypt/Decrypt를 호출해도 안전합니다.
5.Epoch 시간:
- 주석에 명시된 RANDFLAKE_EPOCH_OFFSET = 1730000000 (Sunday, October 27, 2024 3:33:20 AM UTC) 값은 Unix Timestamp로 올바르게 계산된 값입니다.
*/
/*
수명을 17년 이상, 나아가 34년 이상으로 늘리려면 다음과 같은 방법들을 고려해볼 수 있다.
**1. 비트 재할당 (가장 일반적인 방법)**
현재 64비트 구조(`타임스탬프(30) | 노드 ID(17) | 시퀀스(17)`)를 변경하여 타임스탬프에 더 많은 비트를 할당하는 방법입니다. 대신 노드 ID나 시퀀스 번호에 할당되는 비트 수는 줄어듭니다.
* **예시 1: 타임스탬프 32비트**
* 구조: `타임스탬프(32) | 노드 ID(16) | 시퀀스(16)` (총 64비트)
* **수명:** 2^32초 ≈ **약 136년** (부호 비트 문제는 약 68년 후 발생)
* 최대 노드 수: 2^16 = 65,536개
* 초당 최대 시퀀스 수 (노드 당): 2^16 = 65,536개
* **변경 필요:** `RANDFLAKE_TIMESTAMP_BITS`, `RANDFLAKE_NODE_BITS`, `RANDFLAKE_SEQUENCE_BITS` 상수 값 및 관련 `MAX` 값 수정.
* **예시 2: 타임스탬프 41비트 (Twitter Snowflake 방식과 유사)**
* 구조: `타임스탬프(41) | 노드 ID(10) | 시퀀스(12)` (총 63비트 사용, 최상위 비트는 0으로 유지하여 항상 양수)
* **수명:** 2^41 밀리초 ≈ **약 69.7년** (이 방식은 보통 밀리초 단위 타임스탬프를 사용)
* 최대 노드 수: 2^10 = 1,024개
* **밀리초당** 최대 시퀀스 수 (노드 당): 2^12 = 4,096개
* **변경 필요:**
* 상수 값 (`TIMESTAMP_BITS=41`, `NODE_BITS=10`, `SEQUENCE_BITS=12`) 수정.
* Epoch 및 `_timeSource`를 **밀리초(millisecond)** 단위로 변경 (`DateTimeOffset.UtcNow.ToUnixTimeMilliseconds()`).
* 타임스탬프 비트가 41개이므로 부호 비트 걱정 없이 69년 이상 사용 가능.
* **장점:** ID 크기(64비트)를 유지하면서 수명을 늘릴 수 있습니다.
* **단점:** 노드 수나 초당 생성 가능 ID 수가 줄어듭니다. 시스템 요구사항(필요한 노드 수, 초당 ID 생성량)과 원하는 수명 사이의 절충(trade-off)이 필요합니다.
**2. `ulong`으로 해석하여 부호 문제 회피 (수명 연장은 아님)**
ID 자체는 `long`으로 저장하되, ID를 해석하는 `Inspect` 메소드 등에서 비트 연산을 수행하기 전에 `ulong` (부호 없는 64비트 정수)으로 캐스팅하여 처리하는 방법입니다.
```csharp
public (long timestamp, long nodeId, long sequence) Inspect(long id)
{
var bytes = BitConverter.GetBytes(id);
// Decrypt 로직 (수정된 버전 사용 가정)
var decryptedBytes = _sbox.Decrypt(bytes);
long rawLongId = BitConverter.ToInt64(decryptedBytes, 0);
// ulong으로 캐스팅하여 비트 연산 수행
ulong rawUlongId = (ulong)rawLongId;
// ulong 기준으로 비트 연산
var timestampOffset = (rawUlongId >> (RANDFLAKE_NODE_BITS + RANDFLAKE_SEQUENCE_BITS));
var nodeId = (rawUlongId >> RANDFLAKE_SEQUENCE_BITS) & RANDFLAKE_MAX_NODE;
var sequence = rawUlongId & RANDFLAKE_MAX_SEQUENCE;
// 최종 타임스탬프 계산
var timestamp = (long)timestampOffset + RANDFLAKE_EPOCH_OFFSET;
return (timestamp, nodeId, sequence);
}
```
* **장점:** ID가 음수로 해석되는 문제를 해결하여 30비트 타임스탬프의 전체 범위(약 34년)를 문제없이 사용할 수 있습니다. 코드 수정이 비교적 간단합니다.
* **단점:** ID 자체의 **총 수명(약 34년)은 늘어나지 않습니다.** 단순히 부호 비트로 인한 음수 해석 문제만 해결합니다.
**3. ID 데이터 타입 변경 (복잡도 증가)**
ID를 `long` 대신 더 큰 데이터 타입(예: `System.Numerics.BigInteger` 또는 여러 `long`을 포함하는 커스텀 구조체)으로 변경하는 방법입니다.
* **장점:** 이론적으로 무한한 수명을 가질 수 있습니다.
* **단점:**
* ID 크기가 커져 저장 공간 및 전송 오버헤드가 증가합니다.
* 데이터베이스 호환성 문제가 발생할 수 있습니다 (`BigInteger`를 직접 지원하지 않는 경우).
* 비트 연산 및 암호화(Sparx64는 128비트 블록 암호) 로직이 훨씬 복잡해집니다.
* 일반적으로 권장되지 않는 방법입니다.
**결론 및 권장 사항:**
* **단순히 ID가 음수로 보이는 문제를 해결하고 싶다면:** 옵션 2 (`ulong`으로 해석)를 사용하세요. 하지만 총 수명은 약 34년으로 제한됩니다.
* **실제로 ID의 수명을 34년 이상으로 늘리고 싶다면:** **옵션 1 (비트 재할당)**이 가장 현실적이고 일반적인 해결책입니다.
* 귀하의 시스템에서 필요한 최대 노드 수와 초당 필요한 ID 생성량을 고려하여 타임스탬프에 할당할 비트 수를 결정하세요.
* Twitter Snowflake 방식(옵션 1의 예시 2)처럼 **밀리초 단위 타임스탬프**를 사용하고 타임스탬프에 41비트를 할당하면 약 69년의 수명과 초당 수백만 개(밀리초당 4096개)의 ID 생성이 가능해집니다 (노드 1024개 제한). 이는 많은 분산 시스템에서 좋은 균형점으로 여겨집니다.
*/
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
namespace Randflake.Tests
{
[TestClass]
public class GeneratorTests
{
private static readonly byte[] TestSecret = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
[TestMethod]
public void Constructor_ValidParameters_CreatesInstance()
{
var generator = new Generator(1, 1730000000, 1730000100, TestSecret);
Assert.IsNotNull(generator);
}
[TestMethod]
[ExpectedException(typeof(ArgumentException))]
public void Constructor_InvalidNodeId_ThrowsException()
{
_ = new Generator(-1, 1730000000, 1730000100, TestSecret);
}
[TestMethod]
[ExpectedException(typeof(ArgumentException))]
public void Constructor_InvalidSecret_ThrowsException()
{
_ = new Generator(1, 1730000000, 1730000100, new byte[10]);
}
[TestMethod]
public void Generate_ProducesUniqueValues()
{
var currentTime = 1730000050;
var generator = new Generator(1, 1730000000, 1730000100, TestSecret,
() => currentTime);
var uniqueIds = new HashSet<long>();
for (int i = 0; i < 1000; i++)
{
var id = generator.Generate();
Assert.IsFalse(uniqueIds.Contains(id), "Generated duplicate ID");
uniqueIds.Add(id);
}
}
[TestMethod]
public void Inspect_ReturnsCorrectComponents()
{
var currentTime = 1730000050;
var nodeId = 1L;
var generator = new Generator(nodeId, 1730000000, 1730000100, TestSecret,
() => currentTime);
var id = generator.Generate();
var (timestamp, returnedNodeId, sequence) = generator.Inspect(id);
Assert.AreEqual(currentTime, timestamp);
Assert.AreEqual(nodeId, returnedNodeId);
Assert.IsTrue(sequence >= 0);
}
[TestMethod]
public void UpdateLease_ValidParameters_UpdatesSuccessfully()
{
var generator = new Generator(1, 1730000000, 1730000100, TestSecret);
Assert.IsTrue(generator.UpdateLease(1730000000, 1730000200));
}
[TestMethod]
public void UpdateLease_InvalidParameters_ReturnsFalse()
{
var generator = new Generator(1, 1730000000, 1730000100, TestSecret);
Assert.IsFalse(generator.UpdateLease(1730000001, 1730000200)); // Wrong lease start
}
[TestMethod]
public async Task Generate_ConcurrentAccess_ProducesUniqueValues()
{
var currentTime = 1730000050;
var generator = new Generator(1, 1730000000, 1730000100, TestSecret,
() => currentTime);
var uniqueIds = new HashSet<long>();
var tasks = new List<Task>();
var lockObject = new object();
for (int i = 0; i < 10; i++)
{
tasks.Add(Task.Run(() =>
{
for (int j = 0; j < 100; j++)
{
var id = generator.Generate();
lock (lockObject)
{
Assert.IsFalse(uniqueIds.Contains(id), "Generated duplicate ID");
uniqueIds.Add(id);
}
}
}));
}
await Task.WhenAll(tasks);
Assert.AreEqual(1000, uniqueIds.Count);
}
}
}
// 테스트 필요
// 파이썬에 있는 Sparx64 라는 경량 블록 암호(lightweight block cipher)로 알려진 암호화 알고리즘을 C# 버전으로 AI가 포팅한 것이다.
using System;
using System.Collections.Generic;
using System.Linq;
public class Sparx64
{
private readonly uint[] _roundKeys;
private const int ROUNDS = 8;
private const int STEPS = 3;
private const int WORDS = 4;
// 생성자
public Sparx64(byte[] key)
{
if (key.Length != 16)
throw new ArgumentException("Key must be 16 bytes (128 bits)");
_roundKeys = KeySchedule(key);
}
// 키 스케줄링
private uint[] KeySchedule(byte[] key)
{
uint[] k = new uint[4];
for (int i = 0; i < 4; i++)
{
k[i] = BitConverter.ToUInt32(key, i * 4);
}
uint[] roundKeys = new uint[ROUNDS * WORDS];
uint c = 0;
for (int i = 0; i < ROUNDS; i++)
{
// 라운드 키 생성
for (int j = 0; j < WORDS; j++)
{
roundKeys[i * WORDS + j] = k[j];
}
// 키 업데이트
k[0] ^= c;
c++;
k[0] = ((k[0] << 8) | (k[0] >> 24)) & 0xFFFFFFFF;
k[1] ^= k[0];
k[1] = ((k[1] << 16) | (k[1] >> 16)) & 0xFFFFFFFF;
k[2] ^= k[1];
k[3] ^= k[2];
}
return roundKeys;
}
// 암호화
public byte[] Encrypt(byte[] plaintext)
{
if (plaintext.Length != 16)
throw new ArgumentException("Plaintext must be 16 bytes (128 bits)");
uint[] state = new uint[4];
for (int i = 0; i < 4; i++)
{
state[i] = BitConverter.ToUInt32(plaintext, i * 4);
}
for (int r = 0; r < ROUNDS; r++)
{
// ARX-box 단계
for (int i = 0; i < STEPS; i++)
{
state[0] = ARXBox(state[0], state[1], _roundKeys[r * WORDS + 0]);
Swap(ref state[0], ref state[1]);
}
// 선형 계층
state[2] ^= state[0];
state[3] ^= state[1];
// 키 추가
state[2] ^= _roundKeys[r * WORDS + 2];
state[3] ^= _roundKeys[r * WORDS + 3];
// 상태 회전
Swap(ref state[0], ref state[2]);
Swap(ref state[1], ref state[3]);
}
byte[] ciphertext = new byte[16];
for (int i = 0; i < 4; i++)
{
BitConverter.GetBytes(state[i]).CopyTo(ciphertext, i * 4);
}
return ciphertext;
}
// 복호화
public byte[] Decrypt(byte[] ciphertext)
{
if (ciphertext.Length != 16)
throw new ArgumentException("Ciphertext must be 16 bytes (128 bits)");
uint[] state = new uint[4];
for (int i = 0; i < 4; i++)
{
state[i] = BitConverter.ToUInt32(ciphertext, i * 4);
}
for (int r = ROUNDS - 1; r >= 0; r--)
{
// 상태 역회전
Swap(ref state[0], ref state[2]);
Swap(ref state[1], ref state[3]);
// 키 제거
state[2] ^= _roundKeys[r * WORDS + 2];
state[3] ^= _roundKeys[r * WORDS + 3];
// 선형 계층 역연산
state[2] ^= state[0];
state[3] ^= state[1];
// ARX-box 역연산
for (int i = 0; i < STEPS; i++)
{
Swap(ref state[0], ref state[1]);
state[0] = InverseARXBox(state[0], state[1], _roundKeys[r * WORDS + 0]);
}
}
byte[] plaintext = new byte[16];
for (int i = 0; i < 4; i++)
{
BitConverter.GetBytes(state[i]).CopyTo(plaintext, i * 4);
}
return plaintext;
}
// ARX-box 함수
private uint ARXBox(uint x, uint y, uint k)
{
x = (x + y) & 0xFFFFFFFF;
x ^= k;
x = ((x << 7) | (x >> 25)) & 0xFFFFFFFF;
return x;
}
// ARX-box 역함수
private uint InverseARXBox(uint x, uint y, uint k)
{
x = ((x >> 7) | (x << 25)) & 0xFFFFFFFF;
x ^= k;
x = (x - y) & 0xFFFFFFFF;
return x;
}
// 값 교환 헬퍼 함수
private void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
// 사용 예제
/*
public static void Main()
{
byte[] key = new byte[16] { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10 };
byte[] plaintext = new byte[16] { 0x12, 0x34, 0x56, 0x78, 0x9A, 0xBC, 0xDE, 0xF0,
0xA1, 0xB2, 0xC3, 0xD4, 0xE5, 0xF6, 0x07, 0x18 };
Sparx64 sparx = new Sparx64(key);
byte[] ciphertext = sparx.Encrypt(plaintext);
byte[] decrypted = sparx.Decrypt(ciphertext);
Console.WriteLine("Plaintext: " + BitConverter.ToString(plaintext).Replace("-", ""));
Console.WriteLine("Ciphertext: " + BitConverter.ToString(ciphertext).Replace("-", ""));
Console.WriteLine("Decrypted: " + BitConverter.ToString(decrypted).Replace("-", ""));
}
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment