LZY的Code生活

Database RecoveryARIES Log Sequence Numbers MasterRecord 被硬编码到 DBMS，所以我们恢复时这个页面会先被拉到内存中 仅仅当 pageLSN <= flushLSN，才能将 log 刷入磁盘所有的记录都有一个 LSN每次一个事务修改一个页上的 record，pageLSN 会改变每次 DBMS 将 WAL buffer 中的东西写入磁盘，flushedLSN 会更新 Normal Execution Transaction Commit 我们只需要保证在刷新 flushLSN 之前先将日志记录刷新到磁盘即可TXN-END 写入后说明 commit 已经成功，所以 wal 可以清除没有用的 Log Transaction Abort prevLSN 维护一个链表允许我们追踪 abort 事务的记录链表 我们在 abort 和 end 之间可能存在其他日志，我们需要维护这些日志；我们不会在 abort 时立即将这些记录刷写到磁盘 Compensation Log records 是对 up ...

Introduction to distributed database

8-Index Concurrency8.0 Concurrency control 8.1 Latch8.1.0 LOCKS VS. LATCHES 8.1.1 Latch Modes 8.1.2 Latch implementationsTest-and-Set Spin Latch (TAS) 有效，不能支持大规模并发；对缓存不友好；对 OS 不友好 std::atomic CPU 空转，因为 NUMA 之间的通信，会增加硬件通信流量成本 std::atomic_flag latch;while(latch.test_and_set(...){ // Retry? Yield? Abort?}) Blocking OS Mutex：阻塞式实现；不能大规模并发；std::mutex OS 支持，竞争线程进入内核态类似 sleep 涉及到 OS 的系统调用，可能会拖慢整个系统的速度 Reader-Writer Latches 允许并发读 依据 spin latches 实现 8.2 Hash table latching 对一 ...

7-B+Tree Indexes7.1 B-Tree Family 7.1 Tree IndexesDBMS 在执行查询的时候，更多是查询索引而不是查询数据库中的表索引问题 存储开销 维护索引开销 7.2 B+ Tree是一个自平衡树。这是一种插入、删除均为 O(log n)的数据结构。可以支持线性遍历（哈希表不能做到） 相比 Hash Table，最好的性能是 O(1)，最差时退化到 O(n)。因为平衡，所以任意一个叶子结点到根结点的时间复杂度均为 O(log n) 对于读写磁盘上整页数据具有其他数据结构不具备的优势 7.2.1 B+ Tree Properties$M$阶搜索树 $ \frac{M}{2} - 1 \le keys \le M - 1$ 每个中间结点，$k$个关键字有$k+1$个非空孩子 叶子结点存放关键字和数据 Nodekey 继承自索引依赖的属性 value inner node 中 value 是下一个节点的指针；leaf node 中是存放数据的地址或者数据本身 所有的 NULL 值要么存放在 first leaf node，要么是 las ...

9-Sort && Aggregation Algorithm9.0 Query Plan 操作符可以处理比内存更多的数据 尽可能高效地利用 buffer pool 访问磁盘用尽可能多的顺序 IO 9.1 Sort9.1.1 Why do we need to sort 通常情况下，基于哈希的方式比基于排序的方式更优；但是对于预先排序的数据基于排序的方式可能更优 9.1.2 IN-MEMORY SORTING 9.1.3 TOP-N HEAP SORT 如果出现相等的值，就扩展堆数组的大小 9.1.4 EXTERNAL MERGE SORTsorted run 行存储一般采取早期物化，列存储选择延迟物化，先存储 record ID 2-way external merge sort 使用这种方式，可以通过删除排序前的源文件来清理磁盘空间 general external merge sort 9.1.5 Double Buffering general external merge 在同一时刻，CPU 和磁盘总有一个会空闲，所以 Double ...

ResNet贡献 提出了残差模块，解决了深度网络梯度消失/爆炸的问题 残差函数 $$F(x) = H(x) -x$$ 残差模块的输入和输出 这里的加法是逐元素相加，在两个特征图上逐个通道上进行 $$ y = F(x, {W_{i}}) + W_{s}x;\quad W_{s}仅仅用于匹配维度 $$ ResNet中的两种模块 ResNet34左侧的模块构成；ResNet50由右侧模块构成 ResNet101和ResNet152使用更多的三层模块组成 测试 34层的plain网络比18层网络的训练误差要高，但是他们发现可能不会是梯度传播带来的问题，这个问题有待于未来研究 这些普通网络使用 BN 进行训练，确保前向传播的信号具有非零方差。我们还验证了反向传播梯度与 BN 表现出健康的规范。因此，前向或后向信号都不会消失。

new 与 malloc 的区别 malloc始终返回标准类型最大的对齐内存 __STDCPP_DEFAULT_NEW_ALIGNMENT__; new分配按照alignas大小分配；如果用malloc是未定义行为 struct alignas(64) A { long double ld; double d;};A *q = (A*)new (std::align_val_t(alignof(A)))char[sizeof(A)] 在结构体中使用union，该属性不被初始化 new(&mResult) T(std::move(ret));// 等价于std::construct_at(&mResult, std::move(ret));mResult.~T();// 等价于std::destroy_at(&mResult); 属性 new/delete 是 C++关键字，需要编译器的支持 malloc/free 是库函数，需要引用对应的库 使用区别 无需显示填入申请内存的大小，会根据申请的类 ...

多进程编程处理僵尸进程 子进程结束运行，内核不会立即释放进程的进程表项；在父进程查询前，子进程运行结束这段时间叫做僵尸态(Z态)

在系统上运行程序链接 gcc编译链接程序：cpp预处理器预处理源文件，cc1编译器编译.i文件为.S文件，as汇编器将.S文件变为可重定位目标文件.o，最后运行ld链接器，创建一个可执行程序 执行./a.out，shell调用加载器函数，将可执行文件的.text和.data复制到内存并跳转到该程序开头 解析多重定义的全局符号 规则 不允许多个同名的强符号 如果有一个强符号和多个弱符号同名，选择弱符号 如果有多个弱符号同名，选择其中任意一个 链接器不会表示检测到符号的多重定义 未初始化的全局变量交给COMMON段，将可能存在多重定义的变量交给链接器进行裁决 未初始化的静态变量，初始化为0的静态或全局变量在.bss段；全局变量初始化为0是一个强符号 与静态链接库链接 链接器将只复制被程序引用的目标模块 动态链接共享库 链接器复制了.so文件的重定位和符号表信息 在可执行文件加载后，存在.interp节，加载动态链接器(ld-linux.so)；动态链接器本身不能依赖任何动态库，所有它是静态链接的

程序的结构和执行程序的机器级表示 使用基于条件的数据传送替代基于条件的控制转移 // 基于条件的数据传送int ntest = x >= y;if (ntest) { ...} else { ...}// 基于条件的控制转移if (x >y) { } else { } while的两种汇编形式 jump to the middle go to test;loop: bodytest: t = test-expr; if (t){ goto loop; } guarded-do t = test-expr;if(!t){ goto done;}loop: body t = test-expr; if(t) { goto loop; }done: 对抗缓冲区溢出攻击 地址空间布局随机化：栈随机化，每次先在栈上随机分配一大块空间；程序每次加载地址不同 栈破坏检测：在 ...