borgbackup / borgbackup/borg

ChunkIndex: intern pack_id (u32 index) to cut chunks index memory by ~30%

Open
#10,080 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
13.7k
Forks
875
Avg merge
11h 15m
Merged PRs (30d)
192

Description

Follow-up to the memory usage evaluation in #5163.

## Problem

The in-memory `ChunkIndex` is borg's dominant allocation, ~100 B/chunk all-in (see the
`cache-memory-usage` section in `docs/internals/data-structures.rst`). Its value record

```
(flags I, size I, pack_id 32s, obj_offset I, obj_size I) = 48 B (+ 32 B key = 80 B kv record)
```

carries a 32-byte `pack_id` that is 40% of the record and massively redundant: all objects in a
pack share it. With 50 MB packs, typically hundreds of index entries repeat the same pack_id, and
even a 100 TB repo only has ~2M distinct packs — a u32 index is more than enough.

## Idea: intern pack_id in the in-memory ChunkIndex

- ht value format becomes `(flags I, size I, pack_idx I, obj_offset I, obj_size I)` = 20 B;
the `ChunkIndex` wrapper holds a `pack_ids` list + `pack_id -> idx` dict (tiny: #packs entries).
- kv record 80 -> 52 B, i.e. **~100 -> ~72 B per chunk all-in (~30% less)**.
For the docs' example (16 Mi chunks): 1.56 GiB -> ~1.1 GiB.
- Public API unchanged: `__getitem__` / `iteritems` return the existing `ChunkIndexEntry` with
the pack_id expanded to bytes32; `__setitem__` / `add` / `update_pack_info` intern (one dict
lookup). Consumers (repository.py, compact_cmd.py, repo_compress_cmd.py) need no changes.

## Persistence: no format change needed (memory-only interning)

Every repo<->memory crossing of the chunks index is already an entry-by-entry loop, and the
serialized fragments are self-describing (borghash's JSON meta carries field names + struct
format), so the on-repo format and the in-memory format are decoupled:

- **Write**: `write_chunkindex_to_repo` already copies selected entries one-by-one into bounded
temp batch tables (<= `CHUNKINDEX_FRAGMENT_ENTRIES_MAX` = 400k entries) before `ht.write`.
Make the batch a plain `HashTableNT` in the current serialization format (`32s` pack_id) and
expand entries while filling it.
Detail: today the batch fill goes through `ChunkIndex.__setitem__`, which re-adds `F_NEW`, so
serialized entries actually carry `flags=F_NEW` on disk. The new fill must reproduce that
byte-exactly, so identical entry sets keep producing identical fragment content hashes
(dedupe/convergence with fragments written by current borg).
- **Read**: `read_chunkindex_from_repo` returns the raw loaded `HashTableNT` (self-describing;
its `.items()` already yields entries with bytes32 pack_id). The existing merge loops in
`build_chunkindex_from_repo` / `repack_chunkindex` intern on insert.
Transient memory stays bounded: one fragment ≈ 400k × 92 B ≈ 37 MB at a time.
- `UNKNOWN_BYTES32` needs no special-casing: `F_PENDING` entries are never serialized (asserted
in `write_chunkindex_to_repo`), and in memory the filler interns like any other value.
- No flag day: old and new borg read each other's fragments. No borghash change needed.

Optional, later, independent: store fragments interned too (20 B values + a per-fragment pack-id
table appended after the ht section; assigning pack_idx in first-appearance order while filling
the sorted-key batch keeps fragment bytes deterministic, preserving content-hash convergence).
That would cut fragment size ~35% pre-compression — but zstd compresses the repeated pack_ids
well anyway, so measure the compressed sizes first before breaking the format.

## Implementation sketch

- `src/borg/hashindex.pyx`: everything lives in `ChunkIndex` — internal interned value type,
`pack_ids` list + reverse dict, intern/expand in `__init__`, `__getitem__`, `__setitem__`,
`add`, `iteritems`, `update_pack_info`, `clear_new`, `clear` (reset pack table), `read`
(intern per entry while loading), `write` (expand per entry), `size()` estimate.
- `src/borg/hashindex.pyi`: update stub.
- `src/borg/cache.py`: batch table in `write_chunkindex_to_repo` uses the serialization format;
`read_chunkindex_from_repo` returns the raw loaded table for merging.
- `docs/internals/data-structures.rst`: memory formula chunks index ~100 -> ~72 B/entry.
- Tests: interning round-trip; fragment byte-stability across insert orders; fragment content
hashes for identical entry sets unchanged vs. master (compat/dedupe); fragment merge;
pending-entry handling.

## Verification

- Memory: synthetic 1M/10M-entry fills, before vs. after (~30% expected on the chunks index).
- Compatibility: create repo + backup with master, read/extend with the branch and vice versa.
- Perf sanity: index build/merge adds one dict lookup per inserted entry and one list index per
lookup — expected to be noise; spot-check create/extract benchmarks.

Contributor guide

Open the contributing guide

Research direction

Start with ChunkIndex in src/borg/hashindex.pyx and its stub in src/borg/hashindex.pyi, then trace write_chunkindex_to_repo and read_chunkindex_from_repo in src/borg/cache.py. Verify round-tripping, fragment byte stability and compatibility while keeping the documented memory formula in docs/internals/data-structures.rst accurate.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend, performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.