TCB v105 — 비트폭 패킹
상태: 구현 완료 — 변환기와 모든 런타임 · 대상 버전 105 (104를 대체)
배포된 파일이 없으므로 호환 경로를 두지 않습니다. 버전 정수는 개선의 기록이고, 리더는 다른 버전을 거부합니다.
하나의 배치를 두 자리에 씁니다.
- 인코딩 13
BITPACK— 정수 스트림을 그 컬럼의 범위가 요구하는 폭으로 묶습니다(4절). - presence 비트맵의 인코딩 — 비트맵은 폭 1 비트팩이므로 같은 선택을 그대로 받습니다(5절).
둘은 리더에서 같은 코드를 씁니다. 그래서 형식 개정 하나로 묶었고, 두 번째의 추가 비용은 「비트맵도 인코딩 바이트를 하나 갖는다」뿐입니다.
1. 근거 — 후보 표의 구멍
원소별 후보 개수로 보면 bool만 성질이 다릅니다.
| 원소 | 후보 수 | RAW가 뜻하는 것 |
|---|---|---|
| string | 7 | 가변 길이. RAW가 하한에 가까울 수 있음 |
| i32 | 5 | 4바이트 |
| f32 · f64 | 4 | 4·8바이트 |
| i64 | 3 | 8바이트 |
| bool | 2 | 1바이트 — 정보량의 8배 |
| uuid | 1 | 16바이트. 의도적 제외 |
다른 원소는 RAW가 그 값을 담는 데 실제로 필요한 폭이고, 압축되지 않는 데이터라면 RAW가 정당한
바닥입니다. bool은 아닙니다 — RAW는 정의상 엔트로피 하한의 8배이고, 이것은 어떤 시트가
오느냐와 무관한 타입의 성질입니다.
손익분기 16 — 형식의 성질
RLE 페어는 counter32 런 + optimalint 값이 므로 2~3바이트이고, bool의 값은 항상 1바이트입니다.
| 평균 런 길이 | 형식이 고르는 것 | 로우당 | 비트팩 대비 |
|---|---|---|---|
| 1 (교대) | RAW | 1 B | 8배 |
| 3 | RAW ≈ RLE | 1 B | 8배 |
| 8 | RLE | 0.31 B | 2.5배 |
| 16~24 | RLE ≈ 비트팩 | 0.125 B | 같음 |
| 100 | RLE | 0.025 B | 비트팩이 더 큼 |
평균 런 길이가 16 미만인 bool 컬럼은 필요한 것보다 크고, 교대에 가까울수록 8배로
갑니다. 그리고 런 길이는 이 도구가 정하지 못합니다 — 행 순서는 파일에 적힌 그대로라는 것이
형식의 규칙이므로, 같은 데이터도 정렬 키에 따라 런 200이 되기도 런 2가 되기도 합니다.
격자와 비트셋 — 양이 곱으로 자라는 자리
매트릭스 표는 { id, value: T[N] } × M행, 곧 고정 배열 컬럼 하나입니다.
bool 격자는 칸당 1바이트이고 칸 수는 행 × 열입니다.
| 격자 | 칸 수 | 오늘 | 폭 1 |
|---|---|---|---|
| 200 × 200 | 40,000 | 39.1 KB | 4.9 KB |
| 500 × 500 | 250,000 | 244.1 KB | 30.5 KB |
| 1000 × 1000 | 1,000,000 | 976.6 KB | 122.1 KB |
그리고 격자는 섞여 있기 때문에 존재합니다. 두 축의 교차가 균일하거나 유도된다면 작성자가 격자를 만들지 않습니다. 높은 엔트로피가 격자의 예외가 아니라 기본입니다.
원소 스트림은 행 우선으로 평탄화되므로, 격자의 열 방향 규칙은 RLE에 보이지 않습니다 — 어떤
열이 전 행에서 참이면 그 값들은 열 개수 간격으로 떨어져 있어 런이 길이 1입니다.
bitset도 같은 자리입니다. 와이어에서 i64이고 후보는 RAW·DICT·DICT_RLE이라,
플래그를 다섯 개만 쓰는 컬럼도 로우당 8바이트입니다.
2. 계측이 정한 것
형식을 바꾸기 전에 인코딩 보고서에 가상 수치를 넣어 두 데이터셋에 돌렸습니다. 세 가지 설계 결정이 계측으로 정해졌고, 그중 둘은 예상과 반대였습니다.
① base의 필요성
한쪽 데이터셋은 base가 전부 0이라 필요 없어 보였는데, 다른 쪽이 반대였습니다.
41 500 ActorStat.Experience
8 120101 Stage.SpawnIds
4 -1 Equip.MaxClass
3 1 Character.StatKind
base 없이는 이 컬럼들이 폭 17·폭 41이 되어 아무것도 벌지 못합니다.
② 내부 인코딩 후보의 복수 유지
두 데이터셋에서 선택되는 인코딩이 정반대입니다. 한쪽은 거의 전부 RLE, 다른 쪽은 거의 전부 RAW입니다.
하나로 고정하였다면 어느 한쪽을 통째로 잃습니다.
그리고 이것이 이득의 출처입니다. 순수 비트팩은 1절의 표대로 RLE와 같습니다. 차이를 내는 것은
묶은 뒤 다시 인코딩하는 쪽 — 묶기가 비트 수준의 구조를 바이트 수준의 구조로 바꾸고, 대부분
0인 컬럼은 0x00의 런이 됩니다.
③ 바이트 경계를 넘는 폭
실측된 폭입니다.
1 · 2 · 3 · 4 · 5 · 7 · 8 · 24 · 26 · 41 · 44
8의 약수(1·2·4·8)로 제한하면 3·5·7·26·41·44가 전부 한 칸 위로 올라갑니다. 연속 비트 스트림으로 두는 편이 맞고, 시프트·누산 루프는 폭이 1이든 41이든 같은 코드입니다.
헤더 크기의 영향
처음에 base를 8바이트 고정으로 재었다가 varint로 고치니, 선택되는 컬럼이 34개에서 91개로 늘고 varint 원소가 손해에서 이득으로 뒤집혔습니다. 로우가 적은 컬럼은 헤더가 판정합니다.
이 절의 수치는 계측 시점의 것이고, 그 계측에는 5절이 적은 오류가 있었습니다. 결정 셋은 그대로 유효합니다 — base가 필요한 컬럼과 내부 인코딩이 갈리는 데이터셋과 8의 약수가 아닌 폭은 오류와 무관하게 실재합니다. 절감의 크기만 5절이 다시 측정합니다.
3. 바꾸지 않는 것
바이너리 형식의 불변식은 전부 유지됩니다.
- 모르는 컬럼 건너뛰기 =
advance(byteLength)한 번. 폭·base·내부 인코딩이 전부 컬럼 블록 안에 있습니다. - 어떤 스키마 변경도 감지되지 않는 읽기 오류가 되지 않습니다.
- 승격 표는 그대로입니다.
- 행 순서는 파일에 적힌 그대로입니다.
- 디스크립터 배치도 그대로입니다 — 인코딩 바이트 하나가 블록 전체를 결정합니다. 조합은 디스크립터가 아니라 블록 헤더에서 일어납니다.
- 값은 여전히 모든 로우에 대해 기록합니다. v103이 정한 그대로이고, 비트맵이 인코딩된다고 해서 값 블록이 present인 로우만 담게 되지는 않습니다 — 그것은 인코딩 14종 × kind 3종의 디코드를 전부 다시 쓰는 일이고, 이 개정이 산 것이 아닙니다.
4. 인코딩 13 — BITPACK
fixed8 bitWidth 1..64
counter64 base 값에서 빼는 기준값. 지그재그 varint
fixed8 innerEncoding RAW(0) · VARINT(1) · DELTA(2) · RLE(3) · DELTA_RLE(4)
[묶인 스트림] 연속 비트 스트림, 하위 비트부터, 값도 하위 비트부터.
ceil(count × bitWidth / 8) 바이트
RAW면 그 바이트 그대로, 그 외는 바이트를 int 스트림으로 보고
그 인코딩대로
- 값 =
base + 묶인 값. 뺄셈과 덧셈 모두 감싸기(wrapping)로 합니다 — 두 int64가 int64보다 멀리 떨어져 있을 수 있고, 2의 보수 감싸기는 어느 쌍에서도 왕복이 정확합니다. - 값이 바이트 경계를 넘습니다. 패딩은 로우마다가 아니라 컬럼 전체에서 최대 7비트입니다.
- 길이 필드가 없습니다. 값 개수는 디스크립터(또는
ARRAY의totalElements)에 있고 폭이 블록에 있으므로 바이트 수가 계산됩니다.WHOLE이 같은 방식입니다. ARRAY의 원소 인코딩으로 옵니다. 그래서 격자가 닿습니다. 내부 인코딩이므로 검사는 디스크립터가 아니라 읽는 자리에서 합니다.counter64가 새로 필요합니다. 지금 형식에는 32비트 지그재그 varint만 있습니다. base는 i64 컬럼에서 64비트일 수 있으므로 리더가 64비트 판독을 하나 갖게 됩니다.
조합의 순서
ARRAY → WHOLE → BITPACK → 사전. BITPACK 안에 ARRAY는 오지 않고, ARRAY의 원소
인코딩으로 BITPACK은 옵니다. WHOLE의 내부 인코딩으로는 오지 않습니다 — 정수로 바뀐 실수
스트림은 이미 정수 인코딩을 고르는 자리이고, 거기에 한 겹을 더하면 같은 선택을 두 번 합니다.
리더의 (원소, 인코딩) 표
| 원소 | v104 | v105 |
|---|---|---|
| bool · varint | RAW · RLE | RAW · RLE · BITPACK |
| i32 | RAW · VARINT · DELTA · RLE · DELTA_RLE | + BITPACK |
| i64 | RAW · DICT · DICT_RLE | + BITPACK |
| 나머지 | 변경 없음 | 변경 없음 |
i32는 계측에서 합계로는 이득이 작지만(폭이 30 근처인 id 컬럼이 대부분입니다) 개별로 더 작아지는
컬럼이 있고, 선택기가 컬럼마다 고르므로 손해가 없습니 다. 디코드 경로는 원소와 무관하게 같은
코드이므로 넷을 함께 여는 비용이 하나를 여는 것과 같습니다.
거부
| 거부할 것 |
|---|
bitWidth가 0이거나 64를 넘는 것 |
innerEncoding이 정수 인코딩 집합(0~4) 밖인 것 |
| (원소, 인코딩) 표에 없는 조합 — v104의 게이트가 이미 맡은 역할 |
5. presence 비트맵 — 같은 선택을 한 번 더
v103은 비트맵을 RAW로 두면서 「presence가 변하는 컬럼의 비트맵은 압축되지 않는다」고 적었습니다. 그것은 판단이었고, 측정된 적이 없었습니다. 재보니 한 자릿수 차이로 틀렸습니다.
블록: [옵셔널이면: fixed8 presenceEncoding, 그 인코딩대로 담긴 비트맵]
encoding이 정한 배치로 담긴 rowCount개의 값
presenceEncoding은RAW(0)·VARINT(1)·DELTA(2)·RLE(3)·DELTA_RLE(4)입니다 — 4절의innerEncoding과 같은 집합입니다.- 비트맵은
ceil(rowCount / 8)바이트이고, 그 개수를 리더가 이미 알고 있으므로 길이 필드가 없습니다. - 폭과 base가 없습니다. 비트맵은 폭 1, base 0인 비트팩이고, 그 둘은 형식이 이미 아는 값이므로 블록에 다시 적으면 형식이 한 말을 반복하는 것입니다.
- required 컬럼에는 여전히 비트맵도 인코딩 바이트도 없습니다.
리더에 새 경로가 생기지 않습니다. 4절이 이미 「바이트 스트림을 정수 인코딩으로 푼다」를 요구하고, 이것은 그 호출을 한 번 더 하는 것입니다. 변환기에서도 같은 함수 하나가 두 자리에 쓰입니다 — 그래서 값 블록과 비트맵이 같은 비트를 다르게 풀 수 없습니다.
비용은 옵셔널 컬럼당 1바이트입니다. 이전 대규모 코퍼스에서 195바이트를 내고 122,055바이트를 회수합니다.
6. 실제 효과 — 파일을 측정해
구현한 뒤 파일 크기로 측정한 수치입니다.
| 데이터셋 | v104 | v105 |
|---|---|---|
| 이전 소규모 코퍼스 — 67개 테이블 | 141,670 B | 138,446 B (−2.28 %) |
| 이전 대규모 코퍼스의 부분 빌드 7개 테이블 | 1,460,895 B | 1,338,340 B (−8.39 %) |
내역입니다.
| 출처 | 이전 소규모 코퍼스 | 이전 대규모 코퍼스 |
|---|---|---|
| BITPACK (값 블록) | −3,224 B · 67개 컬럼 | −505 B · 18개 컬럼 |
| presence 비트맵 | 대상 없음 (옵셔널 컬럼 0개) | −122,055 B · 195개 중 190개 |
두 데이터셋의 상보성
한쪽이 닿지 않는 곳에 다른 쪽이 닿습니다. 이전 소규모 코퍼스는 옵셔널 컬럼이 하나도 없어서 값 블록이 전부이고, 이전 대규모 코퍼스는 옵셔널 컬럼이 195개라 비트맵이 대부분입니다. 둘 중 하나만 하였다면 데이터셋 하나를 처리하지 못합니다.
이전 대규모 코퍼스의 비트맵이 접히는 이유는 단순합니다 — 옵셔널 컬럼은 대개 거의 전부 있거나 거의 전부
없습니다. 29,574행짜리 Shop.LiveEvent의 비트맵은 3,697바이트에서 4바이트가 됩니다.
정정 — presence 비트맵을 양쪽에 세지 않은 계측
이 결론에 이르기 전에 계측이 한 번 틀렸고, 그 오류가 이 개정의 절반을 찾게 했으므로 남깁니다.
구현 전 계측은 이전 대규모 코퍼스에서 BITPACK이 12.3 KB를 절감한다고 적었습니다. 실제는 505바이트입니다. 컬럼의 「오늘」 크기는 비트맵을 포함한 블록 전체인데 가상 수치는 값 블록만 내므로, 그 둘을 견주면 가상 쪽이 손대지도 않는 바이트를 절감으로 계상합니다.
이전 대규모 코퍼스의 bool 컬럼이 그 함정이었습니다.
| 이전 대규모 코퍼스의 bool 33개 컬럼 (v104) | 바이트 |
|---|---|
| 블록 전체 | 15,193 |
| presence 비트맵 | 약 15,056 (99 %) |
| 값 블록 | 약 137 |
값은 이미 거의 없었습니다. 로우당 1.009비트이고, 1비트는 「이 로우에 값이 있는가」라는 정보 자체의 크기입니다. 비트팩이 진 것이 아니라 가져갈 것이 없었습니다.
같은 편향이 인코딩 보고서의 기존 headroom 절에도 있었습니다. 함께 고쳤습니다 — 이제 모든 비교가 비트맵을 양쪽에 셉니다.
그럼에도 BITPACK을 넣는 근거
비트맵 쪽이 이전 대규모 코퍼스에서 241 배 크지만, BITPACK이 값을 내는 것은 평균이 아니라 최악입니다.
- 1절의 8배는 시트의 정렬 방식이 결정하고, 이 도구는 그것을 통제하지 못합니다.
- required 컬럼이 많은 데이터셋에서는 2.28 %가 실제로 나옵니다. 두 데이터셋의 차이는 형식의 성질이 아니라 시트의 성질입니다.
- 후보를 더하는 것은 정의상 파일을 키우지 않습니다. 선택기는 더 작을 때만 채택하고 크기가 같으면 낮은 번호를 남깁니다.
7. 검증 게이트
| 게이트 | 확인하는 것 |
|---|---|
| 형식 고정 | 버전 바이트가 105로 |
| 적합성 코퍼스 ×13 | BITPACK이 선택되는 컬럼과 선택되지 않는 컬럼을 함께. 선택되지 않는 쪽이 없으면 선택기가 검증되지 않습니다 |
| 입력 공간 스윕 | 사례가 아니라 축으로 — 아래 |
| 모르는 폭·모르는 내부 인코딩 거부 | 4절의 거부 표. presenceEncoding도 같은 집합으로 검사합니다 |
| 비트맵 왕복 | 옵셔널 컬럼의 presence를 인코딩된 비트맵에서 되읽어 값과 대조. string과 bool이 반드시 포함됩니다 — 그 둘은 값이 같아 비트맵이 틀려도 값 대조로는 드러나지 않습니다 |
| 인코딩 선택 단정 | 컬럼별 선택 결과 |
| 골든 트리 | 재기록. 새 인코딩이 선택되는 컬럼의 diff가 리뷰 대상 |
| 샘플 재생성 | samples/*/out/은 게이트가 없으므로 절차로만 지켜집니다 |
스윕 격자. 이 도구는 범용이므로, 사례 두 개가 아니라 가능한 입력의 축으로 확인합니다.
| 축 | 값 |
|---|---|
| true 밀도 · 상태 분포 | 0 · 1 · 5 · 25 · 50 · 75 · 100 % |
| 평균 런 길이 | 1 · 2 · 4 · 16 · 64 · 1024 |
| 열 방향 주기 | 8의 배수 · 8과 서로소 · 주기 없음 |
| 격자 치수 | 얇고 긴 것 · 정사각 · 넓고 짧은 것 |
| 폭 | 1 · 2 · 3 · 4 · 8 · 41 |
| 밑값 | 0에서 시작 · 임의 · 음수 |
| 로우 수 | 8 미만 · 8 · 100 · 100,000 |
| 옵셔널 | required · nullable |
8. 하지 않는 것
- 사전의 인덱스 스트림에 비트팩. 자연스러운 확장이지만
DICT_*가 「평문 / RLE」 두 갈래를 각각 갖고 있어 갈래가 배로 늘어납니다. 값을 확인한 뒤에 판단합니다. WHOLE의 내부 인코딩으로BITPACK. 4절.- 폭을 컬럼이 아니라 블록 단위로 나누는 것(패치드 프레임). 이상치 하나가 폭을 밀어 올리는 경우를 검출하지만, 블록 경계와 예외 목록이라는 개념이 둘 더 필요하고 계측이 그것을 요구하지 않았습니 다.
- 범용 압축 레이어.
flagsbit1이 여전히 자리로 남아 있습니다.
9. 구현 순서
계측— 보고서의 「Bit-width packing headroom」. 형식 무변경. 완료.변환기— 인코딩 13,counter64, 버전 105, bool·varint·i32·i64 후보. 완료.C# 런타임과 생성기— 언팩 커서,counter64, 그리고 비트맵을 인코딩 바이트로 읽기. 적합성 코퍼스 왕복. 완료.나머지 런타임— 언어당 파일 하나. 완료.코퍼스와 게이트— 7절. 완료. 코퍼스에 손이 하나 갔습니다 —BITPACK이 두 참조 컬럼을 가져가면서VARINT가 어느 컬럼에서도 쓰이지 않게 되어, 하네스 전부가 그 디코드 경로를 한 번도 밟지 않는 상태가 되었습니다. 참조 하나가 멀리 떨어진 id를 가리키게 해서 되살렸습니다. 시트의 id는 촘촘하지 않으므로 억지 조건이 아니고, 폭은 전체 범위를 덮어야 하지만 varint는 큰 값이 있는 행에만 값을 씁니다.골든 재기록과 샘플 재생성— 완료. 기록 없이 재검증하는 것은 전체 스위트가 수행하므로 푸쉬 전에 한 번입니다.