CMU15445 lab 4 2020fall

这个lab主要是用SS2PL(不需要index lock，因为不需要实现可序列化)实现三种隔离级别下lock的acquire与release,

• SS2PL可以实现REPETABLEREADS，因为SS2PL只有在一个txn commit的时候才会去释放锁，这样别人就不能修改当前txn所读的数据，也就是说读??也会直到一个txn的commit的时候才去释放
• READ COMMITED由于读??立即释放，那么其他txn就可以立即获取写??，就有可能第二次读，数据不一致了

总览

• 该lab需要实现一个lock manager，依靠它实现query的并发执行
• 根据隔离级别的要求，lock manager分配tuple级别的lock给transactiion，lock包括排他??与共享??
• Lock与Latch的区别
  • Lock：当有transaction需要修改一个tuple，lock manager将rid塞到队列中，那么其他transaction就不能去获取这个tuple
  • Latch：在B+树index，光是单纯的使用lock并不能保证并发的正确性，如果没有latch，中间internal node会被修改，那么会出错

TASK #1 - LOCK MANAGER

• 为了保证事务间的交错执行，DBMS使用lock manager(LM)去控制事务访问数据。LM的实现是，维持一个数据结构，用于记录活跃的事务所持有的lock。每个事务在访问数据之前会向LM请求??。LM要么授予??,要么阻塞该事务，要么终止该事务。LM是全局的，TableHeap或者Executor想要访问/修改tuple时，它们会去向LM请求??。
• 这个lab要求实现一个tuple级别的LM，并且能够支持三种隔离级别:READ_UNCOMMITED, READ_COMMITTED, and REPEATABLE_READ
• 需要实现4个函数，LockUpgrade(Transaction, RID)是尝试将一个tuple的共享??升级为排他??
• 这四个函数需要兼容三种隔离级别的lock操作
• 需要根据隔离级别正确的处理lock的操作，

实现

• 对于lock_manager中的mutex变量，是用来保证加读写??时的互斥，如果不适用这个变量可能会导致两个线程对于一个tuple同时加??的情况，

• 对于错误的lock操作应该把txn的状态设置为ABORTED，并抛出异常

• unordered_map的pair到底怎么初始化的，不能insert？std::condition_variable的拷贝构造被删除了

• 对于读??的授予，granted_的作用是什么？一个request_queue中，一个txn希望获取??，但是granted_为false，那么在deadlock detection中就能够构造wait for graph

• 不能存在两个txn一同upgrade??

• 对于READ COMMITED的读??立即释放，是否说明读??的释放不表明txn进入了SHRINKING阶段了呢,因为存在先读一个tuple在写一个tuple的情况，那么如果按照ppt中的要求，对于READ COMMITED立即释放读??，那么就进入了SHRIKING阶段了，所以对于READ COMMITED不能把读??的释放算入SHRINKING阶段？

• SHRINKING阶段不能够释放??？

TASK #2 - DEADLOCK DETECTION

• lock manager 需要实时的检测deadlock，并通过牺牲最年轻的txn解决deadlock，通过dfs判断死锁
• 需要动态的多线程的构建txn间的wait-for图
• 对于DFS，总是从txn id最小的开始遍历，那么最先淘汰的即使txn id大的那个，也就是youngest的那个，
  通过将youngest的txn的state设置为ABORTED
• 用于检测的thread被唤醒时，需要破除所有的环
• 
  std::this_thread::sleep_for是用来阻塞进程，不过这段话是啥意思？
• 也就是说，graph中的节点可能有多个出边

实现

• 用一个std::unordered_map require_record_;来记录一个txn在等待哪一个RID的??
• 抛出异常是在什么地方？也就是说不是在运行cycleDetection的当前线程抛出异常，不然会无法完成所有的cycle的检测，而是通过唤醒等待??的txn的线程，在其对应线程中抛出异常
  transactionManager到底什么时候去处理这个ABORTED的事务鸭？在execution_engine.h中去处理aborted的事务

TASK #3 - CONCURRENT QUERY EXECUTION

不需要去对index加??，只需要去对tuple上??，那么就不用实现Serializable

• 对于READ COMMITED的隔离级别，读??可以立即释放
• 为了实现事务回滚，需要记录事务的write sets在执行delete等操作时，需要在一个txn的相关数据结构中记录

实现

• 对于aggregation_executor.cpp，不需要添加任何??操作，因为其hash表是每个aggregation_executor独有的，只需要去考虑其子executor的??操作即可
• 对于nested_loop_executor.cpp也是同样的道理，不需要添加??操作，只需要为其子executor添加??操作即可
• 对于一个delete的tuple记录，用于回滚的时候就可以设置为原来的表了index也需要为了事务回滚而记录
• 对于读??的操作，是区分隔离级别的关键，比如READ UNCOMMITED的隔离级别，可以不加读??对于READ_COMMITTED的隔离级别，需要立即解??
• 对于读??的获取，需要考虑的是重复的获取tuple
• update_executor.cpp中从子executor(可能是seq_scan_executor)获取tuple，那么需要对拿到的tuple上写??，但是这里不会卡住吗，如果是在REPEATABLE_READS隔离级别下,子executor不释放读??，那么当前的updateExecutor无法加写??，也就是说对于火山模型，在REPEATABLE_READS隔离级别下，会卡住吗？不会卡住，因为这种情况下会做lockupgrade
• 注意，在delete_executor.cpp,insert_executor.cpp,update_executor.cpp这几个文件中不需要记录write set因为对应得tuple修改函数已经存在添加 write set得操作了，如果重复添加，回滚时会出错
• 对于insert_executor,RawValues的方式不需要加锁，而从别的拷贝的方式，由于需要防止被拷贝的tuple此时的值不变，所以需要对被拷贝的tuple加写??