Bijou64 — 숫자 하나 저장하는 데도 깊이가 있다, Ink & Switch가 제안한 새 가변 길이 정수 인코딩

무슨 일이 있었나요

숫자 하나를 컴퓨터에 어떻게 저장하시나요? "그냥 int 쓰면 되지 않나?" 싶지만 이게 보기보다 깊은 주제예요. Ink & Switch라는 연구 그룹이 최근 Bijou64라는 새로운 가변 길이 정수 인코딩 방식을 공개했는데, 단순히 "비트 좀 아끼자"는 얘기가 아니거든요. 데이터베이스 인덱스, 네트워크 프로토콜, CRDT, 파일 포맷처럼 매일 굴러가는 기반 계층이고, 여기서 살짝만 효율이 올라가도 시스템 전체가 가벼워져요. Ink & Switch는 로컬 퍼스트 소프트웨어와 협업 도구를 연구하는 곳이라 이런 "바닥의 바닥" 같은 주제를 자주 다뤄요.

가변 길이 정수가 뭐길래

먼저 가변 길이 정수 인코딩이 뭔지 풀어 볼게요. 일반적으로 64비트 정수는 8바이트를 고정으로 차지하는데, 우리가 실제로 다루는 숫자는 대부분 작거든요. 카운터, ID, 길이 필드 같은 거요. 99%가 0~1000 사이 숫자인데 매번 8바이트씩 쓰는 건 낭비잖아요. 그래서 작은 숫자는 1바이트, 큰 숫자는 더 많은 바이트로 자동으로 늘어나게 만든 게 가변 길이 인코딩이에요.

가장 유명한 건 protobuf의 varint이고, 그 외에 SQLite varint, UTF-8 스타일의 length-prefixed 인코딩, LEB128 같은 방식들이 있어요. 다 비슷한 아이디어인데 각자 트레이드오프가 달라요. 어떤 건 디코딩 속도가 빠르고, 어떤 건 크기가 더 컴팩트하고, 어떤 건 사전식(lexicographic) 정렬이 숫자 정렬과 일치해서 인덱스 키로 쓰기 좋고요.

Bijou64가 강조하는 핵심은 이름에 들어 있는 "전단사(bijection)" 성질이에요. 이게 뭐냐면, 64비트 숫자 하나하나가 인코딩된 바이트 시퀀스 하나에 정확히 1:1로 대응된다는 뜻이에요. 같은 숫자를 두 가지 방식으로 표현할 수 없고, 모든 가능한 바이트 시퀀스가 어떤 숫자에 대응돼요. 표현이 유일하니까 해시나 비교 연산이 안전해지고, 빈 슬롯 없이 인코딩 공간을 꽉 채워 쓰기 때문에 평균 크기도 작아져요.

기존 varint와 뭐가 다른가요

전통적인 varint는 각 바이트의 최상위 비트를 "다음 바이트가 더 있다"는 신호로 쓰거든요. 그래서 한 바이트에서 7비트만 데이터로 쓰고 1비트는 헤더로 쓰는 구조예요. 작은 숫자는 효율적이지만 같은 숫자를 0x05로도 쓰고 0x85 0x00으로도 표현할 수 있는 모호함이 생겨요. Bijou64는 헤더 비트 방식 대신, 첫 바이트의 앞쪽 비트 패턴만 보고 전체 길이를 한 번에 결정하는 방식이에요. UTF-8 첫 바이트만 보면 몇 바이트짜리 문자인지 아는 그 구조와 비슷해요. 이러면 디코딩 분기가 거의 없어 빠르고, 같은 숫자를 짧은 형태와 긴 형태로 동시에 쓸 수 있는 경우 자체가 사라져요.

또 Bijou64는 바이트 단위 사전식 정렬이 숫자 정렬과 일치하도록 설계됐어요. 이 성질이 왜 중요하냐면, LSM 트리나 B-트리 같은 키-값 저장소에서 키를 바이트째로 비교해도 숫자 순서가 보존되거든요. RocksDB, LMDB, FoundationDB 같은 엔진을 쓰는 시스템이라면 곧바로 활용 가치가 보이는 부분이에요. 인코딩된 값을 그대로 키로 박아도 범위 스캔이 정확히 동작한다는 뜻이니까요.

업계 맥락에서 보면

가변 길이 정수 인코딩은 사실 새로운 분야가 아니에요. 1970년대 Elias gamma/delta coding부터 시작해서 수십 년간 진화해 왔거든요. 그래서 Bijou64의 새로움은 알고리즘 그 자체보다 "어떤 트레이드오프 조합을 선택했느냐"에 있어요. 빠른 디코딩, 유일한 표현, 정렬 보존, 컴팩트한 크기를 한꺼번에 만족시키려는 균형 잡힌 디자인이라는 게 포인트예요. Automerge, Yjs 같은 CRDT 라이브러리, Parquet·Arrow 같은 컬럼 포맷, FlatBuffers·Cap'n Proto 같은 직렬화 시스템에서 이런 표현 계층 선택이 전체 성능을 좌우해요. Ink & Switch가 로컬 퍼스트 소프트웨어를 연구한다는 점을 생각하면, 자기들 CRDT 스택에 깔아 쓸 기반 기술로 만든 것이라고 봐도 자연스러운 흐름이에요.

한국 개발자에게 주는 시사점

실무에서 당장 varint를 갈아 끼울 일은 흔치 않을 거예요. 이미 protobuf나 MessagePack을 쓰고 있다면 그쪽 생태계에 묶여 있을 테니까요. 그런데 자체 바이너리 포맷이나 사내 RPC를 설계할 일이 생긴다면, Bijou64 글은 "어떤 기준으로 인코딩 방식을 골라야 하는지" 체크리스트로 굉장히 좋아요. 디코딩 분기 수, 표현 유일성, 정렬 보존성, 평균 바이트 수 같은 축들이 왜 중요한지 정리되어 있거든요. 분산 시스템이나 DB 내부를 공부 중인 분이라면, 이런 작은 표현 계층 하나가 처리량 곡선을 어떻게 바꾸는지 감을 잡는 데도 도움이 될 거예요.

마무리

"숫자 하나 저장하는 데 뭐 그리 깊은 얘기가 있나" 싶지만, Bijou64는 그 작은 결정들이 모여 시스템 성능과 안정성을 만든다는 걸 다시 보여 주는 사례예요. 여러분이 직접 바이너리 포맷을 설계해 본 적이 있다면, varint와 고정 폭 중 어떤 걸 골랐고 왜 그랬는지, 그리고 정렬 보존성을 챙긴 적이 있는지 댓글로 공유해 주세요.