바이너리 패킹은 생각보다 재미있습니다

AI 요약

JSON 대신 바이너리로 데이터를 저장하면 얼마나 작아질지 궁금했던 글쓴이는 직접 바이너리 포맷을 설계하기 시작합니다. 처음에는 값마다 타입과 길이 정보를 붙이는 방식으로 출발하지만, 필드마다 타입을 저장하면 구조화된 데이터에서 중복이 생깁니다. 그래서 데이터 구조를 미리 선언하는 스키마를 도입하고, 스키마를 읽어 바이너리를 만들거나 언어별 구조체 코드를 생성하는 도구까지 구현합니다.

바이너리 값과 헤더 설계

문자열은 바이트 그대로 저장하면 되지만, 숫자를 ASCII 문자열로 쓰면 104를 저장하는 데 세 바이트가 듭니다. 정수 타입이라는 표시와 값을 별도로 기록하면 한 바이트로 줄일 수 있지만, 문자열처럼 길이가 달라지는 값은 길이 정보도 필요합니다. 글은 헤더의 최상위 비트(MSB)를 이어쓰기 표시로 활용합니다. 비트가 1이면 다음 헤더 바이트가 이어지고, 0이면 헤더가 끝납니다. 정수는 7비트씩 나눠 가변 길이 정수(varint)로 인코딩하며, 구현은 LEB128 방식을 따릅니다.

값마다 타입 정보를 붙이는 대신 스키마가 필드 타입을 알려주도록 바꾸면 타입 표기를 반복하지 않아도 됩니다. 글쓴이는 varint, 32비트 부동소수점(f32), 64비트 부동소수점(f64), 길이 지정 데이터(delimited)를 네 가지 와이어 타입으로 둡니다. 두 비트로 타입을 표현하고, 필드 번호를 두 비트 왼쪽으로 이동한 뒤 타입을 하위 비트에 넣어 하나의 값으로 합칩니다. 이 값을 varint로 기록해 필드 번호와 타입을 함께 전달합니다. 문자열은 태그, 바이트 길이, 실제 바이트 순서로 저장합니다.

스키마 언어와 컴파일러

필드 번호와 타입, 기본값을 매번 코드에서 지정하는 수고를 줄이려고 별도의 스키마 언어를 만듭니다. 메시지와 열거형(enum)을 선언하고, 필드에는 번호·이름·타입을 적습니다. 목록(list), 맵(map), 유니언(union), 기본값, 패키지와 가져오기(import) 문법도 추가합니다. 글은 같은 Player 구조를 자체 문법과 Protocol Buffers의 .proto 문법으로 나란히 보여줍니다.

구현은 C++로 진행합니다. 렉서(lexer)가 입력을 토큰으로 나누고, 파서(parser)가 이를 추상 구문 트리(AST)로 만듭니다. 의미 분석기는 두 차례 검사합니다. 첫 번째 순회에서 메시지와 열거형 심볼을 모으고, 다음 순회에서 선언된 타입인지, 필드 번호가 중복되지 않았는지, 맵 키로 쓸 수 없는 타입을 지정하지 않았는지 등을 확인합니다. 이 구조 덕분에 선언 순서와 관계없이 타입을 참조할 수 있으며, 순환 참조도 검사합니다.

JSON 패킹과 코드 생성

동적 패커는 스키마와 JSON을 메모리에 읽은 뒤 함께 순회합니다. 예를 들어 JSON의 id 값이 나오면 AST에서 해당 필드 번호와 타입을 찾아 태그와 값을 인코딩합니다. C++용 nlohmann/json 라이브러리를 사용해 JSON 파싱 자체는 별도로 구현하지 않습니다. 글의 작은 예시에서는 공백과 따옴표를 포함한 JSON이 약 35바이트이고, 바이너리 결과는 9바이트로 74.29% 줄었다고 설명합니다.

런타임에 스키마를 조회하지 않고 일반 구조체를 쓰고 싶은 경우를 위해 AOT 코드 생성도 구현합니다. AST 노드가 방문자(visitor)를 받아들이는 방식으로 C와 Python 생성기를 분리하고, 각 생성기가 메시지와 필드, 열거형을 방문해 코드를 출력합니다. CLI는 스키마 빌드와 JSON 패킹 명령을 제공하며, 생성된 C 코드에는 구조체뿐 아니라 패킹·언패킹 함수와 접근자도 포함됩니다. 글의 Character 예시에서는 JSON 파일 401바이트를 바이너리 80바이트로 줄였다고 보고합니다. 글쓴이는 시작은 JSON 저장 공간을 줄이려는 시도였지만, 렉서부터 다중 언어 코드 생성기까지 만들게 됐다고 정리합니다.

Reddit 반응

• @Embarrassed_Luck1057 — 이 작성자가 직렬화를 다시 발명한 건가요?
  • @darknecross — 더 나쁘게는 Protocol Buffers를 다시 발명했습니다.
  • @happyscrappy — BER(CER/DER)도 있고, Apple의 바이너리 plist 형식도 있습니다.
  • @GenericAHHyoutuber — 네, 그러게요 ;-;
• @palad1 — 바이너리를 패킹하고 계신 건가요, 아니면 저를 보고 정말 기뻐하시는 건가요?
  • @Asyncrosaurus — 비트가 다 보이네요.
• @DanTFM — 독자 포맷을 만드는 걸 좋아합니다. 예전 직장에서 부풀려진 필드가 들어간 28GB XML 파일을 약 300MB로 줄이는 포맷을 많이 만들었습니다. O(log(n/1024)) 시간에 검색할 수도 있었고요. 글 잘 읽었습니다!
  • @leaving_the_tevah — 제가 괜히 꼬치꼬치 따지는 것 같아 죄송합니다. 제가 놓친 부분이 있으면 알려주세요. O(log(n/1024))는 O(log(n) - log(1024)), 다시 O(log(n) - 10), 결국 O(log(n)) 아닌가요?
  • @DanTFM — 제 실수입니다. 네, 여전히 O(log n)입니다. 실제 검색 집합을 설명하려고 n/1024라고 썼습니다. 포맷이 인덱스 항목을 약 1/1024로 줄여서 이진 검색 단계가 약 10단계 줄었고, 남은 집합을 건너뛰는 데는 O(1)이 들었습니다.
  • @creeper6530 — GZ 같은 걸 쓰면 얼마나 더 줄어드는지 궁금합니다.
  • @DanTFM — 실제로 보관한 데이터만 gzip으로 압축하면 이 포맷보다 더 작아졌습니다. 도메인 데이터 일부를 제거하기도 해서 아마 이 포맷 크기의 10~25%였을 겁니다. 다만 저전력 임베디드 하드웨어에서 압축을 풀지 않고 파일을 바로 검색할 수 있습니다. 내일 압축 지표를 다시 확인해 보겠습니다.
• @SvenWollinger — Minecraft에서 패킷을 읽고 쓸 때 쓰는 ByteBuf가 떠오릅니다. NBT에 더 가까운 것 같지만요.
• @iAmHidingHere — 그냥 CBOR를 쓰지 않는 이유가 있나요?
  • @GenericAHHyoutuber — 아니요, 그냥 재미로 직접 구현해 보고 싶었습니다.
• @kylanbac91 — BSON을 쓰세요.
  • @GenericAHHyoutuber — 그냥 제가 직접 구현해 보고 싶었어요 😭
• @afl_ext — 문서가 없는 Toshiba 전화 라우터의 ASN.1 원시 패킷을 디코딩하던 기억이 되살아납니다...
  • @Cut_Mountain — 저도 한 번 ASN.1로 된 H.248 메시지를 직렬화하는 일을 맡았습니다. 참 여러모로 힘든 시절이었죠.
• @rsclient — Windows에서 출처 불명의 Bluetooth 기기를 지원하는 사람으로서 말씀드립니다. 새로운 바이너리 포맷을 만들지 말아 주세요! 정말 조금도 필요하지 않습니다.
• @VeeFu — 정말 재미있어 보이지만, 웹 서버와 브라우저에서 널리 지원하는 기성 압축 라이브러리를 쓰는 편이 나을 것 같습니다.
  • @DoctorGester — 둘 다 쓰면 안 되나요? 저희는 사용자 정의 바이너리 형식의 네트워크 트래픽에 zstd를 적용합니다. 예를 들어 리플레이 파일은 바이너리 상태에서 45MB에서 3MB로 줄었습니다.
  • @MehYam — 저도 같은 말을 하려 했습니다. 바이너리로 패킹한 데이터도 평범한 .zip 압축만 적용하면 놀랄 만큼 작아질 수 있습니다.

원문: 개인 블로그 / 번역·요약: Trawling