如何从CouchDB加载随机文档(高效公平)？

Question

我想从存储在CouchDB数据库中的一组文档中加载一个随机文档.拾取和加载文档的方法应符合以下要求:

• 效率:文档的查找应该是高效的,最重要的是加载文档的时间不得与文档总数呈线性增长.这意味着不能使用skip query参数.

• 统一分布:选择应该是真正随机的(尽可能使用标准随机数生成器),每个文档应该有相同的选择机会.

在CouchDB中实现此功能的最佳方法是什么？

Answer 1

在给出了更多的想法之后,我想出了一个解决方案.为了完整起见,我将首先展示两种简单的方法,并解释它们为何存在缺陷.第三个解决方案是我要去的那个.

方法1:跳过

这是一个简单的解决方案:你有一个简单的视图(让我们称之为random),它有一个map函数,它发出你想要选择的所有文档和内置的_countreduce函数.要选择随机文档,请按照下列步骤操作:

• N通过调用以下方式查找视图中的文档总数:
  http://localhost:5984/db/_design/d/_view/random
• 选择随机数 0 <= i < N
• 加载i'文件:
  http://localhost:5984/db/_design/d/_view/random?reduce=false&skip=i&limit=1

这种方法很糟糕,因为它不适合大量文档.根据"CouchDB - 权威指南"的这一部分, skip参数只能用于单位数值.

上面的解决方案必须i在返回所选文件之前循环遍历文档.在SQL术语中,它相当于全表扫描而不是索引查找.

方法2:文档中的随机数

通过这种方法,在创建时为每个文档生成随机数并存储在文档中.示例文档:

{
  _id: "4f12782c39474fd0a498126c0400708c",
  rand: 0.4591819887660398,
  // actual data...
}

该random视图具有以下映射功能:

function(doc) {
  if (doc.rand) {
    emit(doc.rand, doc);
  }
}      

这些是选择随机文档的步骤:

• 选一个随机数 0 <= r < 1
• 加载文档:
  http://localhost:5984/db/_design/d/_view/random?startkey=r&limit=1
• 如果没有返回文档(因为r它大于存储在数据库中的最大随机数),请环绕并加载第一个文档.

这是非常快的,一见钟情看起来很棒.然而,存在一个严重的缺陷:并非所有文件都被选中的机会相同.

在最简单的示例中,数据库中有两个文档.当我选择一个随机文档非常多次时,我希望每个文档都有一半的时间出现.假设文档在创建时被分配了随机数0.2和0.9.因此,选择文档A时(r <= 0.2) or (r > 0.9),选择文档B时0.2 < r <= 0.9.每个文件被挑选的可能性不是50%,而A的30%和B的70%.

当数据库中有更多文档时,您可能会认为情况有所改善,但事实并非如此.文档之间的间隔变得更小,但是区间大小的变化变得更糟:想象三个文档A,B和C,随机数为0.30001057,0.30002057和0.30002058(中间没有其他文档).选择B的几率是选择C的1000倍.在最坏的情况下,两个文档被分配相同的随机数.然后只能找到其中一个(文档ID较低的那个),另一个基本上是不可见的.

方法3:1和2的组合

我提出的解决方案结合了方法2的速度和方法1的公平性.这里是:

与方法2中一样,每个文档在创建时分配一个随机数,相同的映射函数用于视图.与方法1一样,我也有一个_countreduce函数.

这些是加载随机文档的步骤:

• N通过调用以下方式查找视图中的文档总数:
  http://localhost:5984/db/_design/d/_view/random
• 选择随机数 0 <= r < 1
• 计算随机索引:i = floor(r*N)
  我的目标是加载i第一个文档(如方法1).假设随机数的分布或多或少是均匀的,我猜测i'文档的随机值大约为r.
• 查找L随机值低于的文档数r: http://localhost:5984/db/_design/d/_view/random?endkey=r
• 看看我们猜测的距离有多远: s = i - L
• if (s>=0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=s&limit=1&reduce=false
• if (s<0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=-(s+1)&limit=1&descending=true&reduce=false

因此,诀窍是猜测分配给i'th文档的随机数,查看它,看看我们离开了多远,然后跳过我们错过的文档数.

即使对于大型数据库,跳过的文档数量也应保持很小,因为猜测的准确性将随着文档的数量而增加.我的猜测是,s当数据库增长时,它仍保持不变,但我没有尝试过,而且我觉得没有资格在理论上证明它.

如果你有更好的解决方案,我会非常感兴趣!