“多粒度锁把IS、IX、SIX的权限、兼容和祖先取得次序完整展开,让粗粒度请求能够发现下方细锁;谓词与区间锁进一步把尚不存在的潜在键也纳入保护。前者规定锁在不同层级怎样相遇,后者规定查询的逻辑…”
形式陈述
资源树和五种非空模式
固定一棵有限有根树,每个叶子是一项逻辑资源,内部节点代表其全部后代叶子的集合。树的边界在一次事务期间不改变。锁表记录“哪个事务在什么节点持有什么模式”;同一事务、同一节点只有一份合并后的模式。这里沿用严格两阶段锁的rigorous口径:读写锁与意向锁都保留到提交或完成中止清理,不在普通执行中提前释放。
S(node)允许读整棵子树,X(node)允许读写整棵子树。IS只表示准备在下方取得共享权限,IX表示准备在下方取得读写权限;意向模式自身不授权读取或修改任何叶值。SIX同时给整棵子树的S权限和向下取得X权限的意向。NL表示没有锁。[1, Part I,Table1]
两个不同事务在同一节点的兼容关系如下。表中“是”只允许两模式同时持有;不保证各事务之后提出的请求也成功。
| 已有/请求 | IS | IX | S | SIX | X |
|---|---|---|---|---|---|
| IS | 是 | 是 | 是 | 是 | 否 |
| IX | 是 | 是 | 否 | 否 | 否 |
| S | 是 | 否 | 是 | 否 | 否 |
| SIX | 是 | 否 | 否 | 否 | 否 |
| X | 否 | 否 | 否 | 否 | 否 |
NL与所有模式兼容。IX与IX兼容,是因为两个事务可能修改不同叶子;真正对同一叶子的排他冲突将在更低层拦住。S与IX不兼容,是因为S已承诺整棵子树可读,而IX持有者可能向下修改其中一项。
自上而下取得足够意向
取得新显式锁前,沿根到该节点的祖先路径核对权限。S或IS请求的每个祖先至少已有IS权限;IX、SIX或X请求的每个祖先至少已有IX权限。所谓“至少”按下述权限偏序,而非模式名称的数值编号:
S与IX互不包含。故IX/SIX/X均足以传递写意向,S不够。S或X祖先已隐式覆盖相应后代访问,通常无需再设冗余细锁;本教学模型允许无害的冗余读锁,但写入仍必须满足排他权限。叶子没有后代,不请求纯IS或IX。[1, pp.369–370]
同一事务再请求一个模式时,取旧模式与请求模式的最小共同上界。例如S加IX成为SIX,IX加S也成为SIX,IS加S成为S。申请转换时仍保留旧模式,先拿新模式与其它事务的持有模式比较,全部兼容才原子替换。失败或等待不撤掉旧锁,也不把尚未批准的新权限用于数据访问。[1, Table3]
为什么祖先检查足够
假设T能够读某叶x,而U能够写x。T沿路径有一个S、SIX或X节点P覆盖x,U有一个X节点Q覆盖x。P、Q都在根到x的一条链上。
若P在Q上方,U为向下取得X,必须在P持有至少IX;它与T在P的S/SIX/X不兼容。若Q在P上方,T向下取得读权限须在Q持有非空意向或更强模式,它与U的X不兼容。P=Q时直接不兼容。因此合法授锁状态不可能让两个事务同时获得这对冲突权限。结合终点释放,旧2PL的锁点证明便可继续使用。
这个证明依赖每次访问都经过同一资源树。偷偷从第二个索引路径写叶子、却不取得该树上的祖先意向,会绕过前提;有多个父节点的资源图需要另定覆盖所有路径的协议,不由本页树证明自动覆盖。
直觉
粗锁不必逐行寻找细锁
想锁整张表的事务不能只看“表节点目前没有X”,否则另一个事务也许早已锁住表内某行。意向锁把下层存在访问计划这一信息留在祖先处。表级S请求只需与表节点的IX冲突,就知道不能越过下面的写者。
意向不是预留一条具体行。两个IX可同时存在;每个写者之后还要为实际叶子取X。SIX则适合“读取整个范围,只改少数记录”:整范围的读权限已经得到,只对待改叶子继续取得排他权限。
例子与边界
三个事务使用两层表结构
树为DB→表A→行a、b。T1修改a,取得IX(DB)、IX(A)、X(a),共三份锁。T2只读b,取得IS(DB)、IS(A)、S(b),也共三份;两者可以同时存在。T3想扫描整个A,IS(DB)可取得,但S(A)与T1的IX(A)冲突,只能等到T1结束。
如果T3在A只持IS,就不能把它当成扫描许可。缺少S(A)或各叶子的S,扫描会读到T1尚未完成的变化。锁模式字段的拼写正确,仍不足以保证访问经过授权检查。
再令T4先读全表,再改a。它已有S(A),请求IX(A)必须转换为SIX(A),并保证DB已具IX。若T2仍持IS(A),转换可成功;若T3仍持S(A),转换必须等待。T4随后还须取得X(a),SIX本身没有给整表排他权限。
升级保留旧保护,也可能形成等待环
T1与T2都持S(a),现在都要求X(a)。自身S不作为自身的冲突者,但另一事务的S确实冲突。双方都保留旧S等升级,便相互等待。兼容矩阵保证授锁安全,没有证明无死锁;年龄定向策略可在这一步选择等待或中止。
把S临时释放再取X不是等价优化:空窗里其它事务可以修改a;而且按本页rigorous合同,正常操作中根本不允许释放。若业务仍使用升级前读到的值计算新值,重获X也不能自动补回丢失的验证。
锁升级到粗粒度也不免费。若要用X(A)替代许多行X,须先按兼容规则取得X(A),才能去掉被覆盖的冗余表示;先删除细锁再申请粗锁会留下未保护窗口。本页核验器保留全部显式锁到终点,不实现这种表示压缩,故没有另作锁升级性能承诺。
推论与应用
逻辑资源不必等于当前存在的行
若叶子只为当前现存行创建,锁完所有叶子仍没有表示“这里不许插入新行”。谓词与区间锁把潜在键位置也作为逻辑资源:固定键域0至31的叶子即使当前无记录仍存在,区间可由内部节点覆盖。由此可把本页跨粒度互斥用于幻读保护;动态B+树页分裂和页面latch是另一层机制。
计锁表,而不把意向当零成本
树高h按根到叶的边数计,一次点访问至多需要h+1个显式节点请求;访问k个叶子的简单上界为O(1+k(h+1))份请求,公共祖先可以复用。实际驻留锁数是不同事务/节点对的数量L,锁表需O(L)记录,不能按整表只算一把锁。
若每次请求检查该节点的g个其它持有者,简单实现需O(1+g)次模式检查;再检查h个祖先得到O(1+h+g)。已建立的持有者索引可避免扫整张锁表,但等待唤醒、事务清理和测试中的全局不变量扫描另计。粗锁减少记录,却扩大阻塞范围,兼容矩阵本身不决定最优粒度。
下载核验器优先保持状态易查:它按事务遍历持有字典,没有建立每节点的持有者索引。若记录A个事务,单次请求含O(1+h+A)工作;path_request还会为路径上每个节点重查祖先,完整路径保守O((h+1)²+(h+1)A),额外全局verify另计。这些调试费用不冒充前述带索引接口的成本。
终点任务把空区间覆盖为两个树节点,再逐个提升写入路径;要求交出失败转换前后仍持有的模式,而不只报告一个“被阻塞”。
参考资料
[1] Jim Gray、Raymond Lorie、Gianfranco Putzolu、Irving Traiger,Granularity of Locks and Degrees of Consistency in a Shared Data Base,Modelling in Data Base Management Systems,1976,pp.365–394,Part I,Table1与Figure2 pp.368–369、树协议pp.369–370、转换Table3 p.377。本文固定树上的两事务证明、32叶实例与有限状态核验自行展开。