持久内存上图数据的功能页级分区与布局方法与流程
本发明涉及计算机存储与数据库,具体涉及一种在持久内存上对图数据进行功能页级分区与布局的方法、系统、存储介质及电子设备。
背景技术:
1、图数据库需要同时管理节点与边两类数据,并支持邻接关系的快速遍历。现有图数据库大多构建于文件系统与虚拟内存机制之上,依赖内存映射文件、内核页表与虚拟文件系统接口完成数据访问,在无文件系统、无虚拟文件系统接口的常驻内存运行环境中难以直接适用。
2、为提升数据局部性,已有方案将节点集合与边集合划分为彼此不相交的存储分区,即节点集与边集之交为空的拓扑图分区。此类分区在节点与边频繁关联变更时需要跨分区同步维护一致性,产生额外的复制、日志与索引修复开销,实现复杂度较高。
3、另一方面,持久内存兼具字节寻址能力与断电后数据不丢失的特性。若仍以文件、页缓存与系统调用为中介访问,将引入不必要的拷贝与上下文切换开销。因此需要一种直接面向持久内存页组织数据的分区布局方案,使功能区划分、索引建立、日志写入与崩溃恢复能够在同一地址空间内协同完成,并使布局本身可自描述、可恢复。
技术实现思路
1、本发明要解决的技术问题是:在持久内存运行环境中,如何对图数据进行分区与布局,使其既便于按功能整区管理与崩溃恢复,又避免节点集合与边集合作拓扑不相交分区所带来的一致性开销,并使邻接关系读取具有单一数据来源。
2、为解决上述技术问题,本发明采用的技术方案是:提供一种持久内存图数据的布局方法,包括以下三层布局。
3、其一,对象统一存储层,将图中的节点与边统一作为堆对象实体,由同一分配器分配于共享存储区域,并以对象句柄中预置的类型标识区分节点实体与边实体,节点对象与边对象不划分至各自独立的存储区域。
4、其二,二级索引层,构建从节点全局标识到对象句柄的节点索引,以及从对象句柄到邻接对象句柄集合的出边邻接索引与入边邻接索引。
5、其三,功能页级分区层,以超级块自描述整体布局,将持久内存划分为位图区、预写日志区与数据区,并由区域管理器按页号区间将页访问请求路由至所属功能区。
6、其中,所述分区按页的功能用途进行划分,不对节点集合与边集合作相交为空的拓扑图分区,即节点与边不做分区存储。
7、在一种实施方式中,所述方法应用于无文件系统与无虚拟文件系统接口的常驻内存运行环境。
8、在一种实施方式中,所述对象句柄为定长位段编码,包含类型标识位段、节点标识位段与局部标识位段,所述局部标识位段用于标识所述堆对象实体在所述共享存储区域中的位置;所述类型标识位段可以为8位,据此在同一共享存储区域内区分节点实体与边实体,使两类对象共用同一套分配、回收与持久化机制。
9、在一种实施方式中,所述超级块位于持久内存的起始页,记录页大小、位图区起始位置、预写日志区页数与数据区起始位置;所述预写日志区包括预定数量的页,例如为64页。区域管理器可以区间树存储各功能区的起止区间,按对数时间复杂度将页号或地址路由至所属功能区。
10、在一种实施方式中,读视图共享同一份邻接表数据而不作拷贝,遍历时由读视图直接按对象句柄从所述共享存储区域读取邻接对象句柄集合。插入节点时写入节点索引,插入边时分别在出边邻接索引与入边邻接索引中登记,删除节点或边时同步移除相应索引条目。
11、在一种实施方式中,对数据区的修改先行记录于预写日志区,持久内存发生断电后按预写日志区的内容对数据区进行重放恢复。所述位图区用于标记数据区中各页的分配状态。所述共享存储区域可以为slab区域,所述分配器为slab分配器。
12、本发明还提供一种持久内存图数据库系统、一种计算机可读存储介质以及一种电子设备,其技术构思与上述方法对应。所述电子设备包括存储器和处理器,存储器上存储有计算机程序,处理器执行所述计算机程序时实现上述任一项方法的步骤;所述计算机可读存储介质上存储有所述计算机程序。
13、本发明的有益效果如下。
14、第一,分区仅针对页的功能用途,不引入节点与边之间的拓扑不相交分区,节点与边的关联变更不需要跨分区同步维护,能够降低跨区一致性维护开销。
15、第二,节点与边混合存储于同一共享存储区域,由同一分配器分配,有利于减少区域碎片与重复元数据。
16、第三,节点索引与出入边邻接索引构成邻接关系的单一数据来源,读视图共享同一份邻接表数据而不作拷贝,有利于避免双源数据漂移。
17、第四,超级块自描述整体布局,区域管理器按页号区间路由,使布局可自发现、可扩展。
18、第五,修改先行记录于预写日志区,断电后按日志重放恢复,崩溃恢复路径确定,便于验证。
1.一种持久内存图数据的功能页级分区布局方法,其特征在于,包括以下三层布局:(一)对象统一存储层:将图中的节点与边统一作为堆对象实体,由同一分配器分配于共享存储区域,并以对象句柄中预置的类型标识区分节点实体与边实体,节点对象与边对象不划分至各自独立的存储区域;(二)二级索引层:构建从节点全局标识到对象句柄的节点索引,以及从对象句柄到邻接对象句柄集合的出边邻接索引与入边邻接索引;(三)功能页级分区层:以超级块自描述整体布局,将持久内存划分为位图区、预写日志区与数据区,并由区域管理器按页号区间将页访问请求路由至所属功能区;其中,所述分区按页的功能用途进行划分,不对节点集合与边集合作相交为空的拓扑图分区,即节点与边不做分区存储。
2.根据权利要求1所述的方法,其特征在于,所述方法应用于无文件系统与无虚拟文件系统接口的常驻内存运行环境。
3.根据权利要求1所述的方法,其特征在于,所述对象句柄为定长位段编码,包含类型标识位段、节点标识位段与局部标识位段,所述局部标识位段用于标识所述堆对象实体在所述共享存储区域中的位置。
4.根据权利要求3所述的方法,其特征在于,所述类型标识位段为8位。
5.根据权利要求1所述的方法,其特征在于,所述超级块位于持久内存的起始页,记录页大小、位图区起始位置、预写日志区页数与数据区起始位置,持久内存初始化时依据超级块的自描述信息恢复各功能区位置。
6.根据权利要求5所述的方法,其特征在于,所述预写日志区包括预定数量的页。
7.根据权利要求6所述的方法,其特征在于,所述预写日志区为64页。
8.根据权利要求1所述的方法,其特征在于,所述区域管理器以区间树存储各功能区的起止区间,按对数时间复杂度将页号或地址路由至所属功能区。
9.根据权利要求1所述的方法,其特征在于,读视图共享同一份邻接表数据而不作拷贝,遍历时由读视图直接按对象句柄从所述共享存储区域读取邻接对象句柄集合。
10.根据权利要求1所述的方法,其特征在于,还包括索引的同步维护:插入节点时写入所述节点索引,插入边时分别在所述出边邻接索引与所述入边邻接索引中登记,删除节点或边时同步移除相应索引条目。
11.根据权利要求1所述的方法,其特征在于,还包括写前日志与崩溃恢复:对数据区的修改先行记录于所述预写日志区,持久内存发生断电后按预写日志区的内容对数据区进行重放恢复。
12.根据权利要求1所述的方法,其特征在于,所述位图区用于标记数据区中各页的分配状态。
13.根据权利要求1所述的方法,其特征在于,所述共享存储区域为slab区域,所述分配器为slab分配器。
14.一种持久内存图数据库系统,其特征在于,包括:对象统一存储模块,用于将图中的节点与边统一作为堆对象实体,由同一分配器分配于共享存储区域,并以对象句柄中预置的类型标识区分节点实体与边实体,节点对象与边对象不划分至各自独立的存储区域;索引维护模块,用于维护从节点全局标识到对象句柄的节点索引,以及从对象句柄到邻接对象句柄集合的出边邻接索引与入边邻接索引;功能页分区模块,用于以超级块自描述整体布局,将持久内存划分为位图区、预写日志区与数据区;区域路由模块,用于按页号区间将页访问请求路由至所属功能区;其中,所述分区按页的功能用途进行划分,不对节点集合与边集合作相交为空的拓扑图分区。
15.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该计算机程序被处理器执行时实现权利要求1至13中任一项所述方法的步骤。
16.一种电子设备,包括存储器和处理器,所述存储器上存储有计算机程序,其特征在于,所述处理器执行所述计算机程序时实现权利要求1至13中任一项所述方法的步骤。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com