本论文来自上海交大，论文主要关于内存中动态图存储（In-Memory Dynamic Graph Storage, DGS）设计的研究论文，论文核心是通过系统评估现有 DGS 方法，揭示其性能瓶颈并指明未来优化方向。动态图存储需支持并发读写，以满足实时图分析和更新需求。现有方法（如 LLAMA、Aspen、LiveGraph、Teseo、Sortledton 等）在读写支持、空间开销和并发控制上差异显著，但缺乏对这些维度权衡的系统研究。作者主要分析了现有系统的设计，以及讨论了如何针对 DGS 算法进行系统评估。

本文阅读该论文的重点一是仔细学习作者类比、分析、抽象系统的做法，二是借作者之手，对现在的 DGS 系统的发展做一个简单的了解。
论文链接 Revisiting the Design of In-Memory Dynamic Graph Storages

文章来自清华大学交叉信息学院，论文聚焦于 LSM 树的Compact策略优化，提出了一种名为 EcoTune 的动态规划算法，旨在通过重新思考Compact操作的定位，最大化系统的平均查询吞吐量。LSM 树的核心挑战在于通过将内存中的数据批量Flush到磁盘形成 “sorted string tables”，并定期Compact重叠的待合并SSTable以减少读放大（RA）。

传统Compact策略主要关注写放大（WA）与读放大的权衡，但忽略了现代存储设备的特性。现代 NVMe SSD 具备极高的写入带宽，写入性能不再是瓶颈。Compact与查询会竞争 CPU 和 I/O 资源，因此Compact策略的核心应是优化平均查询吞吐量，而非单纯降低瞬时读放大。

论文链接 Rethinking The Compaction Policies in LSM-trees

本文讨论了RocksDB的Prefetch和Async机制，在回顾LevelDB的SSTable读流程基础上，深入分析RocksDB的BlockBasedTableReader读流程、Prefetch相关函数及异步读取机制，还介绍了相关类设计和简单测试结果。包括：

1. LevelDB的SSTable读流程：分为Open和Get两个步骤，Open包括文件句柄管理、Footer读取等；Get使用二分查找索引定位数据块，缓存优先读取，启用布隆过滤器且所有块未缓存读取时，与文件系统交互6次。
2. RocksDB的Open流程：调用FilePrefetchBuffer预取文件尾部获取Footer，加载元索引块等，缓存关键元数据，减少磁盘I/O操作。
3. PrefetchTail函数：确定预读取大小和范围，尝试文件系统预取，通过限制浪费比例确保I/O效率提升。
4. Get流程：用户发起请求，经过时间戳和过滤块匹配检查，创建索引迭代器遍历索引块和数据块，最终返回结果。
5. 异步读取：非阻塞操作，提高并发性，与预取结合进一步提高系统并发处理能力。
6. 相关类设计：FilePrefetchBuffer负责预取缓冲区管理；BlockFetcher独立Block的异步化读取操作，结合多种缓存和Prefetch机制。
7. 简单测试：生成测试命令，对比启用和禁用异步扫描的测试结果，RocksDB的Prefetch和Async机制优化了读取性能。

在ParquetReader的构造函数中，会打开文件句柄，加载元数据，并初始化。Scan函数负责实际的扫描过程，处理行组，应用过滤器，读取数据到DataChunk中。首先，在元数据加载部分，parquet文件的元数据通常位于文件末尾，包含schema、行组信息、统计信息等。LoadMetadata函数通过读取文件末尾的元数据部分，解析出FileMetaData结构。

DeriveLogicalType函数根据Parquet的SchemaElement中的类型信息（如Type、converted_type、logicalType）转换为DuckDB的LogicalType。例如，Parquet的INT32可能对应DuckDB的INTEGER，而带有converted_type为DATE的INT32会被转换为DATE类型。这里还处理了时间戳、UUID等复杂类型的转换。

创建列读取器的过程在CreateReaderRecursive中完成，这个函数递归地遍历SchemaElement树，根据每个元素的类型和子元素创建相应的ColumnReader。例如，遇到STRUCT类型时，会创建StructColumnReader，并为每个子列创建对应的读取器，对于重复的字段（如LIST或MAP），会使用ListColumnReader来处理嵌套结构。

初始化时，InitializeSchema调用CreateReader创建根读取器，通常是StructColumnReader，因为它对应Parquet文件的根结构。然后根据读取到的列信息填充columns向量，记录每个列的名称和类型。

扫描数据的过程由Scan函数处理。ParquetReaderScanState用于跟踪扫描的状态，包括当前处理的行组、文件句柄、过滤器等。PrepareRowGroupBuffer函数准备当前行组的数据，可能应用统计信息进行过滤，跳过不需要读取的行组。然后通过ColumnReader的Read方法将数据读取到DataChunk中，应用过滤器（如果有的话），最终将结果返回。

过滤器处理部分，ApplyFilter函数根据过滤条件对读取的数据进行过滤。例如，等值比较、范围比较、IS NULL等条件会被应用到数据上，减少需要处理的数据量，提升查询性能。

先看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v16:16:16-v32:32:32-v64:64:64-v128:128:128-n16:32:64"
target triple = "nvptx64-nvidia-cuda"

declare i32 @llvm.nvvm.read.ptx.sreg.tid.x() nounwind readnone

define void @kernel(ptr addrspace(1) %A,
                    ptr addrspace(1) %B,
                    ptr addrspace(1) %C) {
entry:
  %id = call i32 @llvm.nvvm.read.ptx.sreg.tid.x()
  %ptrA = getelementptr inbounds float, ptr addrspace(1) %A, i32 %id
  %ptrB = getelementptr inbounds float, ptr addrspace(1) %B, i32 %id
  %ptrC = getelementptr inbounds float, ptr addrspace(1) %C, i32 %id

  %valA = load float, ptr addrspace(1) %ptrA, align 4
  %valB = load float, ptr addrspace(1) %ptrB, align 4
  %valC = fadd float %valA, %valB

  store float %valC, ptr addrspace(1) %ptrC, align 4
  ret void
}

!nvvm.annotations = !{!0}
!0 = !{ptr @kernel, !"kernel", i32 1}

DWARF全称为“Debugging With Attributed Record Formats”，其设计初衷是为了配合ELF格式进行UNIX可执行文件的调试信息生成。DWARF调试信息主要面向开发者用以指导如何生成调试信息以及如何使用调试信息。比如编译器、链接器开发者需要参考DWARF来生成调试信息，而调试器开发者需要参考DWARF来使用调试信息。DWARF开始时主要是为 UNIX 下的调试器提供必要的调试信息，例如内存地址对应的文件名以及代码行号等信息。GCC和Clang以及Go和Rust都使用该格式生成调试信息，与该格式相对的，Windows平台使用PDB（Program Database）作为调试信息的主要格式。
2017年，DWARF v5发布，提供了更好的数据压缩能力，调试信息与可执行程序的分离，对macro宏和源代码文件的更好的描述以及更快速的符号搜索、还有对编译器优化后代码的更好描述等等。

在本节中，基于上一节的页模型，提出并发执行正确性的概念，并建立多个事务在时间上交叉执行的模型，提出有关并发事务调度的概念。首先要明确的是，事务的执行是高度动态的，完全建模会带来巨大的理解成本，实际上，当事务到来，并发控制需要对该事务做出执行决定，并使能其和系统中正在运行的事务正确同步。其次，需要考虑执行失败而被终止的事务，在正常执行的路径中，包含提交终止。这些操作的处理方式和直觉很不一样。

并发执行的事务之间的数据访问操作存在潜在的冲突，比如“修改后丢失”、“读不一致”、“脏读”等问题，作为事务执行顺序的保证来说，这些异常都是要避免的，给外部执行一致的印象。

为了判断事务执行时，何种情况是期望的，何种情况是应该避免的，调度器需要在线的应用这些规则。首先，本文假定调度中包含了事务结束标志成功或者不成功，具体的，一个事务成功的结束使用$c$表示，即事务在没有被中断的情况下完成了内部所有的数据操作，而失败事务的结束使用$a$表示，一个被终止的事务不应该对底层数据产生任何影响，这由恢复过程保证。

事务服务的计算模型可以通过多种方法精确创建，和抽象程度有关，而建模数据库事务服务的系统需要遵循一些基本的方法论以及相关实际因素，本系列所作的建模一般分为以下5个步骤：

1. 首先定义数据对象的基础操作，这些操作被认为是原子的，并且独立于其他操作，这一步并没有明确定义什么是数据对象以及需要考虑什么类型数据的基础操作。因此本系列定义两种不同的计算模型：页模型和对象模型；
2. 对事务以及事务执行顺序建模，将其视为在数据对象上基础操作的一个（全/偏）序列；
3. 本系列使用调度或者历史的概念作为对事务执行并发的抽象；
4. 在所有句法正确的调度中，必须从中识别出保证ACID“正确”的调度；
5. 需要“算法”或者“协议”来即时地创建事务正确的调度，当事务提交之后，可以被动态执行；

上述的“页模型”是一个非常简单的模型，可以观察在存储层中，数据页是如何被事务优雅的读写的。接下来可以看到这个模型以一种非常优雅的方式建模了并发控制和事务恢复的实现，并且可以描述非常多（但不是全部）系统实现中的重要语义。
“对象模型”是预留给数据库的上层操作，比如访问层或者查询处理层的操作，很容易想到把上层数据应用的业务数据对象考虑在内，可以推导出更复杂的对抽象数据结构ADT的语义，借由ADT来执行下层数据对象的操作。

2019年，CWI发表了一篇关于DuckDB的论文：《DuckDB: an Embeddable Analytical Database》，旨在OLAP领域构建一个嵌入式的数据库，解决单点交互式数据分析的问题，并给边缘计算提供除SQLite之外的更优选择。在论文中，作者们总结DuckDB为在一个进程内的SQL OLAP DBMS，这句话至少有两个解读点：

1. DuckDB的工作方式应该和SQLite一致，即在进程内部运行，并不需要类似MySQL或者PG的等单独起一个数据库服务；
2. 作为AP系统，可以支撑一定复杂的数据分析和查询任务。

SQLite是在全球运行最多的关系型数据库管理系统，每个浏览器和操作系统以及各种嵌入式设备都能找到该数据库使用的痕迹。但是SQLite更多为TP任务服务，很难利用向量化、内存加速来提高数据分析的速度。所以DuckDB弥补了SQLite这方面的空白。

多线程/进程之间使用缓存一致性协议来保证每个包含独立缓存对象的核心在共享使用内存数据时的一致性，缓存一致性协议保证了缓存实体中的任何更新都会对相同位置的其他缓存进行全部更新。MESI协议是最著名的一致性协议，支持现代CPU中缓存回写。通过监控内存事务保持一致性，一致性问题可以得到缓解，但是是有代价的，导致CPU访存空转，浪费系统带宽，两种具有代表性的内存一致性问题是“真共享”和“伪共享”。