Suốt các phần về định dạng nhị phân (Protobuf phần 3, CBOR phần 7), có một kỹ thuật lặp đi lặp lại làm nền cho sự gọn nhẹ: varint — mã hóa số nguyên sao cho số nhỏ tốn ít byte. Ta đã dùng nó, giờ mổ xẻ nó, vì hiểu varint (và người bạn đồng hành ZigZag) giúp bạn tránh một cái bẫy khiến dữ liệu phình to bất ngờ: một số -1 có thể tốn tận 10 byte. Bài này (phần 8 loạt Serialization) đo thật số byte của từng giá trị để thấy chính xác chuyện gì xảy ra.

Cơ chế varint và cái bẫy số âm

Varint dùng mỗi byte cho 7 bit dữ liệu, 1 bit cao nhất (MSB) làm cờ nối (1 = còn byte nữa, 0 = hết), ghép các nhóm 7 bit little-endian:

300 = 0b100101100
   -> nhóm 7 bit:  0000010  0101100
   -> byte:  1 0101100  0 0000010  =  ac 02   (2 byte)

Số càng nhỏ càng ít byte — tuyệt vời cho id, số đếm, enum. Nhưng đây là cái bẫy: số âm trong bù hai (two's complement) có mọi bit cao đều bằng 1. Ví dụ -1 là 0xFFFFFFFFFFFFFFFF — 64 bit toàn 1. Varint phải mã hóa cả 64 bit đó, thành 10 byte! Một trường đếm chênh lệch có thể âm mà mã hóa thẳng bằng varint thuần sẽ phình to mỗi khi gặp số âm.

ZigZag giải quyết bằng cách ánh xạ số có dấu sang không dấu theo kiểu đan xen: 0→0, -1→1, 1→2, -2→3, 2→4... — số có độ lớn nhỏ (dù âm hay dương) được ánh xạ thành số không dấu nhỏ, nên varint tốn ít byte:

func zigzag(n int64) uint64  { return uint64((n << 1) ^ (n >> 63)) }
func unzigzag(u uint64) int64 { return int64(u>>1) ^ -int64(u&1) }

Ảnh chụp đoạn mã Go nền tối minh hoạ varint và ZigZag, varint số nhỏ ít byte mỗi byte bit cao MSB bằng 1 còn byte nữa bằng 0 hết 7 bit thấp là dữ liệu ghép little-endian 300 bằng 0b100101100 nhóm 7 bit 0000010 0101100 byte 10101100 00000010 bằng ac 02 2 byte 0 tới 127 1 byte 128 tới 16383 2 byte, vấn đề số âm trong varint thuần tốn 10 byte bù hai âm 1 bằng 0xFFFFFFFFFFFFFFFF mọi bit bằng 1 varint phải mã hóa 64 bit 1 bằng 10 byte cho mỗi số âm uint64 int64 âm 1 thành ff ff ff ff ff ff ff ff ff 01 10 byte, ZigZag đan xen âm dương để số âm nhỏ vẫn ít byte ánh xạ 0 sang 0 âm 1 sang 1 1 sang 2 âm 2 sang 3 2 sang 4 func zigzag n int64 return uint64 n dịch trái 1 xor n dịch phải 63 func unzigzag u uint64 return int64 u dịch phải 1 xor trừ int64 u and 1 số có giá trị tuyệt đối nhỏ zigzag nhỏ varint ít byte Go binary PutVarint bằng zigzag cộng varint PutUvarint là varint thuần

Hình 1: Varint dùng 7 bit dữ liệu + 1 bit nối mỗi byte (300 = ac 02); số âm bù hai có bit cao toàn 1 nên varint thuần tốn 10 byte; ZigZag ánh xạ đan xen (n<<1)^(n>>63) đưa số âm nhỏ về mã nhỏ.

Đo thật: số byte theo giá trị

Mình dùng encoding/binary của Go (PutUvarint cho varint thuần, PutVarint đã tích hợp ZigZag) đo số byte:

Ảnh chụp bảng kết quả chạy thật varint zigzag output thật, một varint thuần giá trị dương số byte 0 1 byte 00 127 1 byte 7f 128 2 byte 80 01 300 2 byte ac 02 16384 3 byte 80 80 01 2 mũ 21 4 byte 2 mũ 30 5 byte 2 mũ 60 9 byte số càng lớn càng nhiều byte số nhỏ rất rẻ, hai số âm varint thuần vs ZigZag đo thật số byte giá trị 0 varint 1 zigzag 1 âm 1 varint 10 zigzag 1 1 varint 1 zigzag 1 âm 2 varint 10 zigzag 1 âm 1000 varint 10 zigzag 2 1000 varint 2 zigzag 2 âm 1048576 varint 10 zigzag 3 mọi số âm trong varint thuần bằng 10 byte ZigZag đưa về đúng chi phí độ lớn, ba ZigZag ánh xạ đan xen round-trip khớp n bằng 0 zigzag 0 giải mã 0 n bằng âm 1 zigzag 1 giải mã âm 1 n bằng 1 zigzag 2 giải mã 1 n bằng âm 2 zigzag 3 giải mã âm 2 n bằng 2 zigzag 4 giải mã 2 âm dương xen kẽ giá trị tuyệt đối nhỏ mã nhỏ ít byte, kết luận varint số nhỏ 1 byte tiết kiệm khi phần lớn số nhỏ số âm trong varint thuần luôn 10 byte bù hai bit cao 1 ZigZag số âm nhỏ vẫn ít byte Protobuf dùng cho sint32 sint64

Hình 2: Chạy thật — varint thuần: 0/127 = 1 byte, 300 = 2 byte (ac 02), 2^30 = 5 byte, 2^60 = 9 byte; số âm varint thuần -1/-2/-1000/-1.048.576 đều 10 byte, còn ZigZag đưa -1 về 1 byte, -1000 về 2 byte, -1.048.576 về 3 byte; ZigZag round-trip khớp.

Đọc kết quả đo được:

  • Varint thưởng số nhỏ: 0 và 127 chỉ 1 byte; 128 nhảy lên 2 byte (vì cần bit thứ 8); 16.384 là 3 byte; 2^30 là 5 byte; 2^60 là 9 byte. Số càng lớn càng nhiều byte, tối đa 10 byte cho uint64. Nếu dữ liệu của bạn phần lớn là số nhỏ, varint tiết kiệm lớn so với 8 byte cố định.
  • Cái bẫy số âm rõ ràng: -1, -2, -1000, -1.048.576 — tất cả đều tốn 10 byte trong varint thuần, bất kể độ lớn! Vì trong bù hai, mọi số âm đều có các bit cao bằng 1. Đây là lỗi phình dữ liệu âm thầm: một trường có thể âm (chênh lệch, tọa độ, delta) mà dùng sai kiểu sẽ tốn tối đa mỗi giá trị.
  • ZigZag đưa số âm về đúng chi phí độ lớn: -1 xuống 1 byte, -1000 xuống 2 byte, -1.048.576 xuống 3 byte — bằng đúng chi phí của số dương cùng độ lớn. Và round-trip khớp hoàn toàn: n=-1 → zigzag=1 → giải mã=-1. Đây chính là lý do Protobuf có kiểu sint32/sint64 (dùng ZigZag) tách khỏi int32/int64 (varint thuần).

Đánh đổi cần cân nhắc

Chọn đúng kiểu số theo phân phối giá trị. Bài học thực tế: nếu một trường chỉ dương hoặc hiếm khi âm (id, số lượng), dùng varint thuần (int32/int64 trong Protobuf) là đúng. Nếu trường thường âm hoặc âm-dương cân bằng (delta, chênh lệch nhiệt độ, tọa độ tương đối), dùng ZigZag (sint32/sint64). Chọn nhầm không gây lỗi — chỉ âm thầm phình dữ liệu, thứ chỉ lộ ra khi đo.

Varint là đánh đổi CPU lấy kích thước. Mã hóa/giải mã varint cần dịch bit và kiểm cờ nối từng byte — tốn CPU hơn đọc/ghi một số cố định 8 byte thẳng. Với dữ liệu mà số thường lớn (gần 2^64), varint vừa không tiết kiệm byte vừa tốn CPU hơn fixed64. Đó là lý do Protobuf cũng có fixed64/sfixed64 — dùng khi giá trị thường lớn hoặc cần kích thước cố định để căn chỉnh.

Số float không dùng varint. Varint và ZigZag chỉ cho số nguyên. Số thực (float32/float64) có phân bố bit khác hẳn — varint hầu như không nén được chúng (mantissa ngẫu nhiên), nên chúng được lưu dạng cố định (IEEE 754, 4 hoặc 8 byte). Đừng kỳ vọng varint giúp cho trường số thực.

Ba ý mang về

  1. Varint làm số nhỏ tốn ít byte: đo thật 0–127 = 1 byte, 300 = 2 byte, 2^60 = 9 byte — nền tảng khiến Protobuf/CBOR gọn khi dữ liệu phần lớn là số nhỏ (id, đếm, enum).
  2. Số âm trong varint thuần luôn tốn 10 byte: đo thật -1, -2, -1000, -1.048.576 đều 10 byte vì bù hai có bit cao toàn 1 — cái bẫy âm thầm phình dữ liệu với trường có thể âm.
  3. ZigZag cứu số âm bằng ánh xạ đan xen: đo thật -1 về 1 byte, -1000 về 2 byte (đúng chi phí độ lớn), round-trip khớp — chọn sint32/sint64 (ZigZag) cho trường thường âm, int32/int64 (varint thuần) cho trường thường dương.

Nguồn

Phần sau ta ghép serialization với nén: chạy gzip và zstd lên cả JSON lẫn Protobuf, đo xem nén thu hẹp khoảng cách giữa hai định dạng đến đâu — và khi nào nén một JSON lại tốt ngang việc đổi sang định dạng nhị phân.