|
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개 제한). 이는 많은 분산 시스템에서 좋은 균형점으로 여겨집니다. |
|
|
|
*/ |