z2z63/Virtualfuture's Blog
Posts Friends About
z2z63/Virtualfuture's Blog

第二周：败者树、范式与反范式

z2z63 avatarz2z63
     6744 words   30 minutes 

新内容的博客主题并不明显，基本是最近学习到的知识，平日突然浮现在头脑中的随想，或者很久以前遇到过的一些事情

归并排序与败者树

上篇文章提到的归并排序，经过两次重构已经很完善了，最终的结果是一个归并排序类ExternalMergeSorter，通过一个头文件引入external_merge_sort.h, 非常优雅地隔离了归并排序的细节，只需要给sorter提供记录，然后指示sorter开始排序，最后依次从sorter中取出记录，取出的记录已经是有序的了

关于IO的方式也考虑了很多，mmap，read， fread，std::fstrean都能实现需要的功能，最终选择了std::fstream

  • mmap
    效率很高，读入文件时，相比read少了一次内核数据复制
    read时： 外存中的文件 –> 内核维护的缓冲区 –> 进程维护的缓冲区 mmap时： 外存中的文件 –> 内核分配给进程的页

    mmap分配的页是惰性分配的，mmap调用返回时，分配的页仍然是用户地址空间非法的页，进程第一次访问时，陷入内核态（因为访问了非法的页），然后内核完成页的分配，并填入正确的数据

    此外，mmap分配的页也会正常的换出换入内存，实际内存使用量不会很高

    Q：为什么read读取文件时有内核维护的缓冲区和进程维护的缓冲区？
    A: 内核维护的缓冲区是对进程隐藏的，进程无法访问（在进程的地址空间中不存在），这是为了防止恶意进程破坏操作系统

    部署数据库的服务器可能会关闭内存交换功能，此时操作系统不会将近期不使用的页换出内存

    不过缺点也很明显，需要手动维护读写指针，而且如果设置了每次mmap的页（不是操作系统的页）的大小，还需要再实现大文件分页，包括不满一页，刚好满一页，满n页不满n+1页各种corner case，并需要给corner case写测试，非常繁琐

  • read read和mmap都是linux的系统调用，使用read时操作系统会帮我们维护读写指针，但仍然需要自己处理分页

  • fread libc提供的IO函数，内部会自动维护缓冲，读写指针，如果设置了缓冲区大小，也相当于有了分页的功能

  • std::fstream libc++的IO函数，fread已经能满足要求了，但使用std::fstream是一种"when in cpp do as the cpper do"的做法

归并排序处理大规模数据时，会形成多个文件，假设为k个，最终将k个已排序块合并的过程，就是k路归并排序
k路归并时，每次取出k个已排序块中最小的记录，如何确定哪个记录是最小的，可以简单的遍历k个记录，找出其中最小的一个，也可以使用胜者树、败者树加快归并的过程

遍历k个记录，可以被称为暴力查找，时间复杂度是$$O(k)$$ 而胜者树、败者树的时间复杂度为$$O(\log k)$$

k值一般不会很大，经典值有8，16。虽然k很小，但因为取出每条记录都需要经过归并，此处的算法优化效果是非常可观的，我测试的情况是64M规模排序，使用暴力查找耗时5min，使用败者树耗时大约5s

胜者树的思想是，假设有八个选手A，B，C，D，E，F，G，H参与比赛，他们两两配对并参与比赛，比赛的胜者参与下一轮比赛，只需要三轮比赛就能比出冠军

text

第三轮比赛的胜者                A
第二轮比赛的胜者        A                 H   
第一轮比赛的胜者  A          D        E        H
参赛选手      A    B    C     D   E    F   G    H

八个选手中A胜出，胜者树记录了A通过比赛不断“上升”的过程 现在假设因为某种原因，原来的冠军A被替换成A1，而A1的排名未知，需要重新确定冠军

  1. A1与B比赛，如果A1胜，则A1作为胜者进入下一轮比赛，如果B胜，则B作为胜者进入下一轮
  2. 设A与B比赛的胜者为X1(X1 = A1 | B)， X1与D比赛， 产生的胜者X2进入下一轮
  3. X2与H比赛，产生的胜者即为冠军

胜者树的算法思想是动态规划，八个选手比赛的过程中，有很多重复的子问题，例如，A的排名需要重新确定时，C和D的胜负关系是不会改变的，所以C和D没必要再比赛，同理E和H也没必要再比赛，胜者树这样的数据结构在归并过程中维护了最优子结构，避免了重复完成子问题

将胜者树中的节点的值换成这轮比赛中的败者，其他不变，就形成了败者树

败者树的一个缺点就是不直观，因为节点记录了败者，但参赛的仍然是胜者，事实上，在构建败者树的过程中仍然需要构建胜者树。

败者树相比胜者树的优点是，重新确定冠军时，当前参赛选手需要和上次当轮比赛的败者比赛（例如第一轮比赛中，X1需要和D比赛），胜者树需要从兄弟节点获取败者，而败者树可以直接从父节点获取败者

败者树的另一个理解是，败者树的节点中存储的是左右子树两胜者中比赛产生的次胜者，而优胜者进入下一轮比赛。例如败者树中存储了D的节点，D来源于第一轮比赛中A和D比赛，其中A是优胜者，D是次胜者

text

冠军                          A
第三轮比赛的败者                H
第二轮比赛的败者        D                 E
第一轮比赛的败者  B          C        F        G
参赛选手      A    B    C     D   E    F   G    H

此外败者树的根节点记录的是败者，所以还需要额外记录一个冠军

我使用堆模拟了败者树，败者树也是一种二叉树，堆模拟二叉树的优点如下

  1. 内存碎片小
  2. 节点在内存中是紧邻的，能充分利用高速缓存的性能，cache友好

此外，堆模拟的二叉树中访问父节点，兄弟节点也非常简单，可以使用位运算
假设堆的大小为16，第一个元素不使用，模拟的二叉树如下

text

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

其中的数组表示节点的编号，或节点在堆中的索引 假设当前节点为x，其父节点为x >> 1，兄弟节点为 x ^ 1，左子节点为x << 1，右子节点为(x << 1) + 1

其中第一个未使用的元素在败者树中刚好用来存储冠军，非常巧妙
堆模拟败者树有两个坑点：

  1. 分清节点编号和选手编号（在这篇文章中我特意使用字母ABC表示选手编号，而使用数字123表示节点编号，但实现时，使用的都是数字类型）
  2. 堆模拟的败者树消除了败者树的优势：直接从父节点获取败者，因为堆访问兄弟节点非常方便，而且没有额外的空间开销。此外败者树非常不直观，如果使用堆模拟，可以考虑胜者树

外部归并排序中产生多少个辅助排序文件，一般是不可控制的，选手数量往往不是2的幂
此时增加若干个哑节点(dumb node)，使选手数量达到2的幂，哑节点参与比赛一定败北

最终实现见external_merge_sort.h，在木兰宽松许可证下开源

exit

在对比fread，fwrite和std::fstream时，看到有篇回答提及，如果程序异常退出，std::fstream可能来不及把缓冲区的内容落盘

cpp

#include <stdlib.h>
#include <fstream>
using std::ofstream;

int main() {
  ofstream ofs("hello.txt");
  ofs << "Hello world\n";
  exit(0);
}

这里又涉及一个问题，std::fstream需要手动关闭吗？

答案是可以不手动关闭，因为fstream会在析构时自动关闭。见cppreference对basic_fstream的析构函数的说明

destructs the basic_fstream and the associated buffer, closes the file

然后来翻源码证实一下
首先看一下cppreference对fstream，ifstream，ofstream的说明
basic_istream最终实例化为ifstream，basic_ostream最终实例化为ofstream，basic_iostream最终实例化为fstream，所以fstream相当于ifstream和ofstream的父类

以ofstream举例，它的析构函数在glibc的头文件fstream中

cpp

      /**
       *  @brief  The destructor does nothing.
       *
       *  The file is closed by the filebuf object, not the formatting
       *  stream.
       */
      ~basic_ofstream()
      { }

看来关闭文件的工作是交给filebuf完成的，此处的filebuf指的是basic_ofstream的成员变量_M_filebuf 实现如下

cpp

      /**
       *  @brief  The destructor closes the file first.
       */
      virtual
      ~basic_filebuf()
      {
	__try
	  { this->close(); }
	__catch(...)
	  { }
      }

那么自动关闭和手动关闭的区别在哪里呢？ ofstream的close方法实现如下

cpp

      /**
       *  @brief  Close the file.
       *
       *  Calls @c std::basic_filebuf::close().  If that function
       *  fails, @c failbit is set in the stream's error state.
       */
      void
      close()
      {
	if (!_M_filebuf.close())
	  this->setstate(ios_base::failbit);
      }

它也是调用了filebuf的close方法，除了错误处理有所不同，其他完全一样

初学时总被反复提醒ofstream打开了一定要关闭，但实践不一定需要完全遵循，举几个例子

  1. 一个很短的函数内打开ofstream，可以不关闭，函数退出时自动关闭
  2. 一个很长的函数内打开ofstream，为了尽快释放资源可以手动关闭，也可以利用对象离开作用域立刻销毁的特性，额外创建一个作用域，让ofstream提前销毁，这也是更符合C++的RAII的做法

cpp

{
  std::ofstream file("output.txt");
  // 写入文件
}
// 此处已经关闭

这个特性在其他语言中很少出现，因为C++无GC，对象销毁时机是完全确定的，而GC语言即使提供了析构函数，因为无法确定对象销毁时机，实现某些对销毁时机非常敏感的特性（例如RAII的锁）时，会出现很多无法预料的情况

libc在进程退出和exit时会自动将所有FILE缓冲区残留的数据落盘，并释放缓冲区
linux在进程exit系统调用时会自动关闭进程未关闭的文件，并释放进程的内存

fstream的关闭依赖于其析构函数的调用，只需要绕过析构函数即可，绕过方法其一就是exit函数

前文提及libc的exit函数会关闭所有打开的FILE，关闭的过程包括缓冲区残留的数据落盘和释放缓冲区，但exit函数不会关闭ofstream，因为ofstream自己维护了一个缓冲区，而没有使用FILE对象的缓冲区

首先确定一点，ofstream会自动分配缓冲区，也可以由用户手动设置缓冲区

ofstream的open方法实现如下

cpp

  template<typename _CharT, typename _Traits>
    typename basic_filebuf<_CharT, _Traits>::__filebuf_type*
    basic_filebuf<_CharT, _Traits>::
    open(const char* __s, ios_base::openmode __mode)
    {
      __filebuf_type *__ret = 0;
      if (!this->is_open())
	{
	  _M_file.open(__s, __mode);
	  if (this->is_open())
	    {
	      _M_allocate_internal_buffer();
	      // 省略...
	    }
	}
      return __ret;
    }

_M_allocate_internal_buffer函数完成了缓冲区的自动分配，实现如下

cpp

  template<typename _CharT, typename _Traits>
    void
    basic_filebuf<_CharT, _Traits>::
    _M_allocate_internal_buffer()
    {
      // Allocate internal buffer only if one doesn't already exist
      // (either allocated or provided by the user via setbuf).
      if (!_M_buf_allocated && !_M_buf)
	{
	  _M_buf = new char_type[_M_buf_size];
	  _M_buf_allocated = true;
	}
    }

使用默认内存分配器申请了一块内存用于缓冲区，可以看到并没有把这块内存交给FILE管理

libc和libc++的实现都会随着版本迭代而变化，具体实现一般都对用户隐藏，而只暴露必要的接口，libc和libc++需要保持彼此独立所以也不能使用对方的非公开API

至此已经能回答之前的问题，为什么fstream在调用exit后数据没有落盘？因为数据残留在fstream内部维护的缓冲区中，没有同步到外存，而exit不负责为fstream清理残局

范式与反范式

纵观整个计算机体系，分层的思想从底层到上层都在不断的使用。有句名言：计算机中的一切问题都能使用分层解决
分层解决实际问题的例子

  • 计算机网络仅仅使用五层就实现了世界上规模最大最复杂的网络
  • 通过增加域名这一层，使得32bit的ip拥有了树状结构，符合人类社会的组织规律（国家区域顶级域名，用途特定域名gov,edu等），使得负载均衡，代理等灵活的技术成为可能

分层的工作是，使用当前层提供的原语，屏蔽当前层的细节，向上层提供更简单更强大的原语

以上是教科书内容，分层思想很伟大，但在实践中有时会违背分层的思想。分层是范式，所以理所当然有其反范式，例如NAT

NAT实现了网络地址的转换，它维护一个外网端口号：内网端口号+内网ip的映射，有关NAT的批评其一就是它违反了计算机网络中分层的思想，因为NAT工作在网络层，而它会修改端口号，而端口号属于传输层。即NAT修改了上层报文内容

这体现了分层往往存在的问题：分层尝试屏蔽底层细节，但无法完全屏蔽。所以计算机科学从业者就需要对整个计算机体系的每一层具有足够的了解，才能解决复杂的问题。例子

  • 即使使用C写操作系统，也不得不写汇编指令，因为C没有提供在C层面调用某些汇编指令的能力
  • 跨平台尝试抹平平台差异，但也会限制平台原生能力的使用，所以跨平台往往还需要写平台原生插件
  • linux的VFS向上层提供了一致的文件模型，屏蔽了底层资源、文件系统、硬件等差异，但数据库开发中还是需要考虑计算机的存储设备的硬件情况，例如磁盘读写时间包括了寻道时间，旋转延迟， 传输时间。而其中寻道时间和旋转延迟占了大部分时间，所以数据库会在内存中分块缓存修改后的文件内容，积累一段时间后再写回。数据库使用的IO策略立足于存储设备硬件现实

此外，分层也无法解决全部的问题，分层体系中，往往能找出一些上层重复实现底层功能的例子
例如

  • 操作系统提供了IO缓冲，而libc还要在实现一遍
  • 操作系统提供了LRU的页置换策略，而数据库还需要再实现一遍。数据库有时候甚至需要绕过操作系统这一层(前文提及“部署数据库的服务器可能会关闭内存交换功能”)
  • libc提供了内置的内存分配器，而postgresql也实现了自己的内存分配器
  • libc提供了许多标准库中的函数，例如字符串处理函数，memcpy等，这些在postgresql中也有重复实现

对这一现实，我的理解如下

  • 操作系统访问外存速度很慢，所以操作系统尝试缓冲IO，但进程进行系统调用的过程也很慢，所以libc提供IO缓冲，减少系统调用的次数，提高性能
  • libc的内存分配器和memcpy，考虑的是通用场景，而特定场景下的性能可能不如数据库的实现。例如内存分配器的一个功能是尽可能减少内存碎片，而每次需要分配的内存有多大是由用户随意决定的。如果数据库完全掌握内存使用情况，就能使用针对数据库场景优化的内存分配器，减少内存碎片
  • LRU置换策略，理由同上。数据库能针对各种算子专门优化，而操作系统无法知道进程何时需要访问页面，只能基于局部性原理进行假设
  • libc提供的字符串处理函数安全性不够，实际上很多大型项目都会重新造一遍字符串处理函数，为了解决诸如缓冲区溢出，零结尾等问题

关系型数据库的六范式的作用是减小数据冗余，消除插入异常，删除异常等，但在实践中，往往不会完全遵循六范式，因为划分实体和关联的工作非常复杂，只有领域专家才有可能做到。一般往往只遵循到第三范式

此外，关系型数据库的范式会使越拆越小，在查询时需要做大量的连接操作，连接操作可以使用索引，使用归并连接，使用哈希等方式加快连接速度，但对时间复杂度的减小效果有限，数据量极大时仍然非常耗时。大数据和NoSQL就完全违反了关系型数据库的范式，但换来了非常快的查询速度

如果一个人有很多钟，反而无法确定时间，因为不同钟显示的时间不一样。在工程实践中为了避免这种问题，往往遵循single source of truth，即唯一事实原则，例如

  • 将一些参数提升为配置，其他要使用参数的地方只能引用参数，不能内联
  • JS的ORM框架prisma使用prisma.schema作为唯一事实，并使用这一事实同步数据库和生成的类型

然而唯一事实原则也有其反范式，而且使用非常广泛，即cache
此处cache指CPU提供的高速缓存，它和内存共同维护了一个数据的两个副本，非常明显的反范式，后果就是需要额外维护cache和内存的一致性

  • cache有脏数据，而内存中的数据是干净的：需要将脏数据写回，而且需要选择写回时机
  • 内存中有脏数据，而cache中的数据是干净的，需要同步到cache

此外cache的存在对DMA非常不友好，让DMA变得更加复杂了，因为DMA能在不经过CPU的情况下读写内存

buffer vs cache

最近突发奇想，使用另一个角度理解缓冲与缓存

首先，我认为缓存的译名不准确，因为缓存的“缓”，在字典中是“慢”的意思，而缓存明显是用来加快速度用的，参考cache的台湾译名“快取”

有两个系统A和B，它们通过接口相连，然而A和B的速度是不匹配的（A速度远大于B）。基于以上事实，才有必要使用buffer或cache，这也是现实中非常常见的情况

两个速度不匹配的系统为了能够一起工作，必定还有其他条件，否则认为这两个系统不应该相互连接

如果两个系统不应该连接，此时有两种方案改进

  1. 使用性能更好的B1， 提高系统整体性能
  2. 使用性能低但更便宜的A1，降低系统的造价

此时使用buffer，即缓冲

  • 网络流量往往是猝发的，而操作系统或用户程序无法保证立马响应，所以网卡往往有缓冲区
  • 用户读写文件的操作往往是猝发的（例如一个文本编辑器，用户随时按下按键输入字符），libc维护缓冲区，延迟写入外存，提高IO性能
  • 操作系统为外设IO提供缓冲，因为外设产生数据是猝发的
  • 在加入少量的酸或碱时，溶液的PH值发生突变（扩散作用很快），而缓冲液可以在这个情况下减小溶液PH值变化速度和范围（化学反应速度比扩散作用慢）。缓冲剂往往远多于酸或碱的量（使用滴管加入的）。如果酸或碱的量太多，缓冲液的效果就不好

此时使用cache，即快取

  • 许多包管理器都有cache的功能，因为用户往往重复下载相同的软件包
  • CPU有cache，因为程序往往在一段时间内重复访问一块区域的内存，具有时间局部性和空间局部性
  • 浏览器会缓存部分文件，因为用户每次访问页面，都需要下载相同内容的文件
  • 为了加快访问速度，网站可以把静态资源放到CDN
Updated on 2024-07-01  6b3ea6d
 | Home