The general advice with Protobuf integer types is to just use int64 and to compress your protos if you’re hurting for bandwidth or disk space. But when neighboring values are close together, storing the differences between them can make the data much smaller, even with compression. This is called delta encoding.

The concept

Varints, as you may know, vary their wire size depending on the value being encoded. So small numbers take up fewer bytes on the wire. The general idea with delta encoding is to exploit the fact that changes (deltas) typically have a smaller magnitude than the value itself. That’s all you need to understand the concept.

There’s a small wrinkle to smooth out before digging into real uses of this technique. There’s a quirk with int64 that causes any negative numbers to cost the full 10 bytes. There’s another, slightly different, type called sint64 that treats lower magnitude negatives similar to how it treats lower magnitude positive numbers. So use sint64 if your deltas can be negative. If you know that they can never be negative, int64 is just fine.

Here’s what it would look like encoding geographical latitudes with delta coding compared with just using the full value for every “tick”:

Four consecutive latitudes encoded two ways. Stored as absolute values, each one is a five-byte varint, twenty bytes in total. Stored as one absolute baseline plus deltas, the baseline still costs five bytes but the three deltas cost two, one, and one, nine bytes in total. Segment widths are proportional to their byte counts. ABSOLUTE VALUES · 20 BYTES 515,074,000 515,074,120 515,074,080 515,074,143 5 B 5 B 5 B 5 B BASELINE + DELTAS · 9 BYTES 5 B 2 B 515,074,000 +120 -40 +63
Four consecutive latitudes encoded two ways. Stored as absolute values, each one is a five-byte varint, twenty bytes in total. Stored as one absolute baseline plus deltas, the baseline still costs five bytes but the three deltas cost two, one, and one, nine bytes in total. Segment heights are proportional to their byte counts. ABSOLUTE VALUES · 20 BYTES 5 B 5 B 5 B 5 B 515,074,000 515,074,120 515,074,080 515,074,143 BASELINE + DELTAS · 9 BYTES 5 B 2 B 515,074,000 +120 -40 +63

In this example, absolute values use 5 bytes each, while deltas use one or two bytes each after the first.

Prior art

This technique has been used “in the wild”. Here are three different places that delta encoding is used with protobufs.

OpenStreetMap PBF has stored nodes as DenseNodes since 2010, which are parallel packed sint64 arrays of coordinates, each value delta-encoded against the previous node.

Mapbox Vector Tiles uses repeated uint32 with delta encoding to represent a moving cursor on a grid. Interestingly, to support negative deltas in the uint32 field, ZigZag encoding is applied outside of protobuf.

Prometheus uses delta encoding for the integer bucket counts of native histograms. Note that these deltas are between neighboring buckets within a single histogram, not between samples over time.

The test case

The test case for this post is a fake 10,000-sample GPS trace of a car driving through London, recording a timestamp and coordinate pair every 10ms with slight jitter. It’s synthetic, so treat the numbers as a demonstration of the technique rather than a promise. Sampling frequency and jitter directly influence how much you save.

To show how effective the delta encoding technique is, the benchmark includes two alternatives that use absolute values, as you might do by default: one with int64 and one with sint64. Both use the same parallel packed arrays as the delta schema, just with absolute values in place of deltas, so the comparison measures the encoding difference and nothing else.

Here is the delta schema:

edition = "2024";
 
package bench.delta.v1;
 
message Track {
  // Absolute baseline for the first sample. Without these three fields the
  // rest of the message is undecodable.
  int64 first_timestamp_ms = 1;
  int64 first_latitude_e7 = 2;
  int64 first_longitude_e7 = 3;
 
  // Offsets from the previous sample, one entry per sample after the first.
  // The clock only moves forward, so timestamp deltas stay int64. Coordinates
  // move in both directions, so those deltas are sint64.
  repeated int64 timestamp_delta_ms = 4;
  repeated sint64 latitude_delta_e7 = 5;
  repeated sint64 longitude_delta_e7 = 6;
}

The first_* fields act like keyframes. Without an initial anchor point, the deltas only tell you how far the car moved in each direction, not where in the world it was at the time.

The results

Here are the bytes per sample (with timestamps in milliseconds). Both charts are on the exact same scale so you can see the difference.

Bytes per sample, raw and gzipped: compression closes the sint64 gap but not the delta gap

Look at that gzip chart! Normal compression almost completely wipes out the difference between int64 and sint64, which reinforces the advice in Protobuf Tip #10.

But check out the delta encoding schema. It absolutely crushes int64 and sint64, clocking in at just 1.44 bytes per sample with gzip.

The tradeoff

So, should you use this everywhere? No. Usually you don’t need this.

The wire format savings aren’t free: the complexity moves into your application code. Your decoder has to reconstruct every value by accumulating deltas from the start of the message, so jumping straight to sample 5,000 means summing the 4,999 deltas before it (or adding more anchor fields as keyframes). And since the values live in parallel arrays, your encoder has to keep them aligned: a skipped or extra entry in one array silently corrupts every sample after it.

Delta encoding is really only worth it when you have massive, ordered lists of integers that don’t shift a significant amount. If gzip gets you most of the way there, save yourself the trouble and stick to the simple schema.

For standard request and response RPCs, this extra logic is almost never worth it. But if you are dealing with firehoses of traces, GPS coordinates, telemetry counters, or other massive number sequences, it can save you a lot in bandwidth and storage. In this little test, gzip managed to level the playing field between the standard integer types, but delta encoding was still able to compress the payload by another 67%.