Skip to content

Latest commit

 

History

History
269 lines (194 loc) · 9.98 KB

draft-01_CN.md

File metadata and controls

269 lines (194 loc) · 9.98 KB
Raw

Y3 Codec 数据格式规范 v202007

概览

版本号：Draft-01 (v202007)。该协议定义了Y3 Codec的帧格式。

目录

Design Goals

设计目标

  • 是一个faster than real-time的编码器。
  • 二进制格式适合做编解码，尤其是在流式处理过程中的随机访问场景。
  • 为在QUIC Transport的使用优化。
  • 本文不涉及RPC场景，与连接无关，仅是数据结构定义。

Notational Conventions

本文档中的数据包和框架图使用了定制的格式，其目的是这种格式是为了描述表述方法，而不是定义具体的协议元素。该文档定义了完整的语义和结构的细节。

先为复合结构（complex fields）命名，然后是一个包含在{ }内的字段列表，该列表中的每个字段都由逗号分隔。

各个字段包括长度信息，以及关于固定的字段的指示：值、可选性或重复性。

单个字段使用以下内容符号惯例，所有长度以位（bit）为单位。

x (A): 表示x的长度为A位

x (A..B): 表示x可以是A到B之间的任意长度。A可以省略，表示最小值是0，B可以省略，表示最大值没有设置上限

x (?) = C: 表示x是固定长度为C位

x (?) = C..D: 表示x的值在C到D之间

[x (E)]: []表示该部分是可选的

x (E) ...: 表示x会重复零次或多次（并且每次城府都是长度为E位）

本文档使用大端序（Big-Endian），字段从每个字节的高位开始放置。

按照惯例，单个字段通过使用以下名称来引用一个复杂字段复杂的结构。

例如：

Example Structure {
  One-bit Field (1),
  7-bit Field with Fixed Value (7) = 61,
  Arbitrary-Length Field (..),
  Variable-Length Field (8..24),
  Field With Minimum Length (16..),
  Field With Maximum Length (..128),
  [Optional Field (64)],
  Repeated Field (8) ...,
}

TLV Format

0        7
+--------+
| Tag    |
+--------+--------+--------+--------+
| Length                            |
+--------+--------+--------+--------+
| ...
+--------+--------+--------+--------+
| Value Payloads                    |
+--------+--------+--------+--------+
| ...
+--------+--------+--------+--------+
Base Packet {
  Tag (8),
  Length (8) ...,
  Value (8) ...,
}

Tag {
  TypeFlag (1),
  ArrayFlag (1),
  SequenceID (6),
}

Tag

标签（Tag）的长度是固定8 bits（1 byte）

8   7   6                0
+------------------------+
| F | A |     SeqID      |
+------------------------+
  1. 其最高位F（1000_0000）为数据包类型（Packet Type）标志位，Y3 Codec有两种数据包（Packet）：原始类型数据包（PrimitivePacket）和节点类型数据包（NodePacket）。
    1. 对于原始类型数据包（PrimitivePacket），该bit始终为0。
    2. 对于节点数据包（NodePacket），该bit始终为1。
  2. 【待讨论，请勿实现】次高位A（0100_0000）为数组标识位，当该位为1时，表示该节点的值（Value）为切片（Slice）类型（就像JSON中的数组概念）。
  3. 剩余低6位为顺序ID标识位（Sequence Bits），用于表示该节点的顺序ID（SeqID）（类似于JSON数据结构中的Key的作用）。

Primitive Types

表示其值（Value）的数据类型是基础数据类型。

Node Type

表示其值（Value）包含至少一个节点类型数据包（NodePacket）或原始类型数据包（PrimitivePacket），所有子节点按照Tag-Length-Value编码依次组合成该节点类型数据包（NodePacket）的最终值（Value）。

Length

值位长（Length）描述了该数据包（Packet）的值（Value）的字节长度，是变长整数类型。

Value

值（Value）存储了该数据包（Packet）的值内容，在解码（decode）时，再指明具体数据类型。

TLV Example

示例：如果使用Y3编码表示下面的JSON数据结构

{
    "age" : 5,
    "summary": {
      "name": "CELLA",
      "create": "Y3"
    }
}

首先，定义整个消息的结构，就像ProtoBuffer的.proto文件做的一样：

基础数据类型（Primitive Packet），Tag定义为0x01，表示”age"，其值为变长整型（pvarint）
节点数据类型（Node Packet），Tag定义为0x82，表示"summary"，该节点包含2个基础数据类型（primitive packets）:
  基础数据类型（Primitive Packet），Tag定义为0x03，表示"name"，值为字符串（string）类型
  基础数据类型（Primitive Packet），Tag定义为0x04，表示"create"，值为字符串（string）类型
  1. 使用Tag = 0x01描述key=age，其值是2，使用变长整型 [pvarint] 类型编码。
  2. 使用Tag = 0x82描述key=summary，其值需要从后续步骤推断。
  3. 使用Tag = 0x03描述key=name，其值是"CELLA"，使用字符串 [string] 类型对其编码。
  4. 使用Tag = 0x04描述key=reate，其值是"Y3"，使用字符串 [string] 类型对其编码。

编码顺序（序号表示顺序）:

1️⃣ 0x01 -> Tag=0x01 描述了 key="age"，因为最高位是0，表示它值是基础数据类型
    3️⃣ 0x01 -> 该值的长度为1个字节，所以后续1个字节就是该值的具体内容【对于变长整型（pvarint），0x01表示1】
      2️⃣ 0x05 -> 是变长整型（pvarint），0x05是数字5的编码
8️⃣ 0x82 -> Tag=0x82 描述了 key="summary"，因为最高位是1，表示它的值（Value）是节点数据类型
    7️⃣ 0x0B -> 该值的长度为11个字节，所以后续11个字节就是该值的具体内容【对于变长整型（pvarint），0x0B表示11】
      1️⃣ 0x03 -> Tag=0x03 描述了 key="name"，因为最高位是0，表示它值是基础数据类型
        3️⃣ 0x05 -> 该值的长度为5个字节，所以后续5个字节就是该值的具体内容【对于变长整型（pvarint），0x05表示5】
          2️⃣ 0x43 0x45 0x4C 0x4C 0x41 -> "CELLA"的UTF-8编码
      4️⃣ 0x04 -> Tag=0x04 描述了 key="create"，因为最高位是0，表示它值是基础数据类型
        6️⃣ 0x02 -> 该值的长度为2个字节，所以后续2个字节就是该值的具体内容【对于变长整型（pvarint），0x02表示2】
          5️⃣ 0x59 0x33 -> UTF-8 "Y3"的UTF-8编码

最终表示为：

0x01 0x01 0x05 0x82 0x0B 0x03 0x05 0x43 0x45 0x4C 0x4C 0x41 0x04 0x02 0x59 0x33

Primitive Type System

基础数据类型：

String

使用UTF-8编码

Binary

二进制原始数据

pvarint

变长整型，p-var-int 描述了一种长度可变的整型数值编码：

  • p 表示符号位填充（padding signed bit）。
  • var 表示长度可变（variable-length）。
  • int 表示整型（integer）。
8   7   6                0
+---+---+----------------+
| C |(S)|    payloads    |
+---+---+----------------+
  • 使用大端序（Big-Endian）编码
  • 最高位C是连续标识位（Continuation Bit），该位为1时表示下一个字节（byte）也是该值的一部分，需要继续读取；该位为0时表示该字节是整个数值的最后一个字节。
  • 对于有符号整数（Signed-Integer），次高位S是符号位（Signed Bit）；对于无符号整数（Unsigned-Integer），该位是数据位。
  • 与符号位相同的连续最高位只保留一位，剩余位（bits）使用符号位填充
pvarint for signed-integer {
  Continuation Bit (1),
  Signed Bit (1),
  Payloads (6..),
}

pvarint for unsigned-integer Value {
  Continuation Bit (1),
  Payloads (7..),
}

Pvarint Example

以Rust中的i32类型的十进制数511为例，其二进制表示为：0000 0000 0000 0000 0000 0001 1111 1111，使用了4个字节。如果使用[pvarint]类型编码，将分为以下4个步骤：

  1. 是有符号整数，其有效数据位是：xxxx xxx0 1111 1111（为了表示每个字节是8位，使用x表示忽略的数据位；511是正数，其符号位是0）
  2. 将所有的x位使用符号位0填充：0000 0001 1111 1111
  3. 因为最高位用以表示连续位，所以有效数据位只有7位，我们将每个字节的最高位都插入连续位y：y000 0011 y111 1111
  4. 如果后续还有字节，则该字节的连续标识位（Continuation Bit）为1，否则为0，因此得到：1000 0011 0111 1111

使用Y3编码后，只需要2个字节就表示了511。

以Rust中的i32类型的十进制数-1为例，其二进制表示为：1111 1111 1111 1111 1111 1111 1111 1111，使用了4个字节。如果使用[pvarint]类型编码，将分为以下4个步骤：

  1. 是有符号整数，其有效数据位是：xxxx xx11（为了表示每个字节是8位，使用x表示忽略的数据位；-1是负数，其符号位是1）
  2. 将所有的x位使用符号位1填充：1111 1111
  3. 因为最高位用以表示连续位，所以有效数据位只有7位，我们将每个字节的最高位都插入连续位y：y111 1111
  4. 后续没有字节，则该字节的连续标识位（Continuation Bit）为0，因此得到：0111 1111

使用Y3编码后，只需要1个字节就可表示-1。

Boolean

布尔类型可以使用 [pvarint] 类型描述，1表示True，0表示False。

Float

TODO

Slice

对于Tag的实现，考虑去除次高位的数组标示位，将Slice内置为基础数据类型，其结构为Length-Value的重复。