在解决了性能和可伸缩性问题之后，我们就可以获得一个稳定的Pijul了。在这篇文章中，我解释了近几个月来我一直在做的事情。
这篇博文包含有关Pijul的文档。Pijul根据GNU GPL-2.0或任何更高版本在您方便的情况下获得许可。
因此，如果在读完这篇文章后，你独立地重新发现了这里给出的算法，那是可以的，但你仍然必须在Gnu GPL-2.0许可下授权你的“独立重新发现”，并引用其来源(例如这篇文章)。如果这种重新发现发生在未来，包括零年、一年或更多年后，这也同样适用。
Pijul一直被宣传为一个研究项目，试图实施一种可靠而快速的补丁理论。这是一个雄心勃勃的目标，甚至比最初设想的还要雄心勃勃。
最困难的挑战之一是，源代码本质上是有状态的，这使得迭代算法设计变得更加困难，就像普通研究项目需要的那样。例如，为了从上一次发布的版本到现在的设计，我们经历了许多不同的变体，没有太多可发布的内容。
此外，最终最重要的是UX方面，而在现实世界的项目中测试它是实现它的唯一途径。但是，在编译器中，引导是一步完成的，并且以前的版本总是可用于编译当前的版本，与此不同的是，版本控制系统有一个额外的问题，即如果有错误，以前的版本可能并不总是很容易访问。
自从我意识到更好的数据结构是可能的之后，我听到的批评之一就是我在“秘密工作”。我当然理解这种感觉，但这是基于对研究如何运作的误解。当我第一次有了我在这篇文章中解释的想法时，我意识到需要彻底重写。但在很长一段时间里，除了不可用、不可读的原型，几乎什么都没有发生。
那时候，没有什么可展示的，因为甚至不清楚基本的数据结构是否可以工作。甚至当他们开始以足够大的规模工作时，在他们真正开始工作之前，我也花了相当多的时间在大型存储库上进行测试。
这也意味着在相当长的一段时间内没有什么可展示的，因为新算法直到最近才可用，而在此之前启动的任何存储库都将在几天内过时。
这篇文章的结尾处描述说，这种沉默也有非常专业的原因。
其中一个项目是Sanakirja，它“仅仅”是一个键值存储，但它还有一个额外的功能，即可以高效地克隆数据库。我很乐意只使用现有的库，但没有任何库具有这种克隆功能。然而，Sanakirja的范围仍然相当温和，它做了一件事，做得很好。显然，找到内存管理错误花了一些时间，但我很有信心现在已经找到了。
在Pijul的以前版本中，数据库是使用包含B树的二进制表示形式的单个mmaps文件实现的。尽管B树的写入性能较低(与Log-Structure Merge树等替代方案相比)，而且删除的代码也很复杂，但B树非常适合这种用例：实际上，因为它们是树，所以对节点进行引用计数就足以实现高效的克隆。
剩下的问题之一是，为了扩大数据库，我们需要取消mmap文件的映射，使其增长，然后再次映射它。由于在Pijul中应用单个更改必须是原子操作，因此当发生更改时，我们需要取消事务，并使用更大的文件重新启动它。
另一个问题是，我想让下一个libpijul在没有mmap的平台上编译，比如WASM。然而，如果重新分配一个mmaps文件的复杂性非常低(即使它在系统调用方面的成本不是零)，重新分配一块内存通常需要复制所有内容。这完全违背了Pijul中的算法的观点，该算法依赖于磁盘上数据结构的特定表示形式。
Sanakirja 0.13中的主要创新是使用大小呈指数增长的内存块(在内存中或从文件中映射)向量。开销只是一个额外的间接开销，添加项的复杂性是相同的(因为创建额外块的操作是$O(1)$)。指数级增长的大小意味着分配的内存始终至少是半满的。
另一个是特鲁什。该库实现了SSH协议，并尝试处理许多密钥格式。前者是一个出人意料的简单目标，从历史上看，跟上Tokio的版本是最困难的，而后者是最可怕的类似九头蛇的任务，每次你认为你完成了，新的头部和遗留的格式就会出现。
旧式存储库用有向图$G=(V，E)$表示单个文件，其中V$中的每个顶点$v\代表一条线，V$中的$u\到V$中的$v\的一条边，由某个变化(也称为补丁)编号$c$标记，可以理解为“根据变化$c$，行$u$在$v$之前”。
这意味着更改可能会引入顶点和线，如下例所示，其中在$A$和$B$之间引入了线$D$：
这里，粗线表示从包含行$A$、$B$、$C$的文件到包含新行$D$的文件的更改。需要注意的一个重要特性是，顶点由引入它们的更改的散列以及该更改中的位置唯一标识。这意味着，内容相同的两行，由不同的变化引入，将是不同的。这也意味着，即使在完全不同的上下文中应用更改，线条也会保持其身份。
此外，这个系统是仅附加的，从这个意义上说，删除由更复杂的边缘标签来处理。在上面的示例中，如果我们想删除行$D$，我们只需要进行更改，将$c_0$引入的边映射到已删除的边，我们将其标记为引入它的更改的名称$c_1$：
我们刚刚描述了Pijul中的两种基本动作。没有其他的了。一种将顶点以及它们周围的“活动”边添加到图中，另一种将现有的边标签映射到另一个不同的边上。为了全面描述系统，我还需要提到边标签由两个参数给出：它们的状态(活动的、已删除的，以及与多个文件相关的一些其他参数和下面解释的技术细节)以及引入它们的更改。
如果一个变化$c$添加了一个顶点，我们必须有它的“上下文”，即它之前和之后的线，因此引入这些线的变化依赖于$c$。
如果更改$c$删除了顶点，或者换句话说映射了由更改$d$引入的现有边，则$c$必须依赖于$d$。
当然，这只是理解文本编辑所需的最小依赖集。挂钩和脚本可能会基于语义添加额外的依赖于语言的依赖项。
我们的目标是找到尽可能小的系统，这既是出于数学美学的原因(为什么要储存无用的东西？)。另一个是表演。因此，一个迫在眉睫的问题浮现在脑海中：为什么要把找零的数字放在边缘？
为了回答这个问题，假设我们不保留标签，这意味着映射只在状态之间发生。然后，考虑以下两种情况：
第一个问题发生在两个作者并行删除一行时，其中一个作者恢复了他们的更改。应用这些更改将生成下图，其中两个删除项合并为一个，反之亦然：
然而，这并不是我们所期望的，因为其中一位作者显式地恢复了删除，而另一位作者并行执行了相同的删除。通过保留标签，我们得到的结果是：
为了清楚起见，在这篇文章的其余部分，我们将两个用户命名为Alice(代词为“她/她”)和Bob(代词为“他/他”)。
这种情况下，Alice在段落$p$中间写了一些东西，而Bob并行删除了$p$。这里的一个问题是情况不对称：当Bob应用Alice的更改时，他可以立即判断出有问题，因为Alice编辑的上下文在他的存储库中被标记为已删除。
然而，Alice的情况有所不同：实际上，考虑这样一种情况：Bob在应用Alice的更改后删除了$p$，而不是在删除$p$的同时删除了她的更改。删除的边完全相同，但这不是冲突，如下图所示：
由于该系统与新行上下的上下文不对称，情况变得更加复杂。实际上，如果Bob删除了该行的下行上下文(即，如果他删除了行$C$)而不是向上上下文(行$B$)，则Alice可以检测到冲突，因为在这种情况下，$C$将同时有一个活动边和一个死边指向它($C$在内部称为“僵尸顶点”)，如下图所示：
在每条边上保留更改标识符使我们能够解决这个问题。在Pijul 0.12中，Bob会将删除行周围的所有边的标签添加到其更改的依赖项中。然后，爱丽丝可以在应用它之前判断鲍勃是否知道她的更改。当且仅当Bob不知道新行时，这些更改才是冲突的。
对哪些依赖关系进行了更细致的分析，就会导致新Pijul的不同行为。更改现在有两组不同的依赖项：一组是严格依赖项，这是我们应用当前更改所需的更改；另一组只是一组“已知”更改，应用算法检查这些更改以决定是否标记冲突。
根据我们到目前为止所描述的，皮朱尔有两种类型的冲突：
两个活动顶点之间在任一方向上都没有(有向)路径。
此外，很容易说明Pijul实现了一种无冲突的复制数据类型(CRDT)：实际上，我们只是将顶点和边添加到图中，或者映射我们知道由于依赖而存在的边标签。
然而，Pijul的数据结构以一种无冲突的方式对文本文件中可能发生的冲突进行了建模。事实上，Pijul仍然是一个CRDT，不管有没有上面解释的关于边缘标签的设计选择：例如，我们可以决定“已删除”状态具有更高的优先级。但如上所述，这并不能准确地模拟冲突。
我现在要讨论的场景是从多行开始的顺序(即单用户)场景。我们的用户将它们全部删除，并在开头和末尾各添加一行，如下图所示：
如果我们像图中那样天真地表示这种情况，那么应用更改和输出存储库的复杂性将线性依赖于图形的大小，因为我们需要遍历整个过程才能了解行$C$，并知道它位于$B$之后。
诀窍是使用我们所说的“伪边”，它不是任何变化的一部分，而只是用来保持“活动子图”(活动顶点的子图)的连通性。每次删除边时，我们都会在边源和目标的所有后代之间添加伪边，如下图中的虚线边所示：
我们引入了另一种类型的边缘标签来表示边缘代表文件，因此是不可传递的。特别是，当我们删除一个文件时，下面的所有后代顶点都必须被删除。
每个文件或目录由两个单独的顶点表示：一个是其名称，另一个是表示文件本身的“inode”顶点。这允许目录重命名与文件重命名进行通信，并允许文件重命名与文件开头的编辑进行通信。当并行删除新顶点的上下文时，仅将文件表示为其名称的天真表示将导致上述类型的冲突。
不冲突的情况是，通过收缩来自和到命名顶点的边而减少的活动文件的图形是一棵树，并且每个文件恰好有一个唯一的名称。
首先，当文件被引入并行删除的目录时，可以断开活动文件的图形。当发生这种情况时，我们使用伪边路径将删除的图路径加倍。
另一种冲突是文件$a$并行重命名，Alice重命名为$b$，Bob重命名为$c$。这包括将文件移动到两个不同目录，从而生成非树DAG的情况。
还有一种是当两个不同的文件同时被赋予相同的名称时。
最后，可以创建目录的循环图：从存储库根目录的两个目录$a$和$b$开始，Alice可以将$a$移动到$b$的子目录$b/a$，而Bob可以将$b$移动到$a$的子目录$a/b$。
在前面的Pijul中，每个线-顶点的内容都存储在数据库的一个表中。这并不是最佳选择，因为：
行的内容存储了两次：一次存储在更改文件中，另一次存储在数据库中。
某些用于存储长(>；512字节)行的内存页可能不足。例如，长度为513的行需要4096字节的存储空间。
尽管这看起来很浪费，但在我们分析的存储库中，这只是问题的一半左右。图形占用了另一半的磁盘空间，不仅存储库占用了大量的磁盘空间，而且这也使得非常重要的用例极难调试，因为图形很快就无法绘制，即使在Pijul这样小的代码库上也是如此。
此外，Pijul的一些潜在应用需要基于单词的比较。但这些图表的大小已经超出了线条的控制范围，而文字只会让情况变得更糟，因为这需要每个单词一个顶点。
这是一个重大的可伸缩性问题，甚至比解析特定格式的SSH密钥(这可能是最常报告的问题)还要严重。
当时我确实考虑过放弃这个项目，但就在那之前，我想尝试两个想法：
由于我看到的许多图都有连续线的长路径，我们是否可以将它们“打包”在一起作为单个顶点存储，直到另一个更改需要拆分它们？
老实说，我对这个想法不太满意，因为单词仍然有问题，因为我们必须在存储库的开始，以及对于存储库的所有文件，选择图形是否表示字行。此外，这至少需要进行一次重大重构，以获得潜在的小好处。
同时，我试图解决如何存储内容的问题。毕竟，如果我不得不放弃这个项目，那么如果我设法让磁盘上的数据库变得更小，那么至少Sanakirja可以是一个很好的副产品。
最后，我没有“修复”Sanakirja，而是设法同时解决了这两个问题。如果我们可以存储线组，我们也可以存储字节组，那么图就会更大。另外一个好处是，如果图顶点存储了对更改字节偏移量的引用，我们不必存储将行号映射到内容的表，只需直接从更改文件加载内容即可。
然而，这个想法意味着必须写一本全新的皮朱尔，才能作为这个想法的基准。我在2019年底的圣诞节假期期间编写了核心算法，结果相当令人满意，因为我能够毫无问题地导入大量大文件。更好的是，我能够用图形显示结果。
我对如何公开宣布这一点并不是非常有信心，因为已经有很多人开始使用Pijul，尽管他们知道这个项目还处于实验阶段，但从所有可以想象的方式来看，这一举动都将是一个突破性的变化。此外，我也不清楚我是否仍然在法律上被允许在Pijul上工作(下面有更多关于这一点的内容)。
在这篇文章中，我们首先回顾前两个图表：添加和删除行。现在，顶点由更改编号(例如$c_0$)和该更改中的字节间隔引用(例如$[0，n[$，意思是“从偏移量$0$包含到偏移量$n$排除的字节”)。请注意，顶点现在可以表示任意数量的线。此外，它们在内存中所占的大小与$n$无关(假设$n<；2^{64}$)。
从单个顶点$c_0：[0，n[$和$n$字节(包含任意数量的线)开始，通过更改$c_0$引入，添加一条线的方法是首先在某个偏移量$i<；n$处拆分$c_0：[0，n[$]，然后像以前一样插入新顶点。
这特别意味着，将内容拆分成行是由DIFF算法完成的，并在更改中进行编码，而不是为所有存储库固定不变。使用不同的DIFF算法，我们可以想象根据编程语言结构拆分内容。
一旦我们知道如何拆分折点，删除操作就几乎和以前一样：如下图所示，我们首先应用与上一个示例相同的更改$c_1$，然后应用更改$c_2$，这将删除顶点$c_0的结尾$c_0：[0，i[$从某些$j<；i$删除到$i$，以及顶点$c_1的开头：[0，m[$，from$0$到某个$k<；m。
与以前的一个重要区别是，我们之前的优势有两个不同的角色，直到现在才能清楚地区分开来。其中一个意思是命令行，另一个意思是状态。然而，现在顶点可以拆分了，边的“状态”角色就变得不明确了：例如，一条被删除的边指向某个顶点$c：[i，j[$意味着更改$c$的字节$[i，j[$]，但是如果我们将该顶点拆分为$c：[i，k[$and$c：[k，j[$？我们应该添加额外的删除边吗？如果是，应该在哪里添加？
有一个简单的解决方案：通过引入一种新的边标签(在源代码中称为block)，我们可以区分“内部”或“隐式”边(仅在这里对块进行排序)和“状态”边(通知其目标顶点的状态)。我可能会在未来的博客文章、手册或论文中更多地解释这一点。
在对我们的话语进行讨论之后，“补丁”被重新命名为“改变”。别太碎了，好吧。
所有内容的存储方式都不同，因为顶点的含义甚至与以前不同。
更改现在使用变体zstd进行压缩，允许在不解压缩整个文件的情况下解压缩文件的子集。
更改现在分为两个主要部分：一个包含一个标题，其中包含元数据、依赖项、已知补丁、编辑和内容的加密散列。另一个部分包含更改的内容，它是更改中所有新顶点内容的串联。特别是，更改不会存储删除的内容(实际上从未存储过，即使在Pijul的以前版本中也是如此)。此划分允许服务器和客户端跳过不再有效的内容，同时允许客户端在以后需要时检索和验证内容。
更改现在有一个文本表示，目标是使用二进制更改进行一对一转换。这是一个新事物，要正确处理并不是一件轻而易举的事，特别是因为一个序列化和反序列化周期必须产生完全相同的二进制内容。
当创建新的改变时，向作者呈现文本格式的改变的草稿(除非检测到一些记录的文件是二进制文件)，
.