博客发布于2022年2月24日•最近更新于2022年2月24日•6分钟读取Gnome剪贴板历史（GCH）是一个Gnome扩展，它可以将您复制的内容保存到一个易于访问、可搜索的历史面板中。与现有剪贴板管理器相比的主要创新是使用压缩日志进行持久存储。GCH是对剪贴板指示器的重写，最初的目标是向上更新任何更改。这意味着GCH需要与剪贴板指示器的功能奇偶性。在这些现有功能中，以下性能影响了重写的设计决策：任何历史更改（包括新复制的条目）都会立即写入磁盘。以前复制的条目将重新显示，而不是创建副本（这意味着需要搜索历史记录，以了解刚刚复制的条目是新条目还是现有条目）。
考虑到这些特性对性能的影响，自然会出现几种数据结构选择：仅附加的持久存储结构（即日志）链表存储内存条目映射和反向查找索引存储由瞬态全局唯一ID键入的条目
在复制时，反向查找索引最小化了查找重复项所做的工作，而日志最小化了存储新条目所做的工作。该日志还可以最大限度地减少修改任意条目时所做的工作。类似地，链表最小化了在内存中添加/删除/移动这些条目所做的工作。搜索仍然是一个悬而未决的问题，但我稍后会讨论这个问题。GCH使用一种相对简单的二进制编码来存储复制的条目：一个操作的第一个字节总是它的类型，而后面的字节则是一个操作想要的任何字节。例如，添加操作如下所示：UTF-8数据字节∨00000000 01 49 20 77 61 73 20 63 6f 70 69 65 64 21 00 |。我被复制了！|∧ ∧ 添加op类型NUL终止符
最好存储文本的长度，而不是NUL终止符，但不存在读取N字节的Gnome API。现在让我们看看当你喜欢这个条目，删除它，然后复制并喜欢另一个条目时会发生什么：favorite op type∨00000000 01 49 20 77 61 73 20 63 6f 70 69 65 64 21 00 03 |。我被复制了！。|4字节小尾端ID（=1）∨000000 10 01 00 00 02 00 00 01 4d 65 20 74 6f 6f |。。。。。。。。。。我也是∧ ∧ 删除op类型4字节小尾端ID（=1）000000 20 00 03 02 00 00 00 00 |∧ ∧ 最喜欢的op 4字节小端点ID（=2）
有很多事情要做，所以让我们把它分解一下。首先，您会注意到为这两个项目隐式创建了ID。由于日志是仅附加的，并且总是在开始时读取整个日志，因此可以根据添加的条目的位置推断出全局唯一的ID。此外，由于日志是仅附加的，删除条目实际上不会删除任何内容（这就是压缩的原因）。相反，条目被简单地标记为已被删除，就像条目被标记为被偏爱一样。解析日志时，已删除的项目会附加到内存中的链表中，然后在执行删除操作时删除。ID是单调递增的，并存储在Little Endian中，因为我希望大多数人使用x86，从而节省一些位操作。我本可以通过使用Variant来让自己变得更时尚，但与JavaScript抗争似乎并不值得。未来的研究：使用mmap（或seek）开始读取文件末尾附近的某个地方。支持任意起始解码位置需要自同步，但解码器只能读取最后N个条目（直到用户请求更多）。
就这样！还有一些其他操作，但它们的工作原理都类似。这可以说是日志中最有趣的部分：压缩是让它保持只附加的功能。压缩时，将删除整个日志并从头开始重新创建，同时删除反转操作。反转操作是指相互抵消的操作。例如，添加和删除项目可以替换为不做任何事情。压实后，上面的示例如下所示：00000000 01 4d 65 20 74 6f 6f 00 03 01 00 00 |。我也是|
我的所有痕迹都被复制了！条目已被删除，我的身份证也已下移。因此，ID仅在压缩间隔之间是全局唯一的，这意味着内存中的数据结构必须在每次压缩后更新。经过深思熟虑，我可能应该用add操作存储ID，以最小化压缩工作。唯一的问题是ID溢出，但这可以通过保留一组活动ID来处理，以了解是否已经使用了一个ID。在任何情况下，由于add是主要操作，因此当前的方法都有最大限度地减少浪费空间的好处。
由于压缩成本很高，需要重写整个历史记录，所以理想情况下，我们希望执行压缩…嗯，永远不会！不幸的是，从不压缩意味着磁盘上的历史记录将永远增长，并且由于反转操作的数量，解析日志的速度将变得越来越慢。另一方面，我们可以随时进行压缩，从而使日志大小最小，并且不进行反转操作。因此，目标是在压实数量和浪费（即反转）操作数量之间取得平衡。令人惊讶的是，跟踪浪费的操作非常容易：如果删除某个内容，那么就浪费了两个操作（一个用于添加，一个用于删除）。其他操作也遵循类似的逻辑。接下来，为浪费的操作数选择一些阈值，如果超过该阈值，则执行压缩。容易的在内存中，剪贴板历史记录存储在双链接列表中，允许即时删除和轻松分页。分页对于GCH来说很重要，因为Gnome没有一个UI列表API（比如RecyclerView），它能够扩展到我想要支持的历史大小。最大的挑战是尽量减少迭代，因为链表的内存访问模式非常糟糕。索引（从文本到条目ID）被实现为一个相当标准的链接哈希表。为了最大限度地提高哈希性能，同时最小化冲突，使用了一个特殊的哈希函数，该函数利用了关于语料库的假设。值得注意的是，长字符串不太可能有长度冲突（例如，为什么有人会复制两个长度正好为30224个字符的不同字符串？）而短字符串是（例如，有人复制“abc”和“123”）。因此，我们得到了以下哈希函数：Search使用regex查询并返回按最近程度排序的分页结果，以尝试执行最小数量的匹配。虽然可以，但这显然是次优的，因为应该使用适当的索引。也就是说，我发现性能是足够的，并决定让它成为现实。GCH是用JavaScript编写的，因为它是Gnome扩展支持的唯一语言。作为一个注重性能的人，我发现Gnome扩展开发人员的体验非常令人不满意：语言的选择使得做某些事情变得不可能。注意（非穷举）：链表可以优化为将节点存储为缓存线大小的块。可以使用适当的映射实现，而不是我的优化效果不佳的版本，但JS映射不支持自定义哈希函数。可以使用一个合适的序列化库（比如Serde），这将使初始实现更加容易。任何与多线程有关的事情（比如在后台线程中运行搜索）都是不可能的。日志使用一个op队列来确保可序列化性——在支持单线程执行器的语言中实现这一点很简单。
简而言之，虽然我对自己在目前的限制下所做的事情感到满意，但我很高兴看到API流行起来了_操作系统将提供他们的宇宙DE。