Triển Khai Và Đánh Giá Sproto

Vào cuối tuần này, tôi đã hoàn thành việc triển khai giao thức protocol buffers phiên bản rút gọn được thiết kế từ tuần trước, đồng thời đặt lại tên thành sproto.

Trong quá trình triển khai, tôi nhận thấy nhiều điểm có thể tối ưu trong định dạng mã hóa, do đó vừa thực hiện vừa điều chỉnh để cấu trúc phù hợp hơn cho việc mã hóa/giải mã và tiết kiệm dung lượng hơn. Những thay đổi cụ thể bao gồm:

Vì mục tiêu chính là tích hợp với các ngôn ngữ động như Lua, nên tôi không cần phải truy cập trực tiếp cấu trúc dữ liệu mã hóa như cách làm của Cap’n Proto (ánh xạ dữ liệu thành đối tượng C/C++), do đó việc căn chỉnh dữ liệu (data alignment) là không cần thiết.

Việc đánh số thứ tự trường (tag) theo chiều tăng dần nghiêm ngặt sẽ giúp xử lý dữ liệu nhanh hơn và giảm độ phức tạp triển khai. Các đoạn dữ liệu cũng yêu cầu sắp xếp liên tục, không cho phép tái sử dụng, điều này tạo ra nhiều giá trị 0 trong dữ liệu, thuận lợi cho nén dữ liệu.

Việc đóng gói mảng boolean thành bit không mang lại hiệu quả đáng kể (lại làm tăng độ phức tạp), nên tôi tạm thời loại bỏ tính năng này.

Kiểu dữ liệu ID 64-bit cũng chưa được triển khai trong giai đoạn đầu (sẽ bổ sung sau).

Định dạng dữ liệu nhị phân cuối cùng được xác định như sau:

• Mọi con số đều được mã hóa theo định dạng little-endian
• Đơn vị đóng gói là một cấu trúc (kiểu do người dùng định nghĩa), mỗi gói chia làm 2 phần: 1. Danh sách trường 2. Khối dữ liệu

Cấu trúc bắt đầu với một từ (word) n chỉ số lượng trường, tiếp theo là n từ mô tả nội dung các trường. Tổng chiều dài phần đầu này là (n+1)*2 byte.

Các tag trường bắt đầu từ 0 và tăng dần. Mỗi khi xử lý một trường, tag sẽ tăng thêm 1.

• Nếu giá trị trường v là số lẻ, tag hiện tại sẽ được tăng thêm (v-1)/2 + 1, sau đó tiếp tục xử lý giá trị trường tiếp theo
• Nếu giá trị trường là 0, trường này trỏ đến một khối dữ liệu phía sau
• Nếu giá trị trường khác 0 (và là số chẵn), giá trị thực tế sẽ là v/2 - 1 (có thể biểu diễn giá trị trong khoảng [0, 32767])

Phía sau là các khối dữ liệu được tham chiếu bởi các trường ở phần đầu. Mỗi khối dữ liệu gồm một từ chỉ độ dài (dword) theo sau là chuỗi byte. Khối này dùng để biểu diễn dữ liệu lớn như mảng hoặc cấu trúc. Các số nguyên lớn hơn 32767 hoặc số âm sẽ được biểu diễn bằng khối 4 hoặc 8 byte (tùy yêu cầu triển khai).

Cách mã hóa mảng:

• Mảng boolean: mỗi phần tử chiếm 1 byte
• Mảng số nguyên: đặc biệt hơn, mỗi phần tử có thể chiếm 4 hoặc 8 byte, byte đầu tiên chỉ định độ rộng (4 hoặc 8) cho các số nguyên phía sau

Dữ liệu chứa nhiều giá trị 0 sẽ được nén bằng thuật toán đã trình bày ở bài blog trước.

Triển khai của tôi gồm hai phần chính: thư viện C và binding Lua.

Thư viện C chủ yếu phục vụ việc binding sang ngôn ngữ khác, do đó không cung cấp API phong phú như pbc, mà chỉ tập trung vào hai hàm theo mô hình callback:

1
2
3
4
5
6
7
8

#define SPROTO_TINTEGER 0
#define SPROTO_TBOOLEAN 1
#define SPROTO_TSTRING 2
#define SPROTO_TSTRUCT 3
typedef int (*sproto_callback)(void *ud, const char *tagname, int type, 
 int index, struct sproto_type *, void *value, int length);
int sproto_decode(struct sproto_type *, const void * data, int size, sproto_callback cb, void *ud);
int sproto_encode(struct sproto_type *, void * buffer, int size, sproto_callback cb, void *ud);

Hàm encode sẽ gọi lại (callback) hàm do người dùng cung cấp để thông báo đang xử lý trường nào (tagname) và kiểu dữ liệu. Nếu kiểu là SPROTO_TSTRUCT, tham số sproto_type sẽ chỉ ra kiểu cấu trúc cụ thể, cho phép gọi đệ quy encode.

Hàm callback nhận địa chỉ và kích thước bộ đệm. Nếu bộ đệm không đủ, trả về -1. Nếu mã hóa thành công, trả về số byte đã sử dụng. Với mảng, tham số index > 0 cho biết vị trí (tính từ 1) trong mảng cần lưu dữ liệu. Với dữ liệu không phải mảng, index = 0.

Hàm encode không tự động cấp phát bộ nhớ. Khi buffer không đủ lớn, người dùng cần cấp phát lại và gọi lại hàm.

Quy trình decode tương tự encode, nhưng lúc này buffer chứa dữ liệu đã được giải mã, callback chỉ cần sao chép dữ liệu vào vị trí tương ứng.

Dù thư viện vẫn chưa hoàn thiện hoàn toàn, nhưng các chức năng cốt lõi đã đầy đủ. Tôi đã thực hiện bài kiểm tra hiệu năng đơn giản giữa sproto và pbc (phiên bản Lua binding):

Đầu tiên tôi định nghĩa giao thức sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

.Person {
  name 0 : string
  id 1 : integer
  email 2 : string
  .PhoneNumber {
    number 0 : string
    type 1 : integer
  }
  phone 3 : *PhoneNumber
}
.AddressBook {
  person 0 : *Person
}

Nếu dùng Google Protocol Buffers, sẽ tương đương:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

message Person {
 required string name = 1;
 required int32 id = 2;    // Mã định danh duy nhất
 optional string email = 3;
 message PhoneNumber {
  required string number = 1;
  optional int32 type = 2 ;
 }
 repeated PhoneNumber phone = 4;
}
message AddressBook {
 repeated Person person = 1;
}

Hai định nghĩa hoàn toàn tương đương, chỉ khác biệt