Skip to content

Commit decf959

Browse files
committed
apacheGH-3817: Content defined chunking of data pages
Add opt-in content defined chunking (CDC) to the writer. Data page boundaries are chosen by a rolling gear hash over each column's (definition level, repetition level, value) stream instead of by position, so an insert or delete only changes the pages around it and files deduplicate in content addressable storage. The chunker is a port of Arrow C++ (parquet/chunker_internal) and arrow-rs (column/chunker/cdc.rs): same gear tables, mask derivation, defaults and cut rules, so page boundaries match Arrow C++'s. - ContentDefinedChunkingOptions: min/max chunk size and normalization level, defaulting to 256 KiB / 1 MiB / 0 as in Arrow. - ParquetProperties and ParquetWriter.Builder: withContentDefinedChunkingEnabled, withContentDefinedChunkingOptions. - ParquetOutputFormat: parquet.page.content-defined-chunking.* keys. - ChunkingColumnWriter wraps the column writer only when chunking is enabled, so the default write path is unchanged. - dev/cdc: a parity check against pyarrow, a Python transcription of the C++ chunker, and a dedup probe. ContentDefinedChunkingWriteBenchmarks measures the write cost. Off by default.
1 parent efec555 commit decf959

29 files changed

Lines changed: 4427 additions & 5 deletions

‎dev/cdc/README.md‎

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
<!--
2+
Licensed to the Apache Software Foundation (ASF) under one
3+
or more contributor license agreements. See the NOTICE file
4+
distributed with this work for additional information
5+
regarding copyright ownership. The ASF licenses this file
6+
to you under the Apache License, Version 2.0 (the
7+
"License"); you may not use this file except in compliance
8+
with the License. You may obtain a copy of the License at
9+
10+
http://www.apache.org/licenses/LICENSE-2.0
11+
12+
Unless required by applicable law or agreed to in writing,
13+
software distributed under the License is distributed on an
14+
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15+
KIND, either express or implied. See the License for the
16+
specific language governing permissions and limitations
17+
under the License.
18+
-->
19+
20+
# Content defined chunking: development tools
21+
22+
Where the numbers the unit tests assert come from, and a measurement of what the feature is
23+
for. `parity` needs pyarrow, `model.py` needs nothing, and `dedup` measures rather than
24+
asserts, so none of them runs in the build. Only the Python and this script live here — the
25+
Java halves sit in the modules they belong to, so the build compiles them and spotless
26+
formats them:
27+
28+
- `parquet-hadoop/src/test/java/org/apache/parquet/hadoop/ContentDefinedChunkingParityTool.java`
29+
- `parquet-benchmarks/src/main/java/org/apache/parquet/benchmarks/ContentDefinedChunkingDedupProbe.java`
30+
31+
## `run.sh parity` — page boundaries against Arrow C++
32+
33+
A port checked only against its own output cannot catch a defect it shares with its tests.
34+
This is the independent oracle: pyarrow drives the real Arrow C++ chunker
35+
(`cpp/src/parquet/chunker_internal.cc`) to write reference files, parquet-java writes the
36+
same data with the same options, and the page boundaries of both are compared — read
37+
through parquet-java on both sides, so only the reference *bytes* come from pyarrow.
38+
39+
```bash
40+
PYARROW=/path/to/python-with-pyarrow ./run.sh parity
41+
```
42+
43+
Nothing is interchanged but the settings: both sides generate the values from the same LCG,
44+
so a mismatch is a boundary difference and never a data difference.
45+
46+
One case per level path the chunker dispatches on, plus two that pin the awkward edges:
47+
48+
| case | what it exercises |
49+
| --- | --- |
50+
| `required_int64` | no levels hashed at all (`maxDef == maxRep == 0`) |
51+
| `optional_int64` | definition levels hashed, value only when present |
52+
| `optional_utf8` | same level path, element-bytes dispatch instead of fixed width |
53+
| `optional_list_int64` | both levels hashed, and cuts only at a record start |
54+
| `multi_row_group_int64` | four row groups, pinning where the chunker's state is dropped |
55+
| `tight_envelope_int64` | an envelope whose mask makes the hard maximum-size cut decide most boundaries |
56+
57+
All six match Arrow C++ exactly. The run prints each case's full page vector, which is what
58+
`TestContentDefinedChunkerGoldenBoundaries` asserts, so it is also how those numbers are
59+
regenerated.
60+
61+
## `model.py` — the same check without pyarrow
62+
63+
`reference.py` needs pyarrow, which puts the strongest check behind an install. `model.py` is a
64+
transcription of `chunker_internal.cc` written from the C++ source, generating the gear tables
65+
from their MD5 specification rather than copying them, so agreement with it is independent
66+
evidence that the port is faithful -- weaker than driving the real Arrow, but it runs anywhere.
67+
68+
```bash
69+
python3 model.py vectors
70+
```
71+
72+
prints the chunk size vectors `TestContentDefinedChunker` asserts, keyed by test method name.
73+
Change a vector there and it has to come from here.
74+
75+
The last case is worth its own line. Arrow C++'s header comment claims the rolling state is kept
76+
"without being reset between pages and row groups", but the code it documents does not do that:
77+
`content_defined_chunker_` is a member of `ColumnWriterImpl`, and `AppendRowGroup` builds a fresh
78+
`RowGroupSerializer` whose `InitColumns()` makes new column writers, so every row group starts at
79+
`rollingHash = 0`. parquet-java resets for the same reason -- `initStore()` rebuilds the column
80+
writers -- and arrow-rs is the odd one out, keeping one chunker per file and therefore parting ways
81+
with Arrow C++ after the first row group. Cutting both sides by row count and comparing four row
82+
groups is what holds that decision in place.
83+
84+
Five settings are load bearing. Change one and the comparison stops meaning anything:
85+
86+
- **row groups cut the same way on both sides.** The chunker is dropped at a row group boundary,
87+
and parquet-java ends a row group on buffered size where pyarrow uses a row count -- so either
88+
keep the whole file in one row group, or pin both sides to the same row count as
89+
`multi_row_group_int64` does with `withRowGroupRowCountLimit`.
90+
- **`data_page_size` / `withPageSize` huge**, so the encoded-size cut never fires. Arrow cuts
91+
on an encoder-internal running total that a writer choosing boundaries before encoding has
92+
no counterpart for.
93+
- **`max_rows_per_page` / `withPageRowCountLimit` huge**, on both sides.
94+
- **one Arrow chunk per column** (`combine_chunks()`). Arrow skips the page break after the
95+
last chunk of a `WriteArrow` call, so a multi-chunk table produces boundaries a streaming
96+
writer would not.
97+
- **only types both sides hash identically.** Arrow hashes dictionary *indices* where
98+
parquet-java only ever sees logical values, and it hashes several other types before
99+
converting them to their Parquet representation. `ContentDefinedChunkingOptions`' javadoc
100+
lists them; they are expected to differ and are not what this checks.
101+
102+
## `run.sh dedup` — how much an edit actually costs
103+
104+
Writes a dataset and an edited copy, then chunks the **final file bytes** with a rolling gear
105+
hash — what a content addressable store does on upload — and reports how much of the pair it
106+
could share.
107+
108+
```bash
109+
./run.sh dedup
110+
```
111+
112+
Run it across codecs, because the answer depends on one entirely: with plain uncompressed
113+
pages the bytes after an edit are unchanged and the store's own chunker resynchronises
114+
without any help, so chunking changes nothing. Page boundaries start to matter once each
115+
page is independently encoded.

‎dev/cdc/model.py‎

Lines changed: 202 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,202 @@
1+
# Licensed to the Apache Software Foundation (ASF) under one
2+
# or more contributor license agreements. See the NOTICE file
3+
# distributed with this work for additional information
4+
# regarding copyright ownership. The ASF licenses this file
5+
# to you under the Apache License, Version 2.0 (the
6+
# "License"); you may not use this file except in compliance
7+
# with the License. You may obtain a copy of the License at
8+
#
9+
# http://www.apache.org/licenses/LICENSE-2.0
10+
#
11+
# Unless required by applicable law or agreed to in writing,
12+
# software distributed under the License is distributed on an
13+
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
# KIND, either express or implied. See the License for the
15+
# specific language governing permissions and limitations
16+
# under the License.
17+
18+
"""A transcription of Arrow C++'s parquet/chunker_internal.cc, used as an oracle.
19+
20+
Written from the C++ source rather than from the Java port, and the gear tables are
21+
regenerated from their MD5 specification rather than copied, so agreement between this and
22+
ContentDefinedChunker is evidence the port is faithful. `reference.py` is the other half of
23+
the picture: it drives the real Arrow C++ through pyarrow, which is stronger but needs
24+
pyarrow installed. This needs nothing but the standard library.
25+
26+
python3 dev/cdc/model.py vectors # the expected chunk sizes the Java tests assert
27+
28+
Every case under `vectors` names the test method it feeds, and the two must be kept in step.
29+
"""
30+
import hashlib
31+
import struct
32+
import sys
33+
34+
NUM_GEARHASH_TABLES = 8
35+
MASK64 = (1 << 64) - 1
36+
37+
38+
def gearhash_tables():
39+
"""chunker_internal_generated.h, from the specification it was generated by."""
40+
return [
41+
[
42+
int(hashlib.md5(bytes([seed] * 64 + [n] * 64)).hexdigest()[:16], 16)
43+
for n in range(256)
44+
]
45+
for seed in range(NUM_GEARHASH_TABLES)
46+
]
47+
48+
49+
TABLE = gearhash_tables()
50+
51+
52+
def calculate_mask(min_chunk_size, max_chunk_size, norm_level):
53+
"""CalculateMask(), chunker_internal.cc.
54+
55+
The sum below overflows int64 for envelopes near its maximum, as it does in C++ and in
56+
arrow-rs; RollingHashMask.calculate rejects those instead. Nothing in the vectors here
57+
comes near it.
58+
"""
59+
if min_chunk_size < 0:
60+
raise ValueError("min_chunk_size must be non-negative")
61+
if max_chunk_size <= min_chunk_size:
62+
raise ValueError("max_chunk_size must be greater than min_chunk_size")
63+
avg_chunk_size = (min_chunk_size + max_chunk_size) // 2
64+
target_size = (avg_chunk_size - min_chunk_size) // NUM_GEARHASH_TABLES
65+
target_bits = target_size.bit_length()
66+
mask_bits = 0 if target_bits == 0 else target_bits - 1
67+
effective_bits = mask_bits - norm_level
68+
if effective_bits < 1 or effective_bits > 63:
69+
raise ValueError(
70+
"The number of bits in the CDC mask must be between 1 and 63, got %d" % effective_bits
71+
)
72+
return (MASK64 << (64 - effective_bits)) & MASK64
73+
74+
75+
class Chunker:
76+
"""ContentDefinedChunker::Impl, chunker_internal.cc."""
77+
78+
def __init__(self, min_chunk_size, max_chunk_size, norm_level, max_def=0, max_rep=0):
79+
self.min_chunk_size = min_chunk_size
80+
self.max_chunk_size = max_chunk_size
81+
self.mask = calculate_mask(min_chunk_size, max_chunk_size, norm_level)
82+
self.max_def = max_def
83+
self.max_rep = max_rep
84+
self.rolling_hash = 0
85+
self.has_matched = False
86+
self.nth_run = 0
87+
self.chunk_size = 0
88+
89+
def roll(self, data):
90+
"""Roll(), for a value already reduced to its storage bytes."""
91+
self.chunk_size += len(data)
92+
if self.chunk_size < self.min_chunk_size:
93+
return
94+
for byte in data:
95+
self.rolling_hash = ((self.rolling_hash << 1) + TABLE[self.nth_run][byte]) & MASK64
96+
self.has_matched = self.has_matched or (self.rolling_hash & self.mask) == 0
97+
98+
def need_new_chunk(self):
99+
"""NeedNewChunk(). Note what is not reset: the rolling hash, ever, and nth_run on
100+
the hard size cut."""
101+
if self.has_matched:
102+
self.has_matched = False
103+
self.nth_run += 1
104+
if self.nth_run >= NUM_GEARHASH_TABLES:
105+
self.nth_run = 0
106+
self.chunk_size = 0
107+
return True
108+
if self.chunk_size >= self.max_chunk_size:
109+
self.chunk_size = 0
110+
return True
111+
return False
112+
113+
def offer(self, value=None, rep=0, definition=0):
114+
"""One triplet, in the order Calculate() rolls them: definition, repetition, value.
115+
116+
Returns whether a page ends immediately before it. The caller counts values, the way
117+
ChunkingColumnWriter does, rather than slicing a materialised column as C++ does.
118+
"""
119+
if self.max_def > 0:
120+
self.roll(struct.pack("<h", definition))
121+
if self.max_rep > 0:
122+
self.roll(struct.pack("<h", rep))
123+
if definition == self.max_def and value is not None:
124+
self.roll(value)
125+
if self.max_rep and rep != 0:
126+
# C++ only calls NeedNewChunk() at a record start, so a match found mid-record
127+
# carries forward instead of being consumed here.
128+
return False
129+
return self.need_new_chunk()
130+
131+
132+
def chunk_sizes(chunker, values):
133+
"""Value counts per page, counted as TestContentDefinedChunker counts them."""
134+
sizes = []
135+
current = 0
136+
for value in values:
137+
if chunker.offer(value) and current > 0:
138+
sizes.append(current)
139+
current = 0
140+
current += 1
141+
if current > 0:
142+
sizes.append(current)
143+
return sizes
144+
145+
146+
def lcg(count):
147+
"""The value stream the Java tests generate, as unsigned 64-bit."""
148+
x = 0x243F6A8885A308D3
149+
out = []
150+
for _ in range(count):
151+
x = (6364136223846793005 * x + 1442695040888963407) & MASK64
152+
out.append(x)
153+
return out
154+
155+
156+
def vectors():
157+
"""The chunk size vectors TestContentDefinedChunker asserts, by test method name.
158+
159+
Each case reproduces its Java counterpart's value stream. All of them drive a flat
160+
required column through a 0/64-byte envelope, where a chunk of 8 eight-byte values is a
161+
maximum-size cut and anything shorter is the rolling hash completing a run.
162+
"""
163+
def scaled(count):
164+
"""chunksIntegers: i * 0x9E3779B1 in 32-bit two's complement."""
165+
return [struct.pack("<I", (i * 0x9E3779B1) & 0xFFFFFFFF) for i in range(count)]
166+
167+
def lcg_from(seed, count):
168+
x = seed
169+
out = []
170+
for _ in range(count):
171+
x = (6364136223846793005 * x + 1442695040888963407) & MASK64
172+
out.append(x)
173+
return out
174+
175+
# The chunker hashes a value's storage bytes, little-endian: INT64 and DOUBLE are the low
176+
# eight bytes of the stream, INT32 and FLOAT the low four.
177+
cases = [
178+
("interleavesHashAndMaximumSizeCuts",
179+
[struct.pack("<Q", v) for v in lcg(120)]),
180+
("chunksIntegers", scaled(120)),
181+
("chunksDoubles",
182+
[struct.pack("<Q", v) for v in lcg_from(99, 120)]),
183+
# Quiet NaN payloads: intBitsToFloat/longBitsToDouble may quiet a signalling pattern,
184+
# and which patterns signal is platform dependent, so a signalling range would make
185+
# these vectors architecture dependent.
186+
("floatsHashTheirRawBitsIncludingNanPayloads",
187+
[struct.pack("<I", 0x7FC00001 + i) for i in range(120)]),
188+
("doublesHashTheirRawBitsIncludingNanPayloads",
189+
[struct.pack("<Q", 0x7FF8000000000001 + i) for i in range(120)]),
190+
]
191+
192+
for name, values in cases:
193+
sizes = chunk_sizes(Chunker(0, 64, 0), values)
194+
print("%-46s %s" % (name, ", ".join(str(s) for s in sizes)))
195+
196+
197+
if __name__ == "__main__":
198+
if len(sys.argv) > 1 and sys.argv[1] == "vectors":
199+
vectors()
200+
else:
201+
print(__doc__)
202+
sys.exit(2)

0 commit comments

Comments
 (0)