面向小二进制块的二进制差分算法及TCP数据包优化问询

Great question—small object delta compression is a totally different beast than the large-file algorithms you’ve probably researched, since overhead becomes way more critical when dealing with 5-100 byte objects. Let’s break down how to optimize this for your use case, focusing on packing as many updates as possible into a single TCP packet.

Large-file delta algorithms (like rsync’s rolling hash) come with fixed overheads that make them useless for tiny objects—for a 5-byte object, the hash alone could be larger than the object itself. Your priority needs to be minimizing per-update overhead while keeping delta data as compact as possible.

Here are lightweight approaches tailored to your small object size:

• First, skip delta when it’s not worth it: If the new object differs from the old one by more than ~50% of its bytes, sending the full object will be more efficient than storing delta metadata + changes. Add a quick check for this before generating a delta.
• Byte-wise XOR + Run-Length Encoding (RLE): For objects with long stretches of unchanged bytes, XOR the old and new object, then RLE-compress the result. For example:
  • Old object: 0x12 0x34 0x56 0x78
  • New object: 0x12 0xAB 0x56 0xCD
  • XOR result: 0x00 0x99 0x00 0x14
  • RLE output: [2, 0x99, 1, 0x14] (2 zeros, then 0x99, 1 zero, then 0x14) — this cuts down redundant "no change" markers.
• Position + Delta Value: For objects with only 1-2 changed bytes, directly record the index of the changed byte (1 byte is enough for 100-byte objects) plus the new byte value. For a single changed byte, this adds just 2 bytes of overhead per update.
• Structured Object Shortcuts: If your objects have a fixed schema (e.g., first 2 bytes = type, last 3 = value), define delta type codes. For example, a code 0x01 could mean "update the value field"—then you only send the code + new value, skipping generic delta logic entirely.

To maximize the number of updates per packet (staying under the ~1360-byte payload limit, accounting for IP/TCP headers), optimize your packet structure:

• Compact Object IDs: Use variable-length integers (Varints, like those in Protobuf) instead of fixed-length IDs. IDs <128 fit in 1 byte, IDs 128-16383 fit in 2 bytes—this saves space for small, common IDs.
• Bit-Packed Flags: Instead of using a full byte for a "delta vs full object" flag, pack multiple flags into a single byte. For example, 8 updates can share 1 byte of flags (1 bit per update).
• Sample Packet Structure:

  [Header (2 bytes): Packet version + total number of updates]
  [Flag Byte(s): 1 bit per update (0 = full object, 1 = delta)]
  [Update 1:
     Object ID (Varint)
     Delta Data / Full Object Bytes
  ]
  [Update 2: ...]
  ...
  

Suppose you have 200 10-byte objects, each with 1 changed byte:

• Using the "Position + Delta" method: Each update is ~3 bytes (Varint ID + 1-byte position + 1-byte delta, plus a tiny share of the flag byte). 200 updates would take ~602 bytes, leaving plenty of room in the 1360-byte payload.
• Sending full objects: Each update would be 11 bytes (ID + 10-byte object), totaling 2200 bytes—way over the MTU limit, requiring multiple packets.

• Tiny objects with full changes: For a 5-byte object that’s entirely new, sending the full 5 bytes + ID is better than any delta approach (since delta metadata would add unnecessary overhead).
• Packet Overflow Check: Always calculate the total payload size before sending—stop adding updates once you’re within 10-20 bytes of the 1360-byte limit to avoid accidental fragmentation.

内容的提问来源于stack exchange，提问作者Max Yankov