3.01 数据的计算¶
在1.05节中，我们提到，数据管理系统通常会提供一套数据访问语言，供用户表达数据访问需求。不同数据访问语言的表达能力各不相同，能满足的数据访问需求也不同，因此适用于不同的应用场景。但总的来说，数据访问并非简单的数据存取，还需要在数据上进行一定的计算，以获得比原始数据更进一步的信息。本章介绍数据管理系统实施数据计算的基本过程、架构和模式。
3.01.1 数据管理系统的基本架构¶
第2章介绍了数据管理系统是如何组织和存储数据的。但即便使用索引的存储结构，系统也只能提供简单的数据存取功能。要应对更广泛的数据访问需求，数据管理系统还需要提供一定的计算能力。
图3-1-1给出了一套数据管理系统的基本软件架构。大部分当代的数据管理系统都遵循这个架构。一个数据管理系统通常可以分为三个层次。最下层是存储引擎，提供数据的基本存取功能。其上是计算引擎，负责数据的处理和计算。最上层负责与应用和用户的交互。基于该架构，数据访问的过程大致如下：用户首先将由数据访问语言表达的数据访问请求发送给交互层；交互层解析用户的请求，构建出一套数据访问和计算的流程，将其发送给计算引擎；计算引擎负责执行该流程，一方面访问底层的存储引擎，完成数据的存取，另一方面在数据上实施计算，最终完成用户下达的任务；最后结果再通过交互层返回给用户。
3.01.2 数据查询的处理过程¶
对任意一种数据管理系统而言，它接收的数据计算指令都是由数据查询语言表达的查询语句。它每接收到一条查询语句，就会启动一个查询处理过程。该过程将规划并完成数据访问和数据计算，最后将查询结果返回给用户。一个查询处理的流程通常由查询解析、查询优化和查询执行三个步骤组成。
- 查询解析：查询解释通常是由数据管理系统的用户交互层完成的。它的主要工作是将用户的查询语句翻译成一个数据访问和计算的过程，称为查询执行过程。这个过程通常由多个数据访问和数据计算步骤组成，每个步骤都对应了一段系统内部的程序。一旦完成了查询解析，系统就基本明确了该查询可以如何被执行。用户提交的查询可能会包含一些语法或引用错误，这些错误都会在查询解析中被识别。
- 查询优化：查询优化功能通常是由数据管理系统的计算引擎提供的。虽然查询解析已经将用户的查询语句翻译成了一个可执行的过程，但这个查询执行过程未必是能被高效运行的。查询优化的目的是对这个执行过程进行适当改造，在不影响正确性的前提下，尽可能提升它的运行效率。查询优化采取手段可以包括：去除冗余的计算步骤（比如：如果已知数据已经满足了某个查询条件，就不必再使用该条件对数据进行筛选）、选择最优的数据访问方式（比如：判断使用某个索引是否比扫描全量数据更高效）、选择最优的数据计算算法（比如：判断归并排序算法和堆排序算法哪个在当前情况下运行效率更高）、确定最优的数据计算次序（比如：判断先排序后合并与先合并后排序哪个效率更高）、等等。
- 查询执行：查询执行是数据管理系统的计算引擎的主要任务。一旦通过了查询解析和查询优化，一个查询的执行过程就完全确定了。计算引擎只需要按部就班地运行查询执行过程对应的计算程序，就可以准确无误地获得查询结果。这些被查询执行过程调用的计算程序其实就是计算引擎的主要组成部分。这些计算程序的运行效率对查询性能至关重要。因此，它们通常是由系统开发工程师精心编写的高水准程序，是提升数据管理系统整体竞争力的重要因素。
3.01.3 数据管理系统的计算体系结构¶
图3-1-2简要地展示了数据管理系统的计算体系结构。数据存放在硬盘中的存储结构中。内存中通常会部署一个数据缓存，用于暂存热点数据，以提高数据访问的性能。硬盘的存储结构和缓存都由存储引擎管理，用于提供基本的数据存取功能。当接收到数据访问请求后，系统通过存储引擎将需要的数据取出，然后在计算引擎中开展计算。在计算过程中，这些数据需要被暂存在某个地方。计算还会产生中间结果。在最后结果被计算出之前，这些中间结果也需要被暂时存放。通常情况下，我们将计算过程中的数据放置在内存中，便于快速访问它们。这样的内存被称为工作内存。但内存往往是有限的。当中间数据的体量过大时，我们不得不将其暂存到硬盘中。因此，我们还需要一定的硬盘空间，可称为工作硬盘，以协助完成计算工作。
某些数据管理系统并不是针对数据分析应用设计的，比如键值数据库、文档数据库等，其数据访问过程涉及的计算通常比较简单，因此不需要提供太强的计算功能。这一类数据管理系统，往往不会配备强大的计算引擎，其性能主要由数据存取的效率决定。还有的数据管理系统，比如关系数据库，需要承载较复杂的数据分析和数据处理功能，会用到复杂的数据计算。此类数据管理系统的性能受计算效率的影响很大，其计算引擎就需要精巧的设计与实现。
3.01.4 数据计算性能¶
软件的运行效率不仅仅取决于软件本身的代码实现是否高效（例如算法的计算复杂度是否达到了最优），还取决于这些代码实现是否能够高效利用现代硬件的特点。应用程序对数据管理系统这样的基础软件提出了很高要求，希望它们能够高度适配底层硬件，从而充分发挥硬件的性能。应用软件与硬件的适配通常是交给代码编译器去自动实现的，不要求软件开发者深入了解硬件的特点。但对数据管理系统而言，编译器提供的适配能力是不够的。数据管理系统的开发人员需要充分理解底层硬件的运行机制，并针对性地设计系统内部的数据计算方法，才能构建出高性能的系统。这些针对性的计算方法设计是当代数据管理系统的核心技术之一。
在图3-1-2概括的计算体系结构中，数据计算的性能主要受两方面影响。一方面是访存性能。另一方面是CPU的计算性能。参与计算的数据可能在内存中，也可能在硬盘上。如果数据在硬盘上，硬盘访问将成为数据计算的主要性能瓶颈。如果数据仅在内存中，由于内存访问的速度远低于CPU的指令执行速度，访存过程仍然可能成为数据计算的性能瓶颈。为了获得良好的计算性能，需要让计算过程具备较高的数据访问局部性（参见2.01节）。这对数据管理系统计算引擎的设计提出了极高要求。
如果数据访问的局部性得到了保障，CPU的计算性能就成为了整体性能的主要因素。为了实现高效计算，CPU内部有很多特殊机制，例如流水线机制、向量计算加速机制（SIMD）、超线程机制等。能否有效利用这些机制是获取更高计算性能的关键。这对计算引擎设计的精巧性提出了更高要求。
对于不同的数据管理系统而言，由于其使用的数据模型和数据访问语言有较大差异，它们需要的计算功能和使用的计算方式都是不一样的。因此，本小节不具体讲述数据管理系统的具体算法设计，而只讨论一些计算引擎的笼统设计原则。
3.01.5 批处理和流处理¶
在数据上实施计算的过程往往由若干步骤组成。这些步骤的执行方式大致可以分为两类：批处理模式和流处理模式。它们之间的区别在图3-1-4中得到了展示。批处理模式按照计算的步骤分阶段对数据进行处理。每个阶段实施一个计算步骤，在全量数据上完成该步骤的计算任务后，再将结果整体发送给下一个阶段。执行完最后一个阶段，才能得到最终的数据处理结果。流处理模式则是将各个计算步骤串联成一条流水线。数据项逐个流入流水线。每个步骤完成一个数据项的处理即将其传递给下一个步骤。流水线一边处理数据一边返回结果。
下面的例子进一步展示了批处理模式和流处理模式的计算过程的差异。如图3-1-5所示，间隙编码（Gap Encoding）是一种常用的编码方式。对于一个由数字组成的有序序列，间隙编码不直接记录原始的数字，而是记录相邻数字之间的差距。例如，图中的第2和第3个数字（58和62）对应的间隙编码是30和4，分别是原始数字与自己上一位数字的差。这种编码方式不会丢失信息，可以通过对间隙编码进行累加获得完整的原始数据。这种编码方式的好处是可以大幅缩小数字的取值范围，从而起到很好的压缩效果。
图3-1-6展示了一种数据的平滑处理方法。对于一个由数字组成的序列，我们将每个数字替换为它与前后两个数字的平均值。例如，将58替换为28、58、62的平均值，即49，将62替换为58、62、78的平均值，即66，等。如图3-1-6中的曲线所示，经过平滑处理后的数据波动更小，但保持了原始数据的变化趋势。在现实应用中，类似的平滑数据处理方法常常被用到。
假设我们有一串采用了间隙编码的数字序列，希望将其恢复成原始数据后再对其进行上述的平滑处理。这个简单的数据处理程序既可以采用上面提到的批处理模式也可以采用流处理模式。采用批处理模式的程序可以编写成如下形式。
void transform(int data[], int length)
{
// 首先对所有数据进行解码
for(int i=0, int pre=0; i<length; i++)
{
data[i] = data[i]+pre;
pre = data[i];
}
// 再对数据进行平滑处理
for(int i=1, int pre=data[0]; i<length-1; i++) //第一个和最后一个数字保持原值
{
int x = data[i];
data[i] = (pre+data[i]+data[i+1])/3;
pre = x;
}
}
而采用流处理模式的程序可以编写成如下形式。
void transform(int data[], int length)
{
// 通过一次数据遍历完成解码和平滑处理
for(int i=0, int pre=0; i<length; i++)
{
// 完成当前数字的解码
data[i] = data[i]+pre;
// 完成当前数字的平滑处理
if(i==0 || i==length-1) //第一个和最后一个数字保持原值
pre = data[i];
else
{
int x = data[i];
data[i] = (pre+data[i]+data[i+1])/3;
pre = x;
}
}
}
站在程序编写的角度，批处理的程序显得更直观易懂，编写起来也更容易。然而，从性能上考虑，流处理程序的运行效率则更高。从上述程序我们可以看到，批处理需要对数据进行两次遍历，每次完成一个数据处理步骤。如果数据存放在内存中，这意味着CPU需要两次将数据调入到缓存中进行处理。而流处理只需要对数据进行一次遍历。数据被调入到缓存中后，CPU会连续完成两个数据处理步骤。也就是说，对于上述数据处理任务，批处理的访存代价是流处理的两倍。如果数据存放在硬盘上，流处理的性能优势则更加明显。对上述任务，批处理需要先将硬盘上的数据依次读入内存，解码后再依次写回的硬盘，紧接着再次将数据读入内存，完成平滑处理后再写回到硬盘。这意味着每个数据块需要4次硬盘读写操作。如果采用流处理，只需要读写硬盘各1次就能每块数据的处理任务。
总而言之，流处理模式具备更好的数据访问局部性，通常会带来更高的性能。同时，流处理模式耗费更少的空间来存放数据处理的中间结果，对资源的利用率也更高。因此，当代的数据管理系统更多采用流处理模式进行数据计算，虽然这意味着更复杂的系统实现方式。然而，值得指出的是，并非所有的数据处理流程都能通过流处理模式实现（读者可自行思考什么样的数据处理过程无法被流水线化）。因此，数据管理系统通常也不会完全抛弃对批处理模式的使用。
3.01.6 火山模型¶
当代的大部分数据管理系统都使用火山模型来实现流处理模式的数据计算引擎。通常，一个数据管理系统允许用户将多个计算步骤灵活组合成各式各样的数据处理流程，以满足不同的数据计算需求。这样的数据处理流程可能多达成千上万种（甚至可以有无限多）。我们显然无法为每一个流程都单独编写一个如上节所述的数据处理流水线。鉴于一个数据管理系统通常只提供有限种类的数据计算步骤，我们希望只为每一种计算步骤编写一段程序，再使用一个灵活的主程序，根据用户的需要，将各个步骤连接成一个数据处理流水线。火山模型就为我们提供了像这样的一种数据处理流水线的实现方式。
在火山模型中，每一种计算步骤被抽象成一个数据处理算子（Operator）。每一个数据处理算子则被实现为一个迭代器，对外提供了以下三个接口：
- open()：数据算子初始化，分配资源；
- next()：算子的具体实现。首先向下游算子获取下一条数据记录，并对其进行处理；如果处理结果满足既定条件，就将结果返回给上游算子；否则，继续向下游算子获取数据。
- close()：回收和关闭分配给算子的资源。
上下游算子之间有嵌套调用的关系，就构成了数据处理流水线。例如，上一节提到的平滑曲线计算过程可以被分解成三个算子，分别为数据读取算子、解码算子和平滑算子。基于火山模型，我们可以将它们各自实现为如下的迭代器。三个迭代器通过嵌套调用，就构成一条平滑曲线计算的流水线。
//数据读取算子的实现
static int* read_data; //原始数据
static int read_length，read_cur; //原始数据的长度和当前读取的下标
void readopen(int* input_data, int input_length) //数据读取算子的初始化
{
read_data = input_data;
read_cur = 0;
read_length = input_length
};
int readnext()
{
if(read_cur >= readlength)
return END; // END表示读到了数据的末尾
return read_data[read_cur++];
}
void readclose(){}; //无资源可释放
//解码算子的实现
static int decode_sum; // 当前数据的解码值，即已读数据的累加值
void decodeopen(int* input_data, int input_length) //解码算子的初始化
{
decode_sum = 0;
readopen(input_data, input_length);
}
int decodenext()
{
int item = readnext(); //调用数据读取算子
if(item == END)
return END;
decode_sum += item;
return decode_sum;
}
void decodeclose()
{
readclose();
//无资源可释放
};
//平滑算子的实现
static int smooth_count; // 已读取的数据数量
static int window[3]; // 平滑窗口中的各个数据
static int end_count; // 已读到的END数
void smoothopen(int* input_data, int input_length) //平滑算子的初始化
{
smooth_count = 0;
end_count = 0;
decodeopen(input_data, input_length);
}
int smoothnext()
{
if(end_count == 1)
return END;
if(smooth_count == 0)
{
smooth_count++;
window[0] = decodenext(); //调用解码算子
return window[0];
}
if(smooth_count == 1)
{
smooth_count += 2;
window[1] = decodenext(); //调用解码算子
window[2] = decodenext(); //调用解码算子
return (window[0]+window[1]+window[2])/3;
}
smooth_count++;
int item = decodenext(); //调用解码算子
if(item == END){
end_count++;
return window[2];
}
window[0] = window[1];
window[1] = window[2];
window[2] = item;
return (window[0]+window[1]+window[2])/3;
}
void smoothclose()
{
decodeclose();
//无资源可释放
};
/*
注意：为了便于理解，上述例子使用了硬编码的方式，即个每个上游算子直接显式地调用下游算子。
实际的数据管理系统允许用户对各个算子进行任意组合。因此，在实际的实现代码中，每个算子事
先并不知道各自的下游算子是谁，而需要主程序将下游算子通过函数指针传递给各个算子。这种实
现方式称为后期绑定(Late Binding)，即让程序在运行过程中才决定某个函数调用指令到底调用
哪个函数。读者可以各自思考如何用后期绑定的方式实现以上流水线。
*/
以上程序将三个算子链接成了如图3-1-7所示的数据处理流水线。在这样一条流水线中，一个算子的上层算子称为它的上游算子，一个算子的下层算子称为它的下游算子。上游算子和下游算子之间是调用与被调用的关系。在进行数据处理时，主程序不断循环调用最上游算子的next()函数。每次调用后，最上游算子都会返回一个数据处理结果。这个过程会持续到最上游算子报告数据读取结束为止（上述程序使用常量END代表数据读取结束），至此主程序就得到了所有的数据处理结果。在每次调用过程中，上游算子会依次调用下游算子，而数据（或数据计算的中间结果）则会被下游算子逐级返回给上游算子。一旦一项数据从最底层的算子流到最上层的算子，系统就完成了对它的计算。因此，这个计算过程显然遵循的是流处理模式，而非批处理模式。在整个循环调用的过程中，数据会源源不断的从底层算子流到顶层算子，就像火山喷发时岩浆源源不断从地壳下面流到火山口一样。火山模型因此得名。
从程序实现代码可以看出，本节用火山模型实现的数据处理流水线并没有上一节通过直接编码得到的流水线简洁高效。然而，火山模型却提供了对数据处理算子进行灵活组合的能力。只要完成了每个算子的火山模型迭代器实现，我们就可以将这些算子组合成任意形态的数据处理流水线，并将其交给系统去运行。
由火山模型实现的流水线通常会使用大量的函数调用。熟悉计算机系统工作原理的读者可能会意识到，过于密集的函数调用会严重影响程序的运行性能。当代的很多数据管理系统已经在着手对传统的火山模型的代码运行效率进行优化。鉴于这些优化技术已经超过了本书的范围，此处不做更多展开。编者鼓励有兴趣的读者去查考最新的数据处理引擎的实现技术，例如ClickHouse、DuckDB等。
练习题¶
1. 请分别用批处理模式和流处理模式编写以下计算流程的程序。测试并比较两者的计算速度。
输入：一个数列 $A = a_0, a_1, a_2, ..., a_n$\
输出：一个数列 $C = c_2, c_3, c_4, ..., c_n\(\
**过程**：计算过程分为两个步骤。第一个步骤将数列A转换为数列B，转换方法为\)b_i = a_{i-1} + a_i\(。第二个步骤将数列B转换为数列C，转换方法为\)c_i = b_{i-1}^2 + b_i^2$。
2. 请用火山模型编写上一题的程序。将两个计算步骤编写为两个独立的算子。