This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch docs/numbered-rfcs in repository https://gitbox.apache.org/repos/asf/datasketches-tck.git
commit 2db78be5b19a786c125ce643e7524d996f8b6afe Author: tison <[email protected]> AuthorDate: Wed Nov 18 17:31:16 2026 +0800 docs: organize TCK designs as numbered RFCs Signed-off-by: tison <[email protected]> --- README.md | 18 +--- docs/serialization-snapshots.md | 16 +--- rfcs/0001-serialization-snapshots.md | 32 +++++++ .../0021-count-min-format.md | 100 +++++++++++---------- rfcs/README.md | 25 ++++++ 5 files changed, 112 insertions(+), 79 deletions(-) diff --git a/README.md b/README.md index b234b9b..e2a2a56 100644 --- a/README.md +++ b/README.md @@ -1,22 +1,8 @@ # Apache® DataSketches™ Technology Compatibility Kit -This repository provides a Technology Compatibility Kit for the DataSketches library. +The Technology Compatibility Kit (TCK) provides [serialized sketch snapshots](serialization_test_data/) and generators so DataSketches implementations can test compatibility across languages. -A Technology Compatibility Kit (TCK) is a suite of tests that checks a particular DataSketches implementation for compatibility. - -## Overview - -### Serialization snapshots - -The structure (or image) of a serialized sketch is independent of the language from which it was created. - -This repository contains snapshots of serialized sketches, which a particular DataSketches implementation should be able to read. Snapshot generators are also included. - -See [Serialization snapshots](docs/serialization-snapshots.md) for the repository design, the snapshot generation commands, and the maintainer workflow for updating the corpus from an upstream DataSketches implementation. - -Format specifications: - -- [Count-Min sketch, serialization format version 2](docs/count-min-format.md) +The [RFC index](rfcs/README.md) lists the designs and format specifications used by the TCK. The [snapshot maintenance guide](docs/serialization-snapshots.md) explains how to regenerate, update, and check the corpus. ## Contribute diff --git a/docs/serialization-snapshots.md b/docs/serialization-snapshots.md index 4179642..a82643d 100644 --- a/docs/serialization-snapshots.md +++ b/docs/serialization-snapshots.md @@ -15,13 +15,9 @@ limitations under the License. --> -# Serialization snapshots +# Maintaining serialization snapshots -The serialization corpus is a compatibility boundary between DataSketches implementations. Each directory `serialization_test_data/<language>_generated_files` contains sketches produced by one implementation and intended to be read and validated by the others. - -The DataSketches implementation repositories use the same `serialization_test_data/<language>_generated_files` layout for their cross-language fixtures, so a TCK checkout can serve directly as an implementation's test data root, and moving files between the TCK and an implementation is a plain copy. - -The `main` branch of this repository publishes self-tested snapshot updates from every source language when the file set or stable contents change. Each language validates its own snapshots with its generators and round-trip tests before they reach the TCK, so a snapshot set that passes there is ready to publish. Whether each implementation can read the others' snapshots is then answered by running its cross-language tests against the latest set, not by reviewing the `.sk` files by hand. +[RFC 0001](../rfcs/0001-serialization-snapshots.md) describes how DataSketches implementations use the shared snapshot corpus for cross-language tests. `config.toml` records the repository and exact commit each snapshot directory was generated from, so any TCK commit remains reproducible: @@ -126,14 +122,6 @@ Mise supplies Go, CMake and CTest, Java, Maven, and Rust. Git is required for ev Check accepts `cpp`, `go`, `java`, `rust`, or `all` and is always read-only. Update defaults to all languages at `HEAD`; specifying a language limits the update to that source, and a second argument selects its revision. The former `snapshots sync` command is replaced by `snapshots update <language> <recorded-commit>`. -## Use the corpus from an implementation - -An implementation consumes the `.sk` files as test fixtures. Its compatibility tests should load snapshots produced by the other source languages, deserialize each supported sketch family, and assert observable results with tolerances appropriate to that algorithm. - -This repository centralizes the fixture corpus and source-side generation. Consumer tests remain in the individual DataSketches implementation repositories. - -By default, an implementation should test against the latest snapshot set on `main`. A failure then shows exactly which source language and sketch disagree, as early as possible. To keep a release or a CI run from changing underneath it, an implementation can instead pin a specific TCK commit. - ## Review policy for probabilistic snapshots Some upstream generators contain randomness, so byte-for-byte reproduction is not a valid invariant for every file. The stability policy is source-specific because upstream implementations do not always seed or exercise an algorithm in the same way. diff --git a/rfcs/0001-serialization-snapshots.md b/rfcs/0001-serialization-snapshots.md new file mode 100644 index 0000000..34e384f --- /dev/null +++ b/rfcs/0001-serialization-snapshots.md @@ -0,0 +1,32 @@ +<!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> + +# RFC 0001: Serialization snapshots + +[PR #1](https://github.com/apache/datasketches-tck/pull/1) introduced the snapshot corpus and its generators so that DataSketches implementations can test whether they read each other's serialized sketches. + +## Publishing snapshots + +Each directory in [`serialization_test_data/`](../serialization_test_data/) contains `.sk` files produced by one implementation. The TCK and the implementation repositories share the `serialization_test_data/<language>_generated_files` layout introduced in [PR #14](https://github.com/apache/datasketches-tck/pull/14), so a TCK checkout can serve directly as an implementation's test data root. + +Each source implementation validates its own snapshots with its generators and round-trip tests. The TCK publishes the resulting files on `main` and records the upstream repository and exact source commit for each language in [`config.toml`](../config.toml). The [snapshot maintenance guide](../docs/serialization-snapshots.md) describes how to update the corpus and check it against those pins. + +## Testing an implementation + +Cross-language tests live in the consuming implementation. They load snapshots produced by the other languages, deserialize each supported sketch family, and assert observable results with tolerances appropriate to that algorithm. + +By default, an implementation tests against the latest corpus on `main`, a policy adopted in [PR #15](https://github.com/apache/datasketches-tck/pull/15). A failure then identifies which source language and sketch disagree with the reader. An implementation can pin a TCK commit to run a release or CI build against a fixed set of fixtures. diff --git a/docs/count-min-format.md b/rfcs/0021-count-min-format.md similarity index 69% rename from docs/count-min-format.md rename to rfcs/0021-count-min-format.md index 77896c6..595a1b4 100644 --- a/docs/count-min-format.md +++ b/rfcs/0021-count-min-format.md @@ -15,7 +15,9 @@ limitations under the License. --> -# Count-Min sketch: serialization format, version 2 +# RFC 0021: Count-Min sketch serialization format, version 2 + +Originating pull request: [#21](https://github.com/apache/datasketches-tck/pull/21). **Status:** adopted. The design was agreed by lazy consensus in [Discussion #18](https://github.com/apache/datasketches-tck/discussions/18), which closed on 2026-10-25. This spec was posted there on 2026-11-02, and no objections were raised by the 2026-11-09 deadline. @@ -25,29 +27,29 @@ Version 2 differs from version 1 only in the serial version byte and in the hash ## 1. Parameters -| Parameter | Type | Valid range | -|---|---|---| -| `numHashes` (rows) | unsigned 8-bit | 1 to 127 (Java and Go store it as a signed byte) | -| `numBuckets` (columns) | unsigned 32-bit | at least 3, and `numHashes × numBuckets < 2^30` | -| `seed` (base seed) | 64-bit | any; the library default is 9001 | +| Parameter | Type | Valid range | +|------------------------|-----------------|--------------------------------------------------| +| `numHashes` (rows) | unsigned 8-bit | 1 to 127 (Java and Go store it as a signed byte) | +| `numBuckets` (columns) | unsigned 32-bit | at least 3, and `numHashes × numBuckets < 2^30` | +| `seed` (base seed) | 64-bit | any; the library default is 9001 | ## 2. Byte layout All multi-byte fields are little-endian. -| Byte offset | Size | Field | Value | -|---:|---:|---|---| -| 0 | 1 | preamble longs | 2 | -| 1 | 1 | serial version | **2** | -| 2 | 1 | family ID | 18 (Count-Min) | -| 3 | 1 | flags | bit 0: `IS_EMPTY`; other bits 0 | -| 4 | 4 | unused | 0 | -| 8 | 4 | `numBuckets` | unsigned 32-bit | -| 12 | 1 | `numHashes` | unsigned 8-bit | -| 13 | 2 | seed hash | the standard DataSketches 16-bit seed hash of `seed`, as used by Theta; 9001 gives `0x93CC` | -| 15 | 1 | unused | 0 | -| 16 | 8 | total weight | signed 64-bit; present only if not empty | -| 24 | 8 × `numHashes` × `numBuckets` | counters | signed 64-bit each; present only if not empty | +| Byte offset | Size | Field | Value | +|------------:|-------------------------------:|----------------|---------------------------------------------------------------------------------------------| +| 0 | 1 | preamble longs | 2 | +| 1 | 1 | serial version | **2** | +| 2 | 1 | family ID | 18 (Count-Min) | +| 3 | 1 | flags | bit 0: `IS_EMPTY`; other bits 0 | +| 4 | 4 | unused | 0 | +| 8 | 4 | `numBuckets` | unsigned 32-bit | +| 12 | 1 | `numHashes` | unsigned 8-bit | +| 13 | 2 | seed hash | the standard DataSketches 16-bit seed hash of `seed`, as used by Theta; 9001 gives `0x93CC` | +| 15 | 1 | unused | 0 | +| 16 | 8 | total weight | signed 64-bit; present only if not empty | +| 24 | 8 × `numHashes` × `numBuckets` | counters | signed 64-bit each; present only if not empty | - A sketch is empty when its total weight is 0. An empty image is exactly 16 bytes and has `IS_EMPTY` set. - A non-empty image is `24 + 8 × numHashes × numBuckets` bytes. @@ -77,10 +79,10 @@ Sections 4.4 to 4.6 are placeholders for input rules that apply to every DataSke ### 4.1 Integers -| Item type | Bytes hashed | -|---|---| -| 64-bit integer, signed or unsigned | 8 bytes, little-endian, two's complement | -| Narrower integer | widened to 64 bits first (sign-extended if signed), then as above | +| Item type | Bytes hashed | +|------------------------------------|-------------------------------------------------------------------| +| 64-bit integer, signed or unsigned | 8 bytes, little-endian, two's complement | +| Narrower integer | widened to 64 bits first (sign-extended if signed), then as above | ### 4.2 Strings @@ -143,30 +145,30 @@ These were computed with the DataSketches Java `XxHash64`. The bucket results fo ### 7.1 XXH64 -| Input | Seed | XXH64 | -|---|---:|---| -| empty | 0 | `0xEF46DB3751D8E999` | -| `"a"` | 0 | `0xD24EC4F1A98C6E5B` | -| `"abc"` | 0 | `0x44BC2CF5AD770999` | +| Input | Seed | XXH64 | +|---------|-----:|----------------------| +| empty | 0 | `0xEF46DB3751D8E999` | +| `"a"` | 0 | `0xD24EC4F1A98C6E5B` | +| `"abc"` | 0 | `0x44BC2CF5AD770999` | ### 7.2 Row seeds -| Base seed | Row 0 | Row 1 | Row 2 | -|---:|---|---|---| -| 9001 | `0xD71D64972584A288` | `0xEFE8454A6499F311` | `0x23819BE21B1B1D9E` | -| 42 | `0xB71B47EBDA15746C` | `0x9ED50FD59358D232` | `0xD19FE30002B9A3CD` | +| Base seed | Row 0 | Row 1 | Row 2 | +|----------:|----------------------|----------------------|----------------------| +| 9001 | `0xD71D64972584A288` | `0xEFE8454A6499F311` | `0x23819BE21B1B1D9E` | +| 42 | `0xB71B47EBDA15746C` | `0x9ED50FD59358D232` | `0xD19FE30002B9A3CD` | ### 7.3 Item hashes and buckets Base seed 9001, `numBuckets` = 1000. Each cell shows `XXH64(item, rowSeed[i])` and the bucket. -| Item | Row 0 | Row 1 | Row 2 | -|---|---|---|---| -| integer 1 | `0x9578D22909AB6393` → 185 | `0x73BE69FFC52746B5` → 898 | `0xA16D5BA2EA9D92A9` → 4 | -| integer 9 | `0xE351D001EE0C0725` → 490 | `0x74AB8E217F6C0193` → 217 | `0x4E02535F97CE07D1` → 440 | -| integer -1 | `0x295F6FF9D5F0A170` → 256 | `0x693A5A4C04C19D72` → 641 | `0xC3095F604CF42A69` → 308 | -| integer `0x8000000000000000` | `0x69DD53CB2E1960EE` → 951 | `0xBE1283E430FCA711` → 0 | `0x62BD4CDD3889A7D5` → 298 | -| string `"apple"` | `0x0F686B647380AF74` → 130 | `0x25329624EF6A5FF6` → 747 | `0x501EE67250FD0E21` → 144 | +| Item | Row 0 | Row 1 | Row 2 | +|-----------------------------------------|----------------------------|----------------------------|----------------------------| +| integer 1 | `0x9578D22909AB6393` → 185 | `0x73BE69FFC52746B5` → 898 | `0xA16D5BA2EA9D92A9` → 4 | +| integer 9 | `0xE351D001EE0C0725` → 490 | `0x74AB8E217F6C0193` → 217 | `0x4E02535F97CE07D1` → 440 | +| integer -1 | `0x295F6FF9D5F0A170` → 256 | `0x693A5A4C04C19D72` → 641 | `0xC3095F604CF42A69` → 308 | +| integer `0x8000000000000000` | `0x69DD53CB2E1960EE` → 951 | `0xBE1283E430FCA711` → 0 | `0x62BD4CDD3889A7D5` → 298 | +| string `"apple"` | `0x0F686B647380AF74` → 130 | `0x25329624EF6A5FF6` → 747 | `0x501EE67250FD0E21` → 144 | | string `"été"` (UTF-8 `c3 a9 74 c3 a9`) | `0x38F345607F8C14EC` → 806 | `0x75787F10A22C78A7` → 491 | `0x43BEC0D845165366` → 163 | Several of these hashes have the top bit set, so an implementation that skips the shift or treats the hash as signed gets different buckets. @@ -213,7 +215,7 @@ Reading this image back with seed 9001 gives estimates of 10 for 1, 810 for 9 an ## 8. Cross-language test files -Each implementation generates the files below into its `serialization_test_data/<language>_generated_files` directory, as described in [Serialization snapshots](serialization-snapshots.md), and checks the files generated by the other languages. +Each implementation generates the files below into its `serialization_test_data/<language>_generated_files` directory, as described in [RFC 0001](0001-serialization-snapshots.md), and checks the files generated by the other languages. ### 8.1 Names and contents @@ -221,15 +223,15 @@ File names have the form `count_min_v2_<case>_<language>.sk`, where `<language>` Every file uses `numHashes` = 3 and `numBuckets` = 1000. -| Case | Seed | `N` | -|---|---:|---:| -| `n0` | 9001 | 0 (empty) | -| `n1` | 9001 | 1 | -| `n10` | 9001 | 10 | -| `n100` | 9001 | 100 | -| `n1000` | 9001 | 1000 | -| `n10000` | 9001 | 10000 | -| `seed42_n1000` | 42 | 1000 | +| Case | Seed | `N` | +|----------------|-----:|----------:| +| `n0` | 9001 | 0 (empty) | +| `n1` | 9001 | 1 | +| `n10` | 9001 | 10 | +| `n100` | 9001 | 100 | +| `n1000` | 9001 | 1000 | +| `n10000` | 9001 | 10000 | +| `seed42_n1000` | 42 | 1000 | For each `i` from 0 to `N - 1`, the sketch is updated twice: - with the 64-bit integer `i` and weight `i + 1`; diff --git a/rfcs/README.md b/rfcs/README.md new file mode 100644 index 0000000..fefa841 --- /dev/null +++ b/rfcs/README.md @@ -0,0 +1,25 @@ +<!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> + +# DataSketches TCK RFCs + +- [RFC 0001: Serialization snapshots](0001-serialization-snapshots.md) +- [RFC 0021: Count-Min sketch serialization format, version 2](0021-count-min-format.md) + +## Adding an RFC + +Each RFC takes its number from the pull request that first introduced the design. To propose a new RFC, open a pull request with `rfcs/0000-short-title.md`. Once the PR has a number, replace `0000` with the PR number padded to four digits, link to the PR in the RFC, and add the RFC to the list above. --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
