一种P2P环境下分布式文件存储系统的缓存策略

一 种 P2P环境下分布式文件存储系统的缓存策略 高 伟 韩 华 代亚非 (北京大学计算机科学与技术系，北京 100871) E—mail：gaowei@net．CS．pku．edu．cn 摘 要 在分布式文件存储系统中，缓存技术被广泛用于提高系统性能。针对 P2P环境下分布式文件存储系统的特 点，提出了一种兼顾用户访问效率和复本一致性的灵活的缓存策略，不同于目前已经存在的P2P存储系统 ，论 文使 用“阀 值”来将文件区分为热点文件和非热点文件，并且只针对热点文件来做缓存，根据缓存空间的使用效率和不同的文件类 型来设置不同的阎值使得缓存策略灵活而有效，论文对该策略进行了理论上的分析，然后通过 Trace-Driven模拟的方法 验证 了该策略的可行性 。 关键词 缓存 P2P 分布式文件存储 系统 文章编号 1002—8331一(2004)30—0o45—04 阀值 日志记录驱动模拟 文献标识码 A 中图分类号 TP393 A Caching Strategy for P2P Distributed File Storage System Gao W ei Han Hua Dai Yafei (Dept．of Computer Science and Technology，Peking University，Beijing 10087 1) Abstract： Caching technology is used widely in distributed file storage system to improve the system performance ．We present a flexible caching strategy according the characteristics of P2P distributed file storage system ．Our strategy not only chases better access perform ance，but also keeps higher consistency between all the replicas of a file than other strategies existing．We use ”threshold value”to distinguish files into hot files and non hot files according to their ac． cessed times and only the hot files will be cached．Through assigning different threshold values to different files accord． ing to the usage efficiency and the file type，our caching strategy perform s better than others．This paper analyzes the caching strategy in theory and then proves its feasibility using Trace-Driven simulation． Keywords：cache，Peer-to—Peer，distribute file system，threshold value，trace—driven simulation 1 引言 广域网中的分布式文件存储系统能够更好地为用户提供 文件存储服务，使用户可以随时随地访问存放在网上的数据， 并且能够为文件共享，多用户之间的协作提供支持。而Peer to Peer构架自身所固有的非集中控制性和可扩展性非常符合 分布式系统的内在要求。Peer to Peer系统在近几年以来已经 成为一个研究热点，研究领域涵盖了P2P路由算法和各种 P2P 的应用系统。Plaxton[”，Tapestryr~l，Pastry ，Chord[4~和 CAN[~对 F2P 路由算法进行了研究 ，并提出了各自的P2P体系结构，这为以 后的 P2P应用打下 了基础。P2P应用包括很多领域 ，基于 P2P 来构建分布式存储系统就是其中的一个，目前已经存在许多面 向广域网基于 P2P技术构建的分布式存储系统，如：Pasttg~，O— ceanStord 01，Pangaea[“1等。 缓存机制利用局部性原理来提高系统的性能i7]。在分布式 系统中，缓存机制得到了广泛地运用，对传统的分布式文件系 统中缓存的研究It2,1 懈决了一些在当时环境下的缓存的一些基 本问如：写策略，一致性维护等。随后出现的Cooperative Cachet14,15]对以后的缓存研究影响深刻，其基本思想是利用网络 上其它机器缓存中的数据来提高本地机器性能。随着因特网的 发展，网络上的信息资源越来越多，访问量也越来越大，于是 Web Cache[” 91被提出来提高网络访问速度，均衡 Web服务器 负载。 基于P2P构建的分布式文件存储系统一般都是面向广域 网提供大规模网络存储服务，利用其分布在广域网上的大量的 服务器为用户提供安全的、可靠的和高效的存储访问服务。对 于每一个特定的用户来说 ，其到系统中所有服务器的网络距离 是不一样的，将远端节点服务器上的文件缓存到离客户较近的 服务器上能够节省大量的网络带宽开销和缩短用户访问延迟。 正因为这样，几乎在所有的分布式文件存储系统中都使用缓存 来提高系统性能、减少用户访问延迟、降低网络开销和平衡服 务器访问负载。 由于 P2P环境下分布式文件存储系统是在 P2P构架之上 构建的，资源定位是通过P2P路由来进行，与传统分布式文件 存储系统通过查找集中索引服务器的方式有很大不同，因此它 的缓存策略与传统的分布式文件存储系统的缓存策略也有很 大区别。OceanStore和 Pangaea这两个系统都采用了任何针对 文件的访问均引起该文件缓存复本创建的策略 (Create a replica of file whenever and wherever it is accessed)[HI，这种 策略会在系统中最大限度地复制被访问文件，从而能够有效地 发挥缓存的作用。然而可以注意到该策略不够灵活，当服务器 基金项目：国家 863高科技研究发展计划资助项目(编号：2001AA111013) 作者简介：高伟，男，硕士研究生，主要研究方向为分布式文件系统。韩华，男，博士后，讲师，主要研究方向为网络与分布式文件系统。代亚非，女， 教授，博士生导师，主要研究方向为分布式系统，分布式协同工作。 计算机工程与应用 20o4．30 45 维普资讯 http://www.cqvip.com 缓存空间不是十分充足时缓存命中率下降很快，并且对复本之 间一致性的问题处理不够好【ll一。为了解决以上所述的两个问 题，论文针对这种情况提出了一个灵活的缓存策略，使用阀值 (threshold value)并根据文件的被访问频率来将系统中的文件 分为热点文件和非热点文件，并且只对热点文件作缓存，这样 可以过滤掉大量的非热点文件，使人们在做缓存的时候能够做 到有的放矢。通过为不同类型的文件设置不 同大小的阀值使得 缓存策略更加灵活，相对而言能够更好地解决复本的一致性的 问题。 2 P2P分布式文件存储系统 2．1 P2P分布式文件存储系统的构架 P2P环境下的分布式文件存储系统包含大量分布在广域 网上的节点服务器，这些节点服务器通过 P2P路由机制 自组 织成一个虚拟的 P2P网络 ，在这个 P2P网络中，所有的服务器 具有相同的能力和责任，任意两台服务器之间能够相互通信， 并且所有的通信都是对称的，系统通过这些服务器为用户提供 存储访问服务。如图 1所示。 ● 一 ● _ 路由表 在图 l中，下面的一层是节点服务器所构成的实际物理网 络拓扑图 ，上面一层是通过 P2P路由机制将这些节点 服务器 映射成的虚拟的 P2P网络，在这个 P2P网络中可以看到，每一 个节点服务器都由一个系统唯一的标识符 nid来标识，并保留 一 个路由表，用来保存自己邻居节点的信息，通过这种方式，一 个节点可以方便地将信息路由到系统中任意一个节点上。系统 中的每一个对象(如文件 ，目录等 )也都由一个 系统唯一的标识 符oid来标识，并且都对应一个节点服务器作为其根节点，其 定位信息存放在这个根节点上，可以通过这种对应关系根据 oid来定位该对象。 P2P系统没有任何的中央控制机制 ，因此 P2P系统消除了 传统分布式系统存在的中心服务器的瓶颈效应，具有很好的可 扩展性 、自组织性和容错性 。 2．2 P2P系统中的对象定位 正如前面提到的，P2P系统的对象是通过 P2P路由来定位 的。不同的 P2P系统所采用的 P2P路 由机制不尽相同 ，如 Past 系统采用 Pastry路由机制，OceanStore采用 Tapestry路由机制， 虽然这些路由机制有所不同，但基本的思想是一致 的：根据 oid 与 hid的对应关系获得 hid，然后通过 P2P路由从节点标识为 hid的节点服务器获得该对象的定位信息，进而访问该对象。图 2描述了在系统中定位oid=3A293E51o6B48F6对象的过程： Client向系统发送对象定位请求 (其中对象的 oid= 3A293E5106B48F6)，距离 Client最近的服务器节点 D296(nid= 46 2Oo4．30 计算机工程与应用 D296)接受定位请求并利用oid到 nid的映射关系得到该对象 对应的根节点服务器的nid=48F6(通过 oid的最后 4位十六进 制得到)，于是节点 D296从 自己路由表里选取一个第一位(从 左向右数)匹配与目标 nid第一位相匹配(等于4)的一个节点 (假定选 nid=4257的节点 )，然后将定位请求转发给选定的节 点 ，如果在节点 4257上没有对象的定位信息 ，则接下来由节点 4257匹配目标 nid的第二位(8)，并转发定位请求，假定选取 48A0，然后节点 48A0来匹配，在通常情况下，如果在所有中间 节点不能获得定位信息，则按照这种方法最终能够到达对象 3A293E5106B48F6所对应的根节点 48F6，从而获得该对象的 定位信息。 J ， 一 一 _ _～ ～ 、 ， ， ， 一 ⋯ _ ’ _ 一 ／，， c=I 一 一一目 、、． ／ 一 ， ～ ． ． ． ． ． ． 、 ⋯ 、 ， ， 6ED3 。 一 P一 。 ． 一 一 _ 一 _^ _ - L 、 j 、 - ‘⋯ 、 、 、 · Fc=2 320 ， ， ， ／⋯／ J 一 2．3 P2P分布式文件存储系统的特点 与传统的分布式文件存储系统相比，基于 P2P的分布式文 件存储系统最大的优势在于更好的可扩展性，更适用于面向广 域网提供大规模的存储服务。由于在 P2P分布式文件存储系统 中资源的访问是以文件 为单位的 ，当用户想要访问一个文件的 时候，需要根据文件名所对应的oid通过路由来定位该文件， 在路由过程中最多需要经过rlo ]个节点的转发，其中，M为 表示nid所用的进制数 (通常为 16)，，v为服务器节点的数目， 因此从系统任意一个节点通常只需要经过少量几个 中间节点 就可以到达目的节点。然而由于对任意文件 的访问都需要路由 定位，所以当系统需要处理大量访问请求时，路由消息量是相 当大的。另一方面，基于P2P的分布式文件存储系统的一个文 件访问操作往往就要涉及若干个服务器(包括用户登陆的服务 器．文件所对应的根节点服务器，文件所在的服务器，以及若干 路由可能要经过的中间服务器)，由于网络以及服务器自身的 稳定性问题，为了能够提供稳定的服务，系统就必须增加复杂 的错误恢复机制，这也是 P2P分布式系统实用所面临的一个不 小的问题。因此如果制定的缓存策略能够简化这一访问过程将 能进一步提高 P2P系统的实用性 。 3 缓存策略描述 3．1 文件访问方式 前面提到，通过 P2P路由来定位进 而访问文件的方式具有 很多优点，但也会在一定程度上增大系统的通讯负担以及增加 了用户的访问延迟，因此，为了改进以上缺点，作者使用一种混 合文件访问方式：直接定位和 P2P路由定位相结合的方式。当 用户访问自己的私有文件时可以通过直接定位的方式来进行， 如果直接定位失败或者访问具有多个复本的共享文件时通过 P2P定位来进行。 维普资讯 http://www.cqvip.com 3．2 使用阀值选择缓存对象 由于 P2P分布式文件存储系统面向广域网提供存储服 务，目前所有的分布式文件存储系统都用缓存技术来减'3-'NP 访问延迟，节省网络带宽，提高系统性能。不同系统所采用的缓 存策略虽有所不同，但在缓存对象的选取上基本上是一致的， 在这些缓存策略中⋯一，当用户访问一个文件时，如果该文件不 在离用户最近的服务器上，那么不管该文件最近是否被访问过 都将该文件缓存到最近的服务器上。在实际的应用中，这种缓 存策略不能针对不同的实际情况来作实际调整，显得不够灵 活。为了能够灵活地处理各种情况，作者使用阀值来选择缓存 对象 。 如果一个分布式文件系统中文件和用户的数量足够大，在 短时间内将会有大量的文件被访问，而对于单独的文件来说 ， 被访问的频率是不一样的，这里使用“阀值”的概念来根据文件 的被访问频率区分哪些文件为热点文件，哪些为非热点文件， 当一个文件的被访问频率超过设定的阀值时，则把这个文件称 之为热点文件，反之，则称这个文件为非热点文件。针对热点文 件作缓存，能够有效地利用服务器的缓存空间，避免在缓存空 间不足的情况下发生的“颠簸”情况(即：由于文件复本在缓存 空间频繁地调入调出而导致缓存的命中率下降)。 3．3 设置阀值的大小 由于要使用阀值来选择缓存对象，所以在实际系统中如何 设置阀值的大小是相当重要的。为了充分发挥缓存的作用，阀 值的大小不能是固定不变的，作者认为阀值的大小应该与以下 两个因素相关：缓存空间的大小，文件类型。 (1)缓存空间大小 为了能进一步提高服务器缓存的访问命中率，阀值大小的 设置与缓存空间的大小密切相关，当缓存空间较大，能够容纳 较多的文件复本的时候，可以适当减小所有文件的阀值，从而 更好地利用缓存空间来提高系统访问性能；当缓存空间较小而 造成过于频繁的文件复本的调入调出时，应该适当增大文件的 阀值，使得缓存策略更关注那些较热的文件，从而取得相对较 好的缓存命中率。 (2)文件类型 阀值的设置除了能够用来进一步提高缓存命中率，还能够 控制缓存复本之间的一致性。文件的更新频率与文件类型是密 切相关的。有些类型的文件由于很少更新 ，所 以对访问效率要 求较高而对一致性的要求较低，例如视频和音频文件，而有些 类型的文件却对一致性要求很高，例如doc文件，用户总是希 望得到 自己最新的文档而不是旧的数据。作者为更新较少的文 件类型设置一个较小的阀值，这样文件将更容易被缓存，从而 有更好的访问性能。相反 ，作者为更新较多的文件类型设置一 个较大的阀值，那么该类型的文件就会比较难于被缓存，在系 统 中的复本数量就会较少，从而减少复本不一致的发生。 事实上，如果设定某个文件的阀值为 1，则每一个从其他 服务器节点上转发过来的针对该文件的访问请求都将导致一 个缓存复本的产生，这种情况就是 Pangaea系统采用的缓存策 略一致；如果设定某个文件的阀值为+ ，则该文件在系统中永 远都不会被缓存，因此能够非常灵活地根据实际需要调整缓存 策略。 3．4 缓存复本的一致性的维护与缓存置换策略 在分布式存储系统中使用缓存策略将能提高系统整体性 能，但也带来了多个复本之间的一致性维护问题，在P2P环境 下，维护大量文件的复本一致性是一件十分困难的事，因此大 多P2P分布式文件存储系统都采用了乐观的一致性维护方法， 即：当文件被更新或删除时，将更新或者删除各个缓存复本，但 如果由于服务器或网络故障而造成复本没有被正确更新或删 除，系统并不作更深入的处理，因为这种处理非常复杂而且需 要耗费大量的系统资源和网络带宽。由于在论文提出的缓存策 略中使用阀值来减少更新频率大的文件复本的数量，所以在采 用相同的维护一致性方法的情况下，能够更有效地降低不一致 性的发生。 缓存置换策略不是论述的重点，由于GreedyDual—SizetSl置 换方法相对于其他的置换方法如：LRU，LFU，Size，Hybrid等方 法在 hit ratio，byte hit ratio，network costs等方面具有更多的 优势嘲，所以该置换方法在 P2P分布式文件存储系统中使用的 更为广泛。 4 性能评测 为了能够验证缓存策略的实际性能，作者建立了一个 P2P 分布式文件系统的原型系统，但获得具有试验价值的针对 P2P 分布式文件系统的大规模访问数据是非常困难的12”，不过 ，由 于在数据访 问局部性特性方面 Web Cache与分布式文件系统 比较相似⋯】，因此这里选取 了一组 Web Cache的访问 日志作为 工作负载，并使用Trace—Driven的方法来对缓存策略进行验 证 。 所选取的 Web Cache访 问 日志【’q为 NLANR(美 国应用网 络研究国家实验室)2003年 12月 9日一天共 24小时的 1O个 代理服务器上的日志记录，为了得到更大规模的访问数据，作 者把这 1O个 日志中的有效访 问纪录按照时间顺序合并为一个 较大的 日志文件来作为工作负载。在这个访问 日志中共包含 5，324，738条访 问记 录，1213个独立用户 IP地址 ，2，370，297 个互不重复的URL，17，150，160，428字节的文件。其中， 文件大小最小的文件 0字节，最大的76，241，528字节，平均大 小 9，135字节 。 在实验中，作者模拟了分布在广域网上的 1024台服务器， 所有这些服务器按照 P2P路由机制组成一个 P2P网络，作者 使用散列的方法把从日志中提取到的独立的用户均匀分布到 这些服务器上去，并假设用户在物理上距离自己所分配到的服 务器最近 ，然后用 同样的方法把从 日志中提取到的 URL所对 应的文件均匀分布到这些服务器上去，假设每一个文件都位于 自己所分配到的服务器。这样 ，就把 Web Cache的访问日志纪 录映射到 P2P分布式文件系统上了。由于Web Cache和分布 式文件系统在访问局部性方面的相似性，通过这种方式使用 Web Cache的访问数据来评测论文所提出的缓存策略的性能。 实际上，缓存的性能与用户访问行为的局部性是密切相关 的，通过分析上述 日志文件中1小时时间间隔内的访问纪录得 到相关统计信息如图3所示。 在图 3中，可以看到 ： (1)不同访问次数的文件在总文件中占的比重是不一样的 (称之 为文件比重 )，访 问次数越少 的文件占的比重越大 ，其中 访问了 1次的文件占文件总数的73．83％，而访问了9次的仅 占0-32％。 (2)针对不同访问次数文件的访问在总访问次数中占的比 计算机工程与应用 2004．30 47 维普资讯 http://www.cqvip.com 重也是不同的(称之为访 问比重 )，虽然总的趋势与文件比重类 似，都是随访问次数的增加而降低。但访问比重降低的速度要 慢得多 ，并且由于访问次数为 l的访问比重(30．45％)比文件比 重(73．83％)要小的多 ，所以最终形成了这样一个事实 ：访 问次 数较大的文件比重较小 ，但访 问比重较大 ，比如说访问次数超 过 9次的文件比重为 2．38％，但其访问 比重 占到了40．36％。 图 3 不同访问次数的文件在文件总数以及访问次数中所占的比重 对只访问过一次的文件作缓存不仅不会提高缓存性能，反 而会加大网络负担 ，并在缓存空间有限的情况下降低缓存的性 能。而有多达 73．83％的文件只访问了一次，这使得通过过滤这 些访 问频率较低的文件来提高缓存性能成为可能。 缓存策略的好坏可以从缓存命中率 ，缓存字节命中率等方 面来衡量，图4反映了缓存命中率与缓存空间和阀值大小之间 的关系。 图4 缓存命 中率与缓存空间以及阀值大小的关系 图4中的4条曲线分布反映了把所有文件的阀值都设置 为 l、2、3、4的时候缓存命中率随存储空间使用率的变化而变 化的情况。为了与实际系统相符合，在实验中预设了两个前提： 不采用预取文件的方法 ，因为这在实际系统中是难以具体实现 的；只比较缓存在存储空间中所占比重从0到50％的情况，因 为继续增加缓存空间的大小对于提高性能来说效果不再明显， 而且实际系统很少会把存储空间的一半以上用于缓存。从图4 可以看到 ： (1)在所有在四条曲线中，缓存命中率几乎都是随缓存空 间的相对增大而增大的。 (2)在这 四条曲线中 ，阀值为 1的曲线在缓存 空间较大的 时候性能好，而当缓存空间相对较小时其他的三条曲线性能较 好。原因在于当阀值大于 1时将只会缓存那些被访问较多的文 件，从而能够更有效地利用有限的缓存空间。 (3)在阀值为 1的曲线 中，当缓存在存储空间中的比重从 15％增加到 35％的过程中缓存的命中率迅速增加 ，原因在于在 这个过程中由于缓存空间的增加大幅降低了由于热点文件在 48 2Oo4．30 计算机工程与应用 缓存中调入调出所造成的“颠簸”效应，当缓存空间继续增大 时，缓存命中率的增加变得十分缓慢。然而在其他几条曲线中 缓存命 中率的增加要相对平缓得多。 (4)在缓存空间充足的情况下 ，缓存命 中率 是随 阀值设置 的增大而降低 的，并且降低的幅度较大 ；而在缓存空间不足的 情况下 ，当设置的阀值加大时 ，继续增加阀值的大小并不能使 得缓存命中率有明显增加。原因在于使用阀值来选取热点文件 的同时也会造成较大的缓存命中率损失 。因此并不能为了提高 较小缓存空间的命 中率而一味增大阀值的大小。较为理想的阀 值大小为 l，2，3，4等较小的值。 类似于缓存的命中率 ，缓存字节命 中率 的试验结果也非常 相似 ，因此这里不做特别说明。试验结果表明根据缓存空间的 相对空间大小来及时调整阀值大小能够有效地提高缓存 的性 能。 5 结论 论文首先介绍了 P2P环境下分布式文件存储系统并分析 了其特点 ，接着提出了一种兼顾用户访问效率和复本一致性 的 灵活的缓存策略 ，进行 了理论上的分析 ，并和已有 的 P2P分布 式文件系统的缓存策略作了比较 ，最后采用 Trace—Driven的方 法验证了该策略的可行性并得出结论 ，即该策略是可行的和灵 活的。(收稿 日期 ：2Oo4年 6月) 参考文献 1．C Greg Plaxton。RNmohan Rajaraman，Andrea W Richa．Accessing nearby copies of replicated objects in a distributed environment[C]． In：Proceedings of ACM SPAA ACM。1997—06 2．B Y Zhao，J D Kubiatowicz．A D Joseph．Tapestry：An infrastructure for fault-tolerant wide-area location and routing[R]．Technical Repo~ UCB／CSD-01-l 141。UC Berkeley，2001-04 3．Peter Druschel，Anthony Rowstmn．P~try：Scalable，distributed object location and routing for large—scale peer-to—peer systems．Submission t0 ACM SIGC0MM．200l 4．Ion Stoica，Robert Morris，David Karger et a1．Chord：A scalable pee to-peer lookup service for intemet applications．ACM SIGCOMM，2001 5．Sylvia Ratn~amy．Paul Francis．Mark Handley et a1．A sealable con— tent addressable network．Submission to ACM SlGC0MM．200l 6．P Cao．S Irani．Cost Aware WWW Proxy Caching Algorithms[C]．In： Proc USENIX Syrup．Internet Technologies and Systems(USITS)， l997-l2 7．David A Patterson．John L Hennessy．Computer Architecture：A Qua．一 titative Approach．1996 8．P Druschel，A Rowstron．PAST：A large—scale persistent peer-to—pe er storage utility[C]．In；Proc HOTOS Conf，2001 9．John Kubiatowicz，David Bindel。Yan Chen et a1．OceanStore：An ar-- chitecture for global-scale persistent storage[C]．In：Proceedings of ACM ASPLOS ACM．2000一l l 10．Antony Rowstron，Peter Drusche1．Storage management and caching in PAsT．a large-scale．persistent peer—to—peer storage utility[C]．In： Proceedings of SOSP，2001—10 l1．Y Saito．C Karamanolis，M Karlssom et a1．Taming aggressive replica- tion in the Pangaea wide—area file system[C]．In：Proe of OSDI，2002 l2．M Nelson．B Welch．J Ousterhout．Caching in the Sprite Network (下转 84页) 维普资讯 http://www.cqvip.com 的社会中，任意两个 Agent之间不存在互逆 的希望。 证 明：若两个 Agent都是舍 己为人型或者都是公私兼备 型 ，定理显然成立。若一个 Agent是舍 己为人型 Agent。另一个 是公私兼备型Agent，经证明它们之间不存在互逆的希望。 反证法。假设舍己为人型 Agent A。和公私兼备型 Agent A：的希望互逆。假设 A。具有希望 ot，即日。(a)，A：具有希望 13， 即日2(B)，并且 a；～B。根据舍己为人型Agent的性质日(a)一 (S (a))，有 l(S (a))=--B。(S (～p))=--Bl(～S (B))；根据社会 利益常识公理 (S (a))；C(S (a))有 C(～S (13))；根据公私 兼备型 Agent的性质 日(a)一 (S (a))；因此有 2(S (B))，即 C(S (B))。这与 C((S，(B)))矛盾。 定理 28：在由舍 己为人型 Agent和损人利己型 Agent组成 的社会中。任意两个同类型 Agent之间不存在互逆的希望；任 意两个不同类型的Agent不可能有相同的希望。 证明 ：定理的前半部分是显然的。证明定理的后半部分 ，即 任意两个不同类型的Agent不可能有相同的希望。用反证法。 假如舍己为人型Agent Al和损人利己型 Agent A2有相同的希 望 ot。根据舍 己为人 型 Agent的性质 日(a)一 (S (a))，有 。 (S，(a))；根据社会利益常识公理 (S (a))；C(S (a))有 C(S (B))；根据损人利己型 Agent的性质 日(a)一 (～S (a))，有 2 (～S，(a))。于是根据社会利益常识公理 (S (a))；C(S (a))， 有 C(～S，(B))，这与 C(S (B))矛盾。 定理 29：在由舍己为人型 Agent和公益型 Agent组成的社 会中，任意两个 Agent之间不存在互逆的希望。 证明同定理 27。 定理3O：在由公私兼备型Agent和损人利己型 Agent组成 的社会中。任意两个同类型 Agent之间不存在互逆的希望；任 意两个不同类型的Agent不可能有相同的希望。 证明同定理 28。 定理 31：在公私兼备型 Agent和公益型Agent组成的社会 中，任意两个 Agent之间不存在互逆的希望。 证明同定理 27。 定理32：在损人利己型 Agent组成的社会中，任意两个 A— gent之间不存在互逆的希望。 证明同定理 28。 6 结语 传统的Agent理性模型普遍缺乏对利益的重视，其语义难 以体现利益对于 Agent理性选择 的影响。MAS的研究兴起后 ， 人们开始对效用对Agent理性的影响进行了研究，并尝试将效 用理性和逻辑理性相结合 ，并 出现了 BDICU这样的模 型。此外 还出现 了基于利益逻辑的 RL模 型。该文的工作正是基于 ILL 模型基础上，引进了利益算子并尝试利用逻辑手段形式化讨论 Agent的利益理性 。但与 RL模型不同的是，该文的系统在语义 上较之更为严谨，并将可能世界之间的关系定义为时序关系。 在此基础上 。定义了两种长期利益算子——强长期利益算子和 弱长期利益算子。该文给出了结合长期利益的对希望的理性约 束。并对不同程度满足此约束的道德理性 Agent进行了分类和 讨论 。证明了有关他们之间关系的若干定理。该文的 BHL系统 与传统的 BDI模型(如 Rao和 Georgeff的模型)以及基于传统 BDI模型基础上的 BDICU等模型相比，BHL系统采用了映射 语义从而解决了多重算子语义模糊的问题，并为进一步的长期 利益的定义做好了准备。与 BDICU等结合效用的BDI模型相 比，BHL系统(及姬广峰的RL系统)将利益定义为一个独立的 算子。籍用逻辑的方法讨论和描述利益的性质，利用理论上研 究利益的性质和特性。该文还研究了结合长期利益和当前利益 的 RAS社会 中的道德理性 Agent及他们之间的关系。为进一 步研究RAS中道德理性 Agent的合作关系奠定了基础。 (收稿 日期 ：2Oo4年 3月) 参考文献 1．Bratman M E．Intentions Plans and Practical Reason[M]．Cambridge MA：Hardvard University Press，1987 2．Bratman M E，Israel D I，Pollack M E．P1a／is and resource-bounded practical reasoning[M]．Computer InteHigence，1988；4：349-355 3．Rao A S．Georgeff M P．Modeling Rational Agents within a BDI一 chitecture[C]．In：J Allen，R Fikes，E Sandewall eds．Principles of Know- ledge Representation and Reasoning：Proceedings of the Second In— ternational Conference(KR91)，California：Morgan Kaufmann Publish- ers．1991：473—484 4．Luis Antunes，Helder Coelho．Decisions based upon multiple values： the BVG Agent architecture[C]．In：Proceedings of EPIA 99，Springer- Verlag，1999 5．陆汝钤．人工智能【M】．科学出版社，1996 6．陆汝钤等．面向Agent的常识知识库【M】．1999 7．徐晋晖，石纯一．一种结合效用的Agent思维状态模型【J1_软件学报， 2000；ll(11) 8．姬广峰．常识中理性特性的研究【D1．中科院硕士学位论文．2001 (上接 48页) File System[J]．ACM Transactions on Computer Systems，1988；6(1) 13．Mark Baker，John Hartman ，Michael Kupfer et a1．Measurements of a Distributed File System[C】．In：Proceedings of the 13th Symposium on Operating System Principles(SOSP)，1991—10 14．P Sarkar，J Hartman．Efficient cooperative caching using hints[C]．In： Proceeding of Third Symposium on Operating System Design and Implementation(OSDI)，1996 l5．M Dahlin．T Anderson，D PaRerson et a1．Cooperative caching：Using remote client memory to improve file system performance[C]．In：Proc of OSDI，1994-11 16．Nailonal Laboratory for Applied Network Research．f_tp：／／ircache． 84 20o4．30计算机工程与应用 nlanr．BeL，I。races 17．D Wessels．K Claffy．Internet Cache Protocol(ICP)[S]．version 2，In— ternet Eng Task Force RFC 2186，1997-09 l8．A Rousskov．D Wessels．Cache Digests[J]．Computer Networks and ISDN Systems，1998；30(22—23) 19．P Cao，J Zhang，K Beach．Active Cache：Caching Dynamic Contents on the Web．Distributed Systems 1999 20．Dennis Geels．Data Replication in OceanStore[R]．Technical Report UCB／／CSD一02—1217，2002—11 21．S samiu．P K Gummadi，S D Gribble．A measurement study of Deer—to—poer file sharing systems．Multimedia Computing and Net— working 2002 维普资讯 http://www.cqvip.com