Visual walkthrough — HTTP - 2 — multiplexing, header compression (HPACK), server push

4.3.25 · D2 · Coding › Computer Networks › HTTP - 2 — multiplexing, header compression (HPACK), server

Step 1 — Byte actually kya hota hai, aur 8 slots kyun

KYA HAI. Ek byte 8 bits ki ek row hoti hai. Bit ek single slot hota hai jo $0$ ya $1$ rakhta hai. Yahi sabse chhoti cheez hai jo wire carry karta hai — HTTP/2 mein sab kuch, har frame, har header, aakhirkar inhi 8-slot bytes ki rows hain.

YAH SE KYUN SHURU KAREIN. HPACK ki poori chalaaki yahi hai ki ek hi byte se do kaam liye jaate hain: 8 slots mein se kuch slots kehte hain yeh cheez kaunsi tarah ki hai (ek flag), aur baaki carry karte hain ek number. "5-bit prefix" tab tak samajh nahi aayega jab tak tum 8 slots nahi dekh sakte aur indicate nahi kar sakte ki kaunse slots flags hain.

PICTURE. Neeche, ek byte ke 8 slots. Har slot ki ek "place value" hoti hai — sabse baayi slot ki value $128$ hai, phir $64,32,16,8,4,2,1$. $1$ set hone wala slot apni place value add karta hai; $0$ set hone wala slot kuch nahi add karta. Byte padhne ke liye, tum un slots ki place values ko jodho jo $1$ hain.

Step 2 — Ek byte ko "flag bits" + "number bits" mein split karna

KYA HAI. HPACK number ke liye saare 8 slots use nahi karta. Yeh upar ke kuch slots flags ke liye reserve karta hai (ek code jo kehta hai is header ko kaise interpret karein), aur neeche ke $N$ slots number ke liye chhodta hai. Yeh neeche wala region ==$N$-bit prefix== hai.

KYUN. Har header field ko pehle apna representation type announce karna hota hai: "Main ek fully indexed header hoon" (top slot mein $1$), ya "Main ek literal hoon jo yaad rakhna chahiye" (top do slots mein $01$), wagera. Yeh type-bits 8 slots mein se kuch kha jaate hain. Jo bacha wahi actual index number ke liye jagah hai. Alag alag types mein alag number of slots bachi rehti hain — exactly iseelie spec baar baar "$N$-bit prefix" kehta rehta hai instead of ek fixed number: $N$ depend karta hai ki us representation ne kitne flag bits use kiye.

PICTURE. Wahi byte, ab do rangon mein paint ki gayi: baaye taraf burnt-orange flag slots, daaye taraf teal number slots. "Indexed" case mein ($1$ flag) prefix $N=7$ slots ka hai. "Literal with incremental indexing" mein ($01$ flag) prefix $N=6$ slots ka hai. Plain literal-name reference ke liye yeh $N=4$ hai.

Step 3 — Easy case: number prefix mein fit ho jaata hai

KYA HAI. Agar humara number $I$ itna chhota hai ki $N$ slots mein fit ho jaaye, toh hum bas wahan likh dete hain aur kaam khatam. "Chhota enough" ka matlab hai strictly less than $2^N-1$.

$2^N-1$ boundary kyun (na ki $2^N$)? $N$ slots $0$ se lekar $2^N-1$ tak ki values hold kar sakti hain. Lekin HPACK all-ones pattern ($2^N-1$) ko ek special signal ke roop mein reserve karta hai jiska matlab hai "Main overflow ho gaya — aage padhte raho". Toh jo values fit-and-stop hain woh hain $0$ se $2^N-2$ tak. Jis pal $I$ $2^N-1$ ke barabar hota hai, hum use waise nahi likh sakte; woh pattern "continue" flag hai. Yahi is page ka sabse important rule hai.

PICTURE. Ek 5-bit prefix ($N=5$, toh $2^5-1=31$). Hum $I=10$ store kar rahe hain. Kyunki $10<31$, teal slots $01010$ ban jaati hain aur orange flag slots upar untouched rehti hain. Total ek byte.

Step 4 — Continuation bytes ki zaroorat kyun hai

KYA HAI. Agar $I\ge 2^N-1$ ho? Prefix use hold nahi kar sakta. Toh hum do kaam karte hain: (1) prefix ko all-ones se bharo $(2^N-1)$ — "keep reading" signal — aur (2) remainder $I^{\prime }=I-(2^N-1)$ ko baad mein aane wale extra bytes mein store karo.

Pehle $2^N-1$ kyun subtract karein? Kyunki prefix ne pehle se hi all-ones hone ki wajah se utni magnitude "use kar li" hai. Hum use double count nahi karna chahte. Leftover $I^{\prime }$ store karna numbers ko jitna ho sake chhota rakhta hai, jo byte-count ko kam rakhta hai. Yeh classic variable-length integer idea hai: chhote numbers pe kam bytes lagte hain, bade numbers pe zyada, aur kisi ka bhi size fixed aur wasteful nahi hota.

PICTURE. Ek number jo 5-bit prefix ke liye bahut bada hai. Prefix solid ho jaata hai ($11111=31$), aur ek arrow byte ke bahar un continuation bytes ki taraf point karta hai jo hum Step 5 mein banane wale hain.

Step 5 — 7-bit continuation groups (varint engine)

KYA HAI. Hum leftover $I^{\prime }$ ko continuation bytes mein encode karte hain. Har aise byte mein, top slot ek flag hai ($1$ = "aur ek byte aata hai", $0$ = "yeh aakhri wala hai") aur neeche ke 7 slots number ka ek chunk carry karte hain. Hum $I^{\prime }$ ke 7 bits ek baar mein peelte hain.

7 kyun, 8 nahi? Kyunki humne har byte ka 1 slot "more follows?" flag par kharch kar diya. Baaki 7 slots data ke liye hain. Toh har continuation byte $0$–$127$ ki value carry karta hai, aur $128$ (top slot) "keep going" marker ban jaata hai. Loop:

$\text{while }{I}^{\prime }\ge 128:\text{emit }(I^{\prime }\mathrm{mod}128)+128;I^{\prime }\leftarrow \lfloor I^{\prime }/128\rfloor$ $\text{then emit the final }{I}^{\prime }(\text{now}<128,\text{top bit }0)$

• $I^{\prime }\mathrm{mod}128$ — lowest 7 bits (current chunk).
• $+128$ — top slot set karna yeh kehne ke liye ki "aur bytes aa rahe hain".
• $\lfloor I^{\prime }/128\rfloor$ — 7 bits daaye shift karo, agla chunk expose karo.
• Final emit mein $I^{\prime }<128$ hai, toh uska top slot $0$ hai → decoder rukta hai.

PICTURE. Remainder $I^{\prime }$ ek tall stack ki tarah dikhaya gaya hai, 7-bit chunks mein bottom-up slice kiya gaya. Har slice ek byte ban jaati hai; last ko chhodkar sabke upar burnt-orange "continue" top bit hai; last wale ke upar teal "stop" top bit hai.

Step 6 — Decoding: wapas padhna

KYA HAI. Decoder sab kuch ulta karta hai. Prefix padho. Agar woh $2^N-1$ se kam hai, toh wahi number hai, ruk jao. Agar woh $2^N-1$ ke barabar hai, continuation bytes padhte raho, 7 bits ek baar mein accumulate karte raho, jab tak ek byte ka top slot $0$ na ho.

KYUN AMBIGUOUS NAHI HAI. All-ones prefix aur top "continue" bits self-describing hain: har byte par decoder jaanta hai ki aur expect karna hai ya nahi, bina kisi length field ke. Yahi varint ko ek byte stream mein safely daalne layak banata hai.

PICTURE. 31, 154, 10 ka decode wapas $1337$ mein: prefix $31$ kehta hai "overflow, base $31$ se shuru karo"; phir $154$ apne low 7 bits $26$ weight $128^0$ par contribute karta hai; phir $10$ (stop) weight $128^1$ par contribute karta hai; sum $31+26+10\cdot 128=1337$.

Step 7 — Edge aur degenerate cases (reader ko kabhi stranded mat chhodna)

KYA AUR KYUN, har ek apni row mein figure mein:

• $I=0$. Kisi bhi prefix mein fit ho jaata hai ($0<2^N-1$). Number slots mein all-zeros likh do. Ek byte.
• $I=2^N-2$ (sabse bada jo phir bhi fit hota hai). E.g. $N=5\Rightarrow 30$. Phir bhi ek byte — kyunki $30<31$. Yeh aakhri "sasta" value hai.
• $I=2^N-1$ (trap). E.g. $N=5\Rightarrow 31$. Fit-and-stop nahi hota! Prefix all-ones ho jaata hai aur remainder $I^{\prime }=31-31=0$, toh hum phir bhi ek continuation byte emit karte hain ($0$, top bit off). Total do bytes $31$ store karne ke liye. Yeh log ko surprise karta hai: $30$ ek byte layta hai, $31$ do layta hai.
• Remainder ka multiple of 128 hona. Agar $I^{\prime }=128$ exactly ho: $128\mathrm{mod}128=0$ toh emit $0+128=128$, phir $\lfloor 128/128\rfloor =1<128$ emit $1$. Do continuation bytes.

PICTURE. Ek chhoti table-figure: $2^N-1$ par "cliff" jahan byte-count 1 se 2 ho jaata hai, saath mein $I=0$ aur $I^{\prime }=128$ cases draw kiye gaye.

Ek picture mein poora summary

Yeh final figure poori machine ko ek number par chalata hai: ek byte orange flags + teal $N$-bit prefix mein split; fit-or-overflow decision; aur daaye taraf nikalta 7-bit continuation chain, top-bit ka matlab "aur". Bas yahi hai HPACK integer encoding ka pura mechanism — woh mechanism jo ek baar dynamic table mein aa jaane ke baad baar baar aane wale 200-byte cookie ko ek single referencing byte mein badal deta hai.

Related: yeh varint trick poori tarah Varint-encoding mein dobara milti hai; HPACK generic gzip kyun avoid karta hai yeh CRIME-and-BREACH-attacks mein hai; literal-string path Huffman-Coding use karta hai; aur poora scheme TCP/TLS ke upar baitha hai, transport ke lihaz se HTTP-3-and-QUIC ne ise supersede kar diya hai.

Quick self-checks: