（计算机软件与理论专业论文）语义缓存的一种替换策略.pdf

语义缓存的一种替换策略 中山大学硕士学位论文 语义缓存的一种替换策略 计算机软件与理论 硕士生：洪朝阳 指导老师：李磊教授 摘要 在移动计算环境下，由于有通信带宽窄、网络断接频繁、客户端资源有限 等缺点，给移动环境下的数据访问提出了挑战。这样在客户端进行数据缓存变得 非常必要。语义缓存是基于客户查询语义相关建立的一种客户缓存，内容由以往 查询的结果及相应的语义描述组成。客户端可以利用本地缓存的语义信息进行推 理，从而确定客户查询是否可在本地被完全解答或部分解答。 在语义缓存中，替换策略与缓存模型和查询处理策略密切相关，不同的数 据存储方法和查询处理策略对应不同的替换策略。本文针对一种缓存模型和查询 处理策略提出了m n v a l u e 替换策略，该策略用一个评价函数计算每个关系片的 评价值，评价值最小的关系片优先考虑替换，评价值考虑的因素有：关系片的命 中率，关系片的贡献率，关系片的长度，同时用理论论证了该替换策略的可行性。 本文还设计了一个实验系统。最后通过性能分析实验，在这种语义缓存模型下， 该替换策略的系统性能要优于传统的u w 和u u 替换策略的系统性能。 关键字：移动计算，语义缓存，替换策略 堡兰堡登塑= 壁量垫堕堕。一一坠里墅墅生竖! 垡堕苎 ar 脚l a c e m 【e n tp o u c y f o r s e m a n n cc a c l l e o 咖口p i i l e rs o 脚ma n d 诹o r y n a m o ：i 酗坞z h g s u d e f v i s o r ：n n 嘶ru ，l e i a b 爱e r a c t i nm o b i l cc d i n p u t i i l ge n v i f o 衄e n | ， n a f r o wb a j l d w j d t l i ，缸q u e mn e t 啪r k d i s c o n n e c t i 0 璐a t i dl i n l i t e dc 重i e n tr c s o 圳雠h a 、停b e m eac h a n e n g eo fd a t e 嬲s s l s oi t 西m u c hn e c c 豁甜y 蕾d fc l i e mt oc 盯f y 蛐d a | ec a c b 抽g s e m a m i cc a c h i g 王sa c a c h m gs c h e m eb a s e do ns 啪a n t i cl q c a l 盘y 删“c n t 姗e dq u 盯i c s s 嘲a 嘛 c h em a 鼢i 璐t 醛地o fm e v 缸l s 驴髓缸a 耐啪c 叩o n d i n gd e s a i p t i d n s s 如 m a n 琏c s 吞b 。u lt h e 谥l e h e d 主t e m sa r cs o 粥d 缸s e 嫩n t i cc a c h 谊岛t h ec h c n t 裔a b l et o f e a s o n 如mt kb 髓l 蚀c h et od 咖釉纽ew 搬h e raq u e r yc a nb et o t a ya n s w 暂e d ， l l o w 删c ：h i f c a n b e 羽蟠* 雌d i ns e m n i 盍cc a c h i n 萌唧1 a c e m e n tp o l i c y 虹c l o s e d 勰c j a t e dw i i hc a c h 抽g 脚d e l 柚dq ：l l e r y 弘o c s i n g 舯y d i f b 粥m 嘲h 虹喀m o d e l 粕dq u 盯yp r o c c s s i n gp o e c yj s c o 盯e s p o n d i | 鸣t oi i s 袱；p e c l 萱v c 唧l a m e 珏tp o l i c y i nt h 砖p 印e f am v a i u e 侣p l a 锄e n tp o y 括p l o p 。t s e d ，w h i c l lb a d 蚴a 鹞m 锄i cc a 蛐g 瑚o d e la l i dq u 盯y p m c e 器i n gp o l j c y t h e1 m 珏v a l u e 舯啦c ye m p l 时a v a i 艟e 如n d j o nw h i c h 髓l c l | l a t ct h e 砌u eo f 删e f y r e l a t 娴s c g m e 呶r _ s 办b r s w 鼢t h e l 嘲tv a l u em u s lb er e p k 钟d w 豇h 西e h i g h c s tp r i o t i t 塾码e v a l u e 如嬲曲n l a k e i l l 童oa c 。0 硼t h r c e 自c t o r s ：h i tr a t c o f r s ，c o n 确叭i o nr 矗把。鸯r s ，s 酶o f r s ，a d 唧l a t et h e o r yd e 珏啪s t f a t 劬i s 咖e a tt h e s a m et 细a ne 印e r i m b m m $ y 髓c m 趣d e s i g n c ds y s t 锄。a tl 舔t ，p e r 如胁n c ea n a l y s i s f 髂u l i so f 哪抽舱n t 扯i o ns h o wt h a t l 赫s r e m a c c m # n tp o l i c y 叫t p e r f o 珊st h e 拓a d i t i a li _ r ua 丑dl 删c 妯e 蕈嘲a c e m e t 圃姆b a s e d 鲫m eg i v e ns 嘲a n t i c c h j 岵m o 出儿 k 删内s ：m o b i l 尊秭m 辨l 瓤昏s j 锄扭n t i cc a d 曲勘r 印l a m 髓tp o l i c y 语义缓存的一种警换策略 中山大学须士学位论文 1 1 应用背景 第1 章前言 随着无线通信技术与移动设备这些移动基础设施的高速发展，移动计算环境 臼趋成熟，与传统计算模式相比，移动计算模式显得更加灵活多样，它代表未来 网络通信发展的主流和方向。但是，移动环境有以下缺陷f 2 】： 1 通信带宽窄； 2 网络断接频繁： 3 。移动终端资源的昂贵和有限。 这些缺点给移动环境下的数据访问提出了挑战。而传统的分布式客户一服务 器数据库系统多基于查询传送结构，客户方的功能仅限于提供用户界面、传送 用户请求和接收结果，服务器对查询和事物进行处理。这种结构实现简单，但功 能也有限，没有充分利用客户方的资源，对网络速度和性能的依赖很大，因此它 只适合于高带宽、性能稳定的固定网络系统【3 】。为了提高移动环境下数据库系 统的性能，人们对客户缓存进行了研究。 数据缓存是把客户端经常使用的数据存储到本地，它减少了客户端对服务器 的访问，从而达到了提高客户服务器数据库系统的整体性能、减少网络开销、 ：b b 快查询响应时间的效果。目前，常用的缓存技术有页缓存、语义缓存两类【1 】。 页缓存是基于空间局部性、以页为缓存粒度的缓存策略，它只缓存数据而不缓存 数据的语义信息，如果数据的聚集度不高，一页中往往只有一部分数据是有用的， 这样就降低了缓存的效率，而且页缓存系统有时候很难判断客户查询是否可以在 本地解答，要靠与服务器通信才能确定，这使得大大增加了网络开销，所以页缓 存不适合于移动环境。而语义缓存同时缓存查询结果及其语义描述，客户端可以 利用缓存的语义信息进行推理，从而确定客户查询能否在本地被完全解答或部分 解答，这样就减轻了网络的数据传输量，因此语义缓存技术能够弥补移动环境的 缺陷。 语义缓存的一种替换策略 中山大学硕士学位论文 1 2 研究现状 语义缓存已经被世界各地学者广泛地研究，并在一些领域里得到应用。人们 主要从三个方面进行研究：1 、语义缓存模型和查询处理策略；2 、一致性维护机 制；3 、替换策略。下面将分别从这三个方面简要叙述前人的研究情况。 语义缓存模型和查询处理策略方面。文章【1 】首次提出语义缓存的查询、缓存 项、缓存本身和查询裁剪的概念，并且提出了一个完整的语义缓存模型和相应的 查询处理策略，查询允许做选择、投影操作，不允许做连接操作。但是在【l 】中 的缓存模型中，有时候由于查询的部分谓词属性没有包含在查询的属性集中，这 样，即使缓存包含查询的结果集，但是查询却不能从缓存中导出，这使得查询处 理器必须做修补查询，即需要从服务器中得到缺少的谓词属性，因而增加了网络 开销和查询响应时间，显然，这违背了语义缓存的初衷目标，文章【l 】中描述在 查询处理过程中，查询存在三种裁剪方式：水平裁剪、垂直裁剪和混和裁剪，进 行混合裁减时，查询处理过程非常复杂，造成了极高的时空代价。总之，文章【1 】 只是在理论概念和方法上有很大贡献，但是很难满足实用性的要求。 一致性维护方面。b a 渤b r a 和i m i e l i i l s h k i 首先提出了移动环境下的一致性维 护闯题。文章【1 8 】提出了t s ，筒js i g 三种一致往维护策略。文章【1 6 】给出了l 丑z y r e p l i c a t i o n 维护策略，并形式化的描述了如何保持全局事物串行化，文章【1 7 】将 c l i e n lp o l u n g 和i n v a l i d a t i 0 咀p m t o c 0 1 s 策略结合，一定程度上节省了系统的一致 性维护的网络开销。文章f 5 】提出了基于下行更新的语义缓存一致性维护机制， 该机制很好的解决了语义缓存的一致性维护问题，通过性能分析实验证明它在性 能方面要优于复制控制法。 替换策略方面。在内存页的替换方面替换策略有很多种，其中最常用的f i f d 、 l r u 和u 那。其中兀f c i 以页在内存的停留时间为替换依据，u u 是以页的访 问频率作为替换依据，u t u 是基于时间局部性的替换，由于语义缓存的缓存粒 度、缓存模型和查询处理过程不同于基于页的替换，所以上述替换策略对语义缓 存不能保证很好的性能。在语义缓存的替换研究方面，文章【4 】在文章【3 】的基础 上，提出了最小权值项l w i ( 1 e a s tw e 远h tj t 锄) 替换策略，该镶略由缓存项投影 属性的访问频率和缓存项与查询的条件匹配情况，结合数据访问的时间局部性 2 语义缓存的一种替换策略 中山大学颈士学位论文 ( 1 - e m p o m ll o c a m y ) 考虑决定缓存项的权值，替换最小权值项，通过性能分析 实验，在语义缓存中，l w i 替换策略的系统性能要优于传统的l r u 和u u 替换 策略的系统性能。但是该策略假定缓存项的长度为定值，而实际的应用中，查询 的长度不可能一成不变，所以缓存数据长度也相应不可能为定值。文章f 7 】提出 了一种基于缓存项之间语义距离( m a l l l l a t t 趾d i s t 如c c ) 的替换策略，与最近访问 缓存项的语义距离越近越要保留在缓存中。这种方法利用了缓存项之间的语义相 关性，这种替换策略有一定的启发意义，但是每次查询都要计算所有缓存项与新 缓存项的语义距离，而语义距离的计算相当复杂，这样系统的开销很大。文章【9 】 利用缓存项之间存在不同程度的联系，把相交或被同一个查询包含的缓存项放在 一个聚集中，认为如果一个缓存项被访问的机会大，那么与它相交或同属于一个 查询结果的其它缓存项被访问的机会也会大，从而提出了一个两级u m 替换策 略：通过l r u 挑选聚集，并在聚集中用u m 选择替换项。但实际上，即使数据 曾属于同一个查询结果或包含这些数据中的查询有相交部分，也不能保证客户对 这些数据中不同的部分有相同或相近的兴趣，所以还是以单个缓存项为替换单位 更为合理。 1 3 本文的研究工作 本文根据移动计算环境的特点，在一种语义缓存模型及查询处理策略的基础 上，提出了语义缓存的m j n v a l u e 替换策略，该策略以关系片为替换的单位，用 一个评价函数计算每个关系片的评价值。当客户端产生一次查询，如果查询结果 完全包含在缓存中，则将查询直接在本地处理，这是无需将查询结果缓存，所以 无需替换；如果查询的部分结果包含在缓存中，则将查询裁剪成两部分：探头查 询( p r o b cq u e r y ) 和剩余查询( r e m a i l l d c rq u e r y ) ，探头查询在本地处理，剩余 查询送往服务器处理，这是需要将探头查询的结果作为一个新的关系片进行缓 存；否则，将查询全部送往服务器端处理，并将全部结果作为一个新的关系片进 行缓存。 当有新的关系片要进入缓存区而缓存区空闲空间不足时，就将缓存区中原有 的评价值最小的关系片替换出去，如果空间仍不够，则将评价值次最小的关系片 3 语义缓存的一种替换镶略 中山大学硕士学位论文 替换出去，直到缓存区有足够的空闲空间容纳新的关系片。本文给出了详细推导 评价函数的过程，最后得出关系片的评价函数为m 缸e ( f ) 一a 岛。殿为关系片 的命中率，g 为关系片的贡献率，为关系片豹长度。文章最后设计了一个实验 系统验证了替换策略的可行性。 1 4 论文的组织 本文共分为六个章节。 第一章简单介绍了语义缓存替换策略的研究背景，相关研究现状和笔者在这 方面所做的工作。 第二章讨论了语义缓存模型和查询处理的理论基础，语义缓存的内容，查询 处理规则的逻辑表示r 查询处理的基本思想。后面详细分析了现有替换策略的优 缺点。 第三章介绍了一种语义缓存模型和相应的查询处理策略，这是本文所研究的 替换策略的基础。 第四章基于第三章的语义缓存模型和查询处理策略，提出了m i l l v a l u e 替换 策略，同时用理论详细论证了该替换策略在提声查询喃应时间、节省缓存空间方 面的效果，然后设计了实现替换策略的具体算法。 第五章设计了一个实验系统，用实验验证了该替换策略的可行性。 第六章是对上述工作的总结，并对今后的进一步工作做了展望。 4 语义缀存的一种替换筇略 中山大学硕士学位论文 第2 章知识背景 2 1 语义缓存理论基础 2 1 1 语义缓存模型及内容 在客户服务器数据库系统中，语义缓存是基于客户查询语义相关建立的一 种客户缓存。语义缓存的内容由以往查询的结果以及相应的查询描述构成【3 】。 关系数据库有交、并、投影、选择和连接五种基本运算，其中最常用的是选 择和投影运算。其中，选择运算对应于s q l 语言中的w h c r e 子句，投影运算对 应于s q l 中的s e l e c l 子句。 在移动环境下出于对性能和代价方面的考虑，只是对格式简单的查询进行缓 存，一方面，常用的查询一般都格式简单；另一方面，格式复杂的查询其结果以 后利用的可能性小，缓存的意义也不大。所以在移动环境下，查询的格式为： s e l c c taf r o mrw b e r cf 其结果才进行缓存，其中曰一 墨，兄，日) ， 墨o 一1 ，2 ，f ) 代表数据库中的关系：s e l e d 子旬起投影运算的作用， 彳t 0 4 ，以，4 ) ，4 at 1 ，2 ，一) 代表数据库中关系的属性集：w h c r e 子句起选 择运算的作用，f 为条件表达式，文章【2 4 】中提到，任何一个查询公式都可以转 化为析取范式的形式，所以f 可以用析取范式表示， f = 丑v 忍v v 艺 号一瓯“如6 “吼g 一1 ，幺，研) 吼。- 4o pc ，叩仁， ，一) ，七一1 2 ，再，j 一1 2 ，牌，c 是常数。值得注意 的是，在吼中，o p 不能是一运算，因为运算会导致1 、口1 l a r d 问题。 如果查询只做投影操作，查询q 的结果集可以用一个三元组t 级，q p ，q c ，描 述，其中级佩，兄，r ) ，岛f ，q ct o 西( 。由于语义缓存是以一次查询 5 语义缓存的一种替换策略 中山大学硕士学位论文 返回的结果为缓存粒度，所以每次缓存的数据也相应地用三元组c 品，品，& ，表 示，其中& 蜀，r ，r ) ，s 。一( & ) 。c 是，品，& ，称为缓存项，它 对应于服务器数据库中的一个关系或视图。一个缓存项所描述的内容称为缓存 块，语义缓存区中的内容就是由一组这样的缓存项及相应的缓存块组成。 如果查询同时做做选择和投影操作，则查询用一个四元组c 缘，玩，鲱，q c ) 表 示 1 ，其中繇 蜀，& ，咒) ，q j f ，幺 4 ，4 ，4 i ) ，q c ；硝舀口韩( 级) ， 缓存项也相应的用一个四元组t 品，只，品，& ，其中叉 r ，兄，足) ，品f 只 4 ，4 ，4 1 ) ，品c d 0 ( & ) 。查询做投影操作导致查询处理策略非常复 杂，而且有时候，即使查询结果完全包含在缓存中，但由于查询的谓词属性集中 不含属性集中的属性，查询却不能从缓存中导出结果，例如： 查询为 显然，查询的结果完全包含在缓存中，查询却不能从缓存中导出，这样就不 得不做修补查询( a 1 n e n d h 唱q u e r y ) ，即从服务器端得到相应的主属性，然后通 过主属性导出查询结果，这样就增大了网络开销。雨查询只做投影操作时，查询 的属性集就是关系的属性集，所以查询的谓词属性集必定包含属性集中的属性。 2 1 2 查询处理 2 1 2 1 查询处理规则的逻辑表示 关系数据库应用数学方法来处理数据库中的数据，文章中 2 5 提出，关系数 据库有一个逻辑解释并且可以用逻辑表示，这些逻辑解释和表示构成了语义缓存 查询处理的理论基础。 设是r ：r 似，4 ，4 1 ) 是一个关系模式，则r 是一个n 元谓词。 设怛) = ( q ，) ，( 。，口。) ) 是r 对应的关系，则 r ) 是谓词r 的解释。 6 语义缓存的一种替换策略 中山大学硕士学位论文 设是r ，& 模式，则d 一儇) u u 氏，是数据库。 设eq 是原子公式，设q u e f y ( p ) = p ) ，q u e r y ( q ) = q ，并且 p ) - g ，假 定q u e r y ( p ) 已经执行，p 已经缓存，q u e r y ( q ) 是当前提问，则： ( 1 ) 如果ps u bq ，则 p ) q ) ， q 只需从 p ) 中提取； ( 2 ) 如果p 咖q ，则 p ) = q ) ，q u e r y ( q ) 不必执行； ( 3 ) 如果一( p i n tq ) ，则 聪n q ) = 彩，直接执行q u e r y ( q ) ； ( 4 ) 如果( p i n tq ) ，( p s u bq ) ，则需执行q u e r y ( q ，p ) 。 上述逻辑表示与语义缓存的查询处理有一一对应关系，对应关系如下： p 对应缓存项的条件表达式， p ) 对应缓存项的结果集，q 对应查询的条件表 达式， q 对应查询的结果集。 ( 1 ) 式对应如果查询包含在缓存中，则查询直接由缓存导出； ( 2 ) 式对应如果查询与缓存相等，则将缓存结果直接赋给客户端，但是操作比 上一种情况更简单； ( 3 ) 式对应如果查询与缓存没有交集，则将查询全部送往服务器端处理； ( 4 ) 式对应如果查询与缓存相交，则将相交的那部分由缓存处理，剩余的那部 分送往服务器端处理。 2 1 2 2 查询处理的基本思想 在页缓存或元组缓存的查询处理中，如果要判断查询是否包含在缓存中，查 询处理器必须从第一页或第一个元组开始遍历缓存的结果集，直到发现满足查询 要求的页或元组为止，这样加大了查询处理的时问，特别是在缓存区不能满足查 询要求的情况下更是如此，因为这时候需要遍历整个缓存区。而在语义缓存的查 询处理中，由于客户端缓存了结果集的语义信息，查询处理器只需将查询的语义 和缓存的语义进行比较、而不必在缓存的内容中寻找查询结果就可以判断查询是 否包含在缓存中，这样提高了查询处理速度。 根据上一小节的理论，我们可以得出在语义缓存中查询处理的基本思想为： 在查询处理过程中，我们首先应该将查询的条件表达式q p 和缓存的条件表达 式品进行匹配，( 如果查询同时做选择和投影操作，还要将见和只进行匹配) ， 7 语义缓存的一种替换镶略 中山大学硕士学位论文 然后根据匹配结果来判断查询是否完全或部分包含在缓存中。如果查询完全包含 在缓存中，员l j 将查询直接在本地处理；如果查询只有部分结果包含在缓存中，则 将查询裁剪成两部分：探头查询( p i q b eq u e f y ) 和剩余查询( r e l n a i n d e rq u e r y ) ， 探头查询在本地处理，剩余查询送往服务器处理；否则，将查询全部送往服务器 端处理。 2 2 替换策略 缓存替换在缓存管理中起着非常重要的作用，缓存设置的目标是加快查询响 应时间，减少数据的访问开销，但是在移动环境下，移动终端资源昂贵，因此缓 存空间不会太大，当有新的缓存项要进入缓存区而缓存空间不足时，就必须将原 有的一些缓存块替换出去。如何选择被替换的缓存块就成了替换策略所要解决的 问题。 在操作系统中，由于替换的单位是页，长度固定，加快响应时闻的唯一方法 就是提高内存访问的命中率，所以替换策略的标准就是把命中率最低的页替换出 去，所以替换策略主要是基于时间局部性和访闯频率，例如u 町、u t u 等，替换 策略也相对简单。由于语义缓存的缓存粒度、数据组织模式、查询处理过程不同 于页缓存，所以操作系统的各种替换策略对语义缓存对语义缓存缺乏针对性，从 而不能保证有好的性能。 文章【4 】提出了语义缓存下最小权值项l w i ( 1 e 髂tw e 蟾h lj t e m ) 替换策略，其基本 思想为：当缓存空问不足时，就要从缓存原有及新的缓存项中找出使下面的函数 最大且缓存可以容纳的缓存项集合，替换不在其中的缓存项： 丑明啦；p r 鸲( c 弛( ，1 ) 一c 瓠f ( f i ) ) 百 在上式中，i 代表缓存中的缓存项集合，p r 口政代表缓存项f 在下一次访问被访 问的概率。c r ( 五) 表示从服务器数据库中取缓存项f 的开销，c 瓠t 锅) 则代表了 在缓存内操作和维护缓存项f 的开销。假设每个缓存项的c 钿f ( 工) 一面对g ) 的值 一样。这样，缓存替换策略的关键就是找出下一次访问被用到的概率低的缓存项。 8 语义缓存的一种替换策略 中山大学硕士学位论文 缓存项的访问概率由缓存项投影属性的访问频率和这些投影属性上缓存项数据 的访问情况共同决定。 缓存项权值的设置为：缓存中的各个投影属性都对应一个访问频率值 丘e q u c n c y ，是该属性被客户访问的次数，缓存项的每个投影属性对应于一个缓存 项数据访问概率p r o b ，该值由每次查询与缓存项条件匹配的情况决定，同时采用 指数衰减( e x p o n c n t i a la g i n g ) 的方法使以往得出的概率值随时间指数衰减。缓 存项数据访问概率p r o b 由下式决定； p f o b = q p r o b 。d + ( 1 - 吼) m 其中吒是衰减系数，o ( q ，其中级表示所要查询的关系；q ， 表示查询的语义，表示如析取范式；q c 一乃d 0 ( 级) ，蜴e d 口；查询q 不进行 投影操作。 定义3 3关系片r c l a t i o ns e 鲫e n t ( r s ) 语义缓存的一种替换镱略 中山大学硕士学位论文 该语义缓存模型以关系片i 峪作为缓存项，故r s 也相应的为一个三元组， 船- c 瞩，磷，磷，其中黜；表示结果集缓存的关系；磷表示结果集的语 义，表示如析取范式：r s 。- 仃。( 硒。) ，船。是数据库服务器中的关系之一。 定义3 4 关系块r c h t i 呻q 螂q r c 是由具有相同关系的忍s 组成的集合；r c c 月g ，r q ，r c c ，其中 兄g - 髂r ；尺o - u r 墨p ( 1 s fs 撑) ；其c c 一仃 q ) 显然根据r c 的定义，缓存区中的各个r c 是不相交的。而且，r c 中的各个 r s 是不相交的，在文章【5 】中有详细的证明。 我们的替换策略是以关系片为替换单位进行替换，当客户端需要对查询结果 进行缓存时，则建立一个新关系片用于保存查询结果，如果缓存区空闲空间不足， 则按照一种评价方法将价值较小的关系片替换掉，直到有足够的空闲空间容纳新 的关系片。 3 2 查询处理策略 3 2 1 查询裁剪 定义3 5 查询裁剪 当语义缓存在接受到查询q ( 形如( q 矗，婢，璐，) 后，如果只能部分解答q ， 则将q 分解为两部分； 一部分可从缓存解答，这部分称为探头查询q k ( 形如cq k ，q o ，q k ，) ； 另一部分不能从缓存得到回答，这部分称为剩余查询( 形如 cq ，q 0 ，q k ，) ，这个分解过程叫做查询裁剪。 显然满足下面等式： q 舭一一级； q 咿v 2q p p 一a ，： f 3 语义缓存的一种替换策略 中山大学硕士学位论文 u c ；q c ，n 2 9 ： q _ 。u ；q ，q _ 。n z g ； 探头查询的解空间为q 。n 且c 。，的结果集越大，说明查询q 在本地得 到的解答越多，查询的速度就越快，当q 。一q 时，则查询q 在本地能够被完全 解答。剩余查询q 琦的解空间为q r c c ，剩余查询送往服务器端处理，返回的 结果与探头查询结果合并，得到用户查询结果ar c ，q ，的关系如图 3 一l 所示 o 图3 1 在查询裁减中，以关系块为单位来进行查询裁减，而不是以关系片为单位来 进行查询裁减。因为查询q 有可能与一个关系块中的多个关系片匹配，如果查询 以关系片为单位来进行裁减，则可能需要进行多次裁减才能得到探头查询和剩余 查询，这样查询处理很复杂；而查询q 至多与个关系块匹配，所以查询q 只需 裁减一次就可以得到探头查询和剩余查询。 3 2 2 查询q 与语义缓存( s c ) 之间的关系 定义3 6 包含匹配 如果查询q ( 形如t g ，q p ，q c ，) 和缓存中的一个关系块r c ( 形如 c r g ，r o ，只c c ，满足以下条件： ( 1 ) g r g ； 语义缓存的种替换策略 中山大学硕士学位论文 ( 2 ) 婢一r c p 则q c r c 。，这时q 的全部结果在r c 中，我们称q 与r c 包含匹配。 同理，如果查询q 和缓存中的一个关系片冗s ( 形如c j t 靠，磷，j t ，满足以下 条件： ( 1 ) 级- 礁； ( 2 ) q p 缉 则q 。r c 。，这时q 的全部结果在船中，我们称q 与麟包含匹配。 定义3 7 相交匹配 如果查询q ( 形如cq 矗，q ，q c ，和缓存中的一个关系块r c ( 形如 ( 尺g ，尺c p ，r c c ) 满足以下条件： ( 1 ) 绋= r q ； ( 2 ) 绋 r q 可满足，并且一( q ，j r c p ) 则q cn r c c 一彩并且q cn r * q c ，这时q 的部分结果在r c 中，我们称q 与 r c 相交匹配。 同理，如果查询q 和缓存中的一个关系片兄s ( 形如t 魁。，脚，j t ，) 满足以 下条件： ( 1 ) 级= 船r ； ( 2 ) 绋 脚可满足，并且，( 鳞一眸) 则q cn 硷* 彩并且一( 绋一磷) ，这时q 的部分结果在船中，我们称q 与麟 相交匹配。 包含匹配和相交匹配统称为匹配，根据r c 和黜的定义，一个查询q 至多与 s c 中的个r c 匹配，但可能与一个蜀c 中的多个船匹配。这样在查询处理过 程中，只要发现一个查询q 与某个r c 匹配，就只需将q 在该震c 上进行处理而 不必将q 在其它r c 进行处理，因为其它r c 肯定不含q 的部分结果，这样查询 l s 语义缓存的一种替换策略 中山大学硕士学位论文 处理时间得到了一定程度的降低。 用户在客户端发出查询q 时，q 与s c 同样存在三种匹配关系：l 、包含匹配 q ，2 、相交匹配q n s ct g ；3 、不匹配q n 鼯一乃。下面分尉用图3 2 表示q 与s c 的三种匹配关系： ( 1 ) 包含匹配 3 2 3 查询结果的缓存 厂百一 【，。，。_ | ( 2 ) 相交匹配( 3 ) 不匹配 图3 2 对查询的结果根据情况进行缓存，在语义缓存中，由于查询与缓存存在包含 匹配、相交匹配、不匹配三种情况，所以缓存的方式也不一样，下面分别就这三 种情况对查询结果进行缓存： 1 如果查询q 与缓存区中的某关系块包含匹配，则查询的结果就不需要缓存， 2 如果q 与缓存区中的关系块均不匹配，则根据下面两种情况进行处理： ( 1 ) 如果q 与某关系块r c 属于同一个关系( 即级= r c 盘) ，则将q 作为一个关 系片加入该关系块； ( 2 ) 如果q 与任何关系块均不属于同一个关系，则新建个关系块，并将q 作 为一个关系片加入该关系块。 3 如果q 与某关系块月c 相交匹配，文章 1 采用的办法是根据q 和该关系块的 各关系片的相交情况将原关系片拆分，分为q 与关系片相交部分及q 与关系片不 相交部分，将q 与关系片相交部分删除，并将q 的全部结果作为一个新关系片加 1 6 堡苎墨童堕二壁堇塾簦堕一! 生奎兰堡主堂垒望堕 入r c ，这种办法并不好，因为关系片的拆分需要重新组织缓存数据，改变缓存 数据的描述，带来额外的开销，该策略采用的方法是将剩余查询部分作为一个新 的关系片加入r c ，而探头查询部分则不需要缓存，缓存区中的原关系片也不需 要拆分，这样查询处理的开销就降低了。 3 2 4 查询处理策略 语义缓存查询导出的策略为：设缓存区有n 个船，第i ( 1 曼i 三n ) 个r c 有 啊个船。 l 、客户端在接收到查询q 后，首先检查q 是否与r c l ( 即第一个r c ，后面类 似) 匹配，如果不是，则检查q 是否与尺c z 匹配，依次类推，直到q 与一 个r c 匹配为止，如果q 与缓存区中任何一个r c 均不匹配，则认为查询q 不 可从缓存导出，则将查q 全部送往服务器处理，返回结果后查询处理完毕。 如果查询q 与r c 匹配，则继续笫2 步。 2 、如果q 与r c f 包含匹配，则将q 从该r g 中导出，并将结果返回，查询处理 完毕； 3 、如果q 与r g 相交匹配，则将查询裁剪，其中探针查询部分暂时保存，剩余 查询部分则送往服务器处理。并将其返回结果与探针查询部分合并作为查询 结果返回，然后将剩余查询部分作为一个新的尼s 加入r g 中，查询处理完毕。 1 7 语义缓存的一种替换策略 中山大学硕士学位论文 第4 章语义缓存的替换策略 第2 章详细的分析了目前语义缓存替换策略存在的问题，在第3 章的语义缓 存模型和查询处理策略的基础上，本文提了以关系片为替换单位的m n v a l u e 替 换策略。 4 1 替换策略的目标 一般来说，无论是语义缓存还是其它形式的缓存，缓存替换的主要目标就是 提高查询的平均响应速度，也就是降低查询的平均时延长度比( 即查询的响应时 间与查询结果集所占字节数的比值的期望值) 。在操作系统中，内存替换的单位 为页，长度统一，访问内存的速度和访问硬盘的速度相差了几个数量级，所以命 中率的高低就基本上决定了访问的平均时延长度比的大小，故用命中率一个指标 作为替换策略的依据。但是在语义缓存中，缓存的粒度不是统一的页或元组，而 是满足一定条件的元组集，所以替换单位的长度不是固定的；而且语义缓存中的 命中是指缓存和查询相交、包含匹配，当缓存与查询相交匹配时，只用命中率一 个指标还不能反映命中的程度。本文用贡献率( c o m r i b u t i 0 咀r a t e ) 来表示当查 询命中时，命中的百分比。 事实上，缓存区中的数据越丰富，访问的时延长度比就越低，但是缓存空间 是有限的，不可能无限的扩大，特别在移动环境下，客户端资源非常昂贵，缓存 空间很小，用户只能留出有限的空间用于缓存。所以在语义缓存中，缓存替换的 目标就变成在缓存空间既定的情况下，降低查询的平均时延长度比。 4 2m i n v a l u e 替换策略 基于第三章的语义缓存模型和查询处理策略，现有两种类型的替换策略： ( 1 ) 一级替换策略。也就是说，按照某种评价方法对缓存区内的关系片设置 一个评价值，并且按照评价值大小对整个缓存区中的关系片进行排序，当缓 存空间不足需要替换时，则将缓存区中评价值最低的关系片替换，直到有足 1 8 语义缓存费一种替换策略 中山大学硕士学位论文 够的空闲空间容纳新的关系片。 ( 2 ) 两级替换策略。也就是说，按照一种评价方法a 对缓存区内的关系块设 置一个评价值，并且按照评价值大小对整个缓存区中的关系块进行排序；同 时，按照另一种评价方法b 为每个关系涣中的关系片设置一个评价值，并且 在每个关系块内按照评价值大小对其包含的关系片进行排序。当缓存空间不 足需要替换时，通过方法a 挑选评价值最小的关系块，并在该关系块中通过 方法b 将评价值最小的关系片替换，直到有足够的空闲空阅容纳新的关系片。 如果该关系块内的所有关系片替换后，空闲空间仍不足，通过方法a 挑选评 价值次最小的关系块，依次类推，直到有足够的空闲空间容纳新的关 系片。 使用两级替换策略时排序的时间复杂度要小于一级替换，但是当替换发生时， 一级替换是在整个缓存区内将评价值最小的关系片替换，而二级替换则不是，而 且很难找到一种好的评价方法a 对缓存区内的关系块设置评价值，所以我们的替 换策略采用第一种类型的替换策略。 基于4 1 节的目标，具体的做法是尽可能使查询在本地被解答，使得在有限的 空间内缓存最有价值的关系片，假设缓存区有n 个关系片我们用 w m e g ) ；鼠级置( 1 兰i 三n ) 来衡量关系片的价值，其中p l 表示关系片冠s 的命 中率，吼表示关系片r 写的贡献率，墨表示关系片r s 的长度( 即关系片占用空间 的字节数) 。我们称w 如e ( f ) 为关系片船。的评价值。 因此，我们所研究的m i i l v a l u e 替换策略的基本思想为：关系片飚的评价函 数为阳胁b ( f ) = b 吼墨。当新的关系片要进入缓存区，而缓存空间不足时，将 瑚胁e ( f ) ( 净1 ，2 ，n ) 值最小的关系片从缓存区替换出去，直到有足够的空 间容纳新的关系片。 由于每个关系块由一个以上的关系片组成，当关系块中的所有关系片全部被 替换出去后，在缓存中删除该关系块，当有一个新的关系片要进入缓存，而它不 属于缓存区中的任何一个关系块时，则新建个关系块。 语义缓存的一种替换策略 中山大学硕士学位论文 4 3m 酢v a l u e 替换策略的求解过程 4 3 。1 求解思路 定义4 1r 我们用丁表示客户端一次随机查询的时延长度比的期望值，令疋表示k 次查 询后，下一次随机查询的时延长度比的期望值。 根据替抉策略的目标，我们所研究的替换策略的思路是： 1 、设置关系片的权值。不失一般性，我们假设在客户端已经发生了k 次查询， 首先计算定义4 1 中的五。权值设置的原则是：假设存在一种权值设置函数为每 个关系片设置一个权值，当缓存区要替换一个关系片时，我们可以得到替换不葡 关系片时瓦的值，如果权值最小的关系片被替换后，瓦总是为最小值，则认为 该权值设置函数是最合理的，我们就采用该权值设置函数设置关系片的权值。 2 、由于权值没有考虑关系片大小，所以再计算关系片的单位权值，即权值关系 片的大小( 类似性能价格比的概念) 。这样就得到一个评价函数用于计算每个关 系片的评价值，当有新的关系片要进入缓存区两缓存空间不足对。就将缓存区中 原有的评价值最小的关系片替换出去，如果空间还不够，则将评价值次最小的关 系片替换出去，依次类推，直到有足够的空间存放新的关系片。 4 3 2 关系片权值的求解过程 设k 次查询后，缓存区有n 个关系块，第i ( 1 薹i 耋n ) 个关系块有趣个关系 片。关系块和关系片的编号如下表所示： 语义缓存的一种替换策略中山大学硕士学位论文 表4 1 关系块 关系块中的关系片 r c l硒。硒：磷j砘 r c 2冗s 2 l 船2 2 r s 2 | r s 2 ， r e 磷。r s ： r s “ r s 掘 r e碱，碱2 r s ，lr s 4 3 2 1 相关定义和定理 定义4 2f ：随机一次查询其结果集所占字节数。 为了表达方便，我们在下文把查询结果集所占字节数简称为查询的长度。 定义4 - 3 ，僻g ) ；随机一次查询命中关系块r q 时，查询被其解答部分的 长度的期望值。 由于随机一次查询不一定被缓存完全解答，所以2 2 善7 职g ) 。 定义4 4 ，( r ) ：随机一次查询命中关系片r & 时，查询被其解答部分的 长度的期望值。 定义4 5f ：随机一次查询的响应时间。 定义4 6 f c ：单位长度的查询命中缓存时，在缓存上处理所花费的时间。 由于查询为单位长度，这里的命中指查询与缓存包含匹配。 定义4 7 ：单位长度的查询没有命中缓存时，在网络上传送及服务器上 处理的时间和。 显然，在缓存区中取数据的速度快于到服务器端取数据的速度，故t ，。 语义缓存的种替换策略 中山大学硕士学位论文 定义4 8 喀：第k 次查询韵剩余查询部分。 定义4 9g ：k 次查询后，缓存区中的关系片的集合。 定义4 1 0 咋：第k 次查询中权值最小的关系片。 定义4 。n 关系块霞e 的命中率p ( r c i ) ：查询命中关系块r e 的概率。 f 1 妻i 量n ) 。 定义4 1 2 关系片r g 的命中率p 俾岛) ：查询命中关系片r g 的概率。 ( 1 i 姜n ，l 三j 耋h 0 定义4 1 3 口( 尺g ) ：关系块r c f 的贡献率。即当随机一次查询命中关系块 尺q 时，g 似g ) = ，僻g ) f 。 定义4 1 4 譬( r 岛) ：关系片r g 的贡献率。即当随机一次查询命中关系片 尺乞时，“强) 一，) f 。 随机次查询至多只能命中一个关系块，但它有可能命中某关系块中的多个 关系片，所以根据上述定义有下面结论： ( 1 ) 善p 僻c i ) s 1 ； ( 2 ) p e ) 5 薹p ) ； 定理4 1 盹) = 粪碱) 怒 证明：设客户端产生一个随机查询，其长度为，。 根据定义4 1 1 可知，口僻q ) z 的意义为当查询命中关系块r e 时，查询被关 系块霞g 解答部分的大小的期望值。所以p ( r c f ) - 口 g ) f 的意义为查询被关系块 r q 解答部分的大小的期望值。 根据定义4 1 2 可知，g ( 黜；) ，的意义为当查询命中关系片尼时，查询被关 语义缓存的一种替换策略 中山大学硕士学位论文 系片r 晶解答部分的大小的期望值。所以p ( 强) g ( r 岛) 。f 的意义为查询被关系 片r 毛解答部分的大小的期望值。所以薹p ( 嗡) 霉( 峨) 。的意义为查询被关系 块r c 解答部分的大小的期望值。 所以艺p ( 碜) q ) z p 僻c ) g 僻g ) z ， 铷耋日鸭) ，测。 4 3 2 2 设置关系片的权值 由第3 章的查询处理策略可知，查询的响应时阀f 由三部分组成；1 、查询裁 减的处理时间0 。；2 ；探头查询的平均处理时问f 一：3 、剩余查询的平均处理 时间f ，de 。 贝uf = 0 “+ f 。k + f 。m 。 由于存在各种查询优化技术加快查询裁减速度，所以在上述三种时间中，查 询裁减的处理速度最快，探头查询的处理速度次之，剩余查询的处理速度最慢， 根据在固定网络环境下的查询处理实验发现，使用查询优化技术后，剩余查询的 平均处理时间比探头查询平均时间慢了一个数量级，而探头查询平均处理时间比 查询裁减平均时问慢了也是一个数量级，所以查询裁减平均处理时问只占查询处 理总时间的很小一部分( 1 左右) ，而且在移动环境下，网络的带宽比固定网络 窄，剩余查询的速度更慢，那么查询裁减平均处理时间占查询处理总时间的比例 更小。这样我们在计算查询响应时间时，可以忽略查询裁减时间，而只计算探头 查询处理时间和剩余查询处理时间。 于是f p m + f 。，。 当客户端随机产生一个长度为z 的查询时，查询与缓存的匹配有以下两种情 况： 语义缓存的一种替换策略 中山大学硕士学位论文 ( 1 ) ：查询与缓存区中的任意一个关系块均不匹配，则将整个查询作为剩余查询 送往服务器处理。根据定义4 7 知，查询处理的时间 t = f 。m + l ，。；。= z 。 ( 4 1 ) ( 2 ) ：查询与任意一个关系块r c 匹配( 包含匹配或相交匹配) 。那么查询处理 器将查询裁减成探头查询部分和剩余查询部分，探头查询部分由缓存处理，根据 定义4 6 、4 1 3 可得，探头查询处理时间的期望值 f 础= 日( r c ：) f 。； 剩余查询部分送往服务器处理，剩余查询的处理时间的期望值 f 一。d 盯= ( 1 一口( r c ：”。f 。 那么该查询命中关系块r e 时响应时间的期望值 乇t 窖( r e 。) ；。t 。+ ( 1 一窖( r c f ) ) f 。 ( 4 2 ) 这两种情况构成互斥完备事件组。 由五的定义知，那么下一次随机查询的响应时间的期望值