나는 2-Byte Deltas에 집착해서 실제로 작동하는 Delta Compressor를 만들었다
Source: Dev.to
TL;DR
암호화된 문서 포맷에 아주 작은 델타가 필요했습니다. xdelta3는 간단한 편집에도 40 바이트 이상을 사용합니다. 7개의 특화된 알고리즘과 이전 버전을 참조하는 태그 시스템을 갖춘 xpatch를 만들었습니다. 결과: 실제 코드 저장소에서 중간값 2 바이트 델타를 달성 (120만 건의 실제 변경 사항 테스트). 빠르고 실제로 동작합니다.
중간값 델타가 2 바이트라는 점에 주목하세요. 오타가 아니라 uint16 하나: 헤더만 있고 실제로는 아무것도 없으며, 비교되는 파일이 동일하고 알고리즘이 “버전 5를 보라, 동일하다”고 말하는 것입니다.
The Problem That Broke Me
엔드‑투‑엔드 암호화, 실시간 협업, 전체 버전 히스토리, 오프라인‑우선 동기화 등을 서버 팜 없이 구현하려는 문서 포맷을 만들고 있었습니다.
문제는 암호화 후에는 압축을 할 수 없다는 점입니다. 델타가 암호화되면 더 이상 압축 기회가 없으므로, 모든 델타는 아주 작아야 하며 그렇지 않으면 저장 비용이 제품을 죽입니다.
- Myers diff – 고전적이고 검증된 방법이지만 500 ms마다 캡처되는 마이크로 편집에는 너무 장황합니다. “사용자가 5자를 추가했다”는 정보를 저장하는 데 수십 바이트가 필요했습니다.
- xdelta3 – 큰 변경에선 더 좋지만 “hello” → “hello world” (6 바이트 변경)만 인코딩하는 데도 40 바이트 이상을 사용했습니다 (8배 오버헤드).
- gdelta – 작은 파일에 대한 빠른 압축을 약속하는 2021년 연구 논문이지만, 구현은 3년 된 연구 코드와 거의 컴파일되지 않는 Python 바인딩뿐이었습니다.
gdelta를 Rust로 다시 작성했습니다(레포 참조). 빠르고 효율적이지만, 단순 편집은 여전히 ~20 바이트가 나왔습니다. 계속 스스로에게 물었습니다: 왜 누군가가 “hello”를 입력했다는 사실을 저장하는 데 20 바이트가 필요할까?
The Realization That Changed Everything
대부분의 문서 편집은 예측 가능한 패턴을 따릅니다:
- 텍스트 추가 – “hello” → “hello world”
- 텍스트 삭제 – “hello world” → “hello”
- 변경 되돌리기 – “hello” → “hello world” → “hello”
- 반복 패턴 – “test test test”, 들여쓰기, 데코레이터 등
- 복잡한 구조 변화 – 그 외 모든 경우
xdelta3나 gdelta 같은 범용 알고리즘은 모든 경우를 하나의 접근법으로 처리하려고 하며, 최악의 경우(임의의 바이너리 변경)에 최적화됩니다.
만약 모든 상황에 하나의 알고리즘이 필요하지 않다면? 각 패턴마다 여러 특화된 알고리즘을 시도하고 가장 작은 결과를 선택한다면? 이 아이디어가 xpatch를 탄생시켰습니다.
Building It: The Simple Stuff First
Algorithm 1: Just Store The Damn Characters
가장 흔한 경우는 텍스트 추가이므로, 단순히 문자를 저장합니다.
fn encode_add(position: usize, data: &[u8]) -> Vec<u8> {
let mut encoded = encode_varint(position);
encoded.extend_from_slice(data);
encoded
}Position (가변 길이 정수) + 원시 문자. 위치 6에 “world”를 추가하면 약 6 바이트가 소요되며, gdelta의 20 바이트 이상을 이미 능가합니다.
Algorithm 2: Deletion Is Even Simpler
fn encode_remove(start: usize, end: usize) -> Vec<u8> {
let mut encoded = encode_varint(start);
encoded.extend(encode_varint(end - start));
encoded
}두 개의 숫자: 삭제가 시작되는 위치와 삭제할 바이트 수. 일반적인 오버헤드는 ~3 바이트 정도입니다.
Algorithm 3: Wait, What If We Tokenize This?
텍스트는 무작위가 아니라 단어로 이루어져 있습니다. 흔히 쓰이는 단어를 토큰화하면 작은 ID로 대체할 수 있습니다.
- 토큰 목록: 2¹⁴ = 16 384 토큰 (varint에 들어감; 대부분의 ID는 1 바이트).
- 토큰은 빈도 순으로 정렬해 흔한 단어에 가장 작은 ID를 부여합니다.
- Wikipedia 같은 대규모 코퍼스로 학습해 어휘를 구축합니다.
토크나이저는 배열 인덱스형 자식 노드를 가진 트라이를 사용해 바이트당 O(1) 탐색을 제공합니다:
struct TrieNode {
token_id: Option<u16>,
children: [Option<Box<TrieNode>>; 256],
}
impl TrieNode {
fn find_longest_match(&self, text: &[u8], start: usize) -> Option<(usize, u16)> {
let mut node = &self;
let mut last_match = None;
let mut pos = start;
while pos < text.len() {
let byte = text[pos];
match &node.children[byte as usize] {
Some(child) => {
node = child;
if let Some(id) = node.token_id {
last_match = Some((pos + 1, id));
}
pos += 1;
}
None => break,
}
}
last_match
}
}Choosing the Best Algorithm
enum Algorithm {
Chars,
Tokens,
GDelta,
}
fn encode_delta(base: &[u8], new: &[u8]) -> (Algorithm, Vec<u8>) {
// Start with simple character encoding
let mut best_algo = Algorithm::Chars;
let mut best_data = encode_add(0, new); // placeholder for actual diff
// Try tokenization – might be smaller
if let Ok(token_data) = encode_tokens(0, new) {
if token_data.len() < best_data.len() {
best_algo = Algorithm::Tokens;
best_data = token_data;
}
}
// Fallback to gdelta for anything not covered above
let gdelta_data = gdelta_encode(base, new);
if gdelta_data.len() < best_data.len() {
best_algo = Algorithm::GDelta;
best_data = gdelta_data;
}
(best_algo, best_data)
}인코더는 항상 주어진 변경에 대해 가능한 가장 작은 델타를 반환합니다. 특화된 알고리즘이 더 작을 경우 이를 활용하고, 그렇지 않으면 견고한 범용 압축기인 gdelta로 부드럽게 대체합니다.