This is a test harness to facilitate experimenting with compressing blocks of snowflake IDs. It creates a block of snowflake IDs, runs it through various processing pipelines, and outputs a CSV containing the size of the resulting byte block.
An example results file is included in this repository, along with some charts, to demonstrate the effectiveness of preconditioning the data before compressing it.
As written, the test harness will compare the Zlib, Snappy, LZ4, and Brotli compressors against each other.
Some of the defined pipelines use a bitwise transposition (similar to BitShuffle except performed over the entire block of IDs rather than on 8K chunks) to improve compressibility.
The rationale for doing this is that when you consider each bit in an ID value, there tends to be a high degree of coherence across all of the IDs in a block. The reasons for this:
- Timestamps within the defined epoch, even at millisecond resolution, will still have many common bits, when the ID values are sorted.
- In practice, the number of ID generators in use for a production system tends to be low, so most generated IDs will have similar values here.
- Similarly, unless a production system is generating IDs at an extremely high rate, most sequence numbers in the generated IDs will fall into one of a very small number of values.
The transposition technique improves compressibility by ~15% for Brotli, and by nearly 45% for LZ4, so it should be considered essential for use with performance-oriented compressors like LZ4 and Snappy.
Apart from sorting on the entire ID value, and performing the bitwise transpose, this harness also demonstrates the effectiveness of bucketing IDs by their generator ID and sequence number. This saves another ~4.5% space. When all of these techniques are combined, the performance-oriented LZ4 algorithm produces data whose size is within a couple of percentage points of what is produced by the comparatively slower Brotli algorithm.
These results suggest that, if you're transmitting large blocks of snowflake IDs, and want to use a performance-oriented compression algorithm like LZ4, preconditioning your data is the way to go. At a minimum, you should try to perform a BitShuffle-like transpose, and if you can spare the time to do so, use the generator ID and sequence number as additional sort keys.
The tuning parameters for the program are at the top of Program.fs. You can modify the snowflake ID format, parameters relating to the generation of timestamps and sequence numbers, the number of ID generators to support, the number of IDs to generate for each trial, and the number of trials to run.
By changing the test pipelines at the bottom of the file, you can also experiment with other data transformations, to test their effectiveness.
dotnet run
A results.csv file will be output in the current directory.
This harness uses a number of excellent open source libraries, which greatly simplified the experiment setup.
The MIT License (MIT)
Copyright (c) 2015 Rob Janssen
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
MIT License
Copyright (c) 2017 Milosz Krajewski
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.