精华内容
下载资源
问答
  • 严格两阶段封锁协议
    2022-04-24 12:31:32

    所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁。
    .在对任何数据进行读、写操作之前,首先要申请并获得对该数据的封锁
    .在释放一个封锁之后,事务不再申请和获得任何其他封锁。所谓"两段"锁的含义是,事务分为两个阶段,第一阶段是获得封锁,也称为扩展阶段。在这阶段,事务可以申请获得任何数据项上的任何类型的锁但是不能释放任何锁。第二阶段是释放封锁,也称为收缩阶段。在这阶段,事务可以释放任何数据项上的任何类型的锁,但是不能再申请任何锁。
    例如事务T,遵守两段锁协议,其封锁序列是:
    SlockA SlockB XlockC UnlockB UnlockA UnlockC;
    |←- 扩展阶段–→| |←-- 收缩阶段 --→|
    又如事务T2不遵守两段锁协议,其封锁序列是:
    Slock A Unlock A Slock B Xlock C Unlock C Unlock B;
    可以证明,若并发执行的所有事务均遵守两段锁协议,则对这些事务的任何并发调度策略都是可串行化的。
    需要说明的是,事务遵守两段锁协议是可串行化调度的充分条件,而不是必要条件。也就是说,若并发事务都遵守两段锁协议,则对这些事务的任何并发调度策略都是可串行化的;若对并发事务的一个调度是可串行化的,不一定所有事务都符合两段锁协议。
    两阶段封锁协议实现了事务集的串行化调度,但同时,一个事务的失败可能会引起一连串事务的回滚。为避免这种情况的发生,我们需要进一步加强对两阶段封锁协议的控制,这就是:严格两阶段封锁协议和强两阶段封锁协议。

    严格两阶段封锁协议除了要求封锁是两阶段之外,还要求事务持有的所有排它锁必须在事务提交之后方可释放。这个要求保证未提交事务所写的任何数据,在该事务提交之前均以排它锁封锁,防止其他事务读取这些数据。

    强两阶段封锁协议,要求事务提交之前不得释放任何锁。使用锁机制的数据库系统,要么使用严格两阶段封锁协议,要么使用强两阶段封锁协议。

    注意:两段锁协议和防止死锁的一次封锁法的异同之处。一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁,否则就不能继续执行,因此一次封锁法遵守两段锁协议;但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁,因此遵守两段锁协议的事务可能发生死锁。

    更多相关内容
  • 本小节介绍的两阶段封锁协议(2PL)是其中一种解决方式,它是一种悲观的解决策略,相应的,还有一类乐观的解决策略。 2. Lock Types 在索引并发控制那一小节提到过,Lock和Latch的区别。Latch指物理层面对数据...

    1. Overview

    前面一小节(并发控制理论)介绍了如何并发执行多个事务,设置检测机制判断执行调度满足可串行化。那些方法假设DBMS已知所有负载,然而,在真实系统中,系统往往并不知道用户在未来可能发送的所有请求,在这种情况下如何保证最终产生可串行化调度是一个新的问题。本小节介绍的两阶段封锁协议(2PL)是其中一种解决方式,它是一种悲观的解决策略,相应的,还有一类乐观的解决策略。

    2. Lock Types

    在索引并发控制那一小节提到过,Lock和Latch的区别。Latch指物理层面对数据结构的锁,Lock指对逻辑层面的事务、数据库对象的锁。

    锁的类型分为读锁和写锁,读锁之间不互斥,写锁与任意的锁都互斥。

    为了在事务并发过程中避免读写冲突,可以使用锁对对象进行管理,Lock Manager中记录当前锁的分配情况。

    下图是一个使用锁实现数据对象原子访问的例子,但仅仅这样这还不够,下面的例子不满足可串行化,出现了不可重复读的问题。

    两阶段封锁(2PL)是一种能够无需提前知道未来所有事务内容的情况下保证调度冲突可串行化的一种并发协议。

    两阶段封锁顾名思义分为两个阶段,分别是Growing阶段和Shrink阶段。在Growing阶段,事务从Lock Manager处获得执行事务所需要的所有数据对象的锁;随后进入Shrink阶段,只能释放Growing阶段获得的锁,不能够重新获取新的锁。

    Shrink阶段,只能释放Growing阶段获得的锁,不能够重新获取新的锁(避免了提到的脏读问题)。

    下面是一个运用2PL执行事务T1和事务T2的例子。

    到目前为止介绍的2PL还不够完美,还会发生级联中止的问题(cascading abort)。

    例如下图所示,若T1最终ABORT掉,由于T2已经读了T1写后的值,出现脏读问题,导致T2也要中止。若级联中止导致了DBMS事务冲突率较高,成功提交的事务变少影响性能,可以通过Strong Strict 2PL彻底避免。

    Strong Strict 2PL指只有等到事务最终执行完,决定COMMIT前再释放所有锁(这里一直有个疑问,就是会不会COMMIT失败?)。

    可以看出,Strong Strict 2PL可以彻底避免级联中止的问题,但这是一个trade-off的过程,使用Strong Strict 2PL的同时也降低了执行的并行度。

    下图是一个使用Strong Strict 2PL计算A+B的例子,T2直到T1决定COMMIT了才能够获得A的写锁。

    几种调度的关系如图所示。

    到目前为止介绍的2PL还可能发生死锁的问题,如下图所示,T1和T2因为互相争用锁而发生死锁。

    在发生事务死锁情况下,Wait For 图表现出是一个环。处理死锁的方式可以通过死锁检测或者提前预防死锁的发生。

    对于死锁的检测,Wait For 图可以判断调度中是否有死锁,与上一小节介绍的冲突依赖图不同的是,对于依赖图中冲突的两个事务,先执行的事务指向后发生的事务;Wait For 图中的有向边Ti->Tj表示事务Ti等待事务Tj释放锁。

    下图所示是一个死锁的例子。

    一旦检测到有死锁产生,DBMS会回滚部分事务打破死锁状态,从而能够让系统继续运行,被回滚的事务重新执行。

    允许根据不同规则来选择回滚的事务,目的还是想要回滚带来的损失最小,同时也要避免starvation(饥饿)问题。

    同时,被回滚的事务可以考虑只回滚事务中导致死锁的操作,剩余的操作不回滚,减少回滚带来的损失。

    也可以通过设置预防机制彻底避免死锁的发生,如下图所示的两种策略。第一种策略统一按照时间戳顺序发放锁,第二种相反,通过规定统一的锁分配策略来避免死锁的发生。

    下图分别两种机制对锁争用的处理。

    若一个查询涉及1000万行记录,lock manager同时管理1000万个锁将会造成较低的处理性能。

    通过层级化锁可以达到对大规模tuple上锁的目的。

    具体而言,这种锁叫Intention Lock。

    IS、IX、SIX互斥情况。

    下图是T1、T2、T3通过层次化锁实现并发执行的例子。

    这种层级化锁机制优化了需要获取大规模锁的查询性能,同时也考虑了查询的并发性。

    展开全文
  • 数据库基础知识详解:乐观/悲观锁、封锁级别、三级封锁协议以及锁协议

    写在文章前:本系列文章用于博主自己归纳复习一些基础知识,同时也分享给可能需要的人,因为水平有限,肯定存在诸多不足以及技术性错误,请大佬们及时指正。

    4.乐观锁和悲观锁

    乐观锁和悲观锁在数据库和多线程并发中常被提及,但它们并不是某两个特定的锁,而是两个锁的宏观理念。

    • 悲观锁:认为数据随时会被修改,因此每次读取数据之前都会上锁,防止其它事务读取或修改数据。应用于数据更新比较频繁的场景。

    • 乐观锁:操作数据时不会上锁,但是更新时会判断在此期间有没有别的事务更新这个数据,若被更新过,则失败重试。适用于读多写少的场景。

    乐观锁的实现方式有:
    (1)加一个版本号或者时间戳字段,每次数据更新时同时更新这个字段。
    (2)先读取想要更新的字段或者所有字段,更新的时候比较一下,只有字段没有变化才进行更新。

    5.常见的封锁级别

    意向锁是 InnoDB (MySQL加的数据引擎)自动加的, 不需要用户干预。 对于UPDATE、DELETE和INSERT 语句, InnoDB 会自动给涉及数据集加排他锁(X)。对于普通SELECT 语句,InnoDB 不会加任何锁。事务可以通过以下语句显式给记录集加共享锁或排他锁: 共享锁(S):SELECT * FROM table_name WHERE … LOCK IN SHARE MODE。 其他 session 仍然可以查询记录,并也可以对该记录加 share mode 的共享锁。但是如果当前事务需要对该记录进行更新操作,则很有可能造成死锁。 排他锁(X):SELECT * FROM table_name WHERE … FOR UPDATE。其他 session 可以查询该记录,但是不能对该记录加共享锁或排他锁,而是等待获得锁。

    排它锁(Exclusive Lock)/ X锁:事务对数据加上X锁时,只允许此事务读取和修改此数据,并且其它事务不能对该数据加任何锁。

    共享锁(Shared Lock)/ S锁:加了S锁后,该事务只能对数据进行读取而不能修改,并且其它事务只能加S锁,不能加X锁。

    意向锁(Intention Locks):一个事务在获得某个数据行对象的 S 锁之前,必须先获得整个表的 IS 锁或更强的锁。一个事务在获得某个数据行对象的 X 锁之前,必须先获得整个表的 IX 锁。IS/IX 锁之间都是兼容的。

    好处:如果一个事务想要对整个表加X锁,就需要先检测是否有其它事务对该表或者该表中的某一行加了锁,这种检测非常耗时。有了意向锁之后,只需要检测整个表是否存在IX/IS/X/S锁就行了锁的作用:用于管理对共享资源的并发访问,保证数据库的完整性和一致性。

    封锁粒度

    MySQL 中提供了两种封锁粒度:行级锁以及表级锁

    简单来说即锁住整张表或者锁住一行的数据。

    封锁粒度小封锁粒度大
    优点锁定的数据量较少,发生锁竞争的可能较小,系统的并发性更好。系统开销较小。(加锁、释放锁、检查锁的状态都需要消耗资源)。
    缺点系统开销较大大。锁定的数据量较多,发生锁竞争的可能较大,系统的并发性较差。

    6.三级封锁协议

    • 一级封锁协议:事务在修改数据之前必须先对其加X锁,直到事务结束才释放。

      可以解决丢失修改问题(两个事务不能同时对一个数据加X锁,避免了修改被覆盖)

    • 二级封锁协议:在一级的基础上,事务在读取数据之前必须先加S锁,读完后释放。

      可以解决脏读问题(如果已经有事务在修改数据,就意味着已经加了X锁,此时想要读取数据的事务并不能加S锁,也就无法进行读取,避免了读取脏数据)

    • 三级封锁协议:在二级的基础上,事务在读取数据之前必须先加S锁,直到事务结束才能释放。

      可以解决不可重复读问题(避免了在事务结束前其它事务对数据加X锁进行修改,保证了事务期间数据不会被其它事务更新)。

    7.两段锁协议

    什么是两段锁协议?

    定义:事务必须严格分为两个阶段对数据进行加锁和解锁的操作,第一阶段加锁,第二阶段解锁。

    也就是说一个事务中一旦释放了锁,就不能再申请新锁了。

    可串行化调度是指,通过并发控制,使得并发执行的事务结果与某个串行执行的事务结果相同。

    事务遵循两段锁协议是保证可串行化调度的充分条件(注意不是充要条件,而是充分条件。即事务遵循两段锁协议一定能保证可串行化调度,但保证可串行化调度不一定需要遵循两段锁协议)。

    展开全文
  • 严格二段锁协议实现

    千次阅读 2020-03-26 13:27:17
    DBMS包含一个管理器,用于决定事务是否可以锁定。 它了解系统内部的最新情况。 共享(S-LOCK):允许多个事务同时读取同一对象的。 如果一个事务持有共享,则另一个事务可以获取该共享。 独占锁定(X-...

    原理

    DBMS包含一个锁管理器,用于决定事务是否可以锁定。 它了解系统内部的最新情况。

    • 共享锁(S-LOCK):允许多个事务同时读取同一对象的锁。 如果一个事务持有共享锁,则另一个事务可以获取该共享锁。
    • 独占锁定(X-LOCK):允许事务修改对象。 此锁与任何其他锁不兼容。 一次只能有一个事务持有独占锁。

    使用锁执行:
    1.事务从锁管理器请求锁(或升级)。
    2.锁管理器根据其他事务当前持有的锁来授予或阻止请求。
    3.当不再需要时,事务释放锁。
    4.锁管理器更新其内部锁表,然后把锁给其他等待的事务。

    二阶段锁定

    两阶段锁定(2PL)是一种悲观的并发控制协议,用于确定是否允许事务访问数据库中的对象。协议不需要知道事务将提前执行的所有查询。

    img

    img

    阶段#1:膨胀
    •每个事务都从DBMS的锁管理器请求它所需的锁。
    •锁管理器授予/拒绝锁定请求。
    阶段#2:收缩
    •事务在释放第一个锁后立即进入此阶段。
    •允许事务仅释放先前获取的锁。它无法在此阶段获得新锁。
    就其本身而言,2PL足以保证conflict serializability。它生成precedence graph是无环的。
    2个缺点:
    但它很容易出现级联中止,即当事务中止并且现在必须回滚另一个事务时,这会导致浪费很多资源。

    img

    还有一些可序列化的潜在计划,但2PL不允许这种计划(锁会限制并发)。

    严格的2pl(不会级联回滚,不存在shrinking的情况)

    在执行事务的过程中,所有的数据库操作有可能会要求加锁,但是不能立刻释放锁。必须要等到整个事务提交或回滚后,才能释放锁。

    S2PL确实没有像普通2PL那样shrinking的阶段,如果事务写入的值在该事务完成之前未被其他事务读取或覆盖,则调度是严格的。
    这种方法的优点是DBMS不会导致级联中止。
    同时只要把原来的值赋值回去就可以实现abort了。

    为什么呢?我们看一下S2pl的时序图

    img

    死锁问题

    下面要解决的就是2pl 的死锁问题

    死锁问题的解决思路分为2种,一种是死锁预防,一种是死锁检测。

    死锁检测

    DBMS 创建 wait-for图:如果事务Ti等待事务Tj释放锁,从Ti到Tj有一条边。系统将定期检查等待图中的环,然后决定如何打破它。
    •当DBMS检测到死锁时,它将选择“受害者”事务进行回滚以中断循环。
    •受害者事务将重新启动或中止,具体取决于应用程序如何调用它
    •选择受害者时需要考虑多个事务属性。没有一个选择比其他选择更好。 2PL DBMS都做不同的事情:
    1.按年龄(最新或最旧的时间戳)。
    2.按进度(执行的最少/大多数查询)。
    3.已锁定的项目数量。
    4.通过我们必须用它回滚的#个事务。
    5.过去重启事务的次数
    •回滚长度:选择要中止的受害者事务后,DBMS还可以决定回滚事务的更改的距离。可以是整个事务,也可以是足够的操作(部分事务)足以来打破僵局

    img

    死锁预防(本实现采用,condition variable!!!)

    当txn尝试获取另一个txn持有的锁时,DBMS会杀死其中一个以防止死锁。
    该方法不需要wait-for图或检测算法。

    根据时间戳分配优先级(例如,旧的意味着更高的优先级)。
    这些方案保证没有死锁,因为在等待锁时只允许一个方向。 当事务重新启动时,其(新)优先级是其旧时间戳。
    •Wait-Die(“Old等待Young”):如果T1具有更高的优先级,则T1等待T2。 否则T1中止
    •wound-wait(“Young等待old”):如果T1具有更高的优先级,则T2中止。 否则T1会等待。

    代码

    事务

    /**
     * Transaction states:
     *
     *     _________________________
     *    |                         v
     * GROWING -> SHRINKING -> COMMITTED   ABORTED
     *    |__________|________________________^
     *
     **/
    enum class TransactionState { GROWING, SHRINKING, COMMITTED, ABORTED };
    
    enum class WType { INSERT = 0, DELETE, UPDATE };
    
    class TableHeap;
    
    // write set record
    class WriteRecord {
    public:
      WriteRecord(RID rid, WType wtype, const Tuple &tuple, TableHeap *table)
          : rid_(rid), wtype_(wtype), tuple_(tuple), table_(table) {}
    
      RID rid_;
      WType wtype_;
      // tuple is only for update operation
      Tuple tuple_;
      // which table
      TableHeap *table_;
    };
    
    class Transaction {
    public:
      Transaction(Transaction const &) = delete;
      Transaction(txn_id_t txn_id)
          : state_(TransactionState::GROWING),
            thread_id_(std::this_thread::get_id()),
            txn_id_(txn_id), prev_lsn_(INVALID_LSN), shared_lock_set_{new std::unordered_set<RID>},
            exclusive_lock_set_{new std::unordered_set<RID>} {
        // initialize sets
        write_set_.reset(new std::deque<WriteRecord>);
        page_set_.reset(new std::deque<Page *>);
        deleted_page_set_.reset(new std::unordered_set<page_id_t>);
      }
    
      ~Transaction() {}
    
      //===--------------------------------------------------------------------===//
      // Mutators and Accessors
      //===--------------------------------------------------------------------===//
      inline std::thread::id GetThreadId() const { return thread_id_; }
    
      inline txn_id_t GetTransactionId() const { return txn_id_; }
    
      inline std::shared_ptr<std::deque<WriteRecord>> GetWriteSet() {
        return write_set_;
      }
    
      inline std::shared_ptr<std::deque<Page *>> GetPageSet() { return page_set_; }
    
      inline void AddIntoPageSet(Page *page) { page_set_->push_back(page); }
    
      inline std::shared_ptr<std::unordered_set<page_id_t>> GetDeletedPageSet() {
        return deleted_page_set_;
      }
    
      inline void AddIntoDeletedPageSet(page_id_t page_id) {
        bool exists = false;
        for (Page *i : *GetPageSet()) {
          exists |= (i->GetPageId() == page_id);
        }
        if (!exists)
          std::bad_alloc();
        deleted_page_set_->insert(page_id);
      }
    
      inline std::shared_ptr<std::unordered_set<RID>> GetSharedLockSet() {
        return shared_lock_set_;
      }
    
      inline std::shared_ptr<std::unordered_set<RID>> GetExclusiveLockSet() {
        return exclusive_lock_set_;
      }
    
      inline TransactionState GetState() { return state_; }
    
      inline void SetState(TransactionState state) { state_ = state; }
    
      inline lsn_t GetPrevLSN() { return prev_lsn_; }
    
      inline void SetPrevLSN(lsn_t prev_lsn) { prev_lsn_ = prev_lsn; }
    
    private:
      TransactionState state_;
      // thread id, single-threaded transactions
      std::thread::id thread_id_;
      // transaction id
      txn_id_t txn_id_;
      // Below are used by transaction, undo set
      std::shared_ptr<std::deque<WriteRecord>> write_set_;
      // prev lsn
      lsn_t prev_lsn_;
    
      // Below are used by concurrent index
      // this deque contains page pointer that was latche during index operation
      std::shared_ptr<std::deque<Page *>> page_set_;
      // this set contains page_id that was deleted during index operation
      std::shared_ptr<std::unordered_set<page_id_t>> deleted_page_set_;
    
      // Below are used by lock manager
      // this set contains rid of shared-locked tuples by this transaction
      std::shared_ptr<std::unordered_set<RID>> shared_lock_set_;
      // this set contains rid of exclusive-locked tuples by this transaction
      std::shared_ptr<std::unordered_set<RID>> exclusive_lock_set_;
    };
    

    控制器图例

    img

    数据结构设计

    这幅图的就是一个HASH TABLE的链表实现法。每一个VALUE里还要存所有的在访问这个KEY的TRANSACTION。
    针对每个TRANSACTION 我们需要记录是否是GRANT的 , TX ID , 还有上锁的模式。
    所以上述的图是3层结构。一个HASH表KEY是 RID, VALUE是LIST
    第二层结构里是个TX LIST 存了 属于这个RID的每一个TX ITEM
    第三层 则是TX ITEM。

    img

    随后我们按照需求去构造那个LIST,最开始的设计MAP的VALUE 就是一个LIST
    但是再做UPGRADING的时候,发现要判断之前有没有正在等待锁升级的TRANSACTION,如果有,需要ABORT。所以加了一个变量来观察。就做了一层封装,同时为了增加并发度,做了一个针对TX LIST的粒度锁。这样可以避免锁整个LOCK TABLE。

    img

    最后是最外层结构的定义

    img

    算法的核心 就是实现LOCK TEMPLATE 和 UNLOCK。
    在LOCK TEMPLATE 中,大致分为4个模块
    第一个模块是找到对应的TX LIST并且获得锁
    第二个模块是针对LOCK UPGRADING,因为需要抹掉原来的读锁,才能升级为写锁。
    第三个模块是判断是否可以GRANT。
    第四个模块就是往TX LIST里插入,同时阻塞或者拿锁成功就往TXN 里面放入对应的RID记录。

    img

    在UNLOCK 里,首先要区分是否是S 2PL,是的话就要求只能在COMMIT 和ABORT的时候才可以释放锁。
    随后定位到要删除的元素的TXLIST,从里面抹除,从TRANSACTIONS 的LOCK集合里抹除对应的RID。
    然后判断是否TXLIST EMPTY,抹除对应的KEY。

    最后判断是否可以GRANT 锁给其他的TX。

    img

    二段锁控制器

    class LockManager {
    
      struct TxItem {
        TxItem(txn_id_t tid, LockMode mode, bool granted) :
                tid_(tid), mode_(mode), granted_(granted) {}
    
        void Wait() {
          unique_lock<mutex> ul(mutex_);
          cv_.wait(ul, [this] { return this->granted_; });
        }
    
        void Grant() {
          lock_guard<mutex> lg(mutex_);
          granted_ = true;
          cv_.notify_one();
        }
    
        mutex mutex_;
        condition_variable cv_;
        txn_id_t tid_;
        LockMode mode_;
        bool granted_;
      };
    
      struct TxList {
        mutex mutex_;
        list<TxItem> locks_;
        bool hasUpgrading_;
        bool checkCanGrant(LockMode mode) { //protect by mutex outside
          if (locks_.empty()) return true;
          const auto last = &locks_.back();
          if (mode == LockMode::SHARED) {
            return last->granted_ && last->mode_ == LockMode::SHARED;
          }
          return false;
        }
        void insert(Transaction* txn, const RID &rid, LockMode mode, bool granted, unique_lock<mutex> *lock) {
          bool upgradingMode = (mode == LockMode::UPGRADING);
          if (upgradingMode && granted) mode = LockMode::EXCLUSIVE;
          locks_.emplace_back(txn->GetTransactionId(),mode,granted);
          auto &last = locks_.back();
          if (!granted) {
            hasUpgrading_ |= upgradingMode;
            lock->unlock();
            last.Wait();
          }
          if (mode == LockMode::SHARED) {
            txn->GetSharedLockSet()->insert(rid);
          } else {
            txn->GetExclusiveLockSet()->insert(rid);
          }
        }
      };
    public:
      LockManager(bool strict_2PL) : strict_2PL_(strict_2PL){};
    
      /*** below are APIs need to implement ***/
      // lock:
      // return false if transaction is aborted
      // it should be blocked on waiting and should return true when granted
      // note the behavior of trying to lock locked rids by same txn is undefined
      // it is transaction's job to keep track of its current locks
      bool LockShared(Transaction *txn, const RID &rid);
      bool LockExclusive(Transaction *txn, const RID &rid);
      bool LockUpgrade(Transaction *txn, const RID &rid);
    
      // unlock:
      // release the lock hold by the txn
      bool Unlock(Transaction *txn, const RID &rid);
      /*** END OF APIs ***/
    private:
      bool lockTemplate(Transaction *txn, const RID &rid, LockMode mode);
    
      bool strict_2PL_;
      mutex mutex_;
      unordered_map<RID,TxList> lockTable_;
    
    };
    
    bool LockManager::LockShared(Transaction *txn, const RID &rid) {
      return lockTemplate(txn,rid,LockMode::SHARED);
    }
    
    bool LockManager::LockExclusive(Transaction *txn, const RID &rid) {
      return lockTemplate(txn,rid,LockMode::EXCLUSIVE);
    }
    
    bool LockManager::LockUpgrade(Transaction *txn, const RID &rid) {
      return lockTemplate(txn,rid,LockMode::UPGRADING);
    }
    
    bool LockManager::lockTemplate(Transaction *txn, const RID &rid, LockMode mode) {
      // step 1
      if (txn->GetState() != TransactionState::GROWING) {
        txn->SetState(TransactionState::ABORTED);
        return false;
      }
      unique_lock<mutex> tableLatch(mutex_);
      TxList &txList = lockTable_[rid];
      unique_lock<mutex> txListLatch(txList.mutex_);
      tableLatch.unlock();
    
      if (mode == LockMode::UPGRADING) {//step 2
        if (txList.hasUpgrading_) {
          txn->SetState(TransactionState::ABORTED);
          return false;
        }
        auto it = find_if(txList.locks_.begin(), txList.locks_.end(),
                          [txn](const TxItem &item) {return item.tid_ == txn->GetTransactionId();});
        if (it == txList.locks_.end() || it->mode_ != LockMode::SHARED || !it->granted_) {
          txn->SetState(TransactionState::ABORTED);
          return false;
        }
        txList.locks_.erase(it);
        assert(txn->GetSharedLockSet()->erase(rid) == 1);
      }
      //step 3
      bool canGrant = txList.checkCanGrant(mode);
      if (!canGrant && txList.locks_.back().tid_ < txn->GetTransactionId()) {
          txn->SetState(TransactionState::ABORTED);
          return false;
      }
      txList.insert(txn,rid,mode,canGrant,&txListLatch);
      return true;
    }
    
    
    bool LockManager::Unlock(Transaction *txn, const RID &rid) {
      if (strict_2PL_) {//step1
        if (txn->GetState() != TransactionState::COMMITTED && txn->GetState() != TransactionState::ABORTED) {
          txn->SetState(TransactionState::ABORTED);
          return false;
        }
      } else if (txn->GetState() == TransactionState::GROWING) {
        txn->SetState(TransactionState::SHRINKING);
      }
      unique_lock<mutex> tableLatch(mutex_);
      TxList &txList = lockTable_[rid];
      unique_lock<mutex> txListLatch(txList.mutex_);
      //step 2 remove txList and txn->lockset
      auto it = find_if(txList.locks_.begin(), txList.locks_.end(),
                        [txn](const TxItem &item) {return item.tid_ == txn->GetTransactionId();});
      assert(it != txList.locks_.end());
      auto lockSet = it->mode_ == LockMode::SHARED ? txn->GetSharedLockSet() : txn->GetExclusiveLockSet();
      assert(lockSet->erase(rid) == 1);
      txList.locks_.erase(it);
      if (txList.locks_.empty()) {
        lockTable_.erase(rid);
        return true;
      }
      tableLatch.unlock();
      //step 3 check can grant other
      for (auto &tx : txList.locks_) {
        if (tx.granted_)
          break;
        tx.Grant(); //grant blocking one
        if (tx.mode_ == LockMode::SHARED) {continue;}
        if (tx.mode_ == LockMode::UPGRADING) {
          txList.hasUpgrading_ = false;
          tx.mode_ = LockMode::EXCLUSIVE;
        }
        break;
      }
      return true;
    }
    

    事务控制器

    class TransactionManager {
    public:
      TransactionManager(LockManager *lock_manager,
                               LogManager *log_manager = nullptr)
          : next_txn_id_(0), lock_manager_(lock_manager),
            log_manager_(log_manager) {}
      Transaction *Begin();
      void Commit(Transaction *txn);
      void Abort(Transaction *txn);
    
    private:
      std::atomic<txn_id_t> next_txn_id_;
      LockManager *lock_manager_;
      LogManager *log_manager_;
    };
    
    Transaction *TransactionManager::Begin() {
      Transaction *txn = new Transaction(next_txn_id_++);
    
      if (ENABLE_LOGGING) {
        assert(txn->GetPrevLSN() == INVALID_LSN);
        LogRecord log{txn->GetTransactionId(), txn->GetPrevLSN(), LogRecordType::BEGIN};
        txn->SetPrevLSN(log_manager_->AppendLogRecord(log));
      }
    
      return txn;
    }
    
    void TransactionManager::Commit(Transaction *txn) {
      txn->SetState(TransactionState::COMMITTED);
      // truly delete before commit
      auto write_set = txn->GetWriteSet();
      while (!write_set->empty()) {
        auto &item = write_set->back();
        auto table = item.table_;
        if (item.wtype_ == WType::DELETE) {
          // this also release the lock when holding the page latch
          table->ApplyDelete(item.rid_, txn);
        }
        write_set->pop_back();
      }
      write_set->clear();
    
      if (ENABLE_LOGGING) {//, you need to make sure your log records are permanently stored on disk file before release the
        // locks. But instead of forcing flush, you need to wait for LOG_TIMEOUT or other operations to implicitly trigger
        // the flush operations. write log and update transaction's prev_lsn here
        LogRecord log{txn->GetTransactionId(), txn->GetPrevLSN(), LogRecordType::COMMIT};
        txn->SetPrevLSN(log_manager_->AppendLogRecord(log));
        log_manager_->Flush(false);
      }
    
      // release all the lock
      std::unordered_set<RID> lock_set;
      for (auto item : *txn->GetSharedLockSet())
        lock_set.emplace(item);
      for (auto item : *txn->GetExclusiveLockSet())
        lock_set.emplace(item);
      // release all the lock
      for (auto locked_rid : lock_set) {
        lock_manager_->Unlock(txn, locked_rid);
      }
    }
    
    void TransactionManager::Abort(Transaction *txn) {
      txn->SetState(TransactionState::ABORTED);
      // rollback before releasing lock
      auto write_set = txn->GetWriteSet();
      while (!write_set->empty()) {
        auto &item = write_set->back();
        auto table = item.table_;
        if (item.wtype_ == WType::DELETE) {
          LOG_DEBUG("rollback delete");
          table->RollbackDelete(item.rid_, txn);
        } else if (item.wtype_ == WType::INSERT) {
          LOG_DEBUG("rollback insert");
          table->ApplyDelete(item.rid_, txn);
        } else if (item.wtype_ == WType::UPDATE) {
          LOG_DEBUG("rollback update");
          table->UpdateTuple(item.tuple_, item.rid_, txn);
        }
        write_set->pop_back();
      }
      write_set->clear();
    
      if (ENABLE_LOGGING) {
        // write log and update transaction's prev_lsn here
        LogRecord log{txn->GetTransactionId(), txn->GetPrevLSN(), LogRecordType::ABORT};
        txn->SetPrevLSN(log_manager_->AppendLogRecord(log));
        log_manager_->Flush(false);
      }
    
      // release all the lock
      std::unordered_set<RID> lock_set;
      for (auto item : *txn->GetSharedLockSet())
        lock_set.emplace(item);
      for (auto item : *txn->GetExclusiveLockSet())
        lock_set.emplace(item);
      // release all the lock
      for (auto locked_rid : lock_set) {
        lock_manager_->Unlock(txn, locked_rid);
      }
    }
    
    展开全文
  • 两阶段封锁协议

    千次阅读 2011-01-22 09:46:12
    对锁机制,保证事务可串行性的最常用协议两阶段封锁协议。该协议要求每个事务分个阶段提出加锁和解锁申请: (1)增长阶段。事务可以获得,但不能释放。 (2)缩减阶段。事务可以释放,但不能获得。 ...
  • 两阶段锁协议的理解
  • 前言本文主要是讲述MySql(仅限innodb)的两阶段加锁(2PL)协议,而非两阶段提交(2PC)协议,区别如下:2PL,两阶段加锁协议:主要用于单机事务中的一致性与隔离性。2PC,两阶段提交协议:主要用于分布式事务。MySql本身针对...
  • 锁协议

    千次阅读 2017-11-17 10:19:55
    1、锁协议是指所有事务必须分阶段对数据项加锁和解锁:  1.1、在对任何数据进行读、写操作之前,要申请并获得对该数据的封锁。  1.2、 每个事务中,所有的封锁请求先于所有的解锁请求。  ...
  • (mysql采用两阶段封锁协议) 调度是一组事务的操作的某种合并结果。(mysql支持多事务并行执行) 一个调度是合法的,如果同一时间没发生个不同事务的冲突。(mysql需要保证并行事务不冲突) 因为每个事务T都是...
  • mysql中的锁协议和三级封锁协议

    千次阅读 2019-04-17 09:14:42
    锁协议 一个事务中一旦开始释放锁,就不能再申请新锁了。事务的加锁和解锁严格分为阶段,第一阶段加锁,第二阶段解锁。 目的 :”引入2PL是为了保证事务的隔离性,保证并发调度的准确性,多个事务在并发的...
  • (1)改写T和T2, 增加加锁操作和解锁操作,并要求遵循两阶段封锁协议。 (2)说明T和T2的执行是否会引起死锁,给出T和T2的一个调度并说明之。 二、问题解答 (1)如下表所示 T1 T2 Slock A R(A) Slock B ...
  • 序此篇博客是【眼见为实】系列的第一篇博客,主要从理论上讲了数据库并发可能会出现的问题,解决并发问题的技术——封锁封锁约定的规则——封锁协议。然后简单说明了数据库事务隔离级别和封锁协议的对应关系。后面...
  • 锁协议

    2021-10-14 11:38:50
    锁协议是指每个事务的执行可以分为阶段:生长阶段(加锁阶段)和衰退阶段(解锁阶段) 加锁阶段:在该阶段可以进行加锁操作。在对任何数据进行读操作之前要申请并获得S锁,在进行写操作之前要申请并获得X锁...
  • 两阶段锁

    千次阅读 2015-08-20 18:40:32
    所谓锁协议是指所有事务必须分阶段对数据项加锁和解锁。  .在对任何数据进行读、写操作之前,首先要申请并获得对该数据的封锁  .在释放一个封锁之后,事务不再申请和获得任何其他封锁。所谓"段"锁的...
  • 两阶段锁协议将事务的封锁过程分成了以下阶段。 增长阶段(Growing Phase):事务可以尝试申请任何类型的锁,但是这个阶段不允许释放锁。 收缩阶段(Shrinking Phase):事务可以放锁,但是禁止再申请新的锁。 ...
  • (4)锁协议。 所有事务必须分阶段对数据项加锁和解锁。其中扩展阶段是在对任何数据进行读、写操作之前,首先要申请并获得对该数据的封锁;收缩阶段是在释放一个封锁之后,事务不能再申请和获得其他封锁。...
  • (2PL)和严格两(S2PL)的区别

    千次阅读 2019-04-27 00:18:46
    严格两 在执行事务的过程中,所有的数据库操作有可能会要求加锁,但是不能立刻释放。必须要等到整个事务提交或回滚后,才能释放。 总结 其主要区别简单来说,就是:2PL能随时释放,S2PL只能在事务结束后...
  • 所以只要是使用一次封锁法的协议都遵循锁协议,同时也说明锁协议也有死锁问题。 关于死锁这里提一嘴,有种方法解决: 一是预防:一次封锁法、顺序封锁法; 二是解决:超时法、等待图法。 其中等待图法指的...
  • 如何证明遵循锁协议的事务调度处理的结果是可串行化的 怎么证明遵循锁协议的事务调度处理的结果是可串行化的? 如题 ------解决方案-------------------------------------------------------- 9.4. 可串行...
  • Repeatable Read)③幻读(Phantom Read)④读脏数据(Dirty Read)二、并发控制的主要技术是封锁排它锁与共享锁的相容矩阵三、封锁协议一级封锁协议二级封锁协议三级封锁协议四、活锁和死锁活锁死锁五、两段锁协议两段...
  • 请补充上述执行序列,使其满足2PL协议,并使持有的时间最短。 二、问题解答 【问题一】 将写订单记录和修改库存表作为一个完整的事务来处理,当修改库存表无法执行时,回滚事务,则会撤销写入的订单记录,,数据库...
  • 文章目录第十五章:并发控制15.1 基于协议15.1.1 15.1.3 两阶段封锁协议15.4 基于时间戳的协定15.4.1 时间戳15.4.2 时间戳排序协议 第十五章:并发控制 为保证事务的隔离性,必须对并发事务之间的相互作用加以...
  • MySQL隔离级别和封锁协议

    千次阅读 2018-04-02 12:53:23
    天决定从原理上理解它,整理成自己的知识。查阅资料的过程中发现好多零碎的概念如果串起来足够写一本书,所以在这里给自己梳理一个脉络,具体的内容参考引文或在网上搜一下。由于平时接触最多的是MySQL,所以...
  • 3-2:并发控制

    2020-11-18 22:02:05
    基于协议 对数据项以互斥方式访问 先持有,再访问,访问后释放 共享读 排斥[拥有后可写,可读] 调度是一个动态过程,调度到A时,A因为执行申请操作,而此时申请不到,A阻塞, 再次产生调度,...
  • 前言 随着数据库应用的不断发展,数据规模逐渐升级,为了提高效率。往往会将多个事务并发...封锁方式是基于各种来进行并发控制。在封锁机制中,当多个事务同时访问同一数据时,应对其进行封锁请求的授予或等待。而
  • 天决定从原理上理解它,整理成自己的知识。查阅资料的过程中发现好多零碎的概念假设串起来足够写一本书,所以在这里给自己梳理一个脉络,详细的内容參考引文或在网上搜一下。因为平时接触最多的是MySQL。所以...
  • 2PL协议封锁协议

    万次阅读 2014-04-23 08:58:01
    two-phase locking protocol 2PL协议封锁协议 Two-phase transaction and two-phase locking protocol ...段事务可截然为段:拥有的增长阶段growing phase),拥有的缩减段段(shrinking pha

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,964
精华内容 4,785
关键字:

严格两阶段封锁协议