Ch.15: Algorithms: How gzip Compression Actually Works

0:00 Say our service zips a log full of the same error line. The file gets much smaller, but the reader still needs every byte back. If even one changes, that's a production bug. What did gzip leave out? That repeating line gives gzip something it can point back to; that's how it can avoid spelling the same bytes twice. Take a tiny log: ABC, ABC, ABC. Nine characters, but the same three keep returning. Yeah, I could write the first ABC, then say, “Use that again.” But how does the decoder locate the earlier letters?

0:34 That leaves us a concrete job: turn “use that again” into an instruction the decoder can follow. Let's put bytes on that instruction. First, write the letters A, B, C literally. A literal is just a byte that the decoder should output as itself. Right. Before that first A, there was no past to copy. Now I'm sitting after C, and the next six letters start with the same ABCI've already written. So instead of six more literals, one possible encoding says: copy 6 bytes, starting 3 bytes back from the current output position.

1:09 Length six, distance three. Wait, really? My instinct was to look for six old bytes, but there are only three. That sounds illegal. It only sounds impossible if we picture a frozen source. Copying is sequential. Every byte it writes extends the source available to the next byte. The copy cursor can catch up to a byte we just wrote. So let's trace the copy, because those three old bytes have to supply six new ones. The output starts ABC. Copy A from three places behind the cursor. Now we have ABCA. Next copy B, then C. The output has six letters.

1:47 And the instruction still owes us 3 bytes. The read position now lands on the A we just copied. We repeat that three-letter sequence. Yes. We recover the exact input. If we'd frozen the source at the instruction's start, that last cycle would have had nothing to read. Oh, wow. The copy writes its own future source. So it's not a pointer to a frozen slice; the act of copying creates more source. That self-feeding copy has a boundary. I think a pointer to arbitrary file history would be hard to decode with bounded memory. How tight is the boundary?

2:23 Imagine an error line repeating hours after it first appeared. Could one match reach that distant copy? No. DEFLATE, the compressed stream inside gzip, limits a backward reference to roughly the last 30-2000 bytes of output. So if that line last appeared far earlier, this particular reference cannot reach it. The compressor might have to write it again before a later repeat can match. Okay, the window has a real edge. The window deliberately forgets older output, bounding what the decoder must retain.

2:54 It's a format rule, not a promise that every encoder finds every available match. Yeah. A valid stream can still miss a useful repetition. That's an encoder-quality issue, not a decoder failure. Now our toy has traded six literal letters for one length-and-distance instruction. Have we definitely saved space? We haven't counted the bytes needed to describe the instruction, the block, or the file wrapper. For a tiny input, I could easily spend more than I saved. We can test the warning first. With Python's gzip writer, our nine ABC letters become a 25-byte gzip file. The file grew, even though our copy instruction was perfectly valid as a teaching example. So the instruction isn't a promise about the finished file.

3:39 What could make it pay off at a larger scale? More repeated data can spread the block and wrapper cost over more bytes. The backward-reference move is called LZ77. DEFLATE also assigns bit patterns to the literals and matches it needs to transmit. Common symbols can get short patterns; uncommon ones get longer ones. So it isn't just hunting duplicates. It's also spending fewer bits on whatever turns up often in this block. That second move is Huffman coding. It doesn't discover repeats; it makes common tokens cheap to send, which means a match can cost fewer bits.

4:12 So what do those Huffman bits actually look like? For example, take an eight-symbol message where one letter appears four times. Give it four A's, two B's, and two C's. We could give every symbol a fixed 2-bit code: 16 data bits. Give A the 1-bit code zero. B gets one-zero, and C gets one-one. So the frequent A becomes cheap. Count the data bits: A costs four, B costs four, and the remaining pair costs four. 12 instead of 16. I can decode without ambiguity because no complete code begins another.

4:49 Zero finishes A; a leading one tells me to keep reading. That's what “prefix-free” buys us. But that 12-bit tally left out a line item. Hmm, the decoder needs the codebook too. Right, it needs to know which pattern means A. Those four saved data bits don't establish a smaller file after overhead. Now repeat ABC until the input is 900 bytes. In the same Python measurement, the finished gzip file is 31 bytes. We added 891 input bytes, but only six file bytes. Ah, the short file grew when every part was counted, while the long run gave repetition room to pay off.

5:30 Does every chunk need a brand-new codebook? No. A block is one chunk of coded output. It can use preset codes, describe new ones, or store bytes without Huffman coding. That leaves the encoder a choice for each block, not one universal codebook. Let's return to the decoder. Coded tokens don't directly spell out all nine letters. They tell it to write a literal byte or carry out a match instruction. It reads the first three letters, then decodes a length and a distance before it can perform our 6-byte copy.

6:02 Right. The format has one code set for literals and lengths, and another for distances. So I decode the next symbol, then either write its byte or follow its copy instruction. Got it. Huffman codes tell me which instruction I have. Once I've decoded it, the same growing-output copy reconstructs the repeated letters. Now that DEFLATE has built the coded data, what makes the file dot gee zee instead of just raw DEFLATE data? gzip is the surrounding file format. It starts with a header that identifies the format and compression method, carries the DEFLATE data, then ends with a trailer.

6:38 So the wrapper costs extra bytes. What does its trailer record? A checksum calculated from the original bytes, and their size. A reader can compare those with the bytes it rebuilt, catching many accidental errors. But a checksum isn't a signature. Someone can change the contents and recompute the value. During an incident, that check can flag corruption, not prove who wrote the file. Let's reverse the trip. A reader recognizes the gzip header and finds the inner DEFLATE data. It decodes the Huffman symbols in each block.

7:09 A literal writes a byte. A length plus distance copies bytes from what the decoder has already produced, one at a time. Our ABC example comes back exactly. Then a reader may check the trailer against the rebuilt data. The gzip specification lets a decoder skip some of those checks, so if validation matters, check what your tool actually does. Okay. The file doesn't need a dictionary of every original string. Its instructions rebuild the output, and the decoder can reuse bytes as it writes them. That leaves a separate question: was the new file any smaller?

7:43 But exact reconstruction doesn't guarantee fewer bytes. For example, an API owner tests gzip on the 9-byte string health equals OK before rolling it out to the health endpoint. The Python test turns it into 29 bytes; every probe would ship 20 extra bytes before transport details. She says, “Our compression setting is broken. Turn it up.” No, the compressor worked. She'd spend CPU to send a larger response. We'd pay twice to send more. For that tiny response, I'd skip gzip. The long repeating log is different: it fell to just over 30 bytes in our test.

8:19 Data already compressed by another format may resist both tricks. That leaves a question for the log: could we shrink it further without hurting the service? So for that log, maybe. Take a service that generates it on every request: when it compresses, CPU work can add latency to the hot path. Then the level dial becomes a trade-off. Right. Turning the level up can spend more encoder time searching for smaller output. The decoder still reads DEFLATE; it doesn't need a new algorithm. On a slow link, a smaller result might repay that CPU time.

8:52 On a busy service's hot path, the added work may buy nothing. I'd compare final bytes, compression time, and memory on representative inputs. Yeah, the same format can earn its CPU cost on a repeating payload and lose on the tiny health response. The payload, not the extension, decides. Before touching that level dial, I'd ask what paid overhead and what saved space. DEFLATE carries the literal and copy instructions; gzip wraps them. For our two payloads, I'd leave gzip off this 9-byte health response and measure the repeating log in the real service.

9:26 We know the decoder can recover the bytes; whether this workload wins on size still needs a test. Thanks for listening to Learning Podcasts.