Skip to content

Latest commit

 

History

History
188 lines (144 loc) · 17.2 KB

chapter6.md

File metadata and controls

188 lines (144 loc) · 17.2 KB

#相关云服务

  1. ##前言 【传统交易系统】需要存储和查询两个或者多个数据集之间的联系，一般我们会用【关系型数据库】的【笛卡尔积】来实现，比如从一个数据出发，查询通过一定的关系能关联到的其他数据集合，关系型数据库虽然进行了各种优化措施，但是当关联的方式和关联的数据种类和数量太多的时候，性能会变得极为低下。而且【SQL语言】表示一些复杂的关联也很吃力。

    本文主要描述被称之为【相关云服务】的检索框架，他可以存储几个海量数据集合之间的关联，并可以根据存储的关系进行高效的增删改查。本系统本质上是一个【搜索引擎索引】的变种，他也可以作为搜索引擎的检索部分来使用。

    本文说明了【相关模型】的结构以及存储方案和检索过程，并最后提出利用开源软件进行二次开发的折中方案。【相关云服务】是【云交易平台】不可缺少的部分。

  2. ##【相关模型】和【相关引擎】 万事万物之间都有关联，本节将建立一个描述各事物之间相互关系的模型，并描述一个系统可以将关联进行管理和查询的系统。

    1. ###相关模型

      • 如图，有三个集合 A B C，可以通过一个方法判断两两之间的某个元素是否相关，那么选取其中的元素 a b c，如果 ab ac bc 都存在相关的可能，那么如果判断出 ab ac bc 都相关，那么我们可以认为 abc 是相关的。如果只有 ab 和 bc 存在相关性的可能，那么可以通过判断 ab 和 bc 是否相关来确定 abc 是否相关。
      • 可以将上面的例子推广：
        1. 集合 F {F(1),F(2),...,F(n)} 为【源集合】, 其中 F() 为【数据集合】, 对于 F ,其中每个 F() 中选取的任意一个对象 组成 f {f(1),f(2),...,f(n)} 【元素集合】, 其中 f() 为【元素】。
        2. f 任选 x 个对象的组合 y(x) {y(x,1),y(x,2),...,y(x,C(x,n))} 为【x元集合】, 其中 y(x,) 命名为【x元子】, 可以预见 y(1)===f .
        3. 在 y(2) 中选择 m 个 y(2,) 组成 d { d(1),d(2),...,d(m) } 为【主可判2元子集合】, d() 为【可判2元子】.
        4. 函数集合 L {L(1,),L(2,),...,L(m,)} 为【二元相关函数集合】, L(,)为【二元相关函数】，对每个 L(i,d(i)) 可得一个 [0,1] 的值，这个值说明 d(i) 包含的两个元素之间在 L 上的【相关量】.
        5. 【主相关二元子集合】 p { p(1),p(2),...,p(w) } 是 d 的子集, 是由 d 中在 L 上的相关量都大于【最小相关量】v 的对象组成.
        6. 对于y(x,)中的x个元素, x 中选2组成 q {q(x,,1),q(x,,2),...,q(x,,c(2,x)} 为【待判x元子集合】, q(x,,)为【待判x元子】, 如果q中的对象在d中出现就必然也在p中出现,则y(x,)为【相关x元子】. y(x) 中所有【相关x元子】的对象组成集合 g(x) { i<=C(x,n)|g(x,1),g(x,2),...,g(x,i) } 为y(x) 的【相关x元子集合】. 并可以预见当x=2的时候, g(2)===p(2).

    2. ###相关引擎【Conan】

      本文设计的【相关引擎】可以快速的根据预设的若干个【数据集】之间的关系查询相关的数据：

      1. 以【相关函数集合】L作为输入。
      2. 可以插入和删除L中描述的【数据集合】，系统会对数据进行存储和索引。
      3. 可以根据某个【数据集】中的【元素】快速查询包含这个元素的【相关x元子集合】。
      4. 可以查询符合某个条件的【相关x元子集合】.
      5. 系统提供同步【相关元子集合】变化的通道. 当然，真实系统会随着n的个数增加而计算量剧烈增长，因此实际应用中会限制n的个数，并将某个F()分片存储。

  3. ##相关性的分层结构 为了能够使Conan存储并索引到A集合中各个子集合之间的关系，并能快速根据条件查询任何一个符合L的子集，我们将【相关模型】分层构建。

    1. ###三个数据集合

      我们先看一个三个集合的例子，A B C 为三个集合中的某个元素，根据两两之间可能存在或者不存在相关性, 分为三种情况:

      1. relation1 情况下，只有AC可以判断相关性, 则 ABC 三者不可能相关, 而 AC 则可能相关。
      2. relation2 情况下, ABC 三者可能相关, AB BC 可能相关, 但 BC 不可能相关.
      3. relation3 情况下, ABC三者可能相关, 同时AB AC BC也可能相关，上图是relation3的分层结构。

      我们详细描述一下第三种情况下的分层情况:

      1. level 1.0 是单独为a b c建立一系列的【关键字索引】, 这一层与普通的搜索引擎类似, 但是将建立多个属性的倒排索引.
      2. level 1.1 将为所有可能的二元关系建立索引,比如 a 将可以通过 b 快速查出.
      3. level 2.0 将为【相关二元子】建立关键词索引.
      4. level 2.1 将为每个【相关二元子】建立到【相关三元子】的索引.
      5. level 3.0 为【相关三元子】建立【关键词索引】.

    2. ###更普遍的,我们给出一般情况下层的情况.

      1. 如果集合个数为 N ,整体则分为 N 大层，从 leve 1 ~ leve N。
      2. 第 n 层处理【相关n元子】的索引情况，如 level 1 处理单个数据集合的情况，而 level 2 处理【相关2元子集合】的情况。
      3. 每个大层分为两个小层 leve n.0 level n.1。
      4. 0小层为【关键词索引层】，关键词索引可以快速的根据某个查询条件查出该层【相关n元子】,同时为构建1小层的提供【预关联】.
      5. 1小层为【推进索引层】，记录该层相关n元子和不在这个组合中的元素的相关性。
      6. 特别的，对于最后一层，只有0小层，没有1小层，最后一层不需要再往下推进了。

  4. ##层的操作

    1. ###第n层必备操作函数

      Conan的每个Level都要支持7个基本的操作,对于Level n:

      1. 支持 Add 操作, 可以添加一个【相关n元子】, 这个操作会在内部调用 K_Forward 操作, 并将结果放入管道流中.
      2. 支持 Del 操作, 可以删除一个【相关n元子】, 这个操作会在内部调用 R_Forward 操作, 并将结果放入管道流中.
      3. 支持 Query 操作, 可以采用关键词条件查询一个【相关n元子集合】.
      4. 支持 Extract 操作, 可以给定一个【元素】, 构造出n层上的某个【相关n元子集合】的关键词查询条件.
      5. 支持 K_Forward 操作, 这个操作实际上是Query和Extract的组合,可以在level n.0中查询与某个【元素】相关的【相关n元子】,并推导出包含该【元素】的【相关n+1元子集合】.这个操作的特点是作为查询条件的【元素】可以并不在系统里面.
      6. 支持 Fetch 操作, 可以给定一个【元素】, 然后查询与这个【元素】相关的【相关n元子】的集合.
      7. 支持 R_Forward操作, 这个操作是 Fetch 操作的再封装, 和 K_Forward 类似, 可以在 level n.1 中导出包含该【元素】的【相关n+1元子集合】, 这个操作的特点是作为查询条件的【元素】必须在系统中, 这个操作相对 K_Forward 更快.

    2. ###Conan的插入操作

      当要向Conan插入一个【元素】a的时候, Conan 会首先将a插入到Channel系统中，Level 1 同步到这个变化后，调用 Add 方法将数据插入 Level 1 层, Add方法会调用K_Forward方法返回对于a来说属于 Level 2 的【相关2元子集合】g(2),并将这个集合插入Channel系统中, 然后 Level 2 层会同步到这个变化, 如此循环直到 Level n 层.

    3. ###Conan的删除操作

      当向Conan删除一个【元素】a的时候, Conan 会首先将a删除这个指令插入到Channel系统中，Level 1 同步到这个变化后，调用 Del 方法将Level 1层的数据删除, Del方法会调用R_Forward方法返回跟 a 相关的 Level 2 的【相关2元子集合】g(2), 并将这个集合的删除指令插入Channel系统中，然后 Level 2 层会同步到这个变化, 如此循环往复直到 Level n 层.

  5. ##存储架构

    1. ###LEVEL内部的分层架构

      【相关引擎】是【倒排索引】在某个应用领域的推广, 是大数据量，高并发，准实时的检索系统, 因此存储和查询的实现方式非常重要, 系统需要满足大量的实时数据修改和查询, 从修改到能查到结果之间的时间尽可能短。 Conan 的存储架构与 LSM Tree 结构相似, 但查找和合并上与 LSM Tree 不太一样.

      上面相关性的LEVEL架构中，每个LEVEL内部会分为若干层（B0,B1,...,Bn), 下面将对每个LEVEL的内部结构进行描述.

      1. 将LEVEL的存储结构分为若干层{B0,B1,...,Bn},其中B0和B1在内存中,其它在磁盘上,除了B0之外,其余的各层都不能实时修改,对数据进行修改的时候,先存放于B0层,在B0层达到一定的大小的时候,B0层自动转为B1层,而B1层将下降到B2层,其余的依次类推.
      2. 索引有一个顺序写的操作Log, 任何对数据的修改将先写入Op Log中, Disk和Mem都有一个指针指向Op Log, 当系统奔溃的时候, Memory部分将从Disk的cur指针处进行恢复, 而Memory的cur指针用来记录最后一次操作的地方.
      3. 数据绝大多数都存储在Disk的各个层里面, 当条件允许的时候, 会选取两个层进行合并, 例如选取 Bn-1和Bn, 在线下进行合并为一个新的Bn-1层, 合并完成之后将替换原来的Bn-1和Bn.
      4. 新的数据, 先会在B0层中生效, 删除的数据会先在B0中进行记录, 随时间的推移, 最新的数据永远在上层.
      5. 对于在Disk上的数据, 会有一个根据热度来失效的Cache进行缓存, 因为除了B0之外,其它的层不允许实时修改, 这样的Cache将非常容易实现.
      6. 查询数据的时候, 从上层往下开始查询, 只要对应的Term没有被删除，就必须一直查到最底层. 多个Bn之间，以及符合查询的时候，就会要将多个查询结果进行归并.
      7. Conan的每一个Level，都有一个独立的这样的分层系统 。Level直接通过数据同步来通知变化。

    2. ###LEVEL之间的同步

      如图，LEVEL 1~3 内部各有一个（B0,B1,...,Bn）系统，LEVEL是靠数据变化驱动的，那么数据变化的信息来源于每一层之上的一个Channel，每个LEVEL都会同步他上层的Channel，其中 Channel 1 需要被其他几层全部都同步。


  6. ##检索结构 之前说过, Conan是倒排索引在某个领域的推广, 跟常规的 LSM Tree 不同的是, 在各层合并的时候, 不但要合并 Dict, 还要合并 DocList , 拿 leveldb 来打比方, 就是不但要合并 key , 还要合并 value , 在本节将对倒排索引关键的几个部分进行描述. 包括在磁盘和内存的差异.

    除了B0和B1两层因为全部在内存中有点特殊之外，Conan 的每一层内部都是非常类似的，为了好理解，我们沿用搜索引擎里面的名词，分为 Dels DocInfoList Dict 和 DocSeqnoList。

    1. ###DocInfoList结构

      • 这个部分用来保存正向索引，保存一个顺序的seqno到DocInfo的映射，因为在反向索引存储的时候，DocId都会被转成顺序的整数seqno，以便于压缩，同时可以将修改后的同一个Doc在索引中存储成另一个seqno。
      • 整个Conan不会重复seqno，因此每个Bn都会有个seqno的起始值SeqnoRoot，从外面引用DocInfo的时候，DocSeqno应该是加上这个root值的。
      • DocInfo包括Rank和Field，Rank由排序因子Factor和DocSeqno决定，这样可以保证唯一的顺序，每个Doc下会有几个Field，Field下有若干个Term，各个Field的索引是独立的。另外还有一个是DocId，是原Doc的真正Id。
      • 这个结构的功能是，将DocInfo映射到不重复的连续的seqno，并且在通过seqno查询DocInfo的时候，可以在O(1)的时间完成。
      • 由于Doc修改或者删除后原seqno不会再次出现，所以在内存中DocInfoList可以和磁盘上的结构类似，采用一个分段的数组存储。

    2. ###Dels结构

      • 因为 Conan 删除对象不是真正物理删除，而是打上标记，那么标记就存在于这个部分。与常规搜索引擎不一样的地方是，Conan除了要删除Doc之外，还会删除Term，因而每个数据集合都有一个独立的Dels数组。
      • Dels只需要存储是否删除状态，因此可以采用一个bitmap来表示，如果数据量大的话可以分段Load到内存里面，并采用一个BloomFilter进行过滤。
      • 每一层的Dels作用范围是本层和本层以下的各层，在Bn和Bn-1合并的过程中需要将Dels中的记录应用于真实数据上。

    3. ###Dict的结构

      • 反向索引的字典部分，这个部分可以提供高速的根据Term查询DocSeqnoList的功能。
      • 内存部分由于会新增Term，因此需要一个可以随机增减并排好序的结构存储DocSeqnoList的指针。skiplist和double array trie都是可选的方案。
      • 磁盘上的Dict本质上是一个根据字典顺序排好的数组，数组中有个指针是指向对应Term的DocSeqnoList。这个Array可以直接和其他的Array做归并。如果需要查询Term的话，最原始的可以采用二分法查找，或者在线下建立各种trie的变种，比如double array trie或者是lucene中的FST算法，可以获得更高的查询效率和较好的压缩比。
      • 每个DocInfoList会有一特殊的Dict，那就是，DocId到seqno的字典，这个字典退化成一个 KV Map。

    4. ###DocSeqnoList的结构

      反向索引的组成部分，是某个Term能索引到的在这个块中的所有Docseqno的集合，一般都是压缩的。一般来说，本层的DocSeqnoList只会指向本层的DocInfoList。 在Conan中,DocList是巨量的,怎么将一大批DocSeqno尽可能的压缩, 而且不会严重的影响查询性能是关键. 为了便于跟其他的DocSeqnoList进行归并，排序时采用一个二元组rank(factor, docseqno)，这样可以确保排序是唯一的.

      • 在内存时, 由于要处理DocId新增的情况并且要兼顾合并, 因此需要类似于像skiplist或者是rbtree的结构来处理。
      • 当存储到磁盘上时, 只在层合并的时候新增或者删除Docseqno, 因此可以按rank采用顺序结构存储, 因为需要对DocSeqno进行压缩，一个DocList可以被分为三个部分:
        1. Raw部分 无法进行压缩的DocSeqno存放在这个部分中. 这个部分是一个排好序的DocSeqno数组.
        2. PForDelta部分 这个部分将对一些紧凑的区间采用PForDelta算法进行压缩.
        3. Range部分 这个部分将对连续的区间值保存起始和结尾的位置.

  7. ##检索结构的合并

    1. ###Bn-1与Bn的合并。

      当触发Bn与Bn-1合并时，大体上会执行下面的操作。

      1. 找出Bn-1的rindex部分以及Del部分映射到的Bn的rindex于Bn的rindex部分的交集。
      2. 将上面算出的交集的rindex的部分，将Bn-1和Bn合并，存放为Bn'，这时应该注意，Bn-1的DocSeqno的Root需要改为Bn的DocSeqno的Root，并且需要将Bn-1的Del部分的Doc和Term都过滤掉。
      3. 将Bn-1的DocInfoList追加到Bn的DocInfoList后面。
      4. 将Bn’的rindex部分覆盖到Bn上。

    2. ###查询结构的合并

      当客户端发起Query或者是Fetch请求的时候，Conan会返回一个迭代器来获取数据，这个迭代器会根据查询条件生成子迭代器来迭代不同Term索引到的DocSeqnoList，然后再iterator中做归并处理。

  8. ##分片与归并 Conan是开放式系统，并且是云交易平台中的一个组件，因此，他自己本身不提供分片功能，他的分片可以由Conan加上Doraemon组件来实现。但是归并则由Conan本身的客户端来实现。

    Conan实现Doraemon的Leaner接口，由Leaner来决定Conan同步那写数据，并且Conan自己也记录这些分片的信息。Client会不断的同步Conan的分片信息，当Client向Conan请求数据的时候，根据已经同步到的信息决定请求哪些Conan服务器，在取到结果的时候，Client会提供一个迭代器对各个服务获取到的数据进行归并。

  9. ##折中方案 Conan说到底本质上还是一个搜索引擎，因此我们可以采用Lucene作为底层来实现Bn系统，上层之需要操作各个Level之间的数据流动就可以。采用Solr作为底层可以很快实现一个已经分片的Conan。只是这些方案都不如直接实现整个系统来得直接和高效，因为直接实现整个系统能够从架构上适应Conan系统的业务目的。