实现基于2PL的事务处理原型

基本概念

  • Short duration lock 短锁
    • 动作开始前申请锁,动作结束立即把锁释放
  • Long duration Lock 长锁
    • 动作开始前申请锁,动作结束继续持有锁
    • 2PL的思路
  • 事务从锁的角度看分为加锁和解锁两个阶段
    • Growing
      • 加锁阶段,事务只获取锁,不释放锁
    • Shrinking
      • 解锁阶段,事务只能释放锁,不能加新锁
  • 2pl变种:保守2pl、严格2pl
  • 常见的实现方式
    • 事务进行过程中加锁,事务结束后集体释放
    • 这里只考虑事务结束后统一释放的情况

实现思路

加锁

获取数据项上已有的锁,判断与自己加的锁是否冲突

  • 若不冲突
    • 对数据项上mutex加锁,设置该数据上已有锁信息(owner)为自己加的锁
  • 若冲突
    • 将自己要加的锁(LockEntry)push到该数据的等待队列waitlist中
    • 对该数据mutex加锁,然后阻塞,等待已有的锁释放

解锁

判断数据项上有无阻塞的锁请求(检查waitlist)

  • 若没有
    • 释放mutex上的锁,将数据上的锁owner置为无锁
    • 再次检查waitlist,防止在释放锁的过程中有加锁操作被阻塞,从而使该锁请求不能得到响应
  • 若有阻塞的锁请求
    • 从waitlist中pop出头部的LockEntry,将owner置为该LockEntry
    • 释放mutex上的锁

代码说明

本人完成的代码原型已经上传到GitHub

代码结构

  • global.h:全局配置及变量
  • structure.h/.cpp:实验所用的数据结构定义及基本操作,采用的基础数据结构是hash map
  • cc_lock.h/.cpp:基于锁的并发控制的实现
  • main.cpp:程序入口,测试程序的实现

全局变量

  • 锁类型
    • enum lock_t {LOCK_EX, LOCK_SH, LOCK_NONE };
    • 三种锁类型,EX代表互斥锁,SH代表共享锁,NONE代表无锁
  • 返回值
    • enum RC {RCOK, ERROR, FINISH, NOT_FOUND,ALREADY_EXIST };
    • 代表操作的结果类型,RCOK 正确,ERROR错误,NOT_FOUND数据项不存在,ALREADY_EXIST数据项已存在
  • 并发策略
    • enum cc_type{CC_LOCK, CC_OCC, CC_TO};
    • 代表三种并发策略,LOCK 基于锁,OCC 乐观并发控制,TO基于时间戳
    • 通过配置Engine的cc_type,指定所需的并发策略

数据结构

  • Engine
    • 实验所用的datastore的引擎,实际上就是一个HashMap
    • std::unordered_map data_map;
  • Data
    • 数据项
  • LockEntry
    • 锁,包含属性有:锁类型,持有该锁的线程id

事务

  • 通过开启多个线程,每个线程执行若干条对数据的操作,来模拟多个事务的并发。每个线程相当于一个事务
  • 本实验模拟了4个事务

results matching ""

    No results matching ""