【图文】分布式信息检索_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
分布式信息检索
上传于||文档简介
&&p​p​t
大小：188.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢分布式系统编程，你到哪一级了？ - 文章 - 伯乐在线
& 分布式系统编程，你到哪一级了？
当分布式系统编程成为你生活中的一部分时，你需要经历一段学习曲线。这篇文章描述了一下我当前在这个领域大致属于哪个层次，并希望能为你指出足够多的错误，从别人的错误中学习，从而使你能以最优的路径通向成功。先声明一下，我在1995年时达到第1级，我现在处于第3级。你自己属于哪一级呢？
第0级：完全一无所知
每个程序员都从这一级开始。我不会在此浪费太多口舌，因为这实在没什么太多可说的。相反，我会引用一些我曾经经历过的对话，为从未接触过分布式系统的开发者们提供一些建议。
NN：“在分布式系统中，复制是个很容易的操作，你只需要让所有的结点同时存储你要复制的东东就行了”。
另一段对话（从我记忆深处挖出来的）：
NN: “为了我们的第一人称射击游戏，我们得写一个自己的网络处理引擎。”
我：“为什么？”
NN: “虽然已经有一些优秀的商业引擎了，但获取license的费用非常高昂，我们不想为此买单。”
我：“你之前对于分布式系统有什么经验吗？”
NN：“是的，我之前写过一个套接字服务器。”
我：“你觉得你要花多久能完成这个网络引擎？”
NN：“我想2周吧。保险起见，我计划用4周时间。”
好吧，有时候还是保持沉默比较好。
第1级：RPC
RMI是一种非常强大的用来构建大型系统的技术。事实上，这个技术用Java来描述的话，结合一些工作的例子可以在短短几页纸内描述清楚。RMI技术非常令人振奋，而且它很容易使用。你可以调用你所能绑定到的任何服务器资源，而且你可以构建出分布式的网络对象。过去人们常常为构建复杂的软件系统犯难，现在RMI打开了这道大门。
Peter van der Linden, Just Java(第4版, Sun Microsystems)
我先声明，我并不是说这本书很烂。我清楚的记得这本书读起来很有趣（尤其是章节之间插入的轶闻），我曾经学习Java的时候就是用的这本书（太久以前了，简直不像在一个时空里似的）。一般情况下，我觉得作者说的挺好。他对RMI的态度就是典型的分布式系统设计的第1级水平。处于这个等级的人对统一的对象有共同的看法。事实上，Waldo在他们著名的论文“”（1994）上曾深入描述过，这里我做下总结：
我所倡导的写分布式应用的策略可分为3个阶段。第1阶段，写这个应用时不用担心对象存储的位置，以及它们之间的通讯如何实现。第2阶段，通过具体化对象的位置以及通讯方法来调整程序性能。第3阶段，真枪实弹的测试（网络隔离、机器宕机等各种情况）。这里的思想就是，不管一个调用是本地的还是远程的，对程序的正确性都不会产生任何影响。
同样还是这篇论文，随后进一步挖掘了这个主题并展示了其中的问题。这个观点是错误的，而且已经错了快20年。不管如何，如果说Java RMI达成了一个目标，那就是：就算你从等式中拿掉传输协议、命名、绑定以及序列化，它还是不成立。能记得起的老程序员们同样也会记得它也是不好使的，但他们有一个借口：CORBA还在同各种底层的问题缠斗中。Java RMI将所有这些都抛开了，但使剩下的问题变得更为突出。其中有两点，第一点纯粹就是个麻烦：
网络不是透明的
让我们看看这段简单的Java RMI代码示例（同样取自Just Java一书）
public interface WeatherIntf extends java.rmi.Remote {
public String getWeather() throws java.rmi.RemoteE
public interface WeatherIntf extends java.rmi.Remote {&&&&public String getWeather() throws java.rmi.RemoteException;}
想要使用天气服务的客户端需要这样做：
Remote robj = Naming.lookup(“//localhost/WeatherServer”);
WeatherIntf weatherserver = (WeatherInf)
String forecast = weatherserver.getWeather();
System.out.println(“The weather will be “ + forecast);
}catch(Exception e) {
System.out.println(e.getMessage());
<div class="crayon-num" data-line="crayon-57c0b<div class="crayon-num crayon-striped-num" data-line="crayon-57c0b<div class="crayon-num" data-line="crayon-57c0b<div class="crayon-num crayon-striped-num" data-line="crayon-57c0b<div class="crayon-num" data-line="crayon-57c0b<div class="crayon-num crayon-striped-num" data-line="crayon-57c0b<div class="crayon-num" data-line="crayon-57c0b
try {&&&&Remote robj = Naming.lookup(“//localhost/WeatherServer”);&&&&WeatherIntf weatherserver = (WeatherInf)robj;&&&&String forecast = weatherserver.getWeather();&&&&System.out.println(“The weather will be “ + forecast);}catch(Exception e) {&&&&System.out.println(e.getMessage());
客户端代码需要将RemoteExceptions考虑在内。如果你想看看你究竟会遇到什么样的异常错误，可以看看那20多个的定义。这样你的代码就会变得丑陋，好吧，这个我们就忍了。
局部性错误
RMI的真正问题在于这些调用可能会出现局部性失败的情况。比如，调用可能会在对其他层的请求操作执行前失败，又或者请求成功了，但之后的返回值又不正确。引起这类局部性失败的原因非常多。其实，这些故障模式正是分布式系统特性的明确定义：
“分布式系统就是某一台你根本意识不到其存在的计算机，它的故障会造成你的计算机无法正常使用。”
Leslie Lamport
如果这个方法只是去检索天气预报，出现问题时你可以简单的进行重试，但如果你想递增一个计数器，重试可能会导致产生0到2次的更新，结果就不确定了。这个解决方案应该来自幂等操作，但构建这样的操作并不总是可行的。此外，因为你决定改变方法调用的语义，那你基本上就承认了RMI与本地调用是不同的。而这也就承认了RMI实际上是个悖论。
不论什么情况下，这种范式都是失败的。因为网络的透明度和分布式系统的架构抽象从来就是无法实现的。这也表明了某些软件所采用的方法比其他软件为此所受到的影响更多。Scrum的一些变种方法中倾向于做原型化。原型更集中于“好的方面”（happy path），而好的方面通常都不是问题所在之处。这基本上意味着你将永远停留在第1级的水平。（不好意思，我知道这是个小小的打击）
那些脱离了第一级水平的人懂得对于需要解决的这个问题，我们要有足够的尊重。他们摒弃了网络透明化的思想，从战略性的角度来处理局部性失败的问题。
第2级：分布式算法 + 异步消息传递 + 语言级支持
OK，你已经学习了是什么。你决定吞下这颗子弹，然后对消息传递机制建模，以此显式地控制出现失败的情况。你将应用分为两个层次，底层负责网络和消息传递，而上层处理消息的到达，以及需要处理的各种请求。
这个上层实现了一种，如果你去问设计者这个状态机是用来做什么的，他们可能会这样回答你：这是建立在TCP之上的一个Multi-Paxos算法实现。
明智的开发，这里用到的策略可以归结为：程序员首先在本地主要采用线程来模拟不同的进程来开发这个应用。每个线程运行分布式状态机的一个部分，基本上就是负责运行一段消息处理的循环。一旦这个应用是本地完整的且运行正确，就可以在远端的计算机上用真正的进程来取代线程。到这个阶段，除去网络中可能出现的问题外，这个分布式应用已经可以正常工作了。到容错阶段时，可以通过配置每个分布式实体来正确反映故障的方式来达成，这种方式很直接。（我引述自“”）
因为分布式状态机的存在，局部性故障可以通过设计来解决。对于线程，其实也有很多种选择，但协程（）更适合（在各种不同的编程语言中，协程也被称为纤程fiber，轻量级线程，微线程或者就叫线程），因为协程允许我们对并发行为有更细粒度的控制。
结合“C代码并不会使网络变得更快”的论点，你可以转移到在语言级支持这种细粒度并发控制的编程语言中去。流行的选择如下（排名不分先后）注意，这些编程语言往往都是的：
举个例子，下面让我们看看在Erlang中这种并发控制的代码看起来是怎样的（取自）
-module(tut15)
-export([start/0, ping/2, pong/0]).
ping(0, Pong_PID) -&
Pong_PID ! finished,
io:format(“ping finished~n”, []);
ping(N, Pong_PID)-&
Pong_PID ! {ping, self()},
io:format(“Ping received pong~n”, [])
ping(N – 1, Pong_PID).
finished -&
io:format(“Pong finished~n”, []);
{ping, Ping_PID} -&
io:format(“Pong received ping~n”, []),
Ping_PID ! pong,
start() -&
Pong_PID = spawn(tut15, pong, []),
spawn(tut15, ping, [3, Pong_PID]).
123456789101112131415161718192021222324252627
-module(tut15)-export([start/0, ping/2, pong/0]).ping(0, Pong_PID) ->&&&&Pong_PID ! finished,&&&&io:format(“ping finished~n”, []);&ping(N, Pong_PID)->&&&&Pong_PID ! {ping, self()},&&&&receive&&&&&&&&pong -> &&&&io:format(“Ping received pong~n”, [])&&&&end,&&&&ping(N – 1, Pong_PID).&pong() ->&&&&receive finished -> &&&&io:format(“Pong finished~n”, []); {ping, Ping_PID} -> &&&&io:format(“Pong received ping~n”, []), &&&&Ping_PID ! pong, &&&&pong()&&&&end.&start() ->&&&&Pong_PID = spawn(tut15, pong, []),&&&&spawn(tut15, ping, [3, Pong_PID]).
这看起来绝对是对旧有的RPC机制的一个重大提升。现在你可以推想一下，如果有消息没有到达时会发生什么事情了。Erlang还有附加的超时消息以及一个语言内建的“超时”组件，可以使你以一种优雅的方式来处理超时。
现在，你选择了你要采用的策略，选择了恰当的分布式算法以及合适的编程语言，然后就可以开干了。你很自信能驾驭分布式编程这头野兽了，因为你再也不是第一级的水平了。
哎呀，可惜的是这一路上并非风平浪静。过了一段时间，当第一个版本发布后，你将陷入泥潭之中。人们会告诉你，你的分布式应用有些问题。问题报告中的主题全都是和变化有关的。开始时会出现“有时”或者“一次”这样的表示频率的词，之后的描述变成了：系统处于不期望的状态，卡住不动了。如果够幸运，你有足够的log信息，可以开始着手检查这些日志。稍后，你发现是一系列不幸的事件序列造成了报告中所描述的情况。确实，这是个新的问题。你从来没有考虑过这些，而且在你做大量的测试和模拟时问题从未出现过。所以，你修改代码以将这种情况也纳入考虑范围。
因为你试着要超前考虑，你决定构建一个“”组件，它以伪随机的方式让你的分布式系统做些愚蠢的事情。“猴子”在笼子里使劲扑腾着，很快你会发现在很多场景下都会导致出现不期望的情况，比如系统卡住了，或者甚至更糟糕的情况：系统出现不一致的状态，而这在分布式系统中是永远也不应该发生的事情。
构建一个“猴子”是很棒的主意，而且它确实能减少遇到那些你从未在这个领域内碰到过的怪事的几率。因为你相信，修改一个bug必须和发现这个bug的测试用例联系起来，现在需要回归测试这个用例，以证明bug的消除。你现在只需要再构建一次这个测试用例就可以了。可是现在的问题在于，如果说并非不可能的话，要重现这个错误的场景起码是很困难的。你向上帝祈祷，得到的启示是：当心存疑虑时，就使用暴力法吧。因此，你构建一个测试用例，然后让它跑上无数次，以此来弥补这极小的失败概率。这会使你解决bug的过程变得缓慢，而且你的测试套件会变得笨重。通过对你的测试集做分而治之的处理，你不得不再次做一些补偿。无论如何，经过在时间和精力上的大量投入之后，你终于设法得到了一个较为稳定的系统。
你在第2级已经到顶了，如果没有新的启示，你将永远卡在这一级。
第3级：分布式算法 + 异步消息传递 +
我们需要花点时间才能意识到：长时间运行“猴子”以此发现系统中的缺陷然后再结合暴力法来重现它们，这种做法并不可取。使用暴力法重现只会显示出你的无知。你需要的关键性的启示之一是，如果你可以只将等式中的不确定性拿掉的话，你就可以完美的对每一种场景做重现了。第2级分布式编程的一个重大的缺点是：你的并发模型往往会成为你代码库中的病毒。你希望有细粒度的并发控制，好吧，你得到了，代码里到处都是。因此是并发导致了不确定性，而不确定性造成了麻烦。因此必须得把并发给踢出去。可是你又不能抛弃并发，你需要它。那么，你一定要禁止把并发和你的分布式状态机结合在一起。换句话说，你的分布式状态机必须成为纯函数式的。没有IO操作，没有并发，什么都没有。你的状态机特征看起来应该是这样的：
module type SM = sig
type state
type action
val step: msg -& state -& action * state
<div class="crayon-num" data-line="crayon-57c0b<div class="crayon-num crayon-striped-num" data-line="crayon-57c0b<div class="crayon-num" data-line="crayon-57c0b<div class="crayon-num crayon-striped-num" data-line="crayon-57c0b<div class="crayon-num" data-line="crayon-57c0b<div class="crayon-num crayon-striped-num" data-line="crayon-57c0b
module type SM = sig type state type action type msg val step: msg -> state -> action * stateend
你传入一个消息和一个状态，你得到一个操作和一个结果状态。操作基本上就是任何试着改变外部世界的东西，需要一定的时间来完成，尝试的过程中可能会失败。典型的操作有：
发送一个消息
安排一次超时
将数据存储在持久性的存储介质内
这里要意识到的重要部分是：你只能通过一个新的消息来得到新的状态，再无其他。在这种严格的规定下所得到的好处是很多的。完美的控制，完美的重现能力以及完美的可追踪性。为此而得到的开销也同样存在，你将被迫使所有的操作都变得。而这些基本上就是为了减少程序复杂性而附加的一层间接。你还需要将每一个你关心的外部世界变化都建模为一个消息。
相比第2级的分布式编程，另一个改变在于控制流。在第2级中，客户端会尝试强制更新并动态设置状态。而在这里，分布式状态机假定有完全的控制力，并且只有当它准备就绪，可以做些有用的事情时才会考虑客户端的请求。因此这些必须分离开来。
如果你把这些道理解释给一个2级的分布式系统架构师听，他可能或多或少的会把这个当成一种替代方案。然而，你需要经历足够多的痛苦之后才会意识到这是唯一可行的选择，我们姑且把这些痛苦称为经验吧。
对分布式系统领域的深刻理解：快乐，好心态，好好睡一觉
老实说，我现在只是第3级水平，我也不知道在这一级里有什么新鲜玩意。我深信，函数式编程和异步消息传递是分布式系统谜题的一部分，但这些还不够。
请允许我重申我所反对的东西。首先，我希望我的分布式算法实现能够涵盖到所有的可能情况。这对我而言是个大问题，我已经在系统部署的问题上牺牲掉了很多睡眠时间。大部分问题都是类的（Problem Exists Between Keyboard And Chair意指用户引起的错误），但有一些确是真正的问题，这给我造成了一些挫败感。知道自己实现的健壮性程度是很好的。我应该试试证明一下那些定理吗？我应该做更详尽的测试吗？我不知道。
附带提一下，github上有一个称为的仅用于插入操作的B-树库，我们知道可以通过详尽的生成插入/删除排列并断言它们的正确性之后，我们就可以涵盖到所有的情况。但这里，并没有那么简单，而且我对于要对整个代码库做Coqify处理（是一个正式的证明管理系统，它在一种半交互式的环境下提供了一个正式的语言用来编写数学定义、可执行的算法和定理，用计算机来做检查证明，这里作者生造出了Coqify这个词）还有些犹豫。
第二，为了保持清晰和简单，我决定不去碰其它一些正交性的需求。比如，、认证、授权、私密性以及性能。
说到性能，我们也许是幸运的，至少异步消息传递似乎与性能方面并不产生矛盾。安全性则完全是一个XX（作者真的爆粗口了…），因为它几乎切断了所有你所做的事情。有些人把安全性看成是一种调味酱汁，你只要把它倒在你的应用程序上就可以保证安全了。哎，在这方面我从未取得过成功，而且现在我也认为这个问题需要在设计的最初阶段从宏观的角度策略性的去分析解决。
开发出健壮的分布式系统是个颇为棘手的问题，实际上根本没有完美的解决方案，或者说至少没有让我觉得完全满意的解决方案。我敢肯定分布式系统的重要性将随着处理器和其它一切事物之间的延迟增加而显著提高。这一结果使得这种类型的应用程序开发变得愈发繁荣。
至于分布式编程的第4级，也许我该去问问。这么些年来，我阅读了很多他写的论文，这些论文对于我自己的一些错误认识给了很多启示。关于这些启示的缺点嘛，你常常在大部分时间里看到别人在重复自己的错误，但我无法说服他们应该换种方式去做。
也许，这是因为我无法提供他们想要的那种灵丹妙药。他们就想要RPC，而且他们希望这样能搞定问题。这是固执的…就像宗教信仰一样。
关于作者：
可能感兴趣的话题
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2016 伯乐在线分布式信息检索中的重要问题探讨
：分布式信息检索依据查询相关性，选择文档数据库，在其中进行查询，最后将查询后的结果加以合并，反馈给用户。分布式信息检索可对多个文档数据库进行查询，一定程度上提高了检索效率，有关分布式信息检索的研究也因此成为业内人士关注的热点。&
1 文档数据库的描述&
对多个文档进行分布式信息检索时，首先应确定搜索的起始点，因此，对不同文档数据库进行描述显得尤为必要。为使不同数据库中的词频差异充分显现，尽可能的体现出的特征，提高数据库选择的效率，实际工作中，文档数据库描述是自动生成的。但不同文档数据库描述是否能够共享取决于其所处的环境。即，在非协同环境中，文档数据库并直接共享各自的描述，因此，检索时需借助查询抽样技术，下载不同数据库的相关文本，作为各自的描述。在协同环境中不同文档数据库可用的知识较多，并能计算出不同数据库与查询匹配的评分。&
1.1 协同环境中的数据库描述&
协同环境下，文档数据库可将与被索引文档相关的大量信息提供给检索代理。不过这一过程的实现需要STARTS协议支持。在该协议下，检索代理中存储了大量数据库结果合并以及选择的重要信息，包括抽样结果、停用词表、文档评分范围等内容。在STARTS协议中定义的查询语言有排序表达式、过滤器表达式两部分构成。其中排序表达式对文档不同域排序的重要性差异进行相关说明，而过滤器表达式主要为提高检索精度，将搜索范围文档进一步缩小，并可供用户对查询匹配的域进行指定。另外，当数据库内容相差较大时，为进一步提高分布式信息检索质量与效率，可能还需借助其他元信息。&
1.2 非协同环境中的数据库描述&
现实中分布式检索环境多处于非协同环境中，例如，为达到吸引用户的目的，部分数据库可能提供不真实信息。部分数据库为提高安全性，并不提供描述信息。另外，不同数据库描述较为相近时也需要进行认真的探讨，如，有时尽管检索系统建立的索引完全相同，但参数设置哪怕有丝毫的差别，也会导致检索结果出现较大区别，因此，实际检索操作时依赖数据库搜索引擎中的选择算法并不理想。因此，较为理想的算法不能太复杂，而且不同数据库之间的通信能力应不做要求。同时，具有较好的兼容性，尤其不对硬件要求过高。另外，不要求数据库搜索引擎具体采用何种索引方法。&
根据抽样理论，随机抽样精度一定程度上决定着总体特征，而且语料中单词的出现偏斜分布。由此可知，抽样时即便未获得大量单词，但抽样技术仍能对数据库加以精准的描述。经过多年的研究，人们提出了基于查询的抽样算法，该算法并不难理解，但是包括较多参数，进一步提高了数据库描述准确程度。&
2 文档数据库的选择&
文档数据库选择是分布式信息检索面临的又一重要问题，面对海量的数据库，查询过程中如何进行合理的取舍需要依据专门的算法。接下来以判别模型的选择算法为例，对文档数据库的选择进行探讨。&
判别模型选择算法，首先给每个数据库构建罗杰斯特回归模型，令相关向量={v1，v2，...，vn}，其中当vi=0时表示数据库和用户查询不相关，而当vi=1表示相关。由已知的特征向量，可利用公式1计算出数据库i的相关概率：&
（1）&
公式中的为特征权重向量。利用公式2对各个数据库向量相关概率进行定义：&
（2）&
其中z是归一化因子。&
但构建的模型并未将数据库之间的关系信息考虑在内，因此，需对模型进一步完善，将数据库之间的相似度考虑在内，完善后的模型为：&
（3）&
完成算法构思建模工作后，再对算法进行形式化、求解等方面的处理，便可实现分布式信息检索中的文档数据库选择。&
3 查询结果的合并&
当用户将查询送往数据库中，数据库会根据查询条件返回一个文档列表，期间需对文档列表进行合并处理。对查询结果的合并处理应需依赖一定的算法实现，如CORI合并算法、SSL算法以及SAFE算法，其中SAFE算法重点考虑了搜索代理与不同数据库之间的通信，一定程度上脱离了重合文档数量的限制，较SSL算法相对完善。&
SAFE合并算法的实现涉及三个过程：结合用户查询，抽样数据库排序各个文档；在每个数据库中结合抽样文档在原数据库的局部得分，以及抽样数据库的全局的得分进行回归模型的训练，并利用模型计算各返回文档的全局分数；合并排序返回文档的全局得分。尽管这三个过程和SSL算法较为相近，但其训练模型重合文档数量很少，为解决这一问题，SAFE算法给出了两个假设：&
（1）对一个原数据库而言，当返回的文档无法和抽样数据库重合，SAFE模型认为返回的文档均排在抽样文档之前。&
（2）SAFE模型基于抽样算法的随机性，抽样文档排名均匀分布在原有数据库中。&
其中假设（1）的意思为：在数据库返回文档列表中无法找到抽样文档，返回文档应在第一篇抽样文档的前面。假设（2）的意思为：原数据库返回列表未找到抽样文档，可使用公式4估算抽样文档在原数据库中的排名位置。&
P=r*Ratio&
Ratio=|ck|/|θk| （4）&
其中ck可借助一些方法估算得出，而θk的一般取值为300。从而利用SAFE算法便可获得各个文档在原数据库中的具体位置。经过一系列的试验表明在多个数据集上SAFE算法较SSL算法具有明显优势。&
4 总结&
随着信息技术的发展，分布式信息检索应用越来越广泛，因此，为提高分布式信息检索效率与质量应采取有效策略，解决数据库描述、选择以及插查询结果合并的相关问题，不断优化相关算法，使其更好的为人们的信息检索提供优质服务。&
参考文献&
[1]张刚，谭建龙.分布式信息检索中文档集合划分问题的评价[J].软件学报，6-143.&
[2]谭鑫鑫.分布式图书馆信息检索与引导服务系统[D].湖南大学，2012.&
[3]赵联冠.分布式信息检索引擎的分析与实现[D].华东师范大学，2010.&
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。
