apache / apache/couchdb

[ENHANCEMENT]: Avoid wasting disk space on every commit

Open
#6,108 0 comments 0 reactions 0 assignees View on GitHub
enhancement needs-triage
Dominant language
Erlang
Stars
7k
Forks
1.1k
Avg merge
1d 16h
Merged PRs (30d)
9

Description

### Provide a brief overview of what the new feature is all about

Currently CouchDB writes headers on exactly 4KB boundaries. Header block start with a `01` tag byte and other, non-header blocks, have a `00` tag byte if they fall on the 4KB boundary. The scheme helps us unambiguously determine which header block is genuine, and which one may be fake, inserted by a user as an attachment. The idea is we are protected against "emulation attacks" - where a new couchdb file can be created inside an existing couchdb file via API data insertion.

The major downside of this approach is a lot of wasted space. Every time we commit (and since delayed commits were removed with sequential single doc update we commit with every doc update) we end padding 0s to the next 4KB boundary. So inserting a 10 byte document means actually wasting on average 2KB of disk space on each update. This can be easily noticed as the file sizes inflate rapidly even with small document inserts and pretty soon compaction starts off, even though we haven't updated or deleted any documents yet.

There were a few ways we thought of fixing it before:

1. Use a separate file for attachments. If we don't have attachments we reduce the chance of the emulation attack. But that means having extra file that has to be kept alongside the main file. Means having one extra fsync. And there may still be a small chance someone could figure out a way to craft a header even via a plain document upload with some utf8 encoding or compression in the mix

2. Use base64 encoding for attachments. This would inflate their size and make it harder to serve byte range requests. There may still be some possibility someone could craft a document body or to create a fake header via with/without utf8 encoding/compression in the mix

3. New file format: use a per-couch_file specific ID (a UUID), generated at file creation and saved as the first record in the file. Then, each db header should always reference that file ID. That ID is never visible or retrievable via the HTTP API. This is the most promising and simplest fix, but it's still not 100% there as a leaked backup or a log line with a stack crash could reveal the per-file UUID and then allow the emulated header to be uploaded

The current proposal to fix this problem is with "byte stuffing". Byte stuffing is just a fancy way of saying "escaping". This is not a new concept and it's been done already in the PPP protocol (https://datatracker.ietf.org/doc/html/rfc1662#section-4.2), for example, or JPEG frame encoding, and other cases, where there is a need to have some frame boundary delimiters in the data stream and those boundaries should never appear in the internal data. In our case we'd like to have some magic header frame boundary, and that string to never appear in the internal data: not in doc bodies, checksums, attachments, etc, just in headers. If we can have that, we can always scan back through the file and find the latest header by searching for that string and then validate the header checksum. If we do that avoid wasting all that disk space padding 0 to the next 4KB boundary on each commit.

### Tell us how the new feature should work. Be specific

Since this would involve having a new file format the the idea is to combine byte stuffing with the file ID scheme described above.

For byte stuffing we'd pick some byte prefix with all unique bytes. Preferably something less likely to be used in utf8 text encoding to typical erlang term_to_binary format to avoid having to escape that routinely.

More specifically, say we pick a 7 byte prefix P with some high valued bytes (but excluding 0xff):

`P = f5, f6, f7, f8, f9, fa, fb`

Then pick a byte `H` (=fc) as the header marker byte. The full header tag is then: `P|H = f5, f6, f7, f8, f9, fa, fb, fc`

Pick another byte, X (=fd) as the escape byte. The whole escape prefix is `P|X = f5, f6, f7, f8, f9, fa, fb, fd`

#### Encoding

Encoding a header:
* `P|H -> P|H`

Encoding any other data:
* `P|H -> P|X|H`
* `P|X -> P|X|X`

The main idea is that we never have a raw `P|H` in a non-header by construction

#### Decoding

Decoding (from file, read backwards in overlapping windows):
* `P|H -> P|H` (this is the header)
* `P|X|H -> P|H`
* `P|X|X -> P|X`

#### Advantages
* Disk space usage reduction, especially for small, sequential file updates
* Can be combined with the file ID to get better corruption detection
* File stays append only

#### Disadvantages
* It's a new disk format. Not radically different as we already have blocks and tags but still it's a new version which would require managing (making it non-default first, releasing it, switching to it as a default in a subsequent release, manage upgrades, etc)
* The assumption is we can easily search and replace byte blocks (erlang's binary module has `replace`, `split`, `part/3` and `at` function) but it should be benchmarked to see if we can do it without losing too much performance

Contributor guide

Open the contributing guide

Research direction

The issue names no files or tests. Start by tracing CouchDB's current 4KB header and block format, then investigate Erlang's binary replacement, splitting, and indexing operations and benchmark the proposed byte-stuffing approach. Done means a specified, validated file-format change that reduces per-commit padding while preserving header detection and append-only behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
erlang
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.