坐井观天网

探索易于理解并实现的业余手工业创作技能

菜单
41

版本控制和可追踪的文件和抽象数据结构统一体

既然这个场景Git已经有人在做,现在就可以把UDF的结构写出来了,只是原来的UDF系统代码没弄到Linux上去(主要是GUI部分,文件系统本身没有什么具体的平台相关内容),所以演示就等以后来做了。

啊啊啊啊他其实只是小A图形界面的附属功能而已。

简介

我甚至记不得UDF全称当时是怎么了,应该是Universal Descriptive Format。它是一个文件结构和内存数据结构的统一体,它应具有下面的特征:

  • 描述数据和它们之间的拓扑关联。
  • 对不同形式的数据描述具有兼容的抽象结构。
  • 描述自身的变动历史。

其结构允许符合其规范的软件系统的运作具备如下特点:

  • 信息结构始终可以被同构地解析。
  • 单个和多个协作实例的外在表现一致。
  • 运行时和待命的抽象结构一致。
  • 可增量式的修改和追溯内容的任何局部。

要求

UDF的设计需求是:表示数据结构和它整个生命期的变化。

为表达数据和它们之间的关系,UDF定义下面两个元素:

  • 引用:用以指向任何节点
  • 节点:任意多个值和引用的并集

并定义概念:

  • 连通:节点与其直接下属引用所指的节点是连通的,节点与已连通节点相连通的节点连通。

通过节点和引用,可以用其构建任意抽象数据结构的拓扑等效,并且它们的底层表达方法互相兼容。

为表达差分,需要能在不同版本的拓扑中查询唯一对应,此时需要引入另一个基本元。

  • 标识符:节点的唯一识别,在整个生命期保持不变,是一个创建后立即作为只读的值。

如果一个节点的所有连通节点都包含能充当全生命标识符的值,那么这个节点就是可以被UDF表示的。

UDF磁盘文件存取

UDF的实现可以在任何满足UDF表示的抽象数据结构的外围部署。磁盘文件是UDF的基础功能。

UDF运行时管理器会要求在应用程序初始化时用节点和引用的形式描述现有数据结构。获得该信息之后,它就能将内存中数据结构的内容写入磁盘,并在载入时将储存的部分恢复为等效数据结构,整个过程对软件运行是透明的。一个在节点中不具有唯一标识符的数据结构依然可以被UDF读写,但无法对它记录历史和比较版本差异,因为内存地址仅对单次运行有效。

文件读取时,UDF管理器将读取并按照对数据结构的描述分配节点对应的内存空间,并记录下这些节点的内存地址、他们在文件中的标识符以及所有节点间的原始引用。当所有节点完全就绪之后,UDF管理器将恢复节点间的引用地址。

为成功从磁盘文件恢复数据拓扑结构,还存在一个节点所有者问题。因为在UDF抽象底层,节点之间是等效的,并且引用网不表示节点的从属关系,这样一来无法通过一个无重复的路径遍历所有节点。因此UDF管理器要求为所有者从属引用指定特殊标志,使得所有节点构成单向树型结构。文件读取只为节点的所有者创建子节点的内存数据块,并进入其子级填充它内部的值和下一个子级,否则仅将引用做待匹配标记,读取完成后实际无法找到具体的数据块。对于不能在数据结构层面被较好表示为树形层级关系的节点关系结构,仍然可以描述一个独立于主数据结构的旁通引用以使UDF管理器正确地遍历节点。

将节点引用组合描述为节点树是恰当的。

树形读取的好处是,相当多实际软件的数据结构都已经是具有这样拓扑特征的,并且几乎所有功能结构都可以被提炼为树形结构。

在一个复杂的拓扑数据结构中,节点和引用的数目都非常庞大。UDF管理器中设置了一个4兆字节的哈希表以加快引用查询,节点引用恢复速度非常高。

文件版本管理

全生命期标识符允许增量储存节点树,因为同一个节点,无论它变化再显著,仍然可以通过它的标识符加以识别。事实上,UDF设计了一个版本管理节点头,它不仅包含了节点标识符,还包含了链表头、创建和修改时间、作者等附加实用信息。由于可以比对,UDF管理器就可以以增量方式储存文件。事实上,UDF既可以采取类似git的单独仓库模式,也可以采取版本号迭代的方式储存增量文件。为使用方便,增量文件可以按末位为参考前向应用,读取时无需应用前序修改,后序模式则是为保存最初原始记录,二者也可以同时存在。

应用或拆分节点树增量修改均由UDF管理器执行。与单纯文件的操作类似,数据结构的关联操作是按照描述自动完成的。

UDF允许只为部分节点提供全生命期标识符,版本控制只覆盖这一部分节点,其余节点储存为非增量形式。不具有全生命期标识符的节点在储存文件时使用运行时内存地址作为受限标识符,因此所有对该节点有引用的节点需要同时全部写入和读取,否则有可能出现引用匹配失败。一些场合的冗余引用是不重要的,而且总是可以通过指定后处理回调将恢复后的数据结构配置为需要的状态。

撤销和运行时版本控制

UDF的数据结构描述在软件运行时常驻,因此它可以被用于查分的运行时记录。这个差分记录与文件差分版本是等效的。

撤销栈需要一个初始状态,它和文件值一致,这个初始状态可以用文件内存映像直接表示,但压栈时再次解析文件数据性能较低。UDF为根节点建立了一个镜像读取,这带来了基本两倍于原始数据的内存占用,但有利于快速差分操作。

当运行时数据结构发生任意改变之后,进行撤销栈压栈操作,UDF管理器检查当前结构和上一层状态的差分,并记录新的数值,这个步骤与差分文件写入的唯一差别是它执行在运行时,写入的位置是内存。需要重做时,UDF管理器同样用类似前述差分应用的过程直接操纵运行时数据结构恢复到撤销栈的上一层状态。

运行与文件差分记录等效,这意味着UDF管理器可以直接在运行时实现版本分支,相当于是应用程序运行状态的快照。这十分有利于用户在不确定分支步骤时的尝试和选择,对用户交互容错意义重大。

请扩展相关的内容

通用文件结构始终是有限度的,它具有适用性边界,在一些场合下,维护这样一个描述结构的开销将变得不合理。因此需要根据使用情况尽早判断这种应用是否可行。比如主要执行数值计算的工具就不需要用到这样的结构。这方面的研究尚不完善,欢迎提出您的建议。


迁移自旧文章,并有所编辑。

评论 (0)

要评论,请发送邮件到xp8110@outlook.com