[Search Engine] Document vs Term index

系统设计
1
  1. 请问Document index 的结构是类似这样吗？（To make sure I understand it correctly）
    Machine1 (doc id 1-10):
    term1 : <doc1, 2>, <doc3. 6>
    term2 : <doc1, 4> ,<doc5,8>

Machine2 (doc id 11-20):
term1 : <doc11, 2>, <doc13. 6>
term2 : <doc11, 4> ,<doc15,8>

2.为什么说Document partition可以存在内存中而term partition不可以？
posting list的size说一定的，两种partition的方式只是分区方法不同，数据总量应该是都一样的。如果一个能放到内存里，那另一个应该也可以啊？为什么说docment的可以而term的不可以呢？

  1. 如果使用Document partition的方式，那每次search都要query所有的机器，这样每个机器的Network不就成为bottleneck了么？假设有10个request，10台机器， 用这种方式，每个机器都要处理10个RPC，如果request继续增加，最后就会出现RPC排队的问题。term partition如果分区够好的话应该是平均的，每个机器只有一个RPC，这样scale起来更make sense？
2
  1. 是的
  2. 因为有的特定 term posting list 过长，超过内存可以存储的范围。
  3. Document partition 是有这个缺点，每台机器可以分别加 replica 来提供服务，也是可以实现的，在实践中也是有的。Term Partition Scale 起来每个单词一个 request，更省RPC call.
3

  1. 根据最开始的假设，500M个网站，每个100个网页。假设有一个term非常popular，10%的网页都有，这样是500M * 100 *10% = 5B。每个posting的格式的<docid, position> pair，算每一个10byte，这样算下来需要50G的内存。这样算下来也不是非常夸张。而且对于这些非常popular的词，可以进行2次分片，如果每个机器的内存是16G，只需要分到4个机器上就可以了

  2. 我觉得network的问题还挺严重的。假设所有的posting需要100台机器来存。每台机器能处理100的RPS，现在有10000个request。
    这样基于term的分片机制，如果分片的逻辑没问题，没有hotspot的话，可以认为1w个request被平均分给了100个机器，每个机器100RPS，满足要求
    但是基于document来分，每个机器还是需要处理1w个request，如果要满足要求，就要把所有的机器replicate100遍，就是需要1w台机器。这样成本太高了吧
    而且network不同于内存和硬盘，后者买了后面可以用很久，边际成本很低。但是network用了就有成本，这样并不sustainable啊

4
  1. 你举的这个例子就是单一 term 需要多台机器的。Term based partition 的含义就是每个 term 分配到单一的机器上。你所做的这个分配到4台机器，其实是在 term based partition 基础上再做 document based partition. 是可以考虑的，但是比较系统复杂度会比较高。另外 50G 还是算得比较保守的，热门 term 可以在一个文档里出现多次，10byte 不一定够。
  2. 你的考虑都是有道理，这就是 tradeoff，讨论额外的 concurrency 的好处是不是足够大。你可以读一下 Introduction to Information Retrieval 这一小节