Skip to content

Commit c0d7629

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. - CdcOptions: min/max chunk size and normalization level, defaulting to 256 KiB / 1 MiB / 0 as in Arrow. - ParquetProperties and ParquetWriter.Builder: withContentDefinedChunking(boolean) and withContentDefinedChunking(CdcOptions). - ParquetOutputFormat: parquet.page.content-defined-chunking.* keys. - ChunkingColumnWriter wraps the column writer only when chunking is enabled, so the default write path is unchanged. - CdcWriteBenchmarks measures the write cost. Off by default.
1 parent efec555 commit c0d7629

21 files changed

Lines changed: 3042 additions & 5 deletions

File tree

‎parquet-benchmarks/README.md‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,3 +56,12 @@ make sense to group together or to run in isolation during development. The
5656
./parquet-benchmarks/run.sh clean
5757
```
5858

59+
60+
## Content defined chunking
61+
62+
`CdcWriteBenchmarks` measures what chunking costs to write with. It is an
63+
ordinary JMH benchmark:
64+
65+
```
66+
./parquet-benchmarks/run.sh all org.apache.parquet.benchmarks.CdcWriteBenchmarks
67+
```
Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
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+
package org.apache.parquet.benchmarks;
20+
21+
import java.io.IOException;
22+
import java.util.ArrayList;
23+
import java.util.List;
24+
import java.util.Random;
25+
import java.util.concurrent.TimeUnit;
26+
import org.apache.parquet.example.data.Group;
27+
import org.apache.parquet.example.data.simple.SimpleGroupFactory;
28+
import org.apache.parquet.hadoop.ParquetFileWriter;
29+
import org.apache.parquet.hadoop.ParquetWriter;
30+
import org.apache.parquet.hadoop.example.ExampleParquetWriter;
31+
import org.apache.parquet.hadoop.metadata.CompressionCodecName;
32+
import org.apache.parquet.io.api.Binary;
33+
import org.apache.parquet.schema.MessageType;
34+
import org.apache.parquet.schema.MessageTypeParser;
35+
import org.openjdk.jmh.annotations.Benchmark;
36+
import org.openjdk.jmh.annotations.BenchmarkMode;
37+
import org.openjdk.jmh.annotations.Fork;
38+
import org.openjdk.jmh.annotations.Level;
39+
import org.openjdk.jmh.annotations.Measurement;
40+
import org.openjdk.jmh.annotations.Mode;
41+
import org.openjdk.jmh.annotations.OutputTimeUnit;
42+
import org.openjdk.jmh.annotations.Param;
43+
import org.openjdk.jmh.annotations.Scope;
44+
import org.openjdk.jmh.annotations.Setup;
45+
import org.openjdk.jmh.annotations.State;
46+
import org.openjdk.jmh.annotations.Warmup;
47+
48+
/**
49+
* What content defined chunking costs to write with: the same rows, the same page row count limit,
50+
* chunking the only difference.
51+
*
52+
* <p>Both variants raise the page row count limit. At its default of 20 000 rows the limit cuts a
53+
* page long before a default sized chunk is reached, so the comparison would otherwise be measuring
54+
* page count rather than hashing. The rows are built once and written to {@link BlackHoleOutputFile},
55+
* so neither data generation nor filesystem I/O dilutes the difference.
56+
*
57+
* <p>This does not measure what the feature costs while it is off, which is the number that matters
58+
* to everyone not using it. That one is the existing {@link WriteBenchmarks} figures compared
59+
* across revisions, since a disabled chunker is the absence of work rather than a variant of it.
60+
*/
61+
@BenchmarkMode(Mode.AverageTime)
62+
@Fork(1)
63+
@Warmup(iterations = 3)
64+
@Measurement(iterations = 5)
65+
@OutputTimeUnit(TimeUnit.MILLISECONDS)
66+
@State(Scope.Thread)
67+
public class CdcWriteBenchmarks {
68+
69+
private static final int ROW_COUNT = 100_000;
70+
71+
private static final MessageType SCHEMA = MessageTypeParser.parseMessageType("message m {"
72+
+ " required int64 long_field;"
73+
+ " required binary binary_field;"
74+
+ " required group group {"
75+
+ " repeated int32 int_field;"
76+
+ " }"
77+
+ "}");
78+
79+
@Param({"false", "true"})
80+
public boolean chunking;
81+
82+
private List<Group> rows;
83+
84+
@Setup(Level.Trial)
85+
public void setup() {
86+
SimpleGroupFactory factory = new SimpleGroupFactory(SCHEMA);
87+
Binary[] binaries = TestDataFactory.generateBinaryData(ROW_COUNT, 128, 0, TestDataFactory.DEFAULT_SEED);
88+
Random random = new Random(TestDataFactory.DEFAULT_SEED);
89+
rows = new ArrayList<>(ROW_COUNT);
90+
for (int i = 0; i < ROW_COUNT; i++) {
91+
Group group = factory.newGroup();
92+
group.append("long_field", (long) i);
93+
group.append("binary_field", binaries[i]);
94+
Group subGroup = group.addGroup("group");
95+
for (int j = 0; j < 8; j++) {
96+
subGroup.append("int_field", random.nextInt());
97+
}
98+
rows.add(group);
99+
}
100+
}
101+
102+
@Benchmark
103+
public void write() throws IOException {
104+
try (ParquetWriter<Group> writer = ExampleParquetWriter.builder(BlackHoleOutputFile.INSTANCE)
105+
.withWriteMode(ParquetFileWriter.Mode.OVERWRITE)
106+
.withType(SCHEMA)
107+
.withCompressionCodec(CompressionCodecName.UNCOMPRESSED)
108+
.withPageRowCountLimit(Integer.MAX_VALUE)
109+
.withContentDefinedChunking(chunking)
110+
.build()) {
111+
for (Group row : rows) {
112+
writer.write(row);
113+
}
114+
}
115+
}
116+
}
Lines changed: 210 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,210 @@
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+
package org.apache.parquet.column;
20+
21+
import java.util.Objects;
22+
import org.apache.parquet.Preconditions;
23+
import org.apache.parquet.internal.column.chunking.RollingHashMask;
24+
25+
/**
26+
* EXPERIMENTAL: How to chunk, when content defined chunking (CDC) is enabled: the size envelope and
27+
* the normalization level.
28+
*
29+
* <p>Content defined chunking ends a data page at a boundary derived from the content of the
30+
* column rather than from a size or row count, so that files sharing a run of values also share
31+
* byte-identical data pages and a content addressable storage (CAS) system can deduplicate them.
32+
* The sizes here are measured on the logical values, before any encoding or compression, and
33+
* everything fed to the rolling hash counts towards them, definition and repetition levels
34+
* included.
35+
*
36+
* <p>Shaped after {@code parquet::CdcOptions} in Arrow C++ and {@code CdcOptions} in arrow-rs: the
37+
* same three settings with the same defaults, because chunk boundaries deduplicate across
38+
* implementations only while the settings agree as well as the algorithm does.
39+
*
40+
* <p>Boundaries deduplicate against those two for the types all three hash the same bytes for:
41+
* {@code BOOLEAN}, {@code INT32}, {@code INT64}, {@code FLOAT}, {@code DOUBLE},
42+
* {@code BYTE_ARRAY} and {@code FIXED_LEN_BYTE_ARRAY} written from the corresponding Arrow type.
43+
* They do not where Arrow hashes something other than what Parquet stores, which happens because
44+
* Arrow chunks its own values and converts them afterwards:
45+
*
46+
* <ul>
47+
* <li>{@code int8}, {@code int16}, {@code uint8} and {@code uint16}, hashed there as one or two
48+
* bytes and stored here as {@code INT32}. ({@code uint32} and {@code uint64} are a
49+
* reinterpretation of the same bytes, so those do agree.)
50+
* <li>Timestamps Arrow converts on the way out -- to the unit {@code coerce_timestamps} names,
51+
* nanoseconds to microseconds when it writes Parquet format 1.0 or 2.4, and seconds to
52+
* milliseconds always -- and {@code INT96}, hashed there as the eight-byte timestamp the
53+
* twelve-byte value is built from.
54+
* <li>Decimals, hashed there as Arrow's own little-endian 16- or 32-byte buffer.
55+
* <li>{@code date64} and {@code time32(s)}, both converted before writing. ({@code half_float}
56+
* is stored as the same two little-endian bytes Arrow hashes, so it does agree.)
57+
* <li>Arrow arrays that are themselves dictionary encoded, where Arrow hashes the four-byte
58+
* indices rather than the values. This is the Arrow array's encoding, not Parquet's.
59+
* </ul>
60+
*
61+
* <p>Arrow C++ refuses to chunk outside its Arrow write path, so it never chunks those columns at
62+
* all. This writer has a single entry point and chunks them anyway, on boundaries of its own.
63+
*
64+
* <p>Instances are immutable and are built through {@link #builder()}. A size envelope that cannot
65+
* produce a usable rolling hash mask is rejected there, so an instance is valid by construction.
66+
*
67+
* <p>This API is experimental and may change or be removed in a future release.
68+
*
69+
* @see ParquetProperties.Builder#withContentDefinedChunking(CdcOptions)
70+
*/
71+
public final class CdcOptions {
72+
73+
/** The options used when content defined chunking is enabled without any of its own. */
74+
public static final CdcOptions DEFAULT = builder().build();
75+
76+
private final long minChunkSize;
77+
private final long maxChunkSize;
78+
private final int normLevel;
79+
80+
private CdcOptions(Builder builder) {
81+
this.minChunkSize = builder.minChunkSize;
82+
this.maxChunkSize = builder.maxChunkSize;
83+
this.normLevel = builder.normLevel;
84+
// Deriving the mask is what validates the envelope, so an unusable one is rejected here
85+
// rather than when the first column writer is built.
86+
RollingHashMask.calculate(minChunkSize, maxChunkSize, normLevel);
87+
}
88+
89+
/**
90+
* @return the minimum chunk size in bytes
91+
*/
92+
public long getMinChunkSize() {
93+
return minChunkSize;
94+
}
95+
96+
/**
97+
* @return the maximum chunk size in bytes
98+
*/
99+
public long getMaxChunkSize() {
100+
return maxChunkSize;
101+
}
102+
103+
/**
104+
* @return the normalization level of the rolling hash mask
105+
*/
106+
public int getNormLevel() {
107+
return normLevel;
108+
}
109+
110+
@Override
111+
public boolean equals(Object o) {
112+
if (this == o) {
113+
return true;
114+
}
115+
if (!(o instanceof CdcOptions)) {
116+
return false;
117+
}
118+
CdcOptions other = (CdcOptions) o;
119+
return minChunkSize == other.minChunkSize && maxChunkSize == other.maxChunkSize && normLevel == other.normLevel;
120+
}
121+
122+
@Override
123+
public int hashCode() {
124+
return Objects.hash(minChunkSize, maxChunkSize, normLevel);
125+
}
126+
127+
@Override
128+
public String toString() {
129+
return "CdcOptions{minChunkSize=" + minChunkSize + ", maxChunkSize=" + maxChunkSize + ", normLevel=" + normLevel
130+
+ '}';
131+
}
132+
133+
/**
134+
* @return a builder holding the default options
135+
*/
136+
public static Builder builder() {
137+
return new Builder();
138+
}
139+
140+
/** EXPERIMENTAL: Builds {@link CdcOptions}. */
141+
public static class Builder {
142+
private long minChunkSize = 256 * 1024L;
143+
private long maxChunkSize = 1024 * 1024L;
144+
private int normLevel = 0;
145+
146+
private Builder() {}
147+
148+
/**
149+
* Set the smallest chunk, in bytes.
150+
*
151+
* <p>The rolling hash is not updated until a chunk reaches this size, so no chunk is shorter
152+
* than it.
153+
*
154+
* @param minChunkSize the minimum chunk size in bytes
155+
* @return this builder for method chaining
156+
*/
157+
public Builder withMinChunkSize(long minChunkSize) {
158+
Preconditions.checkArgument(
159+
minChunkSize >= 0,
160+
"Invalid content defined chunking minimum chunk size (negative): %s",
161+
minChunkSize);
162+
this.minChunkSize = minChunkSize;
163+
return this;
164+
}
165+
166+
/**
167+
* Set the largest chunk, in bytes.
168+
*
169+
* <p>A new chunk starts whenever the current one reaches this size, whatever the rolling hash
170+
* says. Note that {@link ParquetProperties.Builder#withPageSize(int)} is a related but separate
171+
* limit on the size of a page <i>after</i> encoding: setting it below the maximum chunk size
172+
* does not reduce how well chunking deduplicates, but it does produce more, smaller pages.
173+
*
174+
* @param maxChunkSize the maximum chunk size in bytes
175+
* @return this builder for method chaining
176+
*/
177+
public Builder withMaxChunkSize(long maxChunkSize) {
178+
Preconditions.checkArgument(
179+
maxChunkSize > 0,
180+
"Invalid content defined chunking maximum chunk size (not positive): %s",
181+
maxChunkSize);
182+
this.maxChunkSize = maxChunkSize;
183+
return this;
184+
}
185+
186+
/**
187+
* Set the normalization level of the rolling hash mask.
188+
*
189+
* <p>Raising it makes a boundary more likely, which tightens the chunk size distribution around
190+
* the average and improves the deduplication ratio at the cost of more small pages; lowering it
191+
* does the reverse. Values outside {@code [-3, 3]} are not useful.
192+
*
193+
* @param normLevel the normalization level
194+
* @return this builder for method chaining
195+
*/
196+
public Builder withNormLevel(int normLevel) {
197+
this.normLevel = normLevel;
198+
return this;
199+
}
200+
201+
/**
202+
* @return the options
203+
* @throws IllegalArgumentException if the size envelope cannot produce a usable rolling hash
204+
* mask
205+
*/
206+
public CdcOptions build() {
207+
return new CdcOptions(this);
208+
}
209+
}
210+
}

0 commit comments

Comments
 (0)