Hi there 👋

Thinking will not overcome fear but action will.

数据库索引实现

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索引。...

October 10, 2023 · 1 min · fffzlfk

使用Docker部署openwrt软路由

前期准备 拉取 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....

June 15, 2023 · 1 min · fffzlfk

Are You Sure You Want to Use MMAP in Your Database Management System?[部分翻译]

原文 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. ↩︎...

December 15, 2022 · 1 min · fffzlfk

反向传播

反向传播 反向传播(英语: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} $$...

October 18, 2022 · 4 min · fffzlfk

组合数学笔记

第一章 组合数学基础 排列 相异元素不允许重复的排列 $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!...

October 8, 2022 · 2 min · fffzlfk