LZY的Code生活

xv6链接脚本OUTPUT_ARCH( "riscv" )ENTRY( _entry )SECTIONS{ /* * ensure that entry.S / _entry is at 0x80000000, * where qemu's -kernel jumps. */ . = 0x80000000; .text : { *(.text .text.*) . = ALIGN(0x1000); _trampoline = .; *(trampsec) . = ALIGN(0x1000); // trampoline不超过一页 ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page"); PROVIDE(etext = .); // 可以在c中进行引用，text段的结尾 } .rodata : { . = ALIGN(16); ...

Buffer PoolTask 1 Extendible Hash Table基本概念 全局深度（global depth），局部深度（local depth）以及桶（bucket）。 桶就是存记录（records）的地方，我可以往桶里放一条，两条，三条。但要规定好最多能装几条。这个例子里我们规定最多能装2条。在图里你能看到bucket 1只有两行。下图这个就是可拓展哈希的初始状态。 插入数据。 插入Comp.Sci和Finance这两条。现在还不涉及全局深度和局部深度的改变。两条新记录（record）就直接往里放就行。 插入Music。这时一个桶的条数大于它的上限（2条），所以要开始分裂。如何分裂是根据哈希值（hash value）决定的。取哈希值第一位。哈希值是二进制数，第一位只有两种可能，0和1。Comp.Sci是1，Finance是1，Music是0。很简单的把是1的放在一个桶（bucket）里，是0的放在另一个桶（bucket）里。由于我们用了哈希值的第一位，所以全局深度（global depth）变成1。这里做一下全局深度和局部深度的区分。两个都表示用了几位哈希值 ...

10-Join Algorithm10.1 join algorithms 尽可能选择较小的表作为外围表 10.2 Join opetatorsOutputdata Cost Analysis CriteriaNested Loop JoinNested Loop Join 已知表非常小的情况下，可以使用 nested loop join，可以适配 L3 缓存 Index Nested Loop Join Block Nested loop join Nested Loop Join SummaryKey Takeaways 选择更小的表作为 Outer table尽可能在 bufferpool 中缓存 outer table使用索引快速访问 inner table Algorithms NaiveBlockIndex Sort-Merge Join Sort Merge 此时 R 中 id 为 200；S 的 id 比 200 大，需要回溯，但是由于表是有序的，不必像 nested loop join 回溯到开头只需要回溯到上一个不大于 R.id ...

11. Query ExecutionProcessing ModelsIterator Model迭代器模型，也叫做火山或者流水线模型 大量函数调用，指令缓存会很快失效 Materialization Model生成所有数据然后返回给上层 对于 OLTP 表现不错，因为没有很大的表需要传递 Vectorized/Batch MOdel 在物化模型和火山模型间是一个良好的平衡可以使用 SIMD 指令加速 Plan Processing Direction 自上而下对于上面的模型来说更加自然 Access MethodsSequential Scan Optimization Prefetching Buffer Pool Bypass Parallelization Heap Clustering 只是取回 RID，最后才取回真正的数据 Late Materialization Data Skipping Data Sipping ZONE MAPS one zone map in one zone，zone 的大小取决于我们的实现，一般为页当 zo ...

Concurrency Control TheoryTransaction in sql ACID Mechanisms for ensuring atomicityLogging LSM tree 是针对单个表文件配置的；而 logging 是针对全局跨文件设置的 Shadow Paging 即使改变几字节，也会复制整个页 Consistency 很多系统采用最终一致性，但在过程中可能出现不一致的情况 Mechanisms for ensuring isolation Formal Properties of schedules Unreaptable Read 读写冲突的情况下，同一事务在两次读取同一个值时读到两个不同的值 Dirty Read 写读冲突下，另一个事务读取了其他事务并未提交的值并提交 Lost Update 写写冲突导致事务更新值消失 Dependency Graph & Confict Serializable 大多数 DBMS 实现冲突可串行化如果图中出现环路，说明这个调度是 bad schedule Transaction ...

Two Phase Lock Concurrency ControlExecuting with locks 事务需要锁(upgrade)锁管理器为请求申请锁事务释放锁锁管理器更新内部的 lock tablelock table 跟踪每个事务持有什么锁，并正在等待什么锁 Locks vs. Latcheslocks 保护数据库磁盘上的对象；lock manager 是内存数据结构，该结构使用 latch 进行保护 Basic Lock Types S-LOCK: shared locks for reads X-LOCK: Exclusive lock for writes Two-Phase locking(2PL) 是一种并发控制协议该协议不需要知道事务将要执行的所有查询**两阶段锁协议可能会发生死锁**，但可以通过适当的策略（如死锁检测和预防）来处理和避免。 Growing 每个事务向 DBMS 的锁管理器请求它所需要的锁锁管理器同意或拒绝锁请求 Shrinking 事务在该阶段仅仅释放或者对锁降级不可以再次申请锁 Executing with 2P ...

Query Planning and Optimization catalog 是一个记录元数据信息的文件 The Physical Plan Query Optimization(QO) Heuristics/Rules 重写查询来去除那些无效的条件 这些技巧需要访问 catalog，但是它们不需要访问数据 Predicate Pushdown Replace Cartesian Product Projection Pushdown Equivalence Architecture Overview Cost-based Search 使用一个模型来预测执行一个计划的成本 遍历多种计划，选择一个成本最小的计划来执行 Bottom-up Optimization 使用动态规划，自底向上构建查询计划成本最低的计划 single-relation query palnning system R optimization 将逻辑计划构建为左深树 Top-Down Optimization 自顶向下的优化控制权更多，我们可以从一个计划开始逐步细化过程 N ...

Timestamp Ordering Concurrency Control 2PL 和时间戳排序算法是悲观并发控制算法还有乐观并发控制算法 T/O Concurrency Control 使用时间戳来确保事务执行的顺序如果 TS($T_I$) < TS($T_j$)，DBMS 需要确保执行的调度必须和$T_i$发生在$T_j$前的串行化调度相同 Timestamp allocation System/Wall Clock Logical Counter Hybrid Basic T/O 事务读取和写入对象不需要锁 W-TS(X)：是最后成功写入的事务的时间戳 R-TS(X)：是最后成功读取的事务的时间戳 如果事务尝试获取时间戳在自己之后的对象，会 abort 然后 restart 为每个事务保存数据副本开销很大；长时间运行的事务很可能会被饿死，新事务可能会使得长时间运行的事务 abort 并 restart Reads 会为 X 创建一个本地副本来确保$T_i$可重复读 Writes Optimistic Conc ...

Mutli-Version Concurrency DBMS 有多个物理版本和一个逻辑版本 一个事务写入时会创建一个新版本；读取时会读取该事务开始时最新的版本 MVCC 实际上是维护多个版本的机制；而版本之间的并发正确性仍然需要并发控制协议来维护 writers do not block readers and readers do not block writers 只读事务可以不获取锁读取一个一致性的快照 MVCC example Write Skew Anomaly 快照隔离并不能确保可串行性；可能出现这种写偏斜问题 Version Storage Append-Only Storage 可以看作是一个多版本的单链表 Oldest to Newest(O2N) Newest to Oldest(N2O) Time-Travel Storage 为本来没有做 MVCC 的系统提供的一种 MVCC 机制 Delta Storage 增量存储：只存储更改后的列 Garbage Collection Tuple-level GC 后台清理：只扫描被修改的 ...

Database LoggingCrash Recovery Actions during normal txn processing to ensure that the DBMS can recover from a failure Actions after a failure to recovver the database to a state that ensures atomicity, consistency, and durability Failure ClassificationTransaction Failures Logical Errors: 事务因为一些内部原因没有完成（完整性约束失效） Internal State Errors: DBMS 必须终止一个活跃的事务因为一个错误的条件（死锁） System Failures Software Failure: OS 或者 DBMS 实现的错误 Hardware Failure: the computer hosting the DBMS crahsed(电源线被拉了)Fail-stop Assumpt ...