让Web服务器推送更高效的策略研究

### 让Web服务器推送更高效的策略研究 #### 1. 引言 在客户端 - 服务器环境中，为了提高服务效率、降低客户端延迟，推送和预取策略成为了重要的研究方向。在万维网的场景下，寻找合适的访问模式以做出有效的推送决策是很自然的想法。本文将探讨一种利用关联规则挖掘技术，在服务器与浏览器或代理之间推送文档，从而降低Web用户延迟的策略。 #### 2. 相关工作 客户端 - 服务器环境促使人们考虑推送和预取策略，以提高服务效率和降低客户端延迟。以下是一些相关的研究： - **Bestravos方法**：通过访问日志计算文档在一定时间间隔内被请求的概率，该方法在文档缺失率降低23%的情况下，会产生10%的带宽开销。 - **Padmanabhan等人方法**：利用Web服务器维护的文档相互依赖关系的统计信息，以图的形式呈现，将统计上最可能的下一个文档推送给客户端。 - **Markotos等人方法**：将最流行的文档推送给最频繁的客户端，报告结果显示，在流量增加10%的情况下，可以获得40%的命中率。 - **Cunha等人方法**：使用随机游走模型来尝试确定下一个文档。 此外，Arlitt等人在访问日志文件中识别出了一些不变量，发现文件大小分布是重尾的，且每日模式具有代表性。之前的研究还提出了使用关联规则挖掘技术将Web文档从服务器磁盘预取到服务器缓存中，结果表明该技术可以有效地预测未来文档的请求。 #### 3. 方法 ##### 3.1 从访问日志中挖掘关联规则 访问日志是按时间顺序记录的条目列表，记录了哪个代理（由客户端机器的IP地址标识）请求了哪个文档（由其URL标识并以其大小为特征）。我们将给定代理在固定时间段内的条目列表称为事务。通过查看访问日志中的所有事务，我们构建形式为Di → Dj的规则，其中Di和Dj是文档（URL）。这种规则的直观解释是，在文档Di被请求后，同一用户很可能会请求文档Dj，并且根据日志，通常在这两个请求之间没有其他请求。规则的可行性通过置信度来衡量，置信度定义为支持度(DiDj) / 支持度(Di)。支持度(Di)是文档Di在事务中出现的总次数与事务总数的比率。 发现所有关联规则Document A → Document B的过程可以分解为两个子过程： 1. 首先找到所有支持度(D)高于最小支持度的文档D，这些文档可被视为流行文档。 2. 然后仅针对流行文档挖掘关联规则Di → Dj，并从所有可能的规则中消除置信度低于预定义阈值（最小置信度）的规则。 与传统规则挖掘和其他Web规则挖掘不同，本文的规则挖掘具有以下特点： - 事务由Web服务器访问日志提供的主机（或IP地址）标识，即以用户为导向，同时不忽略整体视角。 - 事务中的项是按时间顺序排列的，即请求之间的顺序是相关的并被考虑在内。 - 挖掘形式为A → B的规则，以预测用户在请求文档A后会立即请求文档B。 ##### 3.2 使服务器推送相关文档 当给定代理请求文档Di时，如果已经挖掘出形式为Di → Dj的规则，服务器将根据置信度最高的规则推送文档Dj。如果有多个规则具有相同的最高置信度，则任意选择一个。推送文档意味着将额外的文档包含在对初始请求的多部分响应中，或者在未来通过持久连接发送未请求的响应。如果挖掘出的规则代表了典型用户的访问模式，我们可以预期文档Dj在不久的将来会被请求，这样客户端（浏览器或代理）将在其缓存中找到该文档，从而减少延迟。 这种策略可以递归应用。如果存在置信度最高的规则Dj → Dk，我们可以在同一连接中与Di和Dj一起推送Dk，依此类推。策略的一个参数是推送长度，即应用连续关联规则与Di一起推送的最大对象数量。推送长度为0对应于标准协议。使用较大的推送长度虽然可以提高命中率，但会导致带宽消耗增加，即流量增加。 为了考虑推送文档的大小对成本的影响，我们提出了一种使用“大小加权”规则的策略。我们考虑一个函数f(C, S)，它随置信度C单调递增，随文档大小S单调递减。为了简单起见，本文选择f(C, S) = C / S。当给定代理请求文档Di时，如果已经挖掘出形式为Di → Dj的规则，服务