KSUID와 UUIDv7을 동시에 지원하는 경량 UID 생성기: libchronoid 이야기
by Justin Kim
Datalog 엔진을 만들면서 ID 생성기가 필요했는데 많은 고민을 한 끝에 직접 만들기로 했습니다. 단순 난수 기반의 중복을 피하는 ID가 아니라, 생성 순서를 보존해야 하고, 데이터베이스 정렬 성능에 영향을 주지 않으면서, 동시에 외부 시스템과도 호환되어야 했습니다. 그런데 기존 UID 라이브러리들은 C 외부 의존성이 많았고, 임베디드 환경이나 서버 확장 모듈에 포함시키기 어려웠습니다. 결국 C11만 사용하면서 완전히 제어할 수 있는 경량 UID 생성기를 직접 만들 수밖에 없었습니다.
처음엔 KSUID 하나만으로 시작했지만, 외부 API 호출과 로그 시스템을 연결하다 보니 UUIDv7도 지원해야 했습니다. 두 형식 모두 시간 정보를 담고 있으니, 한 라이브러리에서 함께 제공하는 것이 자연스러웠습니다.
이번 포스팅에서는 직접 libchronoid를 구현하며 고민했던 부분들과, 대량 생성 로직에 SIMD와 NEON을 적용해 최적화한 과정을 코드로 남겨두려고 합니다.
왜 KSUID인가, 그리고 왜 UUIDv7인가
KSUID는 20바이트 크기 안에 4바이트 타임스탬프와 16바이트 페이로드를 담습니다. 타임스탬프가 앞쪽에 오기 때문에 생성 순서대로 정렬이 가능합니다. UUIDv7은 2021년 이후에 표준화된 시간 기반 UUID로, 128비트 틀 안에 타임스탬프와 랜덤 값을 섞어 넣습니다.
두 가지 형식을 모두 지원하게 된 데에는 나름의 이유가 있었습니다.
- 내부 저장소 인덱싱이나 로그를 뽑을 땐 정렬이 보장되는
KSUID가 편합니다. - 하지만 외부 서비스나 클라이언트한테 API 응답을 던질 땐 다들 친숙하게 느끼는
UUIDv7이 낫습니다. - 어차피 둘 다 베이스는 ‘시간’이라서, 타임스탬프 원천(source-of-truth)만 동일하면 두 포맷이 결국 같은 의미를 갖거든요.
따라서 어느 하나를 선택하기보다는, 내부 식별자로는 KSUID를 사용하고 외부 연동 시에는 UUIDv7을 함께 제공할 수 있는 구조로 방향을 잡았습니다.
라이브러리 설계 목표: 작고 가볍게
GitHub 저장소: semantic-reasoning/libchronoid
라이브러리를 설계하며 세웠던 주요 기준들은 다음과 같습니다.
- 외부 의존성 없음
- 모듈식 C11 구조 (19개 C 파일, 15개 헤더, 형식별 독립 구현)
- 동적 메모리 할당 최소화
- 범용 컴파일러 호환성 (GCC/Clang, MSVC)
- 선택적 SIMD 가속 경로는
bulk연산에만 적용
KSUID와 UUIDv7 로직을 디렉토리 레벨에서 명확히 분리했습니다. 필요한 모듈의 소스 파일만 선택하여 프로젝트에 함께 빌드할 수 있습니다. 무거운 동적 라이브러리(so/dll)를 들고 다닐 필요가 없어서, 서버에 붙이는 확장 모듈이나 리소스가 빡빡한 임베디드 환경에서도 부담 없이 쓰기 좋습니다.
내부 레이아웃: KSUID와 UUIDv7 둘 다 16바이트 단위로
KSUID의 기본 구조는 다음과 같습니다.
uint32_t timestamp: 생성 시각 (초)uint8_t payload[16]: 임의 데이터
UUIDv7 구조는 다음과 같습니다.
uint64_t time_hi: 48비트 타임스탬프 + 버전uint64_t time_lo: 시퀀스/랜덤
이 두 구조 모두 16바이트 단위로 정렬 가능하고, 대량 생성시 128비트 로드/스토어를 활용하기 유리합니다.
typedef struct {
uint32_t timestamp_be;
uint8_t payload[16];
} ksuid_t;
typedef struct {
uint64_t hi;
uint64_t lo;
} uuid7_t;
여기서 timestamp_be를 big-endian으로 저장하는 이유는 정렬 순서가 메모리 레이아웃과 일치하기 때문입니다. 동일한 값이 CPU 아키텍처에 따라 다르게 정렬되지 않도록 하기 위해서입니다.
SIMD 적용: 포맷팅과 검증 경로에서 성능을 뽑다
libchronoid의 SIMD 최적화는 ID 생성이 아니라 포맷팅(인코딩)과 검증에 집중합니다. 생성 경로(chronoid_ksuid_new(), chronoid_uuidv7_new())는 스칼라 코드로 유지하면서, 벌크 포맷팅 함수(chronoid_ksuid_string_batch(), chronoid_uuidv7_string_batch())에서 SIMD 성능 이득을 봅니다. 이렇게 설계한 이유는 다음과 같습니다.
- 생성 경로: 단일 ID 생성은 경량성이 최우선이므로 스칼라 구현으로 충분합니다.
- 포맷팅 경로: 한 번에 수천 개 이상의 ID를 문자열로 변환할 때 SIMD가 큰 효과를 발휘합니다.
KSUID: base62 포맷팅과 입력 검증
포맷팅 (base62 인코딩): x86_64의 AVX2 8-wide 커널
- 파일:
chronoid/ksuid/encode_avx2.c - 기법: Granlund-Möller 나눗셈 (floor reciprocal multiply divide-by-62)
- 8개의 KSUID를 병렬로 base62로 인코딩하여 27자 문자열 생성
/* AVX2 8-wide chronoid_ksuid_string_batch 커널
* 기법: Granlund-Möller multiply-high를 활용한 나눗셈
* 각 KSUID 20바이트를 5개의 32비트 limb로 분해
* 벡터화된 64비트 곱셈-고위수(mulhi64)로 base62 변환
*/
static inline __m256i
chronoid_ksuid_mulhi64_avx2 (__m256i a, __m256i b) {
// 64x64 → 128 multiply-high, 4-lane wide
// Schoolbook 방식: a*b의 상위 64비트를 벡터로 계산
__m256i ll = _mm256_mul_epu32 (a, b); // low*low
__m256i lh = _mm256_mul_epu32 (a, b_hi); // low*high
__m256i hl = _mm256_mul_epu32 (a_hi, b); // high*low
__m256i hh = _mm256_mul_epu32 (a_hi, b_hi); // high*high
// ... 중간 항 누적으로 최종 high 계산
}
입력 검증: ARM NEON과 SSE2 16-byte 병렬 검증
- 파일:
chronoid/ksuid/base62_neon.c,chronoid/ksuid/base62_sse2.c - 기법: 3가지 범위 테스트 (0-9, A-Z, a-z)를 병렬로 수행
- 16개 base62 문자를 동시에 검증해 파싱 속도 향상
/* ARM NEON base62 16-byte translate-and-validate
* 파일: chronoid/ksuid/base62_neon.c
*/
int chronoid_base62_translate16_neon (uint8_t out[16], const uint8_t in[16]) {
uint8x16_t v = vld1q_u8 (in);
// 범위 1: 0-9 → 0-9
uint8x16_t d = vsubq_u8 (v, vdupq_n_u8 ('0'));
uint8x16_t d_mask = vcleq_u8 (d, vdupq_n_u8 (9));
uint8x16_t d_val = vandq_u8 (d_mask, d);
// 범위 2: A-Z → 10-35
uint8x16_t u = vsubq_u8 (v, vdupq_n_u8 ('A'));
uint8x16_t u_mask = vcleq_u8 (u, vdupq_n_u8 (25));
uint8x16_t u_val = vandq_u8 (u_mask, vaddq_u8 (u, vdupq_n_u8 (10)));
// 범위 3: a-z → 36-61
uint8x16_t l = vsubq_u8 (v, vdupq_n_u8 ('a'));
uint8x16_t l_mask = vcleq_u8 (l, vdupq_n_u8 (25));
uint8x16_t l_val = vandq_u8 (l_mask, vaddq_u8 (l, vdupq_n_u8 (36)));
// 결과 병합: 16개 문자를 한 번에 처리
uint8x16_t values = vorrq_u8 (vorrq_u8 (d_val, u_val), l_val);
vst1q_u8 (out, values);
return 0;
}
UUIDv7: Hex 포맷팅
포맷팅: x86_64의 SSSE3/AVX2 커널
- 파일:
chronoid/uuidv7/hex_ssse3.c,chronoid/uuidv7/hex_avx2.c - 기법: PSHUFB (Packed Shuffle Bytes) 니블→ASCII LUT
- SSSE3: 1 UUID당 한 번, AVX2: 4 UUID 병렬 처리
/* AVX2 4-wide chronoid_uuidv7_string_batch 커널
* 파일: chronoid/uuidv7/hex_avx2.c
* 전략: 4 UUID (64 바이트) → 144 hex chars (36*4)
* VPSHUFB로 니블 추출 후 LUT 변환, 하이픈 삽입
*/
static inline void
chronoid_uuidv7_hex32_avx2 (char out64[64], const uint8_t *in32) {
static const uint8_t kHexLowerLut[16] = {
'0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', 'a', 'b', 'c', 'd', 'e', 'f',
};
// 32 바이트 (2 UUID) 로드
__m256i v = _mm256_loadu_si256 ((const __m256i *) in32);
// LUT를 두 128-bit 레인에 broadcast
__m256i lut = _mm256_broadcastsi128_si256 (
_mm_loadu_si128 ((const __m128i *) kHexLowerLut)
);
// 니블 추출: 각 바이트에서 상위/하위 4비트를 분리
__m256i mask_low = _mm256_set1_epi8 (0x0F);
__m256i lo = _mm256_and_si256 (v, mask_low);
__m256i hi = _mm256_and_si256 (_mm256_srli_epi16 (v, 4), mask_low);
// VPSHUFB로 LUT 변환 (각 128-bit 레인 독립)
__m256i lo_hex = _mm256_shuffle_epi8 (lut, lo);
__m256i hi_hex = _mm256_shuffle_epi8 (lut, hi);
// 결과를 interleave하여 출력 (상위 니블이 먼저)
// hi_hex | lo_hex → "0A" "0B" ... 형태로 저장
}
성능 특성 요약
| 연산 | 포맷 | 스칼라 | SIMD 지원 |
|---|---|---|---|
| KSUID 인코딩 | base62 | 1 ID | 8-wide AVX2 (x86_64만) |
| KSUID 파싱 | base62 범위 테스트 | 1 ID | 16-byte NEON/SSE2 (ARM/x86 모두) |
| UUIDv7 인코딩 | hex | 1 ID | 4-wide AVX2, 1-wide SSSE3 (x86_64만) |
결론적으로 SIMD 최적화는 생성 로직 자체에 강제로 적용하기보다는, 생성된 ID를 문자열로 변환하거나 검증하는 과정에만 적용되도록 분리했습니다. 단일 ID 생성 함수는 최대한 가볍고 단순하게 유지하는 것이 낫다고 판단했습니다.
실제 사용: KSUID와 UUIDv7 생성하기
KSUID 생성
가장 간단한 형태는 현재 시간으로 KSUID를 생성하고 문자열로 변환하는 것입니다.
#include <chronoid/ksuid.h>
#include <stdio.h>
int main(void) {
chronoid_ksuid_t ksuid;
// 현재 시간으로 새 KSUID 생성
if (chronoid_ksuid_new(&ksuid) != CHRONOID_KSUID_OK) {
fprintf(stderr, "Failed to generate KSUID\n");
return 1;
}
// 27자 base62 문자열로 포맷팅
char s[CHRONOID_KSUID_STRING_LEN + 1];
chronoid_ksuid_format(&ksuid, s);
s[CHRONOID_KSUID_STRING_LEN] = '\0';
printf("Generated KSUID: %s\n", s);
// Output: Generated KSUID: 0ujtsYcgvSTl8PAuAdqWYSMnLOv
return 0;
}
생성된 KSUID에서 타임스탬프 정보를 추출할 수도 있습니다.
// KSUID에서 Unix 시간(초) 추출
int64_t unix_seconds = chronoid_ksuid_time_unix(&ksuid);
printf("Generated at: %lld\n", unix_seconds);
UUIDv7 생성
UUIDv7은 유사한 인터페이스를 제공합니다.
#include <chronoid/uuidv7.h>
#include <stdio.h>
int main(void) {
chronoid_uuidv7_t uuid;
// 현재 시간으로 새 UUIDv7 생성
if (chronoid_uuidv7_new(&uuid) != CHRONOID_UUIDV7_OK) {
fprintf(stderr, "Failed to generate UUIDv7\n");
return 1;
}
// 36자 정규 하이픈 형식으로 포맷팅
char s[CHRONOID_UUIDV7_STRING_LEN + 1];
chronoid_uuidv7_format(&uuid, s);
s[CHRONOID_UUIDV7_STRING_LEN] = '\0';
printf("Generated UUIDv7: %s\n", s);
// Output: Generated UUIDv7: 019de2b2-7c56-7e59-98be-2ed3cffbd12e
return 0;
}
UUIDv7에서 밀리초 단위 타임스탬프를 추출할 수 있습니다.
// UUIDv7에서 Unix 시간(밀리초) 추출
int64_t unix_ms = chronoid_uuidv7_unix_ms(&uuid);
printf("Generated at: %lld ms\n", unix_ms);
대량 생성: 벌크 포맷팅
한 번에 많은 ID를 생성하고 포맷팅할 때는 벌크 경로를 사용합니다. 이때 SIMD가 활약합니다.
#include <chronoid/ksuid.h>
#include <stdlib.h>
#include <stdio.h>
int main(void) {
size_t count = 1000;
// 1. 많은 KSUID 생성
chronoid_ksuid_t *ids = malloc(count * sizeof(chronoid_ksuid_t));
for (size_t i = 0; i < count; i++) {
chronoid_ksuid_new(&ids[i]);
}
// 2. 벌크 포맷팅 (SIMD 최적화됨)
// 각 KSUID는 27바이트를 차지하고, NUL 종료자는 없음
char *out = malloc(count * CHRONOID_KSUID_STRING_LEN);
chronoid_ksuid_string_batch(ids, out, count);
// 3. 결과 출력
for (size_t i = 0; i < 10; i++) { // 처음 10개만 출력
printf("%.*s\n", CHRONOID_KSUID_STRING_LEN,
out + i * CHRONOID_KSUID_STRING_LEN);
}
free(out);
free(ids);
return 0;
}
이 방식은 스칼라 루프보다 훨씬 빠릅니다. 특히 x86_64의 AVX2를 지원하는 시스템에서 8배 가까운 성능 향상을 기대할 수 있습니다.
UUIDv7 생성: 메타 정보와 호환성
UUIDv7은 내부적으로 48비트 타임스탬프와 74비트 랜덤/시퀀스로 구성됩니다. libchronoid에서는 uuid7_t를 이렇게 정의했습니다.
typedef union {
uint8_t bytes[16];
struct {
uint64_t hi;
uint64_t lo;
} parts;
} uuid7_t;
생성 과정은 다음과 같습니다.
- 타임스탬프를 48비트로 계산
- 버전 필드(0x7)를 위치에 넣기
- 랜덤 바이트 또는 시퀀스 바이트를 채우기
- 바이트 순서를 네트워크 바이트 오더로 정렬
여기에서도 벌크 경로는 큰 차이를 냅니다. 타임스탬프와 버전 비트 삽입은 16바이트 청크 단위로 처리할 수 있기 때문입니다.
static inline void set_uuid7_timestamp(uuid7_t* u, uint64_t ts_ms) {
uint64_t top = (ts_ms & 0xFFFFFFFFFFFFULL) << 16;
top |= 0x7000ULL; // 버전 7
u->parts.hi = htobe64(top | ((uint64_t)rand() & 0xFFFF));
}
이후 lo 필드는 그대로 랜덤 또는 시퀀스 값을 채우고, htobe64()를 통해 네트워크 바이트 오더로 맞춥니다. 이 과정은 외부 시스템에서 UUID를 다룰 때 흔히 기대하는 바람직한 메모리 표현과 일치합니다.
풋프린트 최소화: 작은 코드, 작은 실행 파일
이 라이브러리를 만들면서 가장 크게 신경 쓴 부분은 풀 스택이 아니라 코어 스택이라는 점입니다.
- 헤더 내부에 작은 구조체와 함수 선언만 둠
- 기본 랜덤 생성은
xoroshiro128+혹은 간단한xorshift를 채택 - 외부 암호화 라이브러리는 넣지 않음
SIMD코드는 선택적 매크로로 분리- 빌드 옵션에 따라
NEON/SSE2를 끌 수 있도록 함
실제로 libchronoid를 -Os로 빌드하면 10KB 안팎으로 유지됩니다. 심지어 bulk 루틴을 제외한 단일 ID 생성만 쓸 경우, 실행 코드가 더욱 작아집니다.
실무 적용 경험
이 라이브러리를 실제 Datalog 엔진에 붙여서 써보면서 몇 가지 재미있는 사실을 깨달았습니다.
- ID 생성 자체가 병목인 경우는 잘 없습니다. 보통은 DB나 네트워크가 먼저 막히죠. 하지만 데이터를 한 번에 대량으로 밀어 넣는(Batch Insert) 구간에서는 이렇게 SIMD로 최적화해둔 포맷팅 로직이 꽤 쏠쏠한 체감 성능 향상을 가져다주었습니다.
- UUIDv7을 지원한 건 정말 잘한 선택이었습니다. 내부에서 아무리 KSUID가 좋다고 해도, 외부 시스템(로그 수집기, 메시지 큐, 외부 API 등)과 연동할 때는 결국 다들 UUID 규격을 기대하기 마련이거든요. 호환성 스트레스가 확 줄었습니다.
- 내부 인덱싱에는 역시 KSUID가 편합니다. 앞에 4바이트 타임스탬프가 확실하게 자리 잡고 있으니, 시간순으로 정렬하거나 히트맵을 뽑아낼 때 데이터베이스 인덱스를 태우기가 훨씬 수월했습니다.
마무리
이번 프로젝트를 진행하며, 시스템 설계 시 단일 포맷만을 고집할 필요는 없다는 점을 다시금 깨달았습니다. 목적에 맞게 KSUID를 내부용으로 활용하면서도, 보편적인 표준인 UUIDv7 규격을 함께 제공하는 유연함이 실무에서 큰 장점으로 작용했습니다.
결과적으로 외부 의존성이 많은 무거운 라이브러리보다는, 필요한 기능만 가볍게 구현하여 유지하는 최소 발자국 접근법이 장기적인 관리 측면에서 훨씬 유리하다는 사실을 체감할 수 있었습니다.
릴리즈 계획
현재 libchronoid 0.99.0은 pre-release 상태입니다. KSUID와 UUIDv7 모두 기능 완성도가 높고, 광범위한 테스트와 CI/CD 커버리지를 갖추고 있습니다. 큰 버그가 발견되지 않으면 곧 1.0 안정 버전으로 릴리즈될 예정입니다. 이때 API와 ABI 안정성이 보장되어 프로덕션 환경에서 장기적으로 사용할 수 있는 기반이 마련될 것입니다.
더 알아보기
- GitHub 저장소: https://github.com/semantic-reasoning/libchronoid
- 라이선스: LGPL-3.0-or-later (KSUID 부분 MIT 호환)
- 현재 버전: 0.99.0 (pre-release)
Subscribe via RSS
Comments