Time-series databases ingest huge volumes of (timestamp, value) samples -- a metric scraped every 15 seconds, forever -- and most of that data is extremely repetitive: intervals between samples are usually constant, and values usually drift only slightly from one sample to the next. Facebook's "Gorilla" paper (which Prometheus's TSDB chunk encoding implements almost directly) exploits exactly that:

• Delta-of-delta encoding for timestamps: instead of storing each timestamp, store the DELTA between consecutive timestamps -- then take the delta of THAT (the "second derivative"). With a near-constant sample interval, the deltas themselves are all nearly equal, so the delta-of-delta is 0 (or very close to it) almost every time.
• XOR-based encoding for values: instead of storing each float, XOR its 64-bit IEEE-754 bit pattern against the PREVIOUS value's bit pattern. Slowly-changing metrics (a temperature, a memory gauge) have bit patterns that mostly agree between consecutive samples, so the XOR is mostly zero bits -- an unchanged value XORs to exactly 0.

float_to_bits/bits_to_float (given) convert a Python float to/from its 64-bit IEEE-754 bit pattern as an int. Implement:

• delta_of_delta_encode(timestamps) -> a list: [timestamps[0], timestamps[1] - timestamps[0], dod_2, dod_3, ...], where each dod_i (for i >= 2) is `(timestamps[i] - timestamps[i-1]) - (timestamps[i-1]
  • timestamps[i-2])`.
• delta_of_delta_decode(encoded) -> the original timestamps list, reversing the above.
• xor_encode(values) -> a list: [float_to_bits(values[0]), xor_1, xor_2, ...], where each xor_i (for i >= 1) is float_to_bits(values[i]) ^ float_to_bits(values[i-1]).
• xor_decode(encoded) -> the original values list, reversing the above (XOR is its own inverse: bits[i] = encoded[i] ^ bits[i-1]).
• encode_samples(samples) -> {"timestamps": ..., "values": ...}, splitting a list of (timestamp, value) tuples into the two streams above.
• decode_samples(encoded) -> the original list of (timestamp, value) tuples, reversing encode_samples.

Example

delta_of_delta_encode([1000, 1010, 1020, 1030])
# -> [1000, 10, 0, 0]   -- constant 10-unit interval compresses the
#    dod tail to all zeros

delta_of_delta_encode([1000, 1010, 1025, 1030])
# -> [1000, 10, 5, -10]  -- interval jumps from 10 to 15 to 5, so dod
#    is nonzero

xor_encode([98.6, 98.6, 99.1])
# -> [<bits of 98.6>, 0, <nonzero>]   -- repeating the exact same
#    value XORs to 0

Constraints

• Handle 0-, 1-, and 2-sample sequences: a 2-sample sequence has no delta-of-delta or XOR term YET (that needs a third sample) -- just [t0, t1-t0] / [bits0, xor1].
• xor_decode must reproduce values EXACTLY (bit-for-bit), not approximately -- XOR-ing 64-bit integer patterns is exact, unlike doing arithmetic on the floats themselves.

Real-world grounding

• Prometheus's TSDB XOR chunk encoding: tsdb/chunkenc/xor.go -- look at xorAppender.Append's dod (delta-of-delta) computation for timestamps, and writeVDelta's leading/trailing-zero-count bucketing for values -- the same XOR-against-the-previous-value idea this exercise implements, taken one step further into an actual bitstream.

Real chunk encoders go further than this exercise: they don't store each dod/xor value as a full machine word -- they bit-pack them, using a single control bit to signal "dod == 0" (near-free), a handful of size-bucketed control bits for a nonzero dod (14/17/20/64-bit buckets, matching how large a delta swing typically gets), and a similar leading-zero-count/trailing-zero-count scheme to shrink an XOR'd value down to just its "meaningful" middle bits. The delta-of-delta and XOR transforms in this exercise are exactly what create the near-all-zero data those bit-packing schemes then squeeze out.