CMU课程15-721最新一期开课啦！

课程安排

Project #2 - Concurrent Index

实现一个支持无锁并发的BW树作为索引底层数据结构

• PID到指针的映射表
• 改动链
• split/merge
• 动态垃圾回收

论文中几个奇怪概念：

• install CAS 即使用CAS操作来替换映射表中的项目
• epoch机制 即使用版本号保证没有其他操作正在进行（可以执行物理删除）

实现要求：

• 支持重复key且可以配置，如果配置为不允许则InsertEntry插入重复key的索引条目时返回false，且DeleteEntry只删除完全匹配的索引条目
• 支持consolidation，需要考虑阈值
• 支持split与merge，特别是并发插入与删除的情况
• 应该有工具函数帮助测试结构完整性并可以修复，类似fsck
• 支持动态垃圾回收，调用Cleanup函数进行物理释放，会使用GetMemoryFootprint统计内存情况
• 支持reverse iterators并保证concurrent mutators正常工作

Profile方法

profile工具使用valgrind或perf

1. valgrind

使用memcheck或callgrind动态检查：valgrind --tool=callgrind --trace-children=yes ./build/src/peloton -D data &> /dev/null&

1. perf

通过收集linux的cpu周期计数实现，也支持收集其他事件
perf record -e cycles:u -c 2000

CMU课程15-721最新一期开课啦！

课程安排

Project #1 - Hash Join Operator

做这个项目前必须了解几个join算法，问题是这些算法在本次课程里都没有讲解过。

1.嵌套循环连接(Nested Loops)

适用范围两个表, 一个叫外部表, 一个叫内部表。如果外部输入非常小，而内部输入非常大并且已预先建立索引，那么嵌套循环联接将特别有效率。循环嵌套连接查找内部循环表的次数等于外部循环的行数，当外部循环没有更多的行时，循环嵌套结束。

2.合并联接(Merge)

指两个表在on的过滤条件上都有索引, 都是有序的, 这样join时, sql server就会使用性能更好的Merge join算法。如果一个有索引,一个没索引,则会选择Nested Loops join算法。首先从两个输入集合中各取第一行，如果匹配，则返回匹配行。假如两行不匹配，则有较小值的输入集合+1。

3.哈希联接(Hash)

如果两个表在on的过滤条件上都没有索引, 则就会使用Hash join算法。也就是说, 使用Hash join算法是由于缺少现成的索引。

哈希匹配分为两个阶段,分别为生成和探测阶段：首先是生成阶段，将输入源中的每一个条目经过散列函数的计算都放到不同的Hash Bucket中；接下来是探测阶段，对于另一个输入集合，同样针对每一行进行散列函数，确定其所应在的Hash Bucket,在针对这行和对应Hash Bucket中的每一行进行匹配，如果匹配则返回对应的行。

同时做这个项目需要了解Peloton tile-based架构几个关键数据结构：

logical_tile设计 [backend/executor/logical_tile]

其中

• position_lists_为vector<vector<oid_t>> 用来描述tiles/colums, 例(1,2,3),(1,1,1)
• schema_为vector<LogicalTile::ColumnInfo> 用来描述logical tile的表字段组合, 会存在position_list_idx与position list对应, 例(Tile A-1 ATTR1, Tile A-1 ATTR2), (Tile A-1 ATTR3, Tile A-2 ATTR1)
• visible_rows_为vector<bool>用来描述position lists中每一行的可见性

ColumnInfo设计 [backend/executor/logical_tile]

在logical tile中用来描述一组表字段信息, 例如(Tile A-1 ATTR1, Tile A-1 ATTR2), 其中

• position_list_idx 指回Position Lists中对应编号
• base_tile为shared_ptr<storage::Tile>指向存储Tile，直接使用指针而不是oid
• origin_column_id 存储Tile中选择的表字段编号

ContainerTuple设计 [backend/expression/container_tuple]

用于包装logical tile中元组, 传入LogicalTile指针与元组行id(logical_tile, row_idx)

HashMapType 设计 [backend/executor/hash_executor]

用于定义hash表结构unordered_map<expression::ContainerTuple<LogicalTile>, unordered_set<pair<size_t, oid_t>, boost::hash<pair<size_t, oid_t>>>, expression::ContainerTupleHasher<LogicalTile>, expression::ContainerTupleComparator<LogicalTile>>
其中pair 表示

使用类型为vector<unique_ptr<executor::LogicalTile>>的left_result_tiles_与right_result_tiles_缓存
最终hash操作返回结果为vector<LogicalTile *> result使用BuildOutputLogicalTile方法(主要调用BuildSchema方法得到表字段组合)返回得到unique_ptr<LogicalTile>

CMU课程15-721最新一期开课啦！

课程安排

并发控制课程（一共三节）已经结束，但具体细节需要结合索引技术（仍然是三节）进行讲解

Indexes I — Locking & Latching

本节就是对应用在传统B树索引上的各种锁和latch技术进行讲解

技术总结信息来自这篇文章：A Survey of B-Tree Locking Techniques

在讲解锁相关技术前，需要把B树家族的各个数据结构先总结说明一下。

B树(键值都在) -> B+树(值都在叶子节点) 其中B+树设计选择有：

• Non-Unique索引 实现方法有1.允许键重复 2.值list
• 变长键 实现方法有1.指针 2.节点长度可变 3.key map（即slot pages）

其他变形：

• T-tree, 基于AVL树（不存key直接存指针），用于内存DB
• Skip List, MemSQL完全使用以替代B+结构，实现上为一组多层list，最低层为排序单链key，每层key减半，插入时几率插入每一层；优势是省空间，无需额外平衡操作，易并发；缺点是反向查找复杂
• Radix Tree 基树
• MassTree
• Fractal Tree

对索引加锁需要注意索引结构可能变化

• lock: 事务粒度上保护索引逻辑，txn duration，可以回滚，(ex,sh,up,i)
• latch: 线程粒度上保护索引内部实现，op duration，不需要回滚，(r,w)

因此lock-free index可以为no lock(MVCC)或no latch(cow,shadow page)

索引锁类型

• predicate lock 在where条件上加锁，不好实现
• key-value lock 在B树key上加锁
• gap lock 在B树key后面gap上加锁
• key-range lock 在B树key及后面gap上加锁
• hierachical lock 一组key-range lock纵向上组合(IX, EX)

Indexes II — OLTP

本节先关注latch实现方法:

• Compare&Swap CAS操作，使用__sync_bool_compare_and_swap(&M, 20, 30) 是其他实现的基础
• Os Mutex 使用pthread_mutex_t (,about 25ns invocation)
• Test&Set spinlock 使用std::atomic_flag(non-scalable, cpu缓存不友好)
• Queue spinlock 使用std::atomic_flag(比mutex性能好，cpu缓存友好) lock chain
• rw locks 可以使用spin lock实现

其中non-scalable指锁阻塞后性能不能线性增长
详细解释

个人补充：工程实践中共享对象的读写一致性方案(读写锁，COW与引用计数)，引用计数并发可以使用HazardPointer解决
个人补充：spinlock vs mutex

重点讲解几个典型mem DB中OLTP索引设计：

1. BW树(Hekaton)

• latch free B+树
• deltas 没有直接修改(使用额外record或info，物理page上挂链表)，建少cpu缓存失效，使用epoch方便垃圾回收
• mapping table 树所有都使用pid，需要维护pid到page物理位置的指针表，CAS使用在该指针上

该技术来自微软Hekaton的这篇文章：The Bw-Tree: A B-tree for New Hardware

1. Concurrent skip list(MemSQL), latch free
   仅使用CAS操作实现insert与update无锁化

该技术来自这篇文章：Concurrent Maintenance of Skip Lists

1. Adaptive基树(Hyper)

Indexes III — OLAP

OLAP的不同在于可以drill down、roll up、slice、pivot等维度变化操作，本节主要讲解OLAP中列索引设计

个人补充：很多需要数据库行转列操作

Star Schema vs Snowflake Schema (分层级关系表) 使用B+树结构因为数据重复会导致大量的空间浪费，OLAP更适合采用列数据库模式(方便压缩)

SQL Server的列索引设计(如何在行存储上实现列索引)：最初设计表必须是只读的, 实现结构为segment directory即blob storage with dictionary/delta encode & compress 针对不同数据类型采用不同编码方法；新版支持insert/update/delete, 采用delta store支持插入更新,bitmap实现删除

bitmap索引技术：每个attr使用一个bitmap表示每个tuple的值(估算10million tuple, 43000个zip codes则需要额外53.75GB，原因是zip作为attr数量太大)，需要考虑压缩方法

Storage Models & Data Layout

主要mem DB的数据存储模型，注意C++使用reinterpret_cast在编译期强制转换类型，需要注意缓存对齐中的按字对齐(e.g. 64-bit word)

Null处理：定义特殊值, Bitmap表示, Null Flag

存储模型分为：

• N-ary Storage Model(NSM) 适合OLTP，insert-heavy，物理上使用堆组织或索引组织元组(比如使用聚族索引)
• Decomposition Storage Model(DSM) 行存储又叫纵向扩展，适合OLAP,元组物理上使用固定长度或嵌入元组id
• Hybrid Model 可以切换或同时适配

可以观察到刚插入的数据一般都比较活跃，时间推移后期一般变成只读数据，OLTP通过ETL过程进入OLAP数据仓库

CMU课程15-721最新一期开课啦！

真是要强烈推荐这门课程：有在线视频，有教案，有作业，甚至还有自动评分工具，除了没老师与TA之外真的分享了几乎所有的课程资源，完全可以让我们这种墙内的后进生们自学。

课程安排

Course Introduction and History of Database Systems

以回顾数据库历史的方式串讲了数据库系统设计中的难点，也就是以后的课程内容目录：

1. 并发控制
2. 索引
3. 存储模型，压缩
4. join算法
5. 日志与恢复
6. 查询优化
7. 新存储器件

未来所有作业与项目都是用C++11写的（牛逼！），准备好调试多线程
推荐每次上课前写一篇本次课阅读paper的心得，包括：主题思想（两句话）、系统使用与修改情况（一句话）、负载测试情况（一句话）

In-Memory Databases

因为新型存储器件的飞速发展导致内存数据库（其实还有内存文件系统）需求越来越强烈，原始基于硬盘为主存储结构的数据库设计因此会有哪些变化呢？

总结下传统硬盘数据库设计特点为：

1. 使用内存做缓存池（涉及内存与磁盘上以“页”为单位的数据同步）
2. 页为单位的索引数据组织（页号、slot号、header、tuple、blob等概念设计）
3. 所有请求都会先经过缓存池（worker线程需要pin住该页防止被swap到磁盘）
4. 并发控制保证事务可以等待磁盘数据读取时间，同时锁（lock）要保存到其他数据结构（非页结构）中防止被swap
5. 使用WAL处理日志与恢复问题
6. CPU时间统计：30%缓存池、30%锁、28%日志、12%真正操作

设计内存数据库，首先不要考虑使用mmap，缺点：内存操作无法非阻塞了、内存结构与磁盘必须相同、数据库系统不知道哪些页实际在内存中（说白了就是操作系统通用设计不可能比数据库架构师专业设计更好！）

内存数据库IO问题退居二线（DRAM 60ns， SSD 25000~30000ns），需要考虑其他性能问题：

1. lock/latch
2. cache-line miss
3. pointer chasing
4. predicate evaluations
5. data move
6. network

总结下设计特点为：

1. 不需要缓存池和页结构（直接用指针取代id索引？定长或变长数据？但是一定得使用checksum保证数据正确）
2. 获得锁时间跟获得数据时间一样！导致可能允许牺牲一点并发度（coarse-grained locking因为数据IO足够快）并且可以将锁信息与数据信息一起保存（增加CPU cache locality，mutex相对太慢，一定改用CAS）
3. 索引设计问题凸显（需要多考虑一下CPU cache）
4. 查询处理方式巨大改变（不需要顺序扫描，传统一次处理一个tuple方式相对太慢），考虑vector-at-a-time
5. 仍然需要WAL，可能可以简化；仍然需要checkpoint操作

内容基本出自92年的文章: High-Performance Concurrency Control Mechanisms for Main-Memory Databases

发布第一次项目作业，等本人做完了另找时间写文章说明。

Concurrency Control I

介绍各种事务模型：nested trx、saga trx（其实在《事务处理》一书里面都已经见识过）

介绍各种并发控制方式：
Two-Phase Locking 和死锁避免方法

• DL_DETECT
• NO_WAIT
• WAIT_DIE

Timestamp Ordering及优化方法

• Basic T/O
• MVCC
• OCC
• H-STORE

测试结果出自14年的文章: Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

个人补充：MC涉及多线程访问内存值，CC解决多CPU副本一致性

Memory Consistency和Cache Coherence

Concurrency Control II — Multi-versioning

详细介绍隔离级别：比可串行化级别低一些的级别，包括REPEATABLE_READS, READ_COMMITTED

• Dirty Read 脏读（提前读到后面修改的内容）
• Unrepeatable Read 不可重复读（事务里两次读操作，后一次读的不同）
• Phantom Read 幻读（读到其他事务插入或删除的数据）

产品方面voltDB完美支持可串行化，oracle11g最高支持SNAPSHOT_ISOLATION级别，新增两种级别：

• CURSOR_STABILITY 内部cursor持有锁，有时防止Lost Update（写操作覆盖顺序不对）

• SNAPSHOT_ISOLATION 保证事务所见snapshot相同（不能强化到可串行化级别 2009新paper有可串行化snapshot方案），防止Write Skew（部分写更新）

下面介绍多版本MVCC现代实现方法(timestamp-ordered好处在于不需要lock！)

mvcc设计考虑：

• version chains（oldest-to-newest[w]，newest-to-oldest[r]）
• version storage（全量或delta存[回滚段]）
• garbage collection（额外线程或合作，GC在重写负载造成15%额外负载]）

Hekaton(SQL Server)

事务开始结束都赋予时间戳, 为每个tuple维护版本链(BEGING, END, POINTER)，维护全局事务状态图(ACTIVE, VALIDATING[precommited,2PL不需要这个状态，因为锁即可保证]),事务维护元数据(Read set,Write set,Scan set[避免幻读],Commit dependency)，乐观事务在多核表现下明显好于悲观事务

实现方面仅使用lock-free数据结构(没有latch或spin lock，使用bw-tree和skiplist，CAS)

该系统设计11年论文：High-Performance Concurrency Control Mechanisms for Main-Memory Databases

Concurrency Control III — Optimistic

首先讨论存储过程，产生于解决使用交互API问题（可以减少网络通信次数与等待）

• ODBC/JDBC
• DBMS wire protocols

存储过程的问题：不好版本控制与调试，不好移植

Optimistic方法 其中validation步骤：（可以并发进行）

• backword 与已经提交的事务判断
• forword 与还未提交事务判断

本课未学完待补充

All cultures seem to believe the idea that history is a kind of chart that guides its members in to the future. Hitory gets transmitted from generation to generation.

These stories of the past offer the members of a culture part of their identity while highlighting the culture’s origins, what is deemed important, and the most significant starting point of Western civilization, which is the culture that most powerfully shapes not only the west but most of world today. It seems to me to be evident that whatever it’s over characteristics, the West has created institutions of government and law that provide unprecedented freedom for its people. It has also invented a body of natural scientific knowledge and technological achievement that together made possible a level of health and material prosperity undreamed of in earlier times and unknown ouside the West and those places that have been influenced.

Society cannot achieve the full benefits of Western science and technology without commitment to reason and objectivity as essentail of knowledge. The primary of reason and the pursuit of objectivity therefore, both characteristic of the Western experience seem to me to be essential for the achievement of the desired goals almost anywhere in the world. Chance and accident often played a vital part in the material condition of life cannot take root and flourish without reason, although it was employed for all sorts of practical and intellectual purposes in some of these cultures, it still lacked independence from religion and it lacked the high status to challenge the most basic received ideas.

It rest on religious authority, tradition, and power with a painful understanding of the limitations of the greatness and possibilities before man that together, composes the tragic vision of the human condition that characterized classical Greek civilization.

incried at Apollo’s temple at Delphi, “know Thyself” “Nothing in Excess” known your own limitations as a fallible mortal(not divine) to train in virtue of the animals when prefected, so he is the worst when seperated from law and justice. For injustice is most dangerous when it is armed. A religion that worshipped a single all powerful deity, who is sharply seperated from human beings.