_{图片来源： www.nikonsmallworld.com}

反-窃是一种专门的搜索引擎，早已在其中进行了介绍。 任何搜索引擎（不管怎么说）要快速运行，都需要有自己的索引，该索引考虑了搜索区域的所有功能。 在有关Habr的第一篇文章中，我将讨论搜索索引的当前实现，搜索索引的发展历史以及选择一个或另一个解决方案的原因。 有效的.NET算法不是神话，而是艰难而富有成效的现实。 我们将深入研究散列，按位压缩和多级优先级缓存。 如果您需要比O（1）更快的搜索怎么办？

如果其他人不知道这张照片中的带状疱疹在哪里，欢迎...

带状疱疹，索引以及为什么要寻找它们

带状疱疹是一段文本，大小为几个单词。 带状疱疹彼此重叠，因此得名（英语，带状疱疹，鳞片，瓷砖）。 它们的具体大小是一个公开的秘密-4个字。 还是5？ 好吧，这取决于。 但是，即使这个值给出的值也很小，并且取决于停用词的组成，用于标准化词的算法以及在本文框架中不重要的其他细节。 最后，我们将基于此切片计算出64位哈希值，以后我们将其称为切片。

根据文档的文本，您可以创建许多带状疱疹，其数量可与文档中的单词数量相媲美：

文字：字串→带状疱疹：uint64 []

如果两个文档中有多个带状图重合，则我们假设这些文档相交。 匹配的瓦片越多，这对文档中的文本就越相同。 索引搜索与被检查文档相交最多的文档。

_{图片来源： Wikipedia}

Shingles索引允许您执行两个主要操作：

1. 用标识符将文件的标题索引：

   
   

   index.Add（docId，带状疱疹）

2. 搜索并显示重叠文档标识符的排名列表：

   
   

   index.Search（带状疱疹）→（docId，得分）[]

我认为，排名算法通常值得单独写一篇文章，因此我们在这里不再赘述。

带状疱疹的索引与著名的全文索引（例如Sphinx，Elastic或更大的索引：Google，Yandex等）有很大不同。一方面，它不需要任何NLP和其他生活乐趣。 所有文本处理以及文本中带状疱的顺序均被删除，并且不影响处理过程。 另一方面，搜索查询不是一个单词或多个单词的短语，而是多达数十万个哈希 ，这些哈希在聚合中起着至关重要的作用，而不是单独存在。

假设，您可以使用全文本索引代替带状疱疹索引，但是两者之间的差异太大。 下面将介绍使用一些著名的键值存储的最简单方法。 我们看到了我们的自行车实施方案，称为-ShingleIndex。

我们为什么要打扰呢？ 但是为什么。

• 卷数
  
  1. 有很多文件。 现在我们大约有6.5亿，而今年显然会有更多。
  2. 独特的带状疱疹的数量正在飞跃增长，已经达到了数千亿。 我们正在等待一万亿美元。
• 速度 ：
  
  1. 白天，在夏季会议期间，通过Anti-Plagiarism系统检查了30万多个文档。 从流行的搜索引擎的标准来看，这有点高，但是它保持了基调。
  2. 为了成功验证文档的唯一性，索引文档的数量应比要检查的文档大几个数量级。 我们索引的当前版本平均每秒可以填充4000多个中型文档。

一切都在一台机器上！ 是的，我们可以复制 ，我们正在逐步在集群上实现动态分片 ，但是从2005年至今，一台机器上的索引经过精心维护，已经能够解决所有上述困难。

奇怪的经历

但是，现在我们是如此有经验。 不管喜欢与否，但我们也已经成长，并在成长过程中尝试了不同的事情，现在想起来很有趣。

_{图片来源： Wikipedia}

首先，没有经验的读者可能想使用SQL数据库。 您并不是唯一这样认为的人，SQL实现已经为我们服务了很多年，以实现很小的集合。 但是，焦点立即集中在数百万个文档上，因此我不得不走得更远。

如您所知，没有人喜欢自行车，而LevelDB尚未进入公共领域，因此在2010年，我们的目光投向了BerkeleyDB。 一切都很酷-持久的内置键值库，具有合适的btree和哈希访问方法以及悠久的历史。 她的一切都很棒，但是：

• 在散列实现的情况下，当其达到2GB的容量时，它只是下降了。 是的，我们仍在32位模式下工作；
• B +树实现稳定运行，但是由于容量超过数GB，搜索速度开始显着下降。

我们必须承认，我们从来没有找到一种方法可以根据我们的任务进行调整。 也许问题出在.net绑定中，但仍然必须完成。 在填写主要索引之前，最终将BDB实现用作SQL的替代，作为中间索引。

时间过去了。 在2014年，他们尝试了LMDB和LevelDB，但没有实现。 我们的抗-病研究部门的人员使用RocksDB作为他们的索引。 乍一看，这是一个发现。 但是，即使是小批量的补货，缓慢的搜索速度和中等的速度也使一切变得毫无用处。

在开发我们自己的自定义索引的同时，我们完成了以上所有操作。 结果，他变得非常善于解决我们的问题，以至于我们放弃了以前的“塞子”并专注于改进它，现在我们将其用于生产中。

索引层

最后，我们现在有什么？ 实际上，带状疱疹的索引由具有恒定长度的元素（从0到128位）的几层（数组）组成，这不仅取决于层，而且不一定是8的倍数。

每个层都起作用。 有些使搜索速度更快，有些节省了空间，有些则从未使用过，但确实需要。 我们将尝试描述它们，以提高搜索的整体效率。

_{图片来源： Wikipedia}

1.索引数组

在不失一般性的前提下，我们现在将考虑为文档分配一个单独的瓦片，

（docId→瓦片）

我们将交换该对中的元素（取反，因为索引实际上是“取反的”！），

（带格→docId）

按带状疱疹的值排序并形成一层。 因为 带状疱疹的大小和文档的标识符是恒定的，现在任何了解二进制搜索的人都可以在文件的O（登录）读数之外找到一对。 太多了，地狱很多。 但这比仅O（n）好 。

如果文档有多个带状疱疹，那么文档中将有多个这样的对。 如果有多个具有相同带状对象的文档，那么这也不会有太大变化-同一行中将有几对成对出现。 在这两种情况下，搜索将进行可比较的时间。

2.组数组

我们以任何方便的方式将上一步中的索引元素仔细地分为几组。 例如，为了使它们适合群集扇区，分配单元块 （读取的4096字节），考虑到位数和其他技巧，将形成有效的字典。 我们得到了这些组的简单位置数组：

group_map（哈希（带状））-> group_position。

搜索带状疱疹时，我们现在将首先搜索该组在字典中的位置，然后卸载该组并直接在内存中搜索。 整个操作需要两次读取。

组位置字典比索引本身占用的空间少几个数量级，通常可以简单地将其卸载到内存中。 因此，将不会有两个读数，而是一个。 总计， O（1） 。

3.布隆过滤器

在面试中，求职者通常通过发布具有O（n ^ 2）甚至O（2 ^ n）的唯一解来解决问题。 但是我们不做愚蠢的事情。 世界上有O（0）吗？ 让我们在没有太大希望的情况下尝试...

让我们转到主题区域。 如果学生做得好并且自己写了作品，或者只是没有文字，而是垃圾，那么他的带状疱疹的很大一部分将是独特的，并且不会在索引中找到。 像布隆过滤器这样的数据结构在世界上是众所周知的。 在搜索之前，请检查其上的瓦片。 如果索引中没有盖瓦，那么您将无法看得更远，否则就走得更远。

Bloom过滤器本身非常简单，但是在我们的卷中使用哈希向量毫无意义。 使用以下方法就足够了：从Bloom过滤器中读取+1 。 如果木瓦是唯一的，并且在过滤器中没有误报，则这会从后续阶段提供-1或-2读数。 小心你的手！

布隆过滤器错误的概率是在构造过程中设置的；未知带状疱疹的概率由学生的诚实决定。 简单的计算可​​以得出以下依赖性：

• 如果我们信任人们的诚实（即，实际上该文档是原始文档），则搜索速度将会降低；
• 如果将文档清楚地缝合在一起，则搜索速度将会提高，但是我们需要大量内存。

有了对学生的信任，我们就拥有“信任，但要验证”的原则，实践表明，布隆过滤器仍然有好处。

鉴于此数据结构还小于索引本身，并且可以缓存，因此在最佳情况下，它使您无需进行任何磁盘访问就可以丢弃碎片。

4.粗尾

几乎到处都有带状疱疹。 它们在总数中所占的份额很少，但是在第一步中构建索引时，在第二步中，可以获得数十和数百MB大小的组。 我们将分别记住它们，我们将立即从搜索查询中丢弃它们。

当这个琐碎的步骤于2011年首次使用时，索引的大小减半，并且搜索本身也得到了加速。

5.其他尾巴

即使这样，带状疱疹也可以有许多文件。 这是正常的。 数以万计，成千上万个……将它们保留在主要索引内变得无利可图，它们也可能不适合组，这使组位置字典的数量膨胀了。 将它们放在一个单独的序列中，以提高存储效率。 据统计，这样的决定是合理的。 此外，各种按位打包可以减少磁盘访问的次数并减少索引的数量。

因此，为了便于维护，我们将所有这些层都打印到一个大文件-块中。 其中有十个这样的层。 但是一部分未在搜索中使用，一部分很小并且总是存储在内存中，一部分在必要/可能的情况下被主动缓存。

在战斗中，最常见的搜索结果是将数据读取到一两个随机文件。 在最坏的情况下，您必须执行三个操作。 所有层都是有效的（有时是按位的）恒定长度的元素的打包数组。 这就是归一化。 与存储期间总容量的价格相比，解包时间微不足道，并且具有更好的缓存能力。

构造时，主要是预先计算层的大小，然后顺序写入，因此此过程相当快。

你怎么到那里，不知道在哪里

2010 , . , . , .

_{图片来源： Wikipedia}

最初，我们的索引由两部分组成-上面描述的一个常量和一个临时的部分，其作用是SQL或BDB或它自己的更新日志。 有时，例如，每月一次（有时是一年一次）对临时目录进行排序，过滤并与主目录合并。 结果是一个统一的，两个旧的被删除。 如果临时存储区无法放入RAM，则该过程将进行外部排序。

该过程相当麻烦，它以半手动模式启动，实际上需要从头开始重写整个索引文件。 为数百万个文档重写数百GB的数据-好吧，如此愉快，我告诉您...

为了使SSD不会特别劳累，并且索引会更频繁地更新，在2012年，我们按照以下方案涉及几部分链：

这里的索引由相同类型的块链组成，除了第一个。 第一个插件是仅附加日志，在RAM中具有索引。 随后的块的大小（和年龄）增加到最后一个（零，主，根等）。

骑单车的注意事项...

有时候，您不应该无所顾忌地编写代码，甚至不去思考，而只需在Google上进行更彻底的搜索即可。 直到该符号为止，该图类似于1996年文章“日志结构的合并树”中的该图 ：

添加文档时，首先将其折叠成插件。 当其已满或根据其他标准时，将在其上构建永久块。 相邻的几个块（如有必要）合并为一个新块，并删除了原来的块。 更新文档或删除文档的方法相同。

合并标准，链长，旁路算法，已删除项目和更新的说明，其他参数已调整。 该方法本身涉及几个类似的任务，并在干净的.net上作为独立的内部LSM框架而形成。 大约在同一时间，LevelDB开始流行。

在我们的案例中， LSM算法具有非常合适的功能：

1. 即时插入/删除/更新，
2. 减少了更新期间SSD的负载，
3. 简化的块格式，
4. 仅在旧/新块上进行选择性搜索，
5. 平凡的备份
6. 灵魂还想要什么。
7. ...

通常，发明自行车自我发展有时很有用。

宏观，微观，纳米优化

最后，我们将分享有关我们如何在.Net上（不仅限于此）进行反pla窃的技术提示。

请提前注意，通常一切都取决于您的特定硬件，数据或使用模式。 缠绕到一个位置后，我们飞出了CPU缓存，移到了另一个位置-遇到了SATA接口的带宽，第三处进入了-我们开始挂在GC上。 在某个特定系统调用的执行效率低下的地方。

_{图片来源： Wikipedia}

处理文件

访问文件的问题在我们看来并非唯一。 有一个TB级的EB大文件，其大小是RAM大小的许多倍。 任务是读取散布在周围的百万个较小的随机值。 并快速，高效且廉价地执行此操作。 我们必须努力，进行基准测试和思考。

让我们从一个简单的开始。 要读取珍贵的字节，您需要：

1. 打开文件（新的FileStream）；
2. 移至所需位置（位置或搜索，无差异）；
3. 读取所需的字节数组（Read）；
4. 关闭文件（处理）。

这很糟糕，因为它又长又沉闷。 通过反复试验，反复尝试和反复尝试，我们确定了以下动作算法：

• 单开，多读

  
  

  如果这个顺序在额头上完成，那么对于磁盘的每个请求，我们都会迅速弯曲。 这些项目中的每一个都进入对OS内核的请求，这很昂贵。

  
  

  显然，您应该打开文件一次，然后依次读取它的数百万个值，这是我们要做的

• 没什么

  
  

  获取文件大小，当前位置也很困难。 即使文件没有更改。

  
  

  应该避免任何查询，例如获取文件大小或当前位置。

• 文件流池

  
  

  下一个 File，FileStream本质上是单线程的。 如果要并行读取文件，则必须创建/关闭新文件流。

  
  

  在创建类似aiosync之类的东西之前，您必须发明自己的自行车。

  
  

  我的建议是为每个文件创建一个文件流池。 这样可以避免浪费时间打开/关闭文件。 而且，如果将其与ThreadPool结合使用，并考虑到SSD会通过强大的多线程发布其megaIOPS，那么，您理解我。

• 分配单位

  
  

  下一个 存储设备（HDD，SSD，Optane）和文件系统在块级别（集群，扇区，分配单元）上处理文件。 它们可能不匹配，但是现在几乎总是4096字节。 在固态硬盘中，在两个这样的块的边界处读取一个或两个字节比在块本身内部慢大约一半半。

  
  

  您应该组织数据，以便减去的元素在群集扇区块的边界内。

• 没有缓冲区。

  
  

  下一个 FileStream默认情况下使用4096字节的缓冲区。 坏消息是您无法将其关闭。 但是，如果读取的数据多于缓冲区的大小，则将忽略后者。

  
  

  对于随机读取，应将缓冲区设置为1个字节（它将不会减少工作量），然后考虑不使用它。

• 使用缓冲区。

  
  

  除随机读数外，还有顺序读数。 如果您不想一次读取所有内容，则缓冲区在这里已经非常有用。 我建议您从本文开始。 要设置的缓冲区大小取决于文件是在HDD还是SSD上。 在第一种情况下，1MB是最佳；在第二种情况下，标准4kB就足够了。 如果要读取的数据区域的大小与这些值相当，则最好像随机读取的情况一样，跳过缓冲区一次将其减去。 较大的缓冲区不会提高速度，但是会开始打击GC。

  
  

  当顺序读取大块文件时，对于HDD，应将缓冲区设置为1MB，对于SSD，应将缓冲区设置为4kB。 好吧，这取决于。

MMF与FileStream

2011年，MemoryMappedFile有了一个提示，因为此机制自.Net Framework v4.0起已实现。 首先，他们在缓存Bloom过滤器时使用了该过滤器，由于4GB的限制，在32位模式下已经不方便了。 但是当进入64位世界时，我想要更多。 最初的测试令人印象深刻。 免费缓存，速度快，结构读取界面方便。 但是有问题：

• 首先，奇怪的是速度。 如果数据已经被缓存，则一切正常。 但是，如果不是这样，则从文件中读取一个字节会伴随着比常规读取要大得多的数据“提升”。
• 其次，奇怪的是记忆。 加热时，共享内存会增加，工作集会增加-不，这是合乎逻辑的。 但是，随后的进程开始表现得不太好。 他们可以进行掉期交易，或者偶然从OoM跌落。 RAM，无法控制MMF在RAM中占据的体积。 在可读文件比存储器大几个数量级的情况下，从缓存中获得的利润变得毫无意义。

第二个问题仍然可以解决。 如果索引在docker或专用虚拟机上工作，它将消失。 但是速度问题是致命的。

结果，MMF被彻底抛弃了。 开始以明确的形式进行反P窃的缓存，如果可能的话，以给定的优先级和限制将最常用的层存储在内存中。

_{图片来源： Wikipedia}

位/字节

没有字节的世界是一个。 有时您需要下降到位级别。

例如：假设您有数万亿个部分有序的数字，渴望经常保存和阅读。 如何处理所有这些？

• 简单的BinaryWriter.Write？ -快但慢。 大小很重要。 冷读取主要取决于文件的大小。
• VarInt的另一种形式？ -快但慢。 一致性很重要。 卷开始取决于数据，这需要额外的内存来进行定位。
• 打包？ -快但慢。 您必须更加小心地控制手。

没有理想的解决方案，但是在特定情况下，只需将范围从32位压缩到存储尾部所需的范围，就比VarInt多节省了12％（数十GB！）（当然，仅节省了相邻尾部之间的差异），并且是数倍基本选项。

另一个例子。 您在文件中具有指向一些数字数组的链接。 链接64位，每TB文件。 一切似乎还好。 有时阵列中有很多数字，有时很少。 经常一点。 很多时候 然后，只需将整个数组存储在链接本身中即可。 获利 仔细包装，但不要忘记。

结构，不安全，批处理，微选项

以及其他微优化。 我不会在这里写过庸俗的“值得在一个循环中保存数组的长度”或“它更快，for或foreach”。

这里有两个简单的规则，我们将遵循它们：1.“对所有内容进行基准测试”，2.“更多基准”。

• 结构 。 随处使用。 请勿运送GC。 而且，由于今天很流行，我们也有自己的超高速ValueList。

• 不安全的 。 使用时允许mapit（和unmap）结构为字节数组。 因此，我们不需要单独的序列化方法。 的确，有一些问题需要对堆进行固定和碎片整理，但到目前为止尚未显示出来。 好吧，这取决于。

• 批处理 。 处理许多元素应通过包/组/块进行。 读/写文件，在函数之间传输。 一个单独的问题是这些包装的大小。 通常有一个最佳值，它的大小通常在1kB到8MB之间（CPU缓存大小，群集大小，页面大小，其他大小）。 尝试通过IEnumerable <byte>或IEnumerable <byte [1024]>函数进行抽水，并体会其中的不同。

• 汇集 。 每次您写“新”时，小猫都会死在某个地方。 一旦有新的字节[ 85000 ]-拖拉机骑着一吨鹅。 如果无法使用stackalloc，则创建一个包含所有对象的池，然后再次使用它。

• 内联 。 如何创建两个功能而不是一个功能可以使所有功能加速十倍？ 很简单 函数主体（方法）的大小越小，内联的可能性就越大。 不幸的是，在dotnet世界中，仍然没有办法进行部分内联，因此，如果您有一个热功能，在处理前几行后有99％的情况下出来，剩下的一百行去处理其余的1％，然后安全地分成几部分两个（或三个），将沉重的尾巴变成一个单独的功能。

还有什么

• Span <T> ， 内存<T> -很有希望。 该代码将更简单，也许更快一些。 我们正在等待.Net Core v3.0和Std v2.1的发布以切换到它们，因为 .Net Std v2.0上的内核，通常不支持跨度。

• 异步/等待 -迄今为止存在争议。 最简单的随机读取基准测试表明，CPU消耗实际上在下降，但是读取速度也在下降。 必须注意。 我们尚未在索引中使用它。

结论

我希望我的遥远感使您能够从理解某些决定的美中得到乐趣。 我们真的很喜欢我们的索引。 它高效，漂亮的代码，效果很好。 系统核心（工作的关键位置）中的高度专业化的解决方案要比一般解决方案好。 我们的版本控制系统会记住C ++代码中的汇编程序插入。 现在有四个优点-仅纯C＃，仅.Net。 在它上面，我们甚至编写了最复杂的搜索算法，一点也不后悔。 随着.Net Core的出现，向Docker的过渡，通往光明的DevOps未来的道路变得更加容易和清晰。 在不降低解决方案的有效性和美观性的情况下，解决动态分片和复制问题的方法就在前面。

感谢所有读完本书的人。 对于所有差异和其他不一致之处，请写评论。 我会很高兴收到评论中的任何合理建议和反驳。