Length-prefix framing

Deep dive

How it works

In: chunks of a byte stream · Out: whole messages · State: receive buffer, read offset, and a pending length if the header was parsed · Cost: O(1) per frame, each byte copied about once

stream:  |00 00 00 05|h e l l o|00 00 00 02|h i|00 00 01 ...
          header len  payload    header      ...  partial: wait for more bytes

1. Append each read to a receive buffer (or read directly into its free tail).
2. While available ≥ header_len: parse the length; reject if > max; if available ≥ header_len + len, hand out the payload slice and advance; else stop.
3. Compact the buffer (move the unread tail to the front) only when the read offset passes half the buffer, so each byte is moved at most about once.
4. Sending: write header and payload in one syscall (writev, or one buffer) to avoid Nagle/delayed-ACK stalls.

Code

use std::io::{self, IoSlice, Read, Write};

const HDR: usize = 4;

#[derive(Debug)]
pub enum FrameError { TooLarge(usize), Io(io::Error) }

/// Receive side: [u32 big-endian length][payload], length excludes the header.
pub struct Decoder { buf: Vec<u8>, start: usize, end: usize, max: usize }

impl Decoder {
    pub fn new(max: usize) -> Self { Decoder { buf: vec![0; 64 * 1024], start: 0, end: 0, max } }

    /// Read once from `r` into the free tail. Ok(0) = EOF. WouldBlock passes through.
    pub fn read_from<R: Read>(&mut self, r: &mut R) -> io::Result<usize> {
        if self.start > 0 && (self.start > self.buf.len() / 2 || self.end == self.buf.len()) {
            self.buf.copy_within(self.start..self.end, 0); // amortized compaction
            self.end -= self.start;
            self.start = 0;
        }
        if self.end == self.buf.len() {
            let n = self.buf.len() * 2;
            self.buf.resize(n, 0); // a single frame is larger than the buffer: grow by doubling
        }
        let n = r.read(&mut self.buf[self.end..])?;
        self.end += n;
        Ok(n)
    }

    /// Next complete frame, borrowed from the buffer until the next call.
    pub fn next_frame(&mut self) -> Result<Option<&[u8]>, FrameError> {
        let avail = self.end - self.start;
        if avail < HDR { return Ok(None); }
        let h: [u8; HDR] = self.buf[self.start..self.start + HDR].try_into().unwrap();
        let len = u32::from_be_bytes(h) as usize;
        if len > self.max { return Err(FrameError::TooLarge(len)); } // check before growing
        if avail < HDR + len { return Ok(None); } // read_from grows the buffer as bytes arrive
        let a = self.start + HDR;
        self.start = a + len;
        if self.start == self.end { self.start = 0; self.end = 0; } // cheap reset when drained
        Ok(Some(&self.buf[a..a + len]))
    }
}

/// Send side: header + payload in one writev; loops on short writes.
pub fn write_frame<W: Write>(w: &mut W, payload: &[u8]) -> io::Result<()> {
    let len = u32::try_from(payload.len()).map_err(|_| io::Error::other("frame too large"))?;
    let hdr = len.to_be_bytes();
    let (mut h, mut p) = (&hdr[..], payload);
    while !h.is_empty() || !p.is_empty() {
        let n = w.write_vectored(&[IoSlice::new(h), IoSlice::new(p)])?;
        if n == 0 { return Err(io::ErrorKind::WriteZero.into()); }
        let hn = n.min(h.len());
        h = &h[hn..];
        p = &p[n - hn..];
    }
    Ok(())
}

#[test]
fn split_reads() {
    let mut wire = Vec::new();
    write_frame(&mut wire, b"hello").unwrap();
    write_frame(&mut wire, b"hi").unwrap();
    let mut d = Decoder::new(1 << 20);
    let mut got = Vec::new();
    for chunk in wire.chunks(3) {               // simulate TCP splitting arbitrarily
        d.read_from(&mut &chunk[..]).unwrap();
        while let Some(f) = d.next_frame().unwrap() { got.push(f.to_vec()); }
    }
    assert_eq!(got, vec![b"hello".to_vec(), b"hi".to_vec()]);
}

Complexity and constants

• Boundary detection O(1) per frame (vs O(n) scanning for delimiters); bytes are copied once from the kernel into the buffer, plus at most about one compaction move each.
• A 64 KB receive buffer and read sizes of 16-64 KB keep syscalls per MB low (order of 16-64 per MB).
• Header cost: 4 bytes fixed; protobuf varint 1 byte (< 128), 2 bytes (< 16 384), 3 bytes (< 2 MiB).
• Nagle + delayed ACK on separate header and body writes: up to 40 ms (Linux minimum delayed ACK) to 200 ms of added latency per message.

Efficiency

• Cost: boundary detection is O(1) per frame; each byte is copied once from the kernel into the receive buffer, plus at most about one compaction move. Header is 4 bytes fixed or a 1-3 byte protobuf varint. With 16-64 KB reads, order of 16-64 syscalls per MB. The bound is syscalls and allocation, not parsing.
• Levers:
  • Large receive buffer, many frames per read — fewer syscalls per MB (Complexity) — small messages.
  • Zero-copy decode (slices of the receive buffer, e.g. Bytes) — no per-frame allocation or copy — high message rates.
  • Compact once per read, not per frame — avoids O(n²) memmove (Pitfalls) — many small frames behind a partial one.
  • One writev, or one buffered write, for header and body — avoids the Nagle plus delayed-ACK stall of up to 40-200 ms (Complexity) — request/response protocols.
  • Varint header — 1 byte under 128 — mostly tiny messages.
• Naive → standard → state of the art:
  • Delimiter scan (\n) · O(n) byte scan plus escaping, and a copy per message.
  • Length prefix with a bounded buffer · O(1) boundary, one allocation checked against max.
  • Length prefix with zero-copy slices of a shared buffer · no allocation per frame (tokio-util Bytes model, Netty ByteBuf slices).

Implementation notes

• Defaults worth copying: tokio-util LengthDelimitedCodec (4-byte BE, max 8 MiB), gRPC (max received message 4 MiB by default), Kafka (message.max.bytes about 1 MB, socket.request.max.bytes 100 MB).
• Decide and document: endianness (network order = big-endian is the convention), header size, whether the length counts the header (PostgreSQL: yes, includes its own 4 bytes but not the type byte), signedness (Java int lengths can be negative).
• Large messages: frame them as chunks of ≤ 16-64 KB so one huge message doesn't block others on a multiplexed connection (HTTP/2 caps frames at 16 KB by default).
• For files and logs add a checksum per record (CRC32C) so torn writes are detected; on a TCP stream TLS or the TCP checksum already covers corruption.
• Zero-copy decode: hand out slices of the receive buffer and parse in place; copy only what outlives the next read.

Pitfalls

• vec![0; len] from an unchecked length: one 4-byte packet allocates 4 GB. Check max first, then grow gradually as bytes actually arrive.
• Treating one read as one message: works on localhost, breaks under load or with TLS record boundaries.
• Compacting on every frame: O(n²) memmove when many small frames sit behind a large unread tail.
• Slowloris: a client sends a 1 MB length then trickles bytes; enforce per-frame read deadlines.
• Mixing framing layers (length inside TLS inside WebSocket) and counting the wrong one in limits.

Variants and alternatives

In production

Kafka, Thrift (framed transport), gRPC (over HTTP/2 DATA frames), HTTP/2 and HTTP/3 frames, PostgreSQL and MySQL wire protocols, TLS records (5-byte header, 2-byte length, max 16 KB plaintext), Redis RESP bulk strings ($len\r\n), Netty LengthFieldBasedFrameDecoder.

Implementations

Sources

• Thomson, Benfield, RFC 9113: HTTP/2, 2022. rfc
• gRPC Authors, gRPC over HTTP2 (PROTOCOL-HTTP2.md), github.com/grpc/grpc. spec
• PostgreSQL Global Development Group, Frontend/Backend Protocol, PostgreSQL documentation. docs
• Apache Kafka, A Guide To The Kafka Protocol, kafka.apache.org. docs