做毕业设计的网站设计,wordpress缓存数据库,做餐厅网站的需求分析,织梦网络设计工作室网站模板为何要有VLL#xff1f;VLL旨在解决什么问题#xff1f;
在数据库系统中#xff0c;锁是广泛使用的并发控制机制。然而对于内存数据库系统#xff0c;锁管理器却成为了性能瓶颈所在。 一项研究说明内存数据库中有16%#xff5e;25%的时间用于与锁管理器的交互 在传统的锁…
为何要有VLLVLL旨在解决什么问题
在数据库系统中锁是广泛使用的并发控制机制。然而对于内存数据库系统锁管理器却成为了性能瓶颈所在。 一项研究说明内存数据库中有16%25%的时间用于与锁管理器的交互 在传统的锁管理器中最常见的实现方式是采用以数据主键为id请求该数据的锁请求链表为值的hash表锁请求链表还存在锁头追踪该项的锁状态以及支持互斥操作。
对于与磁盘相关的数据库这些hash表查找、锁获取和链表操作都是可以忽略不计的可对于内存数据库来说这些额外的内存访问、cache未命中、cpu周期、以及临界区就可能接近或者超过执行实际事务逻辑的成本
VLL在上述锁管理器上做出了两个主要变化
将锁信息从中心hash表中移出到原始数据中从锁数据结构中删除哪些事务对特定锁未完成请求的信息取而代之的是原始数据包含未完成的写、读请求的数量CX记录未完成的写请求数量、CS记录未完成的读请求数量
在事务获取锁时会一次请求所有锁并按照请求锁的顺序对事务排序按照这种全局事务顺序来确定哪个事务应该先解除堵塞并执行
可是VLL也并非银弹在高争用负载下可能会导致并发减少和CPU利用率差。为解决这个问题又引入了选择性竞争优化SCA在需要的时候高效计算最有用的竞争信息子集
VLL算法介绍
锁结构
VLL锁管理结构由
储存到每个原始数据的的未完成锁写请求数量CX和未完成锁读请求数量CS中心事务请求全局队列TxnQueue
组成
流程
具体流程如下 当事务到达分区时会尝试对该分区所有在其生命周期内访问的记录加锁 每个锁请求都采取相应记录的CX或CS加1的形式 如果请求后的CX1且CS0则认为独占锁被请求事务抢占 如果请求后的CX0则认为请求事务获取了共享锁 当事务获取锁之后就被添加到TxnQueue 请求锁和向队列添加事务都发生在同一临界区中 在离开临界区时若事务在请求时获取到所有锁则该事务为free否则为堵塞。那么只有free事务才能够立即执行
问题
考虑以下问题
单线程VLL在需要其他节点协作的事务请求中如果一直等待会导致资源的浪费在没有中心锁管理结构情况下如何释放等待中的堵塞事务执行呢如果在CX0的情况下才能获取锁而写请求到达之后都能递增CX那么在存在多个写请求事务堵塞情况下CX会永远大于0随着TxnQueue大小增长新事务能立刻获取锁的概率大大降低
为解决这些问题
引入waiting状态标识事务正在进行中但需要获取搭配远程结果才能继续执行。因此在进入waiting状态之后就可以挂起不会导致额外的资源浪费让后台线程检查TxnQueue中每个堵塞事务的请求数据CX、CS值若CX下降到1CS为0则说明该事务获取到互斥锁CX为0CS大于0则说明获取到共享锁对于队列头的堵塞事务直接解除堵塞并执行。这是因为事务位于队列头说明在此之前请求锁的事务都已经完结了为TxnQueue设立阈值当超过后将会停止处理新事务从TxnQueue中寻找可以被解除堵塞的事务。而在阈值内则会优先处理新请求事务
代码及流程展示
以下是代码展示
func beginTransaction(t *TxnItem) {// 开始时事务状态为Freet.TxnStatus Free// 遍历本地读集合检查是否存在冲突若存在冲突则事务状态为Blockedfor _, readKey : range t.ReadSet {if inLocal(readKey) {data[readKey].csif data[readKey].cx 1 {t.TxnStatus Blocked}}}// 遍历本地写集合检查是否存在冲突若存在冲突则事务状态为Blockedfor _, writeKey : range t.WriteSet {if inLocal(writeKey) {data[writeKey].cxif data[writeKey].cs 0 || data[writeKey].cx 1 {t.TxnStatus Blocked}}}// 若事务状态为Free且事务为分布式事务则事务状态为Waitingif t.TxnType TxnTypeDistributed t.TxnStatus Free {t.TxnStatus Waiting}
}func commitTransaction(t *TxnItem) {// 提交事务时释放读集合的锁for _, readKey : range t.ReadSet {if inLocal(readKey) {data[readKey].cs--}}// 提交事务时释放写集合的锁for _, writeKey : range t.WriteSet {if inLocal(writeKey) {data[writeKey].cx--}}
}func vll() {for {// 若接收到远程事务消息则处理该事务的消息并执行事务、提交事务以及从队列中移除该事务t, ok, message : selectReceivedMessageTx()if ok {handleReadResult(t, message)if isReadyToExecute(t) {execute(t)commitTransaction(t)txnQueue.dequeue(t)}continue}// 若队列头事务堵塞在分布式事务时设置状态为等待并给其他参与节点发送事务请求// 否则设置状态为空闲执行事务、提交事务以及从队列中移除该事务if txnQueue.front().TxnStatus Blocked {t txnQueue.front()if t.TxnType TxnTypeDistributed {t.TxnStatus Waiting// 给其他参与节点发送事务请求} else {// 注意此处对于队列头的堵塞事务直接解除堵塞并执行// 这是因为事务位于队列头说明在此之前请求锁的事务都已经完结了。并且考虑到存在多个事务增加同数据CX值的情况使得CX总是会大于1导致死锁t.TxnStatus Freeexecute(t)commitTransaction(t)txnQueue.dequeue(t)}} else if !txnQueue.isFull() {// 若队列未满则获取新事务请求// 新事务状态为Free执行事务、提交事务// 若事务状态为Waiting给其他参与节点发送事务请求并入队// 若事务状态为Blocked入队// 注意检查未满的缘故在于平衡新旧事务的处理。在阈值内优先处理新事务请求阈值之外优先处理waiting的事务t getNewTxnRequest()beginTransaction(t)switch t.TxnStatus {case Free:execute(t)commitTransaction(t)case Waiting:// 给其他参与节点发送事务请求txnQueue.enqueue(t)case Blocked:txnQueue.enqueue(t)}}}
}考虑下面场景下的演变表中展示的是各事务请求的数据
txnread setwrite setAx, yxBx, yxCx0DyzE0y
最开始所有数据的CX、CS都是0TxnQueue为空事务A发起读取x、y并写入x请求此时数据x的CX递增数据y的CS递增并且事务A作为free事务加入TxnQueue事务B发起x、y读x写的请求。当由于x.CX0所以B无法获取到x的写锁因此作为堵塞事务加入到TxnQueue当A完成执行后释放锁。此时x.CX–、y.CS–并将A从TxnQueue移除B而后标记为free获取锁开始执行事务C发起读取x的请求因此x.CS由于x.CX0因此事务C的读请求无法保证作为堵塞事务加入到TxnQueue事务D发起对y读请求对z写请求。那么y.CSz.CX1由于y.CX和z.CX此前均为0事务D所有锁获取成功并作为free事务加入TxnQueue事务E发起对y的写请求由于y.CS0所以E请求失败作为堵塞事务加入到TxnQueue事务B执行完毕后释放x写锁、y读锁并从TxnQueue移除C此时位于TxnQueue队列最前面因此标记为free成功获取到x读锁并执行最后事务E也能够安全执行因为不与TxnQueue中在其之前的任何事务冲突。但又由于VLL算法仅允许TxnQueue最前面事务执行所以还是不能够执行。SCA将解除该限制
array VLL
array VLL采用向量或数组的数据结构来连续储存锁信息这会使得数据和锁信息是在两次单独请求中进行的但在单独线程中由于在核心缓存中所以也能在性能上有着较好的发挥
一次性获取所有锁的障碍
在运行事务前事务读写集可能是未知的由于每个节点都有TxnQueue并且临界区在本地那么不同的节点可能处理顺序并不一致这可能会导致死锁
为解决第一个问题允许事务在进入临界区前能给执行所需要的任何读取
为解决节点事务顺序不一致引发的死锁问题有两种解决方法
允许产生死锁通过使用死锁检测协议取消死锁事务协调节点使各节点事务顺序一致
VLL采用协调节点的方式可以在增加协调开销的情况下仍然产生改进的性能
SCA——提升在高争用下的性能
对于高竞争和高百分比的多分区工作负载VLL引入了SCA进行模拟标准锁管理器去检测哪些事务应该继承已释放锁的能力
SCA只在真正需要的时候才会激活比如在CPU处理空闲时。从队列头往尾部进行扫描分析在事务之前的事务是否存在冲突
func sca(q TxnQueue) *TxnItem {// 初始化冲突检测数组dx : make([]int8, 10010)ds : make([]int8, 10010)for _, item : range q {// 如果事务被阻塞if item.TxnStatus Blocked {success : true// 检查读集合若读集合中的数据已经被写占用则事务失败for _, read : range item.ReadSet {key : hash(read)if dx[key] 1 {success false}// 读集合中的数据标记为已占用ds[key] 1}// 检查写集合若写集合中的数据已经被读、写占用则事务失败for _, write : range item.WriteSet {key : hash(write)if ds[key] 1 || dx[key] 1 {success false}// 写集合中的数据标记为已占用dx[key] 1}// 若事务成功则返回该事务if success {return item}}else {// 事务未被阻塞仅标记读写集合数据被占用for _, read : range item.ReadSet {key : hash(read)ds[key] 1}for _, write : range item.WriteSet {key : hash(write)dx[key] 1}}}return nil
}VLLR——支持范围的VLL
对于频繁读取、写入、删除同一事务中的许多连续行锁定行范围比锁定多个单独行更有用可以避免幻读以及在删除一个数据行共享其主键的公共前缀的实体的常见用例中特别有用
VLLR通过锁定位串前缀进行范围锁定。当锁定一个范围主键时将该范围表示为集合R然后生成集合P使得R中任何一个元素都能在P中找到前缀。最简单生成P的方式时选择R中最小和最大位串的最长公共前缀
在得到集合P之后VLLR采用分层锁的方式进行。即先从数据库获取意图锁而后从表获取意图锁接着在页获取意图锁最后获取行锁
此外为了更好管理锁状态VLLR在CX、CS的基础上引入了P集合的LX、LS计数器也就是如果当前请求属于集合P的写请求则LX递增属于集合P的读请求则LS递增
func requestLock(item *TxnItem, rg *txnRange, exclusive bool) bool {// 事务加入队列txnQueue.enqueue(item)// 获取锁范围的前缀pfs : rg.toPrefix()// 请求前缀锁success : truefor _, pf : range pfs {success success requestPrefixLock(pf, exclusive)}return success
}func requestPrefixLock(key string, exclusive bool) bool {success : truek : hash(key)// 检查当前key数据锁是否不可获取if exclusive {success success (cs[k] 0)}success success (cx[k] 0)// 检查key数据所在前缀锁是否不可获取if exclusive {success success (ls[k] 0)}success success (lx[k] 0)// 检查key所有前缀的数据锁是否不可获取for i : 1; i len(key); i {h : hash(key[:i])success success (cx[h] 0)if exclusive {success success (cs[h] 0)}}// 标记key数据锁if exclusive {cx[k]} else {cs[k]}// 标记key数据所有前缀的前缀锁for i : 1; i len(key); i {h : hash(key[:i])if exclusive {lx[h]} else {ls[h]}}return success
}func releaseLock(item *TxnItem, rg *txnRange, exclusive bool) {// 释放锁范围的前缀pfs : rg.toPrefix()for _, pf : range pfs {releasePrefixLock(pf, exclusive)}// 事务出队列txnQueue.dequeue(item)
}func releasePrefixLock(key string, exclusive bool) {// 释放key数据锁k : hash(key)if exclusive {cx[k]--} else {cs[k]--}// 释放key数据所有前缀的前缀锁for i : 1; i len(key); i {h : hash(key[:i])if exclusive {lx[h]--} else {ls[h]--}}
}Ref
https://www.cs.umd.edu/~abadi/papers/vldbj-vll.pdf
