コンテンツを意識する ウェブキャッシュ 成 凱、 上林弥彦 京都大学大学院 情報学研究科 社会情報学専攻 DBWeb2000合同シンポジウム (12月06日~08日・東京) 発表内容 背 景 ウェブキャッシュとその特徴 従来のウェブキャッシュ手法の欠点 セメンチックスよりアクセス傾向の推定 コンテンツを意識するウェブキャッシュ コンテンツを意識する置換手法LRU-SP+ 実験結果とディスカッション 2000年12月7日 (C)上林研究室 2 背 景 アクセススピード:ウェブユーザの最も気にな る要素(GUVインターネットユーザ調査・98) Scalability対策→キャッシュ必要不可欠 インターネット・トラフィック:ウェブは75%あまり かつ半年ぐらい倍になる しかしネットワーク帯域幅:僅か年に50%増加 サーバ能力、ネットワーク帯域幅増加だけではいけなくて 冗長データ技術(キャッシュなど)は必要不可欠 2000年12月7日 (C)上林研究室 3 ウェブキャッシュとは ウェブアクセスを効率化するミッドルウェア よくアクセスされるものをキャッシュに格納 三種類: WWW 繰り返し 再利用 2. プロキシ・キャッシュ 1. ブラウザ・キャッシュ 3. サーバ逆キャッシュ 複数ユーザ 共 有 2000年12月7日 (C)上林研究室 4 キャッシュに関する問題 置換手法→ヒット率(Hit Rate)もっと高める 1 一致性維持→コンテンツの新鮮さ コンテンツ管理→キャッシュコンテンツを共有 2 情報源として積極的利用 法的・倫理的・経済的な問題 著作権 プライバシー ウェブ広告ヒット数 2000年12月7日 (C)上林研究室 5 ウェブキャッシュの特徴 従来のキャッシュ ウェブキャッシュ キャッシュ・ユーザ システム 人 間 働く環境 CPU、OS、DBなど WWW データ単位 物理的・ブロック 論理的・ウェブページ データサイズ 単一、小さい 大きい差がある 時間制約 厳しい 余裕がある アルゴリズム 簡 単、履歴ベース 複 雑 性能測定 Hit Rate Hit Rate、Byte Hit Rate 2000年12月7日 (C)上林研究室 6 従来のウェブキャッシュ手法の欠点 利用履歴だけに基づくキャッシュ置換手法 アクセス頻度→60%一度しかアクセスしてない→判断できず アクセス時間 キャッシュ空間 観測時間が必要 新入者 被観測者 置換該当者 アクセス履歴データなしでも測定できる方法は?? 2000年12月7日 (C)上林研究室 7 提案:コンテンツを意識するキャッシュ Request/Response (Hits/Misses) ④人気内容をユーザに推薦など ① 情報要求解析 どんな内容が欲しいか? ②新規内容測定 ③キャッシュ置換 2000年12月7日 (C)上林研究室 8 新しいキャッシュ構造 子キャッシュ 制約条件 ユーザ・興味 制御部 CKBルール ストレージ ブラウジング 索 引 質問 2000年12月7日 ロード サーチ (C)上林研究室 WWW 9 ユーザ情報要求(Needs)解析 1. Most Frequently Queried 順 番 1 2 2. Most Frequently Appeared 重 み 3 3 順 番 1 2 Gambling Game 重 み 3 3 2 3 Investing 2 4 hardcore Gambling 2 4 Movie 2 5 6 Investing Game 2 1 5 6 ticket Java 1 1 3 2000年12月7日 MFQ言葉 Movie database W1 = 0.7 (C)上林研究室 MFA言葉 W2 = 0.3 10 セメンチックスよりアクセス傾向の推定 順 人気トピック 重み P 番 1 Movie 2.7 Gambling 2.3 2 3 Database 2.1 4 Investing 2.0 5 6 Game hardcore 1.6 1.4 2000年12月7日 (C)上林研究室 Document 内容による人気度 (類似度計算)) similarity ( D, P) 11 セメンチックスを利用する利点 内容による人気度推定 観察時間短縮 情報要求 キャッシュ空間 時空効率 高い 人気内容 空いている 2000年12月7日 置換該当者 非人気内容 (C)上林研究室 12 従来のウェブキャッシュ手法 アルゴリズム LRU LFU SIZE Size-Ajusted LRU Segmented LRU LRU-SP 2000年12月7日 最近度 O X X O 頻度 X O X X サイズ X X O O O O X O O O (C)上林研究室 13 コンテンツを意識するLRU-SP+ LRU-SP(Size-adjusted and Popularityaware LRU, K. Cheng et al Compsac’00) RF 1 利益 小さいものをキャッシングしない Size T RF:引用頻度; T アクセス最近度 LRU-SP+ (Content-Sensitive LRU-SP) ( RF 1) e 利益 1 小さいものをキャッシングしない Size T similarity ( D, P) 2000年12月7日 (C)上林研究室 14 LRU-SP+の実装について ③. 最終決置換 2.5KB 一番小さい ( RF 1) e 1 Size T 5KB 2.5KB ②.置換候補 時間的に最も長く 5KB 2.5KB 2.4KB/2 Hit 4KB/2 5.2KB 5.2KB/2 ①.オブジェクト分類 2000年12月7日 引用されてないもの 5.02KB Size subcache# ln( ) ( RF 1) (C)上林研究室 15 実験設計 実験内容の選択 コンテンツによる人気度測定は正確か?(実験中) コンテンツの人気度=長期的人気度?(実験中) 長期的人気度を用いてキャッシュ効率高める? 実験モデル: “コンテンツ人気度“=1+ ドキュメントAのアクセス回数 実験データでのすべてのアクセス記録数 2000年12月7日 (C)上林研究室 16 実験結果: Hit Rates LRU-SP SgLRU LRV 8 7 6 5 4 3 2 0.25 0.23 0.21 0.19 0.17 0.15 0.13 0.11 0.09 0.07 0.05 0. 15 0. 3 0. 5 0. 8 1. 5 Hit Rates LRU-SP+ Cache Sizes (% of Total Need) 2000年12月7日 (C)上林研究室 17 実験結果: Byte Hit Rates SgLRU LRU-SP LRV 8 7 6 5 4 3 2 1.5 0.8 0.5 0.3 0.25 0.23 0.21 0.19 0.17 0.15 0.13 0.11 0.09 0.07 0.05 0.15 Byte Hit Rates LRU-SP+ Cache Sizes (% of Total Need) 2000年12月7日 (C)上林研究室 18 終わりに ウェブの人間向き、ドキュメントベースの特徴 を生かし、キャッシュ(データ!)とキャッシュ の使い道(情報!)を再び検討すべき コンテンツを積極的に利用しキャッシュ効率を 高める方法は提案した。 実験的検証について コンテンツもワークロードもあるBenchmarkはな い → シミュレーション的検証は困難 実験内容を分けて、段階的にやる必要がある 2000年12月7日 (C)上林研究室 19
© Copyright 2025 ExpyDoc