第四章原则的运用.ppt

4.13 对大数据库的增量访问 假定用户连续读一个存放在web网站的大数据库，用户只想知道自上一次读过之后变化了的内容。 问题 为数据库找到一种高效地执行增量查询的方法。 令数据库记住每个用户之前读的内容是不现实的。 有没有一个对数据库来说负担不那么重的方法？ 分析 如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。 分析 如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。 什么样的简单信息可以刻画用户的上一次请求？ 分析 如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。 什么样的简单信息可以刻画用户的上一次请求？ 上一次请求的时间 分析 如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。 什么样的简单信息可以刻画用户的上一次请求？ 上一次请求的时间 在数据库中增加什么状态（P12），可以根据用户传递的信息来加快增量查询？ 分析 如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。 什么样的简单信息可以刻画用户的上一次请求？ 上一次请求的时间 在数据库中增加什么冗余状态（P12），可以利用用户传递的信息来加快增量查询？ 数据库更新历史列表 解决方案 增加一个更新历史列表，仅保存数据库发生的更新。 更新记录按照时间顺序排列，越近的更新越靠近表头。 读请求中包含上一次读的时间 T，查询处理程序从表头开始扫描更新历史表，找到 T 之后所有的内容更新。 4.14 长标识符的二分查找 假定每个标识符的长度为 W 个字，匹配一个标识符需要 W 次比较操作。 如果表中有 N 条标识符，且已按字典序排列，简单的二分查找需要W×log2N 次比较操作。 若所有标识符的前（W-１）个字都相同（有共同前缀），理想情况应只比较 log2N 次，而不是W×log2N 次。 希望修改二分查找，使得比较次数为 log2N+W。 按列进行二分查找 问题 修正当前的算法，使得经过（log2N+M）次操作后得到正确的结果。 算法出现错误的原因： 当查找移动到下一列、并且依据二分查找法确定一个新的查找位置时，假设该位置上的标识符和所要查找的标识符具有相同的字符前缀。这个假设一般是不成立的。 问题：增加什么状态可以避免做出这样错误的假设？ 解决方案 给每一个元素增加两个指针，将二分查找约束在正确的范围内进行。 解决方案（续） 一般地，为每个多字条目（W1W2…Wn）保存一个预先计算好的保护范围，其中Wi的保护范围指出前 i 个字为（ W1W2…Wi ）的条目的范围。 如果有N条标识符，该策略需要log2N+M次查找。 代价是给每个元素增加了两个16位的指针，相当于增加了一倍的内存空间。 这里运用了P12（增加状态）和 P2a（预先计算）两条原则。 4.15 基于ATM的视频会议 标准的ATM允许“一对多”虚电路（VC）： 源节点发送的任何数据被交换机复制，发送给每个接收者。 many-to-many VC ATM交换机硬件很容易实现“多对多”VC： 交换机将任何一个源节点发送的数据复制后发送给所有的接收节点。 “多对多”VC的问题： 如果两个源节点同时发送，它们的数据（带有相同的VC号）可能以任意交错的顺序到达接收节点，引起混乱。 ATM标准不支持“多对多”VC 。 应用 设计一个视频会议应用： 每个工作站上建立一个屏幕，显示当前正在说话的人，并播放其讲话。 当两人进行对话时，能看到两个人的表情。 问题 问题：如何在ATM上实现 many-to-many 的视频会议？ 最简单的方法是使用N2个点-点 VC。 较好的方法是使用N个one-to-many VC。但ATM交换机的带宽要在N个one-to-many VC之间静态划分，限制了参会的工作站数量。 还有扩放性更好的方案吗？ 分析 利用交换机硬件支持many-to-many VC的能力（P4c），但需要解决每次只能一个节点发送的问题。 如何协调发送者？ 解决方案 协调发送者（运用系统思维）： 谁的视频最应当被输出：当前说话者。 如何确定当前的说话者：给每个工作站添加一个语音检测器（P5，增加硬件）。 原理： 如果工作站 X 上的语音检测器检测到有意义的语音活动，检测器将 X 的视频连接到C。 优化预期情形 最常见情形是两个与会者之间对话，保留上一个说话人的视频图像可以提供视觉上的连续性。 为此，使用两个many-to-many VC，C和L： C 用于传输当前说话人的视频 L 用于传输上一次说