Generate snapshots programmatically

[tisonkun]

Yeah. I think it's technically reasonable to have snapshots for tests. The key point here is how these snapshots get generated, can we reproducibly make them? And how we can modify/update them.

In other words, how the snapshots in datasketches-go gets generated originally?

Originally posted by @tisonkun in #1 (comment)

---

@freakyzoidberg told me there are some "tests" which generate those files in the go repository (https://github.com/apache/datasketches-go/blob/f7bc4b1db865c2dd1be9134d8a61eeb8bc24b1c6/hll/hll_sketch_serialization_test.go#L29) I assumed it's similar for the other implementations.

Originally posted by @notfilippo in #1 (comment)

---

Great! Then at least we can reuse the Go logic to generate Go snapshot. But I can see that it would require extra engineer effort so I won't block this PR by such potential improvement to avoid (mysterious) binaries as much as possible.

For the Java and C++ snapshot, perhaps @leerho and @AlexanderSaydakov can give some inputs here.

Originally posted by @tisonkun in #1 (comment)

---

CPP / Java and Go repo do have some test that generate and cross-test the synopsis from the other repos.

It's vey much convention and quite manual - and as Lee hinted in the other thread we didn't really think about how to scale this with more language (very much M*N issue)

you can find the Java HLL x-check here and the cpp ones for ser/de there

Also worth noting that not all synopsis are guaranteed to have byte for byte equality (they'll behave the same, logically equivalent from a behavior aspect and are fully serializable/deserializable between language - but not all provide guarantee of idempotency generation when looking at raw bytes - tldr not all rng are seeded - they could I suppose though)

Originally posted by @freakyzoidberg in #1 (comment)

---

very much M*N issue

Not quite. Each language can implement its own serialized snapshots, and any language should leverage the existing snapshots while patching its own.

We can have a shared snapshot library like shared proto definitions in other projects.

Anyway, this is another topic, so I'll open a new issue to track it.

Originally posted by @tisonkun in #1 (comment)

[tisonkun]

This may not be a datasketches-rust specific issue, but for all the DataSketches impls.

However, we don't have such a shared repo now, and the main repo (https://github.com/apache/datasketches) is a portal only.

Perhaps it'd be better to discuss it on the mailing list. But it happens to be a GitHub issue for easily bringing up previous discussions from the PR.

I'll try to reproduce the Go snapshots generation standalone these days.

[tisonkun]

C++ and Java have GitHub Workflows to generate snapshots on the fly:

https://github.com/apache/datasketches-java/blob/37edd8c9898f8f073aaafad7097cb0949eb84c85/.github/workflows/check_cpp_files.yml

https://github.com/apache/datasketches-cpp/blob/7bb979d3ef8929e235bcd22d67579e1f695f6ecd/.github/workflows/serde_compat.yml

But it seems not quite complete.

[tisonkun]

For Java, the comand is:

mvn test -P generate-java-files
cp serialization_test_data/java_generated_files/*.sk java

Logics are grouped by generate_java_files test group.

For C++, the command is:

# Configure C++ build
pushd build
cmake .. -DGENERATE=true
popd

# Build C++ unit tests
cmake --build build --config Release

# Run C++ tests
cmake --build build --config Release --target test

# Make dir
mkdir -p serialization_test_data/cpp_generated_files

# Copy files
cp cpp/build/*/test/*_cpp.sk serialization_test_data/cpp_generated_files

[leerho]

As I mentioned in the Discussions thread , we don't claim to have the perfect solution to the cross-language testing. How this evolved is historical. We first had two languages, C++ & Java when we setup the current scheme, Then we added Python, and later Go and now Rust. We clearly need a better solution!

Having a test repo that holds a common set of snapshots seems quite logical. It would only be a dependency for tests, so it wouldn't burden the runtime size of any of the language component libraries.

There are some issues to think about.

• Our serialization format is designed for compactness and speed. Compactness is critical because there can be millions of these sketch images in the memory of large systems and any structural space overhead in these images will quickly add up. Speed is important because we want to be able to serialize and deserialize quickly. In some cases we can merge two sketch images without having to deserialize them -- by reading the images directly.

• For all the sketches the first 3 bytes of the serialized image are the same:

  • PreLongs (or PreInts) (byte) gives the size of the metadata region of the image.
  • SerVer (byte) This is the serialization version of the image structure. This has remained constant for many years, as our goal is to be able read any sketch with a prior serialization version for backwards compatibility.
  • FamID (byte) This is a simple unique sequence number for each of the sketch families. The the enum for this is in the DS-java repo, and so far we have 21 sketch families. There can be multiple types of sketches in one family, but it is up to the deserializers in each family to figure that out.
  • The remainder of the first 8 bytes are core values that almost every sketch needs. For example, K, flags, and seedHash even if the sketch is empty.

• Some of our Sketches (e.g., KLL, Classic Quantiles, REQ) are purely probabilistic in nature, which means that given the same data in exactly the same order will produce a slightly different result -- but it be within the confidence interval with a specified probability defined by the configuration of the sketch. For these sketches it is critical that they not be modified to produce a deterministic result!

  • For these sketches, the accuracy of the sketch depends on injecting randomness into the algorithm. If you defeat that, we can no longer guarantee what the error properties of the sketch will be -- and it will likely be biased in an unknown direction by an unknown amount.
  • Because of this our tests do not depend on a byte-for-byte comparison of the sketch images. We test against the probability distribution that the sketch is within bounds of the desired result.

[leerho]

There are two repos we have that aren’t used that we could leverage to keep our snapshot files to be leveraged for all of our languages: datasketches and datasketches-common.

[leerho]

I envisioned DS-common as a place to keep common functions used by multiple sketches, for example, hash functions and certain math functions that are useful for sketches, but not generally available in math libraries (or when implemented, may be too generic). This same repo could hold the *.rs snapshot files for testing.

Generally, I don't like adding dependencies for all kinds of reasons, but I don't like duplicating code either. So I have mixed feelings about this.

Thoughts?

[leerho]

Another idea would be to just choose a language as the "master generator of the *.rs snapshot files" (e.g. Java)-- since the files themselves should be language and platform independent. And then every language would run a script that loads (e.g. Java) and has java create the files dynamically and then test them against the local language. This is what C++ does today. In this model, Java wouldn't do the reverse, otherwise we end up with the n^2 situation -- what we potentially have now.

[tisonkun]

Cool.

I think we can start prototyping in datasketches-common (I guess you mean https://github.com/apache/datasketches-java-common? Would have a better name, although).

apache/datasketches would be the portal repo and we shouldn't put other casual dev artifacts there.

Roughly, I'm considering having a script to generate snapshots of multiple languages, as we do in this repo now. Then we may check the snapshots in, and may or may not run compatibility tests there.

end up with the n^2 situation

Each languages (not binding like datasketches-python) can provide a way to generate snapshots and optionally test compatibility with other langauges.

So the producing side is O(n), while the testing part can be optionally O(n^2) but for each language, O(n).

Anyway, a prototype can be more expressive and see if that works for us.