Documentation
¶
Overview ¶
Package chunk implements the zero-alloc value-column codecs (DESIGN.md §14 M0): delta-of-delta timestamps, Gorilla XOR float gauges, T64, dictionary, and scaled-decimal+nearest-delta. Each codec is an append-style Encode(dst []byte, ...) []byte over bitstream and is fuzzed for round-trip identity. Not yet implemented (M0 in progress; bitstream is the first foundation).
Index ¶
- func DecodeBytes(dst [][]byte, src []byte) ([][]byte, int, error)
- func DecodeFloats(dst []float64, src []byte) ([]float64, int, error)
- func DecodeFloatsDecimal(dst []float64, src []byte) ([]float64, int, error)
- func DecodeIntsT64(dst []int64, src []byte) ([]int64, int, error)
- func DecodeTimestamps(dst []int64, src []byte) ([]int64, int, error)
- func EncodeBytes(dst []byte, vals [][]byte) []byte
- func EncodeBytesBlob(dst, blob []byte, offsets []int32) []byte
- func EncodeBytesRaw(dst []byte, vals [][]byte) []byte
- func EncodeBytesRawBlob(dst, blob []byte, offsets []int32) []byte
- func EncodeFloats(dst []byte, vals []float64) []byte
- func EncodeFloatsDecimal(dst []byte, vals []float64, precisionBits uint8) []byte
- func EncodeIntsT64(dst []byte, vals []int64) []byte
- func EncodeTimestamps(dst []byte, ts []int64) []byte
- func EncodeU128(dst []byte, vals []U128) []byte
- func IsEOF(err error) bool
- type Codec
- type DecimalDecoder
- type DictColumn
- type DictEncoder
- type FloatDecoder
- type GorillaDecoder
- type TsCursor
- type TsDecoder
- type U128
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DecodeBytes ¶
DecodeBytes decodes a dictionary-encoded column from src into dst. Returned byte slices alias src.
func DecodeFloats ¶
DecodeFloats decodes a Gorilla XOR encoded float64 column from src into dst.
func DecodeFloatsDecimal ¶
DecodeFloatsDecimal decodes a scaled-decimal + nearest-delta encoded float64 column.
func DecodeIntsT64 ¶
DecodeIntsT64 decodes a T64-encoded int64 column from src into dst.
func DecodeTimestamps ¶
DecodeTimestamps decodes a DoD-encoded timestamp column from src into dst (growing it as needed) and returns the result with the number of source bytes consumed.
func EncodeBytes ¶
EncodeBytes appends a dictionary-encoded []byte column to dst and returns the extended slice (DESIGN.md §6, §14 M0).
It uses a pool.ByteIntMap (xxh3-based open-addressing hash table) instead of Go's map[string]int: xxh3 is faster than the runtime's string hash, and []byte keys avoid the string-conversion allocation on every lookup. For low-cardinality columns (≤256 distinct), each row id is 1 byte.
Layout: [uvarint rows] [1 byte flag] [payload]
flagDict payload: [uvarint dictSize] [dict entries: per entry uvarint len + bytes] [row ids: 1 byte each if dictSize ≤ 256, else 2 bytes big-endian each]
flagFlat payload: per row [uvarint len]bytes (the flat fallback for >65536 distinct).
For repeated encodes of many column batches, prefer a DictEncoder: it keeps the hash table and scratch slices cache-warm across calls instead of paying the sync.Pool Get/Put on each call.
func EncodeBytesBlob ¶ added in v0.25.0
EncodeBytesBlob is EncodeBytes over the blob+offsets column form (cell i is blob[offsets[i]:offsets[i+1]]; len(offsets) == rows+1, offsets[0] == 0). The output is byte-identical to EncodeBytes over the equivalent [][]byte, without materializing a view per row.
func EncodeBytesRaw ¶ added in v0.2.0
EncodeBytesRaw encodes a byte-string column without a dictionary (CodecBytesRaw): when every value shares one length it writes a single shared width followed by the values back-to-back (the fixed-width form, ideal for id columns); otherwise it falls back to the same length-prefixed inline layout as the dictionary codec's flat fallback. The output is a self-describing bytes-column stream that DecodeBytes and DecodeBytesDict read directly.
Layout: [uvarint rows] [1 byte flag] [payload]
flagFixed payload: [uvarint width] [rows × width bytes] flagFlat payload: per row [uvarint len][bytes]
func EncodeBytesRawBlob ¶ added in v0.25.0
EncodeBytesRawBlob is EncodeBytesRaw over the blob+offsets column form (see EncodeBytesBlob); the output is byte-identical to EncodeBytesRaw over the equivalent [][]byte.
func EncodeFloats ¶
EncodeFloats appends a Gorilla XOR encoded float64 column to dst and returns the extended slice (DESIGN.md §6, §14 M0; Prometheus/Gorilla-style).
Layout: [uvarint rows] [bitstream payload]:
row 0: raw64(Float64bits(v0)) // 64 raw bits, MSB-first
row 1+: xor-delta(v_n, v_{n-1}) // per the 3-case prefix below
The XOR control-bit cases (delta = Float64bits(new) XOR Float64bits(prev)):
0b0 → delta == 0, value unchanged (1 bit) 0b10 + M bits → reuse prev leading/trailing, M = 64-leading-trailing 0b11 + 5b lead + 6b sig + S bits → new leading/trailing, S = sig (0→64 sentinel)
Leading-zero count is clamped to 31 (5-bit field). The significant-bit count is stored in 6 bits; 0 is a sentinel meaning 64 (when leading==trailing==0). The meaningful XOR bits are stored right-shifted by trailing (the trailing zeros are dropped and re-shifted on decode).
func EncodeFloatsDecimal ¶
EncodeFloatsDecimal appends a scaled-decimal + nearest-delta encoded float64 column to dst (DESIGN.md §6, §14 M0; VictoriaMetrics-style). precisionBits controls the lossiness: 64 = lossless (no bit zeroing), <64 = lossy (zeros trailing low bits of deltas so the varint stream is ZSTD-compressible, reaching ~0.4–0.8 B/point).
Layout: [uvarint rows] [varint exponent] [uvarint precisionBits]
[zigzag-varint v0] [zigzag-varint delta1] ... [zigzag-varint deltaN-1]
Pipeline:
- Convert each float64 to a scaled int64 with a shared exponent e: f ≈ v * 10^e. The mantissa is minimized (trailing decimal zeros stripped into e).
- Compute first differences: d_n = v_n - v_{n-1}.
- If precisionBits < 64, zero the trailing (originBits - precisionBits) low bits of each delta (the "nearest-delta" step), with counter-reset hysteresis.
- Zigzag-varint encode the deltas; v0 is stored out-of-band.
With precisionBits=64 the round-trip is exact for integer-valued floats and near-exact (within float64 rounding) for fractional values. With precisionBits<64 the codec is deliberately lossy.
func EncodeIntsT64 ¶
EncodeIntsT64 appends a T64-encoded int64 column to dst (DESIGN.md §6, §14 M0; ClickHouse T64: bit-transpose + crop of unused high bits).
Layout: [uvarint rows] [8 bytes min] [8 bytes max] [transposed valuable bits]
The valuable-bit count is numBits = 64 - clz(min ^ max). If min == max (numBits==0), only the header is stored (constant column). Otherwise the values are processed in blocks of 64: each block is transposed so that bit j of all 64 values sits in a single uint64, and only the lowest numBits transposed rows are emitted (the high zero bits are cropped). On decode the cropped high bits are restored by OR-ing the common high prefix (min & ~((1<<numBits)-1)).
This codec is lossless. It is a preprocessor: the output is designed to be fed to a general compressor (ZSTD/LZ4) which benefits from the transposed, repetitive layout.
func EncodeTimestamps ¶
EncodeTimestamps appends a delta-of-delta encoded timestamp column to dst and returns the extended slice (DESIGN.md §6, §14 M0; Prometheus-style).
Layout: [uvarint rows] [bitstream payload]:
row 0: varint(t0) // signed zigzag varint, absolute timestamp row 1: uvarint(t1 - t0) // unsigned varint, first delta row 2+: dod(t_n) // delta-of-delta, 5-case prefix (see below)
The DoD bit layout (dod = tDelta_n - tDelta_{n-1}):
0b0 + 0 bits → dod == 0 (1 bit total) 0b10 + 14 bits → |dod| ≤ 2^13 (16 bits) 0b110 + 17 bits → |dod| ≤ 2^16 (20 bits) 0b1110 + 20 bits → |dod| ≤ 2^19 (24 bits) 0b1111 + 64 bits → escape, full int64 (68 bits)
The 14/17/20-bit values are stored as unsigned two's-complement and sign-extended on decode (values ≥ 1<<(n-1) are negative). The 64-bit escape is a raw int64 cast. Timestamps must be non-decreasing for optimal compression; decreasing timestamps still round-trip but produce 68-bit escapes.
func EncodeU128 ¶
EncodeU128 appends a run-length-encoded U128 column to dst (CodecID128). The id sort key of a metric part is long runs of one id (all of a series' samples are contiguous), so RLE stores a distinct id + run length per run — far smaller than storing every row.
Layout: [uvarint rows] then per run [u128 id big-endian][uvarint runLength].
Types ¶
type Codec ¶
type Codec uint8
Codec identifies a column encoding (DESIGN.md §6, §14 M0). It is stored in the column/part metadata so the decoder selects the right [Decode] function. Values are stable (persisted/wire-stable); never reorder.
const ( // CodecNone is the identity codec (raw values, no compression). CodecNone Codec = iota // CodecDoD is delta-of-delta for timestamps (Prometheus-style, ms-resolution // buckets 14/17/20/64). ~0 bits/sample at constant scrape interval. CodecDoD // CodecGorilla is Gorilla XOR for float64 values. ~1 bit/sample when consecutive // float values share leading/trailing zero structure. CodecGorilla // CodecDict is dictionary encoding for low-cardinality strings (≤256 distinct → // 1 byte/row). CodecDict // CodecT64 is ClickHouse T64: bit-transpose + crop for low-range int64 values. // Lossless; crops unused high bits, transposes 64-wide blocks. CodecT64 // CodecDecimal is VictoriaMetrics-style scaled-decimal + nearest-delta for // float64. Optionally lossy (precisionBits < 64): zeros trailing low bits of // deltas so the varint stream is ZSTD-compressible. CodecDecimal // CodecID128 is run-length encoding for 128-bit id columns ([U128]): a sorted id // column (e.g. the SeriesID sort key of a metric part) is long runs of one id, so // RLE stores a distinct id + run length per run. CodecID128 // CodecBytesRaw stores byte-string columns with no dictionary: a fixed-width block // (one shared length + values back-to-back) when every value is the same length, else // length-prefixed inline values. It is the right choice for high-cardinality, near-unique // id columns (e.g. a span id) where a dictionary is pure overhead. The decoder reads the // self-describing flag in the stream, so [DecodeBytes]/[DecodeBytesDict] handle it without // consulting the codec. CodecBytesRaw )
type DecimalDecoder ¶ added in v0.15.0
type DecimalDecoder struct {
// contains filtered or unexported fields
}
DecimalDecoder is a forward cursor over a scaled-decimal + nearest-delta encoded float64 column (EncodeFloatsDecimal).
func NewDecimalDecoder ¶ added in v0.15.0
func NewDecimalDecoder(src []byte) (*DecimalDecoder, error)
NewDecimalDecoder parses the column header and returns a cursor over its rows.
func (*DecimalDecoder) Len ¶ added in v0.15.0
func (d *DecimalDecoder) Len() int
Len returns the column's total row count.
func (*DecimalDecoder) Next ¶ added in v0.15.0
func (d *DecimalDecoder) Next() (float64, error)
Next decodes and returns the next value. It returns an IsEOF error after the last row.
func (*DecimalDecoder) Pos ¶ added in v0.15.0
func (d *DecimalDecoder) Pos() int
Pos returns the number of rows already decoded.
type DictColumn ¶
type DictColumn struct {
// Entries holds the unique values, indexed by id. In the flat-fallback form
// (IDWidth == 0) it instead holds one value per row, indexed directly by row.
Entries [][]byte
// IDs is the raw row-id array as stored: IDWidth bytes per row, big-endian. It is
// nil when IDWidth == 0.
IDs []byte
// IDWidth is the number of id bytes per row: 1 (dict ≤ 256 entries), 2 (larger
// dict), or 0 for the flat fallback where Entries is indexed by row directly.
IDWidth int
}
DictColumn is a decoded dictionary column in its split form: the unique entries plus the raw per-row id array, without the gather that materializes one []byte slice header per row. It is the output of DecodeBytesDict.
Profiling (see git history of the dict codec) showed 82% of DecodeBytes time was the gather loop `dst[i] = entries[idBuf[i]]`, which is pure store bandwidth and cannot be sped up in place. The split form defers that work to DictColumn.At, so a query that filters most rows on their id before projecting pays the gather only for surviving rows (DESIGN.md §7 fetch contract: decode only what the query touches).
All byte slices alias the source passed to the decode; they are valid only until that source is mutated or released. A DictColumn must not be retained past its source.
func DecodeBytesDict ¶
func DecodeBytesDict(src []byte) (*DictColumn, int, error)
DecodeBytesDict decodes a dictionary-encoded column (as written by EncodeBytes or DictEncoder.Encode) into its split form without gathering per-row values. It returns the column, the number of source bytes consumed, and any error. The returned DictColumn and all its byte slices alias src.
This allocates a fresh DictColumn; to decode repeatedly with zero allocations, reuse one column via DictColumn.DecodeBytes.
func (*DictColumn) At ¶
func (c *DictColumn) At(row int) []byte
At returns the value at row, as a view aliasing the decode source. row must be in [0, Len()).
func (*DictColumn) DecodeBytes ¶
func (c *DictColumn) DecodeBytes(src []byte) (int, error)
DecodeBytes decodes a dictionary-encoded column from src into c, reusing c's Entries backing array. It returns the number of source bytes consumed and any error. The decoded byte slices alias src.
func (*DictColumn) Len ¶
func (c *DictColumn) Len() int
Len reports the number of rows in the column. It is derived from the fields so a DictColumn can be constructed directly (e.g. a constant column: one entry, an all-zero IDs slice of the desired length, IDWidth 1).
type DictEncoder ¶
type DictEncoder struct {
// contains filtered or unexported fields
}
DictEncoder is a reusable dictionary-column encoder. Unlike the standalone EncodeBytes, it owns its pool.ByteIntMap and scratch slices for the lifetime of the encoder, so a sequence of DictEncoder.Encode calls keeps the hash table and id arrays cache-warm and skips the per-call sync.Pool Get/Put.
It is intended for the write path, where one goroutine encodes many column batches in a row. The zero value is not usable; create one with NewDictEncoder. Not safe for concurrent use; pool one per goroutine.
func NewDictEncoder ¶
func NewDictEncoder() *DictEncoder
NewDictEncoder returns a DictEncoder with a warm, empty hash table.
func (*DictEncoder) Encode ¶
func (e *DictEncoder) Encode(dst []byte, vals [][]byte) []byte
Encode appends a dictionary-encoded column for vals to dst and returns the extended slice. The output is byte-identical to EncodeBytes for the same input. Each call resets the encoder's internal state first, so Encode is self-contained.
func (*DictEncoder) Release ¶
func (e *DictEncoder) Release()
Release returns the encoder's hash table to the shared pool. After Release the encoder must not be used. Use it when an encoder's lifetime ends so the map can be reused by [NewByteIntMap]/EncodeBytes.
func (*DictEncoder) Reset ¶
func (e *DictEncoder) Reset()
Reset clears the encoder's retained state without freeing its backing arrays, so the next DictEncoder.Encode starts from a clean, cache-warm encoder. Encode resets implicitly, so calling Reset is only needed to drop references to a prior batch's input values held in the entries slice.
type FloatDecoder ¶ added in v0.15.0
FloatDecoder is the forward-cursor interface over a float64 column, regardless of codec.
func NewConstFloatDecoder ¶ added in v0.15.0
func NewConstFloatDecoder(n int, value float64) FloatDecoder
NewConstFloatDecoder returns a cursor that yields value for n rows.
func NewFloatDecoder ¶ added in v0.15.0
func NewFloatDecoder(codec Codec, src []byte) (FloatDecoder, error)
NewFloatDecoder returns a forward cursor over a float64 column encoded with codec, or an error if codec is not a float codec (CodecGorilla, CodecDecimal).
type GorillaDecoder ¶ added in v0.15.0
type GorillaDecoder struct {
// contains filtered or unexported fields
}
GorillaDecoder is a forward cursor over a Gorilla XOR encoded float64 column (EncodeFloats).
func NewGorillaDecoder ¶ added in v0.15.0
func NewGorillaDecoder(src []byte) (*GorillaDecoder, error)
NewGorillaDecoder parses the column header and returns a cursor over its rows.
func (*GorillaDecoder) Len ¶ added in v0.15.0
func (d *GorillaDecoder) Len() int
Len returns the column's total row count.
func (*GorillaDecoder) Next ¶ added in v0.15.0
func (d *GorillaDecoder) Next() (float64, error)
Next decodes and returns the next value. It returns an IsEOF error after the last row.
func (*GorillaDecoder) Pos ¶ added in v0.15.0
func (d *GorillaDecoder) Pos() int
Pos returns the number of rows already decoded.
type TsCursor ¶ added in v0.15.0
TsCursor is the forward-cursor interface over an int64 timestamp column (CodecDoD).
func NewConstTsCursor ¶ added in v0.15.0
NewConstTsCursor returns a cursor that yields value for n rows.
type TsDecoder ¶ added in v0.15.0
type TsDecoder struct {
// contains filtered or unexported fields
}
TsDecoder is a forward cursor over a delta-of-delta encoded timestamp column (EncodeTimestamps).
func NewTsDecoder ¶ added in v0.15.0
NewTsDecoder parses the column header and returns a cursor over its rows. bound is the byte length of the column stream (header + payload), used to bound-check the row count.
Source Files