Paper Reading: Don't Hold My Data Hostage
这篇paper是 Don’t Hold My Data Hostage: A Case for Client Protocol Redesign, in VLDB, 2017。
对应15-721的Networking Protocols部分，主要涉及到数据库的传输协议设计，可以帮助解惑，为什么选择chunk-based的内存模型。
Introduction
从数据库传输large data出来，是一个常见的任务，比如一些复杂的AP分析和ML应用，都需要从访问大量的数据，这个过程cost是很昂贵的，尤其是当下基于cloud存储计算分离的数据架构。
下图展示了一个SQL查询，SELECT * FROM lineitem通过ODBC在不同database上的表现，虚线是netcat直接发送CSV文件的耗时。
localrun是代表client和server是在同一个机器上测试的，忽略了网络影响，只关注在(de)serialization消耗。当然后面也会加入网络消耗考虑。
State-of-the-art
Overview
第一步，需要搞清楚目前各种类的database在每个step上的耗时。因此，选取了不同种类的database，row-based：MySQL、PostgreSQL；columnar：MonetDB；NoSQL：HIVE，MongoDB。
MongoDB的传输的size是基准的6x，主要原因是它是基于document-based数据模型，每个document都可以是任意的schema，因此每个result都需要包含所有的fields name，从而造成了大量的overhead。
Network Impact
从上面localrun的结果，大致看出即使没有network影响，client和server的传输耗时仍然很大，因此network并不是传输的bottleneck，相比而言，(de)serialization result的消耗会更大。
network影响的更多是，传输协议client protocal的表现：
- low bandwidth：低带宽，导致传输数据会很慢
- high latency：高延迟，带来了及时性问题。即往返的确认数据包消息会更多，比如在authentication阶段。
latency越大，表现越差的可能原因：client和server之间需要，存在明确的confirmation message，才能ready to receive next data。
可以看出，所有的database都会随着latency增大，受到影响。这是因为所有protocol基于的底层TCP/IP，都要通过ACK来确认数据包收到，发送数据越多，受到影响的次数也就会越多。
当网络带宽太低的情况下，所有database情况都类似，这时候network就是当前bottleneck，而压缩与序列化则不是首要瓶颈。
Result Set Serialization
为了更好地分析不同protocol传输时间差距，第一步需要明白它们的serialization format。
我们准备2行数据，它的schema和data为
| int32 | varchar10 |
|---|---|
| 100,000,000 | OK |
| NULL | DPFKG |
下图为不同database的serialization fromat。数据为16进制格式，实际数据的字节为绿色，其它overhead的字节为白色，为了清楚展示，前导0展示为灰色。
PostgreSQL的序列化格式特点：
- 每一行都是单独一条message，包含total length，每个field length
- 如果field=NULL，长度为-1 (FFFFFFFF)
- cons: 每一行的metadata数据量，大于实际存储的数据量。这些冗余的信息，也解释了为什么PG传输的数据较多
- pros: 另一方面，这种简单的format，也减少了(de)serialization的cost，当网络不是瓶颈时，这种格式会降低传输时间，因为CPU消耗少
MySQL的序列化格式特点：
- metadata采用binary encoding，实际数据采用text encoding
- 行格式：3 byte数据长度 | 数据包序列号 | field长度 | field data
- NULL值，使用特殊字段长度 0xFB 进行编码
- field data以ASCII格式传输
Hive的序列化格式特点：
- Hive和Spark SQL都使用thrift-based协议传输数据
- Hive2开始使用columnar format形式，如上图中的column1和column2。thrift支持序列化结构化数据的能力
- 从上图也可以看出，一个column中许多不必要的开销(stop/beign/mask)等，这些cost取决于结果集中的行数
- 每个field的开销是，length和NULL mask。其中NULL mask为每个值一个byte，浪费了很大空间
Protocol Design Space
这章主要讨论，protocol设计在computation和transfer之间的trade-off。
Row vs Column Layout
- 行存：most systems采用的方式。比如ODBC/JDBC。优势：直观，调试友好。
- 列存：相同类型的数据存储在一起，数据更紧凑，利于更好的压缩。存在问题：传输是要等column1发完，才能接受下个column数据。
因此折中的方案是：vector-based / chunk-based。即chunk直接是按行切分，而chunk内部是按列存储的。
Chunk Size
chunk-based方案中，chunk size如何选择？
- chunk size越大：客户端每次需要分配的memory越多。
- chunk size太少：无法获取到columnar的优势。
上图不同chunk size分析出结论：
- 当chunk size很小=2KB时：即一个chunk可能就只是一行数据。耗时最长，发送数据最多，压缩率最低。
- 当chunk size=1MB时：在不同数据集中，都有很好的表现。因为大小刚好，client也不需要分配大量内存去处理数据。
Data Compression
数据压缩在Row Layout和Column Layout上不同表现，普遍列存压缩率较高。
数据压缩率也存在着trade-off。如果压缩率过高，则数据量变小，网络传输cost降低；但同时带来CPU压力变大，也会影响性能。
如上图展示：
- 最好的压缩算法，其实依赖于client和server之间的网络环境。
- 如果是localrun，则不需要任何压缩。如果网络带宽是个瓶颈，则轻量的压缩带来性能会更好。
同时，还有基于特定列类型的压缩算法。但它们在不同数据集上表现差距太多，可能由于NULL值影响，因此文章目前没有采用。
Data Serialization
前面我们已经得出了一个row或column的编码方式，现在需要一种序列化多条数据的方式。如下图，比较了custom serialization和protocol buffer。
总结：自定义的格式性能会更好。原因：protobuf作为一种通用的protocol，它在server和client端都必须要做字节序大小端转换，带来了不必要消耗。
String Handling
字符串序列化是比较困难的部分，它的常见编码方法有：
- Null-Termination：用一个0 byte标志字符串结尾
- cons：client必须scan完当前整个字符串，才能知道下个字符串开始。
- Length-Prefixing：字符串开头记录它的长度
- pros：可以直接计算出下个字符串读取位置。
- cons：需要额外空间存储长度，特别当大量小字符串时候。它可以通过varint prefix解决。
- Fixed-Width：每个字符串都是对应SQL Type的固定长度
- cons：理想情况下，字符串没有额外padding。但是对于varchar来说，大小不够长的字符串，也会引入额外padding。
如上图表示，1_returnflag列长度为1，分析得出：
- VARCHAR(1)：这种情况下的fixed-width性能最好，因为它没有额外padding
如上图表示，1_comment列最大长度为44，分析得出：
- VARCHAR(44)：它传输的size是上面2种的2x倍，原因有些字符串不足44，需要额外padding。
- VARCHAR(10000)：大量的额外padding，对性能有很大影响。
- fixed-width适合小字符串，不适合变长的大字符串。
- 大变长字符串情况下，Null-Terminated更合适。
Implementation
作者为PostgreSQL设计了一个新的chunk-based protocol，相比原来figure5中的row-based，新的serialization format如下
相比原先serialization format的改动：
- chunk-based layout
- NULL值处理：每个column数据之前都有bitmask来标志哪一行数据不存在。
三个数据集的测试结果表明，LAN网络环境下，PG(chunk-based+压缩) 耗时相比 原生PG(row-based) 都至少减少2倍以上。
延伸阅读
TiDB 2.0 中，我们引入了一个叫 Chunk 的数据结构用来在内存中存储内部数据，用于减小内存分配开销、降低内存占用以及实现内存使用量统计/控制，其特点如下：
- 只读
- 不支持随机写
- 只支持追加写
- 列存，同一列的数据连续的在内存中存放
在这一版本中，SQL 执行引擎引入新的内部数据表示方式 — Chunk，一个结构中保存一批数据而不仅是一行数据，同一列的数据在内存中连续存放，使得内存使用更紧凑，这样带来了几点好处：
- 显著减小了内存消耗；
- 批量分配内存，减小了 GC 开销；
- 算子之间可以对数据进行批量传递，减小调用开销；
- 在某些场景下，可以进行向量计算以及减小 CPU 的 Cache Miss 的情况。
TiDB 2019 The Future of Database Vectorized与SIMD 部分
TiDB SQL 引擎是用了 Volcano 模型，这个模型很简单，就是遍历一棵物理计划的树，不停的调 Next，每一次 Next 都是调用他的子节点的 Next，然后再返回结果。这个模型有几个问题：
- 第一是每一次都是拿一行，导致 CPU 的 L1、L2 这样的缓存利用率很差，就是说没有办法利用多 CPU 的 Cache。
- 第二，在真正实现的时候，它内部的架构是一个多级的虚函数调用。大家知道虚函数调用在 Runtime 本身的开销是很大的，在 《MonetDB/X100: Hyper-Pipelining Query Execution》 里面提到，在跑 TPC-H 的时候，Volcano 模型在 MySQL 上跑，大概有 90% 的时间是花在 MySQL 本身的 Runtime 上，而不是真正的数据扫描。所以这就是 Volcano 模型一个比较大的问题。
- 第三，如果使用一个纯静态的列存的数据结构，大家知道列存特别大问题就是它的更新是比较麻烦的， 至少过去在 TiFlash 之前，没有一个列存数据库能够支持做增删改查。那在这种情况下，怎么保证数据的新鲜？这些都是问题。
我们已经把 TiDB SQL 引擎的 Volcano 模型，从一行一行变成了一个 Chunk 一个 Chunk，每个 Chunk 里面是一个批量的数据，所以聚合的效率会更高。而且在 TiDB 这边做向量化之外，我们还会把这些算子推到 TiKV 来做，然后在 TiKV 也会变成一个全向量化的执行器的框架
未来一定 I/O 不会是瓶颈，那瓶颈会是什么？CPU。我们怎么去用新的硬件，去尽可能的把计算效率提升，这个才是未来我觉得数据库发展的重点。比如说我怎么在数据库里 leverage GPU 的计算能力，因为如果 GPU 用的好，其实可以很大程度上减少计算的开销。所以，如果在单机 I/O 这些都不是问题的话，下一个最大问题就是怎么做好分布式，这也是为什么我们一开始就选择了一条看上去更加困难的路：我要去做一个 Share-nothing 的数据库，并不是像 Aurora 底下共享一个存储。