Posts

B 树 B 树（B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。 在 B 树中，有两种结点: 内部结点（internal node）：存储了数据以及指向其子结点的指针。 叶子结点（leaf node）：与内部结点不同的是，叶子结点只存储数据，并没有子结点。 B+ 树 B+ 树是 B 树的一个升级。 所有的非叶子结点可以看成是索引部分，不存储数据； 叶子结点存储数据，并且所有叶子结点形成链表。 相比 B 树的优点 B+ 树中数据都存储在叶子结点上并链接在一起，这使得 B+ 树在查询范围内的数据时更加高效，因为它可以在一次遍历中查询出所有符合条件的数据。 全表扫描性能好，而B树需要完整遍历整棵树。 B-link 树 B-link 树是在 B+ 树上的一种改进，该结构提升了读写并发度，能够保持高并发下的性能稳定。PostgreSQL 中使用的就是这中索引结构。 在中间结点增加字段 link pointer，指向右兄弟结点，B-link Tree 的名字也由此而来； 在每个结点内增加一个字段 high key，在查询时如果目标值超过该节点的 high key，就需要循 着 link pointer 继续往后继结点查找。 优势 树结构调整时无需对全局或者局部子树加锁，进而有利于高并发下的性能稳定性。 哈希索引（Hash Index） 哈希索引是基于哈希表实现的。对于每行数据，存储引擎都会对所有的索引列计算一个哈希值，哈希值不同键值的行计算出来不同，哈希索引将所有的哈希值存储在索引中，同时在哈希表中保存指向每个数据行的指针。 全文索引（Full-text Index） 全文索引是一种特殊的索引结构，它主要用于快速查询文本数据。全文索引使用的数据结构通常是倒排索引。倒排索引是一种线性结构，它记录了每个单词出现在文本中的位置。使用倒排索引可以快速查询出符合某些文本条件的数据。 空间索引（Spatial Index） 需要存储一些地理数据的位置或需要存储形状相关的数据时，可以使用空间索引。 R-Tree R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据创建索引。 KD-Tree kd-tree简称k维树，是一种空间划分的数据结构。常被用于高维空间中的搜索。 网格索引（Grid Index） 对地理空间进行网格划分，划分成大小相同的网格，每个网格对应着一块存储空间，索引项登记上落入该网格的空间对象。 BRIN 索引 Block Range Index，简称BRIN索引。...

前期准备 拉取 Docker image docker pull registry.cn-shanghai.aliyuncs.com/suling/openwrt:x86_64 注：这里的镜像 tag 为架构，这里是 x86_64，可以根据自己的架构选择镜像。 开启网卡混杂模式 sudo ip link set eth0 promisc on 这里的eth0修改为自己的网卡名称。 创建 Docker 网络 docker network create -d macvlan --subnet=192.168.0.0/24 --gateway=192.168.0.1 -o parent=eth0 macnet 同样的，这里的subnet修改为自己的网段，gateway修改为当前网络内的网关。 部署镜像 创建网络配置文件 vim /path/to/openwrt/network 配置文件如下： config interface 'loopback' option ifname 'lo' option proto 'static' option ipaddr '127.0.0.1' option netmask '255.0.0.0' config globals 'globals' option packet_steering '1' config interface 'lan' option type 'bridge' option ifname 'eth0' option proto 'static' option ipaddr '192....

原文 Are You Sure You Want to Use MMAP in Your Database Management System? 4 实验分析 正如上一节解释的那样，一些mmap的问题可以通过仔细地实现来克服，但是我们认为，如果不进行重大的操作系统级别的重写，其固有的性能限制就无法解决。在这一节，我们通过实验结果分析展示了这些问题。 我们所有的实验在一个单处理器插槽的机器上运行，其配置信息为：AMD EPYC 7713 CPU(64 cores, 128 hardware threads)，512GB RAM，其中100GB可用于Linux（v5.11）的页面缓存，对于持久性存储，该机器有10×3.8TB的 三星PM1733固态硬盘（额定读取速度为7000MB/s，写入速度为3800MB/s），我们将固态硬盘作为块设备来避免潜在的文件系统开销。 作为基准线，我们使用了存储基准工具fio1，使用直接I/O(O_DIRECT)来绕过操作系统页面缓存。我们的分析专门聚焦在只读工作负载上，这代表了基于mmap的DBMS的最佳情况；否则，他们需要实现复杂的更新保护（3.1节），从而产生大量的额外开销。特别的是，我们评估了两种常见的访问模式：(1) 随机访问 和 (2) 顺序访问。 4.1 随机读取 在第一个实验中，我们在一块2TB SSD 范围内使用随机访问模式来模拟大于内存的OLTP工作负载。由于页面缓存只有100GB的内存，95%的访问都导致了缺页中断（即工作负载是I/O绑定的）。 图2a展示了100个线程每秒随机读取的数量。我们的fio基准线表现出了稳定的性能，达到了接近每秒90万次的读取速度，这符合100次出色的I/O操作和大约100𝜇s的NVMe延迟的预期性能。换句话说，这个结果表明，fio可以使NVMe SSD的性能完全饱和。 另一方面，mmap表现较差，即使是使用提示来匹配工作负载访问模式。我们在实验中观察到MADV_RANDOM的三个不同阶段。mmap在开始的27秒内与fio表现接近，然后在接下来的5秒钟突然下降到接近0，最后恢复到fio性能的一半。这个突然的性能下降发生在页面缓存被填满的时候，迫使操作系统开始从内存把页面置换出去。不出意料地是，其他访问模式提示下有更糟的性能表现。 在3.4节，我们列举了页面置换开销的三个关键来源。第一个问题是 TLB shootdowns2，我们使用/usr/interrupts记录的情况如图2b所示。如前所述，TLB shootdowns是十分昂贵的（需要成千上万个时钟周期），因为它涉及到发送处理器间的中断来刷新每个核心的TLB。第二，操作系统使用单个进程（kswapd）来置换页面，这在我们实验中是受CPU限制的。最后，操作系统必须同步页表，这在许多并发的线程中变得高度有竞争性。 4.2 顺序扫描 顺序扫描是DBMS的另一种常见的访问模式，特别是在OLAP工作负载中。因此，我们也在2TB SSD范围内对比了fio和mmap的扫描性能。我们首先使用仅仅一块SSD运行了我们的实验，然后我们在10块SSD组成的RAID 0上重新跑了相同的工作负载。 图3展示了fio可以利用一块SSD的全部带宽，同时保持稳定的性能。像之前的实验一样，mmap的性能开始和fio相似，但我们再次观察到，一旦页面缓存在大约17秒后被填满，性能就会急剧下降。另外，和这个工作负载预期的一样，MADV_NORMAL和MADV_SEQUENTIAL标志位比MADV_RANDOM性能要好。 图4展示了在10块SSD上重复顺序扫描的结果，进一步凸显了现代闪存理论上能够提供的与mmap能够实现的之间的差距。我们观察到在fio和mmap之间大概有20倍的性能差距，与使用一块SSD的结果相比，mmap几乎没有任何提升。 总的来说，我们发现mmap仅仅在单块SSD上的初始加载阶段表现得好。一旦页面置换开始或者使用多块SSD，mmap要比fio差2~20倍。随着PCIe 5.0 NVMe得即将发布，预计每块SSD的带宽将增加一倍，我们的结果展示了mmap不能够与传统的文件I/O的顺序扫描的性能相媲美。 6 结论 本论文提出了反对在DBMS中使用mmap来进行文件I/O。尽管有有限的好处，我们还是介绍了mmap的主要缺点，我们的实验分析证实了我们在其性能限制的发现。最后，我们向DBMS的开发者提供以下建议。 什么时候你不应该在你的DBMS中使用mmap： 你需要以一种事务安全的方式进行更新。 你想在不阻塞慢速I/O的情况下处理缺页中断，或者需要对内存中的数据进行明确控制。 你关心错误处理，需要返回正确的结果。 你需要在高速持久性存储设备上获得高吞吐量。 什么时候你也许应该使用mmap： 你的工作集（或者整个数据库）适合在内存中，并且工作负载是只读的。 你需要急于将产品推向市场，而不关心数据的一致性或者长期工程的头痛问题。 否则，永远不要使用。 fio: Flexible I/O Tester. ↩︎...

反向传播 反向传播（英语：Backpropagation，意为误差反向传播，缩写为BP）是对多层人工神经网络进行梯度下降的算法，也就是用链式法则以网络每层的权重为变数计算损失函数的梯度，以更新权重来最小化损失函数。 简单例子计算 符号 $ w_{ij} $ 权重 $ z_i $ 输入 $ y_i $ 输出 $ E = \frac{1}{2}(y_p-y_a)^2$ 损失 $ f(x) = \frac{1}{1+e^{-x}}$ 激活函数 例如更新$w_{53}$ 主要思想就是我们无法找到$E$和$w_{53}$的直接关系，所以使用链式求导法则来间接求梯度： $$ w_{53}(new) = w_{53}(old) - \Delta w_{53} $$ $$ \begin{cases} E = \frac{1}{2}(y_5-y_a)^2\\ y_5 = f(z_5)\\ z_5 = w_{53} * y_3 + w_{54} * y_4 \end{cases} $$ $$ \begin{align} \Delta w_{53} &= \frac{\partial E}{\partial w_{53}} \\ &= \frac{\partial E}{\partial y_{5}} \frac{\partial y_5}{\partial z_5} \frac{\partial z_5}{\partial w_{53}} \end{align} $$...

第一章 组合数学基础 排列 相异元素不允许重复的排列 $P(n, r)$ 球盒模型：将$r$ 个有区别的球放入 $n$ 个不同的盒子里，每盒不超过一个。 计算公式：$$ P(n, r)=\frac{n!}{(n-r)!} $$ 集合描述：$$ S=\{1 \cdot e_1, 1 \cdot e_2,…,1 \cdot e_n\} $$ 相异元素允许重复的排列 $RP(\infty, r)$ 球盒模型：将$r$ 个有区别的球放入 $n$ 个不同的盒子里，每个盒子的球数不加限制而且同盒的球不分次序。 计算公式：$$ RP(\infty, r) = n^r $$ 集合描述：$$ S=\{\infty \cdot e_1, \infty \cdot e_2,…,\infty \cdot e_n\} $$ 不尽相异元素的全排列 球盒模型：将$r$个有区别的球放入$t$个不同的盒子，每个盒子的容量是有限的，其中第$i$个盒子最多只能放入$n_i$个球，同盒的球不分次序。 集合描述：$$ S=\{ n_1 \cdot e_1, n_2 \cdot e_2,…,n_t \cdot e_t \}, n_1+n_2+…+n_t=n $$ 特例 $r=1$ $$ RP(n, 1) = t $$ $r=n$ $$ RP(n, n) = \frac{n!...