
技术摘要:
本发明公开了一种树形数据的加锁方法,首先提取欲加锁的子树组的标识树并计算出局部标识Map,然后对局部标识Map中的每个节点的加锁标记计数值,取同一节点在整棵树的全局标识Map中的加锁标记计数值进行对比,以判断此次加锁是否允许,若允许加锁,将局部标识Map叠加到 全部
背景技术:
随着互联网时代的发展,业务的复杂度越来越高,IT系统倾向于组件化、模块化、 微服务化,即是对业务拆分成相对独立的底层组件,再在高层加以综合而形成整体业务。体 现在业务的数据上,就是业务的一个实例的数据保存为一个树形结构,每个底层业务组件 对应的数据是树中的一棵子树,并且这种拆分-组合的关系可以嵌套。 在业务处理过程中,有的业务场景只涉及单个底层组件,这样业务的数据改变只 会涉及该组件对应的子树,而不影响树中的其他数据。如果在同一个业务实例中,两个业务 场景涉及两个不同组件,它们修改的数据是同一棵树上的两个不同子树,那么它们就可以 同时执行。相反,如果两个业务涉及到相同的组件,它们就很可能修改同一组数据,而不能 同时执行。如果它们同时执行,就很可能造成数据被覆盖、数据完整性破坏等访问冲突,在 这种情况下,就需要对业务将要访问的数据进行加锁,以保证业务逻辑和数据的正确。 例如,某个业务由组件X和Y组成,而整个业务的数据结构如附图1所示。其中组件X 的数据对应于B1子树,而组件Y的数据对应于B2子树。如果一个业务只涉及到X组件,那么它 就只需要修改B1子树的数据,而不需要修改B2子树的数据。涉及Y组件的业务同理。这样,一 个只涉及X组件的业务与另一个只涉及Y组件的业务就可以同时执行,而两个涉及X组件的 业务就不能同时执行,或者一个涉及X组件的业务与另一个同时涉及X和Y组件的业务也不 能同时执行。这样就可以实现访问数据有重叠的业务互斥,访问数据无重叠的业务不互斥 的效果。 在并发访问和处理树结构时,通常需要采用加锁的方式避免发生冲突和保证数据 一致性,现有技术有两种: 1.对整棵树进行加锁,即每棵树对应一个锁,在业务访问一棵树前,需要先对该树 对应的锁进行加锁,处理完该请求后对该锁进行解锁,其他业务才能获取该锁,从而访问这 棵树。在这种加锁方式中,一棵树同时只能被一个业务访问,即使是无关的业务也无法同时 处理,对并发性能影响很大。例如:两个业务各自需要访问同一棵树的D2和E5节点。为了确 保数据的正确性,需要对访问的数据加锁,但在对整棵树加锁的方式中,两个业务都需要获 取到整棵树的锁后才能处理数据,从而只能依次执行,而不能同时执行。可见,该方式需要 对整棵树加锁,一棵树同时只能有一个业务处理,即使是多个业务处理的数据不同也是如 此,在业务高并发时会极大的影响性能,无法满足业务的需要。 2.对业务需要修改的每一个数据节点都加锁。一棵树中每个数据节点都对应一个 锁,业务处理前需要对自己本次处理的所有数据节点都获取到锁,才能开始处理。例如:一 个业务需要访问一棵树的D2子树,它就必须对D2、E1、E2、E3、F1、F2等6个节点加锁后才能开 始处理。其他涉及这几个节点的业务必须等该节点处理完成后释放锁才能开始,而不涉及 这些节点的业务可以与该业务同时执行。这种方式可以避免第1种方式无法并发的问题,但 4 CN 111597193 A 说 明 书 2/14 页 要求业务对树中每个节点的数据访问进行细致的控制,增加了业务复杂度。此外还要求业 务预先知道自己将要处理哪些节点,而这在某些场景下是不可能的。如果遗漏了对必要节 点的锁定,而有其他业务同步修改数据,会造成业务错误。
技术实现要素:
本发明的目的是为了克服现有技术的缺陷,提供一种树形数据的加解锁方法,尤 其是一种对树形数据的多个子树作为整体进行加解锁的方法,通过本发明能够确保数据的 一致性,简化业务逻辑,增进数据并发处理能力,提升系统性能。 为实现上述目的,本发明提供一种树形数据的加锁方法,特别是一种对树形数据 的多个子树作为整体进行加锁的方法,该方法包括以下步骤: a.提取子树组去重、去包含后的标识树; b.提取出该标识树的局部标识Map; c.获取整棵树的全局Lock; d .校验标识,对步骤b得到的局部标识Map中的每个元素,取其对应节点在整棵树 的全局标识Map中的加锁标记计数值进行对比,以判断此次加锁是否允许;若允许加锁,则 转到步骤e;若不允许加锁,则转到步骤f; e.将局部标识Map叠加到全局标识Map中,并保存局部标识Map,加锁成功,释放整 棵树的全局Lock,处理结束; f.释放整棵树的全局Lock,加锁失败,按失败策略等待重试或放弃。 进一步地,提取子树组的标识树的方法,对将要加锁的子树组中一个子树的根节 点,向上找它的父节点,对找到的父节点继续向上找父节点,直到整棵树的根节点,就得到 从一个子树根节点到整棵树的根节点的路径;如果在路径上存在子树组中另一个子树的根 节点,则丢弃该节点路径;剩下的所有节点路径中节点的并集就是这个子数组的标识树。 进一步地,构造标识Map的方法为:标识Map的键是节点id,值是节点标识数据;节 点标识数据是一个四元组,包括:本节点读锁计数,本节点写锁计数,子节点读锁计数,子节 点写锁计数。为整棵树和每个加锁的子树组各分配一个标识Map。 进一步地,简化标识Map的方法为:当一个节点的标识数据全为0的时候,该节点不 放入标识Map中,只有当节点的标识数据至少有一个非0,才放入标识Map。 进一步地,标识树的局部标识Map的提取方法为: 首先,构造一个空的标识Map;然后,对于找到的标识树的每个叶子节点,向Map中 加入以下项目: 如果是加读锁:<节点id>-->(1,0,0,0), 如果是加写锁:<节点id>-->(0,0,1,0), 然后,对于找到的标识树的每个非叶子节点,向Map中加入以下项目: 如果是加读锁:<节点id>-->(0,1,0,0), 如果是加写锁:<节点id>-->(0,0,0,1)。 进一步地,对局部标识Map中的每个元素LE的加锁标记计数值LEV,取其对应节点 在全局标识Map中的加锁标记计数值GEV进行对比,以判断此次加锁是否允许。对单个元素 对比的方法如下: 5 CN 111597193 A 说 明 书 3/14 页 1)如果全局标识Map中不包含同一节点的元素,则当前元素检查通过; 2)如果全局标识Map中包含同一节点的元素GE,则对LE和GE的加锁标记计数值LEV 和GEV做以下检查: i.如果LEV的“本节点读锁计数”不为0,那么GEV的“本节点写锁计数”、“子节点写 锁计数”都必须为0; ii.如果LEV的“本节点读锁计数”不为0,那么GEV的“本节点写锁计数”、“子节点写 锁计数”都必须为0; iii.如果LEV的“子节点读锁计数”不为0,那么GEV的“本节点写锁计数”必须为0; iv.如果LEV的“本节点写锁计数”不为0,那么GEV的“本节点读锁计数”、“子节点读 锁计数”、“本节点写锁计数”、“子节点写锁计数”都必须为0; v.如果LEV的“子节点写锁计数”不为0,那么GEV的“本节点读锁计数”、“本节点写 锁计数”都必须为0; 所有4个检查都通过,则当前元素检查通过。如果4个检查中任何一个检查不通过, 则当前元素检查不通过。 进一步地,如果局部标识Map中所有元素都检查通过,那么此次加锁操作被允许; 如果任一个元素检查不通过,那么此次加锁操作不允许执行。 进一步地,当对子树组的加锁操作允许时,将子树组的局部标识Map叠加到整棵树 的全局标识Map中,其方法为: 对局部标识Map中的每个元素LE,在全局标识Map中查找键相同的元素; i.如果没有找到,那么把元素LE直接加入到全局标识Map中; ii.如果在全局标识Map中找到元素GE,那么将LE的值中每个计数的值加到GE的值 中对应计数的值上; iii.保存本次加锁操作的局部标识Map,以备解锁时使用。 进一步地,如果加锁不区分读写场景,则等同于加写锁。 为实现上述目的,本发明还提供一种树形数据的解锁方法,该方法与加锁方法相 对应,对树形数据的多个子树作为整体进行解锁,包括以下步骤: a.获取之前对子树组加锁时生成的局部标识Map; b.获取整棵树的全局Lock; c.将之前加锁时叠加到全局标识Map上的局部标识Map从全局标识Map中去掉; d.释放整棵树的全局Lock,解锁完成。 进一步地,将之前加锁时叠加到全局标识Map上的局部标识Map从全局标识Map中 去掉,具体做法是:对局部标识Map中的每个元素LE,在全局标识Map中找到键相同的元素GE 后,将LE的值包含的4个计数值从GE的值包含的对应计数值中减去。减去后如果GE的值包含 的4个计数值全为0,则将GE从全局标识Map中移除。 本发明技术方案带来的有益效果: 本发明提供的一种树形数据的加解锁方法,通过对子树组的标识树中所有节点进 行标记,实现加解锁操作。与现有的常规做法相比较,本发明的优势是: 1 .通常来说,一个子树组的标识树中的节点数要比子树组中的节点数少得多,本 方法对标识树操作而非对子树组中的节点操作,从而减少了需要操作的节点数量,提高了 6 CN 111597193 A 说 明 书 4/14 页 性能。 2.控制加锁粒度为子树组,在确保数据一致性的同时,精准锁定区域范围,避免锁 定无关区域;以及区分读写场景,允许多个业务同时读取相同数据,可以有效减少并发业务 锁定数据时发生锁冲突和等待的概率。 3.对多个子树的原子性加解锁操作,及加锁冲突时的策略,使业务免于承担部分 加锁成功部分失败的处理,简化了业务逻辑。 4.通过分析子树锁原理,设计出对子树组的标识树中每个节点标记的方法,以及 标记的数据结构,通过Map查找节点标识,通过简单的算术运算实现加解锁标记,具备良好 的性能。 附图说明 为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例或现 有技术描述中所需要使用的附图作简单地介绍,显而易见地,下面描述中的附图仅仅是本 发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以 根据这些附图获得其它的附图。 图1是本发明的树形数据结构的一个示例图; 图2是本发明的树形数据结构加锁后标记形态的一个示例图; 图3是本发明的加锁流程图。