Nghiên cứu một số thuật toán cho web caching và Ứng dụng

Bộ nhớ đệm Web caching là một giải pháp giảm thiểu các địch vụ và tải giao thông mạng nút cô chai, cải thiện thời gian đáp ứng yêu cầu và cải thiện các đối tượng Web có sẵn bằng cách lưu

ĐẠI HỌC THÁI NGUYÊN, TRUONG DAI HOC CONG NGHE THONG TIN VA TRUYEN THONG

Nguyễn Quang Thanh

CUU MOT SỐ THUẬT TOÁN CHO WEB

CACHING VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS.TS Nguyễn Văn Tam

Thái Nguyên, năm 2016

Truyền thông - Dai hoc Thai Nguyên, đưới sự hướng đẫn, giúp đỡ của các

cô và bạn bè đồng nghiệp, đặc biệt là sự hướng đẫn, giúp đỡ của PGS.TS

Nguyễn Văn Tam

Đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất tới PGS.TS Nguyễn Văn

Tam, người hướng đẫn khoa học, đã tận tình chỉ bảo, giúp đỡ tôi thực hiện

luận văn

Tôi xin cảm ơn các thay cô trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã giảng day và truyền đạt kiến thức cho tôi

Cuối cùng, tôi xin cảm ơn những người thân và các bạn bè chia sẻ, gúp

đỡ tôi hoàn thành luận văn này

"Mặc dù đã hết sức cổ gắng hoàn thành luận văn với tắt cả sự nỗ lực của bản than, nhưng luận văn vẫn còn những thiếu sốt Kính mong nhận được

những ý kiến đóng góp của quý Thây, Cô và bạn bè đồng nghiệp

LOICAMDOAN

LOICAM ON

PHU LUCDANH MUC CAC KI HIEU, CAC CHU VIET TAT

DANH MỤC CAC KI HIEU, CAC CHU VIET TAT

DANH MỤC CÁC HINH VE

DANH MỤC CÁC BẰNG

‘MO DAU

CHUGNG 1: TONG QUAN VE WEB CACHING

1.1 Giới thiệu web caching

1.1.1 Vấn đề tải truy cập Intemet va web caching

1.1.2 Định nghia web Caching

1.1.3, Mét s6 khai niém vé Caching

1.2 Cac kién tric web Caching

1.2.1 Kiến trúc cache phan ting và phân tán

1.2.2 Kiến trúc kết hợp (Caching lai),

1.3 Ưu nhược điểm của Web caching

1.4 Kết luận chương

CHƯƠNG 2: MỘT SỐ THUẬT TOÁN WEB CACHING

2.1 Thuật toán Least Frequently Used with Dynamic Aging (LFU-DA), 2.2 Thuật toán Greedy Dual Size (GDS)

2.3 Thuật toán Cost Effective (CE),

2.4 Thuật toán Least recently used (LRU)

CHUONG 3: KY THUAT CACHE TRONG WEB PROXY,

3.1 Cơ bản về cache trong Squid

3.1.1 Lệnh cache_địc

3.1.2 Thuật toán thay thể

3.1.3, Loại bố đối tượng Cache

3.2 Điều khiên cache trong Squid

3.2.1 Thông tin kết nổi

3.2.2 Thông tin Cache

3.2.3 Thời gian địch vụ trung bình

3.2.4 Sữ dụng tài nguyên

iv

3.2.5 Ham quan lý bộ nhớ sit dung

3.2.6 KF thuat quan If bé nhớ trong

3.2.7 Mô ti cdc file sit dung trong Squid

3.2.8 Cấu trúc đữ liệu trong Squid:

3.3 Mô hình thữ nghiệm và đánh giá kết quả

3.3.1 Cải đặt Squid

3.3.2 Thống kê, vẽ đồ thị

3.3.3 Đánh giá kết quả

3.4 Kết luận chương 3

KET LUAN VA HUONG PHAT TRIEN

TAI LIEU THAM KHẢO

PHU LUC

le Internet Service Provider

ARPANET Advanced Research Projects Agency Network

|[NSFNET National Science Foundation Network

‘eeu Central Processing Unit

LRU Least recently used

LFU-DA Least Frequently Used with Dynamic Aging

vi

DANH MUC CAC HINH VE

Hinh 1.1 Vi trí 15 Web cache

Hinh 1.2 Sơ đỏ biêu dién Proxy server cache

Hình 1.3 Vi tri dit origin server cache

Hình 1.4 Mô hình phn cap cia ISP

Hình 1.12 Thời gian truyền cho caching lai với số bộ đệm tối ưu k, p=0,8 17

"Hình 2.1 Cấu trúc một phân tử trong bảng trang 4 Hình 22 Lược đồ thay thế nội dung cache cia thudt toan LRU 25 Hình 2.3 Cầu trúc một phân tir trong bing trang 2

“Hình 2.4 Thuật toán thay thé cache LRU 3 Hình 2.5 Thuật toán thay thé cache HLRU 36

Hình 3.8 Giao điện chạy SquidclienL 6 Hinh 3.10 Cache hit va Byte hit, cing s n

DANH MUC CAC BANG

Bảng 2.1 Các thuộc tính hữu ích nhất của mỗi đối tượng lưu trữ ¡ 28

Bang 2.2 Cau tric dữ liệu chính cia LRU va HLRU 37

MỞ ĐẢU

LLY DO CHON DE TAI

Ngày nay, World Wide Web (WWW) ngiy cảng phất triển đi sâu vào

mọi ngõ ngách cuộc sống hiện đại, là phương tiện truy cập mạng đơn giản,

thân thiện với người sử đụng Việc sử đụng dich vụ Web đang tăng theo cấp

số mũ, lưu lượng WWW trên các mạng Internet quốc gia và quốc tế cũng ting

đột biến Và Việt Nam cũng không nằm ngoài vòng xoáy của con Ibe WWW cổng giao tiếp điện tử đang là những ứng đụng mới và đang được phát triển Trong tương lai, các ứng đụng này cảng phát triển hơn cũng sự phát

triển của hạ t

ig mạng máy tính và đồi hỏi nền tăng công nghệ thông tin ngày, cảng cao Tuy nhiên để có được điều đó không phải là vấn đề đơn giãn Hiện tại mạng may tính tại Việt Nam ngày càng phát triển, tuy nhiên với điều kiện

của nước ta, cơ sở vật chất hạ tầng mạng máy tính còn thấp kém Chất lượng

địch vụ và thời gian đáp ứng có thể được cải thiện bằng cách giảm tải cho

‘mang, mét trong số đồ là phương pháp sử dụng kỹ thuật Webcaching Kỹ thuật Web caching ra đời nâng cao được hiệu qua trong việc thực hiên ting

tốc các ứng dụng WWW

‘Ban than lam công việc quản lý hệ thống mạng với mong mui

nghiên cứu về hạ ting mang cơ sỡ, tôi lựa chọn dé tai: “Nghiên cứu một số thuật toan cho Web Caching và ứng đụng”

Luận văn trước tiên nghiên cứu một wat toan Web Caching Trén

cơ sở đó, luận văn nghiên cứu và trình bày thuật toán LRU trong phần mềm Squid proxy để nâng cao hiệu quả ứng dụng WWW của hệ thống Cuối cùng

là chương trình thử nghiệm và đánh giá kết quả của thuật toán LRU trong 'Squid proxy tại ngân hàng Vietinbank chỉ nhánh đèn Hùng - tỉnh Phú Thọ

II MỤC TIÊU, ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU

+ — Mgetiêu

‘Nim bit co bản được các thuật toán Web Caching và các ứng dụng của

phương pháp này,

- Tìm hiểu xây đựng thuật toán LRU trong việc thử nghiêm Web Caching

- Cải đặt thử nghiệm

II PHƯƠNG PHÁP NGHIÊN CỨU

~ _ Phương pháp nghiên cứu tài liệu, phân tích, tổng hợp

- Phuong phap trao đổi khoa học, lấy ý kiến chuyên gia

- Phương pháp thực nghiệm và đối chứng qua chương trình thử, nghiệm

CHƯƠNG 1: TONG QUAN VE WEB CACHING

LL Giới thiệu web caching

1.11 Vấn để tải truy cập Internet và web caching

111

để tải truy cập Internet

Tiên thân của mạng Internet ngày nay là mạng ARPANET Thuật ngữ

"Taternet" xuất hiện lẫn đầu vào khoảng năm 1974 Lúc đó mạng vẫn được goi là ARPANET Năm 1984, ARPANET được chia ra thành hai phần: ARPANET và MILNET Đến năm 1980, ARPANET được đánh giá là mạng trụ cột của Iaternet Giữa thập niên 1980 thành lập mạng liên kết các trung tâm máy tính lớn với nhau gọi là NSENET Sự hình thành mạng xương sống của NSFNET và những mạng vùng khác đã tạo ra một môi trường thuận lợi cho sự phát triển của Intemet Tới năm 1995, NSENET thu lại thành một

mạng nghiên cứu còn Internet thì vẫn tiếp tục phát triển Các dịch vụ trên

Internet khéng ngừng phát triển tạo ra cho nhân loại một thời kỷ mới: thời kỳ thương mại điện tử trên Internet

‘Viet Nam là nước có tốc độ tăng trưởng số người đùng internet trong

tốp 10 nước có tốc độ tăng trưởng số người đùng nhanh nhất khu vực châu Á

và cũng là một trong những nước có tốc độ tăng trưởng lớn so với thế giới

(giai đoạn 2000-2009), tăng 10,662.2 %

“Xu hướng tăng trưởng Internet Việt Nam

Tính từ năm 2003, trung tầm TNTERNET Việt Nam (VNNIC) thuộc

Bộ thông tin và truyền thông, đã nghiên cứu và thống kê số liệu phát triển Internet tai Viét Nam theo băng đưới đây [S]

Tang dung lwong truyé

Tang dung lvong truyén dan là việc đầu tư, nâng cấp đung lượng truyền dẫn Việc này sẽ triển khai đơn giản, nhanh nếu có sẵn các hệ thống truyền dẫn tuy nhiên nó sẽ trở nên phức tạp nếu hệ thống truyền dẫn không có sẵn

'Ngoài ra chỉ phí thuê kênh quốc tế cũng rất đất, việc vận hành khai thác các kênh truyền

Sử dụng thiết bị quản lý băng thông:

định mức độ băng thông cụ thể cho từng loại

hình địch vụ Việc sử dụng thiết bị quản lý băng thông nay có thé ấn định

được mức độ băng thông cụ thể cho từng loại địch vụ tuy nhiên chỉ phí đầu tư

hệ thống cũng không nh Bên cạnh đó nếu băng thông không đủ lớn thì sẽ có

những địch vụ bị änh hưởng đến chất lượng đo bị lấy băng thông để dành cho

địch vụ tu tiên, như vậy không thỏa mãn được tối đa nhu cầu người sử dụng

Sữ dụng các hé théng Web Caching:

"Ngày nay, World Wide Web (WWW) ngày cảng phat triển đi sâu vào mọi ngõ ngách cuộc sống hiện đại, nhu cầu của người sử đụng ngày cảng đòi hỏi nhiều hơn các về chất lượng địch vụ mã nô cung cấp để chạy nhiều loại hình ứng đụng khác nhau Bộ nhớ đệm Web caching là một giải pháp giảm

thiểu các địch vụ và tải giao thông mạng nút cô chai, cải thiện thời gian đáp ứng yêu cầu và cải thiện các đối tượng Web có sẵn bằng cách lưu trữ một bản sao cache lưu trữ những đối tượng có thể sẽ sử đụng tới trong tương lai

Trong những năm gần đây, nhiều nghiên cứu đã được dành riêng đễ nâng cao

hơn nữa hiệu suất của Web và cung cấp nhiều địch vụ khác nhau cho người

sử dụng Tuy nhiên, nhiều việc cần phải được thực hiện khi cung cấp nhiều

cấp độ địch vụ trong proxy cache, nó đóng một vai trò quan trọng trong việc đây nhanh hiệu suất Web

Khi sử dụng giải pháp này, chúng ta sẽ tiết kiệm được băng thông

WAN do việc đưa thông tin về gần với người sử đụng Đám bảo và nâng cao chất lượng truy nhập vì thời gian đáp ứng dịch vụ nhanh Tuy nhiên nếu hệ

'thống không đủ lớn cũng có thê gây đến việc thường xuyên bị quá tải, có thé

ảnh hưởng tới hoạt động của địch vụ Do đặc thủ riêng của từng ISP mà mỗi ISP c6 cách lựa chọn giãi pháp nâng cao chất lượng mạng riêng của mình Và

‘Web caching là một trong những giải pháp như

1.1.2 Dinh nghĩa web Caching

`Web caching (bộ nhớ đệm WEB) là việc lưu trữ bản sao của những tài ligu web sao cho gần với người đùng, cd về mặt chite ming trong web client hoặc những máy chủ bộ đệm lưu trữ riêng biệt Cache (bộ đệm) được chia thành các loại: Browser cache (b6 đệm trinh duyét), Proxy Cache (b6 dém iy nhiệm), Gateway cache (bộ đệm cổng vào) [1]

Cơ chế hoạt động WebCaching sử đụng một bộ nguyên tắc để xác định

thời điểm cung cấp các đối tượng (hay các tài liệu Web), tất nhiên là với điều

y

~ Nô cô thời gian tồn tại (hoạt động theo đạng một loại bộ đếm) còn

nằm trong khoảng thời gian fresh (chưa quá hạn)

- Néu mét browser cache da timg hién thị đối tượng và đối tượng này

đã được đánh dấu là đã kiếm tra trong một phiên trước đó

- Nếu proxy cache mới xử lý nó gần đây và nô đã được sửa đôi trước

đồ tương đối lâu, các đối tượng fresh được lấy trực tiếp từ cache mà không cần kiểm tra với server gốc

+ Nếu một đối tượng được coi là cũ, server gốc sẽ được yêu cầu xác nhận đối tượng hoặc báo cho cache rằng đối tượng đó vẫn còn giá trị sử đụng 1.1.3 Một số khái niệm về Caching

‘Web caching giit lại một bin sao của các trang web ở những noi gần với người dùng cuối Bộ đệm Caches được tìm thấy trong các trình duyệt và

trong bat kỳ web trung gian giữa đại lý người đùng và máy chủ gốc Thông

thường, một bộ đệm cache nằm ở client (tình duyệt cache), máy chủ proxy (proxy cache) va may chủ gốc (máy chủ cache) như thể hiện trong hình sau

H1

Hình 1.1 Vị trí của 6 nho Web cache Browser cache

Browser cache nim trong cic client Browser cache hay còn được gọi

là bộ dém trinh duyét Những trình duyệt như IE, Moziila, Firefox chúng ta

đùng để truy cập mạng, đều có sẵn một thư mục trong đó các nội đung đã được tải về sẽ được lưu đề sử đụng trong tương lại Bộ nhớ cache này rất hữu

ích, đặc biệt là khi người sử đụng nhấn vào nút "back" hoặc bấm vào một liên

kết để xem một trang mà họ đã xem qua Ngoài ra, nếu người đùng sử đụng

các hình ảnh chuyển hướng như nhau trong cả trình duyệt, họ sẽ được phục

vụ từ cache trình duyệt gằn như ngay lập tức

Proxy server cache

Proxy server cache 1a may chi caching trung gian nhim giảm tải lưu

lượng trên đường truyền Web Proxy Cache (b§ dém Web Proxy) làm việc cùng nguyên tắc với Browser Cache nhưng ở quy mô lớn hơn Nó được tìm thấy trong các máy chủ proxy giữa các máy client và máy chủ gốc Né hoạt động trên nguyên tắc tương tự của trình đuyệt bộ nhớ cache, nhưng nó cô một

quy mô lớn hơn nhiều Không giống như các cache của trình đuyệt chỉ có một người sử đụng đuy nhất, các proxy phục vụ hàng trăm hoặc hàng ngàn người

sử dụng theo cùng một cách Khi nhận được yêu cầu, các proxy server sé

kiểm tra bộ nhớ cache của nó Nếu đối tượng cô sẵn, nó sẽ gửi các đối tượng cho khách hàng Nếu đối tượng là không có, hoặc đã hết hạn, các máy chủ

èu cầu các đối tượng từ máy chủ gốc và gửi nó cho khách hàng

proxy sẽ ÿ

“Hình 1.2 Sơ đồ biểu diễn Proxy server cache

Origin server cache

Ngay cả tại các máy chủ gốc, các trang web có thể được lưu trữ trong một bộ nhớ cache phía máy chủ để giảm sự cần thiết cho các tính toán đự

phòng hoặc cơ sở dữ liệu có khả năng tìm lại Do đó, việc tãi server c thể

được giảm bớt nếu bộ nhớ cache máy chủ gốc cũng làm việc Origin server

cache (Gốc máy chủ cache) là máy chủ caching nằm trước các Web server

(máy chủ web) nhằm giảm tải cho các web server Nô thường được biết đến

a 1a “reverse proxy cache”

Hinh 1.3 Vi tri dat origin server cache

Các bộ nhớ dém proxy được sử dụng rộng rãi bởi các quản trị mạng

máy tính, các nhà cung cấp công nghệ, và các đoanh nghiệp để giảm sự chậm trễ sử đụng và để giảm bớt tắc nghẽn Internet

12 Các ki

trúc web Caching

1.2.1 Kiến trúc cache phân tầng và phân tán

Kiến trúc phân tầng: mỗi một thành phần của mạng được xem như một

hệ thống gồm nhiều tầng, và mỗi một tầng bao gồm nhiều chức năng truyền

thông Các tầng được chỗng lên nhau, số lượng và chức năng phụ thuộc vào

các nhà sản xuất và thiết kế Tuy nhiên quan điểm chung là trong mỗi ting co nhiều thực thể ( các tiến trình) thực hiện một số chức năng nhằm cung cấp một số địch vụ, thủ tục cho các thực thể tầng trên hoạt động

Kiến trúc phân tán là tổ hợp bao gồm cá máy tính độc lập với trình điễn

hệ thống như một máy tính đơn trước người đùng Do đồ có các đặc điểm cơ

‘ban 1a: tinh chia sé tài nguyên, tính mỡ, khả năng song song, tinh mỡ rộng,

'khã năng thứ lỗi, tính trong suốt

Kiến trúc phân tầng có thời gian kết nối nhỏ hơn kiến trúc phân tán Bởi vì trong kiến trúc phân tầng các bản sao của một trang được lưu trữ một cách dư thừa tại các hệ thống cache ở các cấp độ mạng khác nhau dẫn tới giảm được thời gian kết nói Ngược lại kiến trúc phân tán có thời gian truyền nội đung của trang Web thấp hơn kiến trúc phân tầng, bởi vì trong kiến trúc

phân tán lưu lượng Web được lưu chuyển trên các ting mang phía đưới và ít

Chúng ta xây dung topology của mạng đưới đạng cấu trúc cây diy đủ

Hình 1.5 Mô hình phân cấy trong đó:

~ O đại điện cho độ mở (số nhánh) của mỗi nút trong cấu trúc cây

- H là số đường kết nối mạng giữa nút gốc của mạng quốc gia với nút gốc của mạng cấp vùng H cũng đại điện cho số đường kết nói giữa nit 26

của mạng cấp vùng với nút gốc của mạng cấp khu vực

~Z là số kết nối giữa máy chủ gốc và nút gốc

- 1 là số cấp của cây (0< 1<2H+z) trong đó:

*_ 1=0lã mức mạng của các bộ đệm cơ quan

- Ci, Ca, Cy là tốc độ truyền đẫn (transmission rate) của các kết nối ở

‘mang co quan, ving, quốc gia

~ C: tỷ lệ nghẽn nút cổ chai trên đường truyền dẫn quốc tế

Kiến trúc phân tầng

u

Hinh 1.6 Sơ đồ đầy đủ một

én tric phan tang Web Caching ciia mét ISP

He thống cache thường được đặt tại diém truy nhập giữa hai mạng khác nhau để giảm chỉ phí truyền trang qua một mang mới Tại một nước thì chỉ có

một mạng quốc gia và một hệ thống cache quốc gia Vậy sẽ có O” mạng vùng

và mỗi mạng sẽ có một hệ thống cache cấp vùng Cô O*# mạng khu vực và mỗi mạng sẽ có một hệ thống cache cấp khu vực

Hệ thống cache được đặt ở độ cao 0 của cấu trúc cây tương ứng cấp độ

1 trong kiến trúc phân tầng, độ cao H của cấu trúc cây tương ứng cấp độ 2 trong kiến trúc phân tầng, độ cao 2H của cấu trúc cây tương ứng cấp độ 3

trong kiến trúc phân tằng Cache được nói tới các ISP qua các kênh truy nhập Chúng ta giã sử rằng dung lượng kênh truy nhập tại mỗi cấp độ bằng dung

lượng kênh trung kế của mạng tại cắp độ đó nghĩa là Cụ, Cz, Cx va C cho từng

cấp độ tương ứng Tỷ lệ hit tại hệ thống cache của các cấp khu vực, vùng,

quốc gia được đại điện bởi các giá trị: hit, hits, hit; (hít: số phẩn trăm yêu cầu được đáp ứng ở mức bộ đệm)

Cache chỉ được đặt tại cấp khu vực và sẽ không cô bản sao trung gian

của các trang Web tại các cấp mạng khác ĐỂ chia sẽ các bản sao giữa các hệ thống cache khu vực, hệ thống cache tại cấp mạng trung gian sẽ lưu giữ dit liệu meta-data nó chứa đựng thông tin về nội dung được lưu trong các hệ ống cache khu vực Các cache khu vực trao đổi định kỷ lượng thông tin

meta-data về các tài liệu mà chúng lưu trữ Chúng ta giả sử rằng các thông tin

1à thường xuyên cập nhật tại tắt cả các cache khu vực khi mà cô một tài liệu

mới được lầy về ở bắt kỹ cache nào

1.2.1.1 Thời gian kết nối T

Thời gian kết nói là phân đầu tiên của độ trễ khi truy vấn lấy văn bản

(nội đung) Chúng ta giã s thời gian kết nối chỉ phụ thuộc vào khoảng cách

từ client đến với văn bản xét trên phạm vi mạng lưới Thời gian kết nói đến

một văn bản cô độ phổ biến 2„ đối với trường hop sit dung caching phân tán

và caching phân cấp Khoảng thời gian cập nhật trong trường hợp này A= 24

giờ; thời gian cập nhật cảng dài thì số lượng các yêu cầu càng tăng Tuy nhiên

hiệu năng tương đối của mô hình caching phân tán và caching phân cấp vẫn

tương đương nhau

Trước hết, với một văn bản không phô biến (2s nhỏ), cả hai mô hình

phân tần và phân cấp đều có thời gian kết nối khá cao đo yêu cầu kết nối phải chuyển tới máy chủ chứa văn bản đồ Khi một văn bản hay được truy cập, thời gian kết nối của mô hình phân tán và mô hình phân cấp là rất gần nhau

đo xác suất văn bản được tìm thấy ở máy chủ caching ở biên mạng cao

1.2.1.2 Thời gian truyền T

Phan bé của lưu lượng được tạo ra bởi mô hình caching phan tan B4 va

mô hình caching phân cấp ÿ ở tất cả các cấp độ mạng Với N=250 triệu trang

‘Web, phan bé theo luật Zipf Thời gian cập nhật một trang là A=24h Tổng lưu lượng mạng O'* 81000 truy nhập/s Chúng ta cố định kích thước trang

S=15KB Ta tính được tỷ lệ hit tại mỗi cấp độ cache hit=0.5, hitạ=0.6 và

hit70.7

"Mô hình caching phân tin gây tăng gấp 2 lần băng thông ở các mức

mạng thấp và sử đụng nhiều băng thông hơn ở mức mạng quốc gia so với mô

hình caching phân cấp Tuy nhiên, lưu lượng ở những nút mạng bị nghén lại

13

được giảm đi chỉ còn 1/2 Chúng ta thiết lập băng thông mạng ở cấp khu vực

C¡= 100Mb/s Mạng ở cấp độ quốc gia và vùng cô băng thông như nhau Cxy

Cạ Chúng ta không cố định hai băng thông này mà chỉ xem xét độ nghền mạng p

của hai mạng này

Chúng ta thay đôi mức độ sử dụng băng thông p của các kết nối mạng cấp quốc gia trong kiến trúc caching phân cấp) Kết nối quốc tế thường xuyên

nghén và cô mức độ sử đụng băng thing (10™ (1-hity)S/C) = 0.95

Nút thắt cỗ chai lưu lượng đuy nhất trên đường kết nói từ client đến máy chủ gốc là đường kết nói quốc tế Chúng ta quan sát thấy hiệu năng của

mô hình phân tân và phân cí 1g nhau vì không cô kết nối bị nghẽn

cao ở các mạng cấp vùng và cấp quốc gia Mô hình caching phân tán có thời gian truy én din thấp hơn phân cấp vì có nhiều yêu cầu được thỏa mãn ở các mức mạng không bị nghẽn

1.2.1.3 Thời gian trễ tông thể

"Thời gian trễ tổng thể là tổng thời gian kết nối và thời gian truyền dẫn _Với các văn bản lớn, thời gian trễ tổng thể sẽ xấp xỉ với thời gian truyền dẫn

'Với các văn bản nhỏ, thời gian truyền đẫn rất nhỏ và trong trường hợp này,

rễ é xi với thời gian kết nói Mô hình mạng phân tầng

(phân cấp) cô thời gian trễ thấp hơn với các văn bản nhỏ hơn 200KB do mô

tình mạng caching phân cấp có thời gian kết nổi thấp hơn mô hình caching phân tán Tuy nhiên mô hình mạng caching phân tán có thời gian trễ thấp hơn

trong trường hợp các văn bản có kích thước lớn do thời gian truyền dẫn của

mô hình này nhỏ hơn

"Mức ngưỡng của đung lượng văn bản phụ thuộc vào mức độ nghẽn của

mạng quốc gia Nghẽn càng lớn thì với mức ngưỡng kích thước văn bản càng nhỏ, mô hình caching phân tán có độ trễ nhỏ hơn mô hình caching phân cấp

1.2.1.4 Băng thông sử dụng

Tính toán lượng băng thông sit dung đựa trên số lượng đường link (tiên

kết) cần thiết để gửi trả về 1 gói tin cho clients (khách hàng) Mô hình

caching phan tin sit dung nhiều băng thông hơn mô hình caching phin cấp trong mạng cấp Tuy nhiên lưu lượng mạng được phân tán tốt hơn với phần lớn băng thông được sử đụng ở các mức mạng ít nghẽn Ngoài ra các mô hình

caching phân cấp sử dụng ít kết nói hơn trong mạng cấp vùng đo các văn bản được tìm thấy ở máy chủ caching cấp vùng Ở cấp mạng quốc gia cũng tương

các hướng tiếp cận chỉ sử dụng các chủ caching ở mức biên và máy trạm để cung cấp ứng đụng nội dung thường có hiệu năng kếm xét về mặt băng thông hơn các hướng tiếp cận khác

1.2.2 Kiến trúc kết hợp (Caching lai)

Hinh 1.8 So a Hybrid Web Caching của một ISP

Kiến trúc cache lai là kiến trúc cô một số lượng xác định k cache liên kết tại mọi mức mạng của kiến tric phan ting

1.2.2.1 Thời gian kết nối Te

Thời gian kết nói trong kiến trúc kết hợp phụ thuộc vào số lượng cache kết hợp k tại mỗi cấp mạng Số lượng cache kết hợp tại mỗi cấp thay đôi từ 1 tới O#= 64 (toàn bộ số lượng cache bên cạnh trong cùng một cấp độ cache kết

hợp) Hình đưới cho ta thấy thời gian kết nối trung bình cho toàn bộ N trang

web, phụ thuộc vào số cache kết hợp

Hinh 1.9 Thời gian kết nối trung bình cho toàn bộ N trang Web, phu thuéc

vào số cache kết hợp k Khả năng tìm thấy một trang tại hệ thống cache bên cạnh gần đấy là rất nhỏ, như vậy phần lớn yêu cầu được cache cấp trên phục vụ với một khoảng cách H Khi số cache kết hợp tăng lên, thời gian kết nối giảm tới một giá trị

nhỏ nhất Bởi vì khả năng đễ truy nhập được một trang tại hệ thống cache bên cạnh gần hơn so với hệ thống cache cấp trên Tuy nhiên khi số cache két hop

tăng quá ngưỡng k,=4, thì thời gian kết nối tăng rất nhanh bởi vì trang được yêu cầu từ hệ

thống cache bên cạnh có khoảng cách mạng lớn Số lượng cache kết hợp tối

ưu k; để tối thiểu hóa thời gian kết nói là số lượng cache mà khoảng cách mạng gần hơn so với mạng cấp trên: k,=OfZ2)

C6 thể thấy kiến trúc hỗn hợp với số kết nói tối ưu k có thời gian kết

nối nhô hơn kiến trúc phân tần và thậm chí nhỏ hơn kiến trúc phân tầng trong một khoảng lớn

1.2.2.2 Thời gian truyền Tr

Tình 1.10 biéu din cho thoi gian truyền của tắt cả N trang Web phụ thuộc vào số cache kết hợp tại mí

Tình 1.11 Thời gian truyền của N trang Web

Sau khi xem xét hai trường hợp mạng cấp quốc g gia không nghẽn (

điểm nút cỗ chai là các đường quốc tế, và mạng cắp quốc gia nghén (p

chúng ta nhận thấy rằng khi mạng quốc gia không nghẽn thi sự thay đổi

8)

lượng cache kết hợp không ảnh hưởng đến thời gian truyền Tuy nhiên khi

mạng quốc gia bị nghẽn thì thời gian truyền phụ thuộc nhiều vào số lượng

cache kết hợp tại mỗi cấp mạng Nếu số lượng cache kết hợp rất nhỏ, thì có ít khả năng trang Web được lấy từ cache bên cạnh Các trang phần lớn được lấy

ti cache cấp trên qua các đường kết nối ở mức trên cũng bị nghẽn nặng Khi

số cache kết hợp tăng, khả ning dé nhận một trang tại hệ thống cache bên

cạnh tăng và như vậy thời gian truyền nhỏ đi Nếu số cache kết hợp vượt qua ngưỡng k=16, thời gian truyền lại tăng lại bởi vì các trang Web sẽ được nhận

qua các cô khoảng cách lớn

và các đường kết nối bị nghẽn nặng Số cache kết hợp tối ưu kt để tối thiểu

hóa thời gian truyền phụ thuộc vào số lượng cache kết hợp có thể đạt được mà

không làm nghẽn các kênh kết nồi

Trong trường hợp kênh ở lớp trên cùng của mạng cấp quốc gia bị nghẽn, số lượng cache kết hợp tối ưu tại mỗi cấp là k, =16 Giá trị này tương ứng với số cache vùng có thê kết hợp với nhau để đáp ứng yêu cầu truy nhập

mà không cần phải đi đến các đường kết nối cấp quốc gia: k, = Of”

'Thời gian trễ tông thể

'Với trường hợp các trang kích thước nhỏ thỉ số cache kết hợp tối ưu

gần với giá trị &., bởi vì & tối thiểu thời gian kết nối Với trường hợp các trang kích thước lớn thì số cache kết hợp tối ưu gần với giá trị &, bởi vì & tối

thiểu thời gian truyền Với một kích thước bắt kỹ thì số lượng cache kết hợp

tối ưu để tối thiêu hóa thời gian trễ có gid tri Ree:

fe shape she

"em phụ thuộc vào kích thước trang, giá trị Ken thay đổi trong khoang

6 Với các trang cô kích thước nhỏ hơn hoặc bằng vài KB thi

Kiến trúc kết hợp với số cache kết hợp tối ưu có tổng thời gian trễ nhỏ hơn kiến trúc phân tầng và kiến trúc phân tán

“và

1.2.2.4 Bang thông sir dung

Băng thông sử dụng trong mô hình caching lai nhỏ hơn so với băng thông sử đụng trong mô hình caching phân tán với các mức độ phổ biến

khác nhau của nội đung được yêu cầu trong các mạng cấp vùng và cấp quốc

gia Nguyên nhân của kết quả này là do có thêm các máy chủ caching trung

gian giúp giảm đáng kế băng thông sử đụng, cũng giống như trong trường

hop sit dung multicast ở lớp ứng dung Hiệu năng của mô hình caching lai so

với mô hình caching phân cấp phụ thuốc vào số lượng máy chủ caching

công tác Đặc biệt trong trường hợp có š = š, = 2 máy chủ caching cộng tic,

băng thông sử đụng của mô hình caching lai thậm chí còn nhỏ hơn băng thông sử dụng của mô hình caching phân tân (khoảng 1.2 lẫn với các văn bản

cô mức độ phổ biến trung bình) Chú ý rằng, với È = š, = , số lượng các

chuyển tiếp trung gian của một yêu cầu caching được giảm thiểu Khi cô &

*&= i6 máy chủ caching cộng tác để giảm thiêu thời gian truyền dẫn trong

trường hợp mạng nghẽn, băng thông sử đụng tăng nhẹ (khoảng 7.3 lần với các vin bản cô độ phổ biến trung bình) so với mô hình thu ân phân cấp do sẽ

cô các trường hợp phải lấy thông tin từ các máy chủ caching ở xa đề tránh các đường kết nối bị nghẽn ở mức trên [7]

1.3 Ưu nhược điểm của Web caching

Ưu điểm:

‘Web caching 14 mét trong những giải pháp thành công nhất trong việc

nâng cao hiệu suất của hệ thống trên nên web Trong Web caching, đối tượng web phổ biến đô có thê được truy cập trong tương lai gần được lưu trữ ở các

vi trí gần gũi hơn với người sử đụng như máy khách hoặc máy chủ proxy

‘Nhu vay, bộ nhớ đệm Web giúp trong việc giảm địch vụ nút cổ chai, làm giảm lưu lượng truy cập qua Internet và cải thiện khả năng mỡ rộng của hệ

thống Web Các bộ nhớ đệm Web có ba lợi thế hấp dẫn cho người tham gia 'Web, bao gồm cả người đùng cuối, các nhà quản lý mạng, và người thiết kế

nội dung:

a Web caching làm người sử dụng giảm cảm nhận độ trễ: bởi vì những

đáp ứng có sẵn trực tiếp cho các yêu cầu đã được lưu trữ, và gần với client

được phục vụ hơn Bởi vì yêu cầu được thỏa mãn tại cache (gần với client

hơn) thay vì từ server chính, nó giảm được thời gian cho client để lấy và hiễn thị đối tượng Nó làm cho các web sites đường như đáp ứng nhanh hơn

'b Web caching làm giảm băng thông sử đụng mạng: bi vì một

cầu và đáp ứng cần phải thông qua mạng máy tính Mỗi đối tượng chỉ nhận được từ server khi có yêu cầu, web caching làm giảm một lương băng thông

chiếm đụng bởi client Việc này giúp tiết kiệm tiền nếu client phải trả tiền cho

Các tru điểm của web caching là chính, tuy nhiên Web caching cũng

đồi hôi cai tiến bổ sung so với các hệ thống web thông thường như:

- Đầu tư thiết bị ví đụ Prosy Server

- Thay đôi phần mềm của client để có thể truy nhập Proxy

Theo 46, web caching là một trong những giải pháp thành công nhất trong

việc nâng cao hiệu suất của hệ thông trên nền web

‘Web caching (bộ nhớ đệm WEB) là việc lưu trữ bản sao của những tài ligu web sao cho gần với người đùng, cả về mặt chức năng trong web client hoặc những máy chủ bộ đệm lưu trữ riêng biệt Cache (b6 đệm) được chia thành các loại: Browser cache (b6 đệm trinh duyét), Proxy Cache (bộ đệm ủy nhiệm), Gateway cache (bộ đệm cổng vào) Các kiến trúc web caching gồm có: kiến trúc cache phân tầng và phân tần; kiến trúc kết hợp (kiến trúc la),

‘Web caching cé rat nhiều ưu điểm như giúp người đùng giảm cảm nhận

độ trễ, làm giãm băng thông sử đụng mạng, giảm tải trên máy chủ gốc, đồng

thời làm cho web kinh tế hơn và tối ưu hơn.

CHUONG 2: MOT SO THUAT TOS

N WEB CACHING

"Thuật toán bộ nhớ đệm, hay thuật toán thay thể đã được mô tả và phân tích kể từ khi bộ nhớ xử lý bộ nhớ đệm được phát minh Sự kết hợp của các

thuật toán thay thế và khối lượng công việc được cung cấp xác định hiệu quả

của bộ nhớ cache trong việc tối ưu hóa việc sử đụng tài nguyên hệ thống

"Nhiều thuật toán bộ nhớ đệm đã được thiết kế cho những tác vụ Web

Thuật toán thay thế bộ nhớ cache đồng một vai trò cực kỳ quan trọng

trong Web caching Do đó, việc thiết kế các thuật toán thay thế bộ nhớ cache

hiệu qua 1a cin thiét dé dat được cơ chế rất tính vỉ trong bộ nhớ đệm Nói chung, thay thế bộ nhớ cache, thuật toán này cũng được gọi là thuật toán bộ nhớ đệm Web,

“Khi kích thước của bộ nhớ cache là hạn chế, một thuật toán thay thể bộ

nhớ cache là cần thiết để xử lý nội dung bộ nhớ cache Nếu bộ nhớ cache là đầy đủ khi một đối tượng cần phãi được lưu trữ, thuật toán thay thế sẽ xác

định đối tượng là bị loại bỏ đễ cho phép không gian cho các đối tượng mới Các thuật toán thay thể tối ưu làm cho việc sử đụng tốt nhất không gian bộ

nhớ cache có sẵn, để cải thiện t lệ hit cache, và để giảm tải trọng trên máy

chủ gốc [2]

2.1 Thuật toán Least Frequently Used with Dynamic Aging (LFU-DA) FU-DA là thuật toán đựa trên tần suất truy nhập, trong đó giả định chỉ phí và kích thước của trang là không đổi Trong thuật toán LFU, quyết định loại bỏ nội đung một trang căn cứ vào số lẫn truy nhập đến trang đỏ Việc

đếm số lần truy nhập của tắt cả các trang trong cache được lưu lại và trang có

số lần truy nhập đến nhỏ nhất sẽ bị loại bỏ Thuật toán LFU-DA được mỡ xông từ LFU bằng cách sử đụng thêm thuật toán tuổi động ( Dynamic Aging ) Qua thực nghiệm người ta quan sit được tỷ lệ byte hít ( là tỷ lệ giữa tổng kích thước trang Web được yêu cầu có nội dung nằm sẵn trong cache với tổng kích thước trang Web được yêu cầu) của thuật toán LFU-DA 1a kha cao

Hầu hết các máy chủ Web proxy vẫn quan tâm với thuật toán bộ nhớ

đệm truyền thống Những thuật toán này thường là phù hợp trong bộ nhớ đệm

21

cache truyén thống như CPU và hệ thống bộ nhớ do, nhưng họ không phải là hiệu quả trong lĩnh vực Web caching Các cách tiếp cận quản lý bộ nhớ cache đơn giãn nhất và phổ biến nhất là thuật toán Least recently used (LRU), trong

đồ loại bô các đối tượng ít truy nhập nhất cho

khi truy cập có đủ không

gian cho các đối tượng mới LRU là đễ đàng để thực hiện và thành thạo để

thống nhất kích thước các đối tượng, giống như bộ nhớ Cache Tuy nhiên, nỗ không thực hiện tốt trong Web caching vi nó không xem xét các kích thước

hoặc tải về độ trễ của các đối tượng Least Frequently Used with Dynamic

Aging (LFU) là một bộ nhớ đệm web phổ biến mà việc thay thể các đối tượng với số lượng ít nhất của người truy cập LFU giữ các đối tượng web phổ biến

và loại bỗ các đối tượng ít được sử đụng hơn Tuy nhiên, LFU bị ô nhiễm bộ nhớ cache trong các đối tượng với các tài khoản tham chiếu lớn, mà không

giờ được thay thể, ngay cả khi họ không tái truy cập lần nào nữa

2.2 Thuật toán Greedy Dual Size (GDS)

Thuật toán này đã tính đến sự thay đổi của chỉ phí và kích thước của trang Việc loại bé trang khỏi hệ thống được căn cứ trên tỷ lệ giữa kích thước và chỉ phí của trang Cũng giống nhw thuat toan LFU-DA, GDS gin mot

gi trị H(p) với một trang p trong cache Khi một trang mới được lưu vào

trong cache hoặc khi một trang đang nằm trong cache được truy nhập lại thì

gid tri H(p) được cập nhật lại

đồ Ï được đặt bằng giá trị Hp) cia trang bị loại bỏ Tuy nhiên cũng giống

như 7#, GDS không tính đến tần suất truy nhập

2.3 Thuật toán Cost Effective (CE)

được tài liệu

‘hin chung, những người sử đụng Internet có thé được chia 2 nhóm như sau:

(0 Khách hàng tìm kiếm thời gian đáp trả ngắn hơn

Thuật toán CE được đưa ra để giảm toàn bộ chỉ phí

(đi) Khách hàng tìm cách tối đa hóa sit dung bing thông (vi dụ một Internet Service Provider, ISP)

‘Vivay, c6 hai mô hình chi phí đề tối ưu hóa proxy cache cho hai nhóm

mục tiêu sử đụng Thứ nhất, một mô hình độ trễ mà có thể đo độ trễ tải về

của người đùng cuối, và thứ hai là một mô hình lưu lượng truy cập mà cô thể

đo được lưu lượng mạng

Cö thể xác định tỷ lệ giảm chỉ phí (CRR) abu sau:

Hx, cRr- LEX «109%

zc với Hi =] néu yéu clu i 14 Hit còn lại la Hi=0; C; la chi phi ld y được đối tượng í

Có thể xác định chỉ phí như là độ trễ tải về quan sát được của người đùng trong mô hình độ trễ, và là số lưu lượng mạng được tạo ra trong mô hình

lưu lượng Trong CE, giá trị lợi ích (Beneñt Value-BT) được gần cho mỗi đối

tượng, biểu tầm quan trọng của nó trong cache Khi cache đầy, các đối

tượng với BT thấp nhất bị thay thé BV’ bao gém 3 phần: chỉ phí, xác suất tái truy cập (Pr) và tuổi động

“Xác suất tải truy cập: BI'=(Cost/Size)*Pr+Age

Cost: Chi phi lay được đối tượng từ máy chủ

Pr: Xac suit tai truy cập:

Dy: S6 tài liệu được truy cập ít nhất là ƒlần

a :Gia tri đặc trưng của luật phân bổ Zjyƒ_

ð là hằng trọng số

Size: Kích thước của đối tượng được yêu cầu.

23

Age: Tuéi của cache, được xác định là 8ï bé nhất của tất cả các đối tượng

‘Néu một đối tượng đã được đọc / lẫn, ước tính xác suất tái truy cập là Đ/=D„ /D, là số tài liệu được truy cập ít nhất f lẫn Tỷ lệ truy cập trung bình của một đối tượng có thể được ước tính bởi kích thước của nó Cho Ä là tỷ lệ

truy cập trung bình cho một đối tượng và S là kích thước của nó # có thể

được tước tính là #=C / S:, nơi C và ở là hai hằng Tỷ lệ truy cập trung bình

PS“ (12g, se) vớibl,3 và C là hẳng

Brelau gidi thiệu một mô hình cho các yêu cầu trang web, theo luật ZipE

với Z là đô thông đụng của trang, K và ø là 2 tham số độc lập

Tuổi cache là thời gian truy cập gần đây nhất Khi một đối tượng được

đưa đến cache, 3ï của nô là chỉ phí lấy được đối tượng cộng với # (ban đầu

—7= 0) Trong trường hợp cache hit, H được đặt

việc thay thé trang ~ chọn một trang đang nằm trong bộ nhớ mã không được

sử dung tai thoi điểm hiện tại và chuyển nó ra không gian swapping trên dia

để giải phông một khung trang dành chỗ nạp trang cần truy xuất vào bộ nhớ

‘Nhu vay néu không có khung trang trồng, thì mỗi khi xảy ra lỗi trang cần phải

thực hiện hai thao tác chuyển trang : chuyển một trang ra bộ nhớ phụ và nạp một trang khác vào bộ nhớ chính Có thể giảm bớt số lần chuyển trang bằng cách sử dụng thêm một bït cập abit (dirty bit) Bit nay được gắn với mỗi trang

để phân ảnh tình trạng trang có bị cập nhật hay không : giả trị của bít được cơ chế phần cứng đặt là 1 mỗi lần có một từ được ghi vào trang, đễ ghỉ nhận nội

đung trang có bị sửa đổi Khi cần thay thế một trang, nếu bit cập nhật có giá

trị là 1 thì trang cần được lưu lại trên đĩa, ngược lại, nếu bịt cập nhật là 0, nghĩa là trang không bị thay đổi, thì không cần lưu trữ trang trổ lại đĩa

đảng

bit s6 higu trang bit valid-inv:

Hinh 2.1 Câu trúc một phần tử trong bang trang

Sự thay thế trang là cần thiết cho kỹ thuật phân trang theo yêu cầu Nhờ

cơ chế này, hệ thống có thé hoàn toàn tách rời bộ nhớ ao và bộ nhớ vật lý, cung cấp cho lập trình viên một bộ nhớ ão rất lớn trên một bộ nhớ vật lý có

thể bề hơn rất nhiều lần

Sự thỉ hành phân trang theo yêu cầu hay việc áp dụng kỹ thuật phân

trang theo yêu cầu có thê ảnh hưởng mạnh đến tình hình hoạt động của hệ thống

Gia sử p là xác suất xảy ra một lỗi trang (0< p < 1):

p =0: không cô lỗi trang nào

P mỗi truy xuất sẽ phát sinh một lỗi trang

Thời gian thật sự cần để thực hiện một truy xuất bộ nhớ (7Z4) là:

TEA = (1-p)ma + p (tdp) [= swap out ] + swap in ~ tái kích hoạt

Trong công thức này, mz là thời gian truy xuất bộ nhớ, s4? thời gian xử

1ý lỗi trang

Có thể thấy rằng, để duy trì ở một mức độ chấp nhận được sự chậm trễ

trong hoạt động của hệ thống do phân trang, cần phãi đuy tr tý lệ phát sinh lỗi

trang thấp Hơn nữa, dé cài đặt kỹ thuật phân trang theo yêu cầu, cần phải giải quyết hai vấn đề chính yếu : xây đựng một thuật toán cấp phát khung trang,

và thuật toán thay thể trang

1.4.2 Các thuật toán thay thé trang

_Vấn đề chính khi thay thé trang là chọn lựa một trang « nạn nhân » để

chuyển ra bộ nhớ phụ Có nhiều thuật toán thay thế trang khác nhau, nhưng tất cã cùng chung một mục tiêu : chọn trang « nạn nhân » là trang mà sau khi thay thế sẽ gây ra ít lỗi trang nhất Có thể đánh giá hiệu qủa của một thuật

toán bằng cách xử lý trên một chuỗi các địa chicần truy xuất và tính toán

lượng lỗi trang phát sinh

‘Vi du: Gia sit theo vat xử lý của một tiến trình và nhận thấy tiến trình 'thực hiện truy xuất các địa chỉ theo thứ tự sau

Thuật toán LRU

'Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập, trang

được chọn để thay thể sẽ là trang lâu nhất chưa được truy xuất

Thuật toán giả định là một trang vừa mới được lấy ra khỏi cache sẽ tiếp

tục được truy nhập trong thời gian tới Để thay thé một nội dung trong cache, LRU sé xoá bố các trang không được truy cập đến trong một khoảng thời gian đài nhất Chức năng của LRU duoc mink hoạ trong hình đưới đây:

Hình 2.2 Lược đồ thay thể nội dung cache của thuật toán LRU

Vi đụ: sử đụng 3 khung trang, khởi đầu đều trồng:

Í7 812 0nl3í0 4/234|0l32 1201701

p77 22/2244 400012211121 foo oc o003 3333300000

Thuật toán FIFO sử dụng thời điểm nạp để chon trang thay thé, thuật

toán tối ưu lại đùng thời điểm trang sẽ được sử đụng, vì thời điểm này không thể xác định trước nên thuật toán LRU phải đùng thời điểm cuối cùng trang được truy xuất ~ đùng quá khứ gần để dự đoán tương lai

Thuật toán này đòi hôi phải được cơ chế phần cứng hỗ trợ để xác định một thứ tự cho các trang theo thời điểm truy xuất cuối cùng Có thể cài đặt

theo một trong hai cách

Sử dụng bộ đếm: thêm vào cấu trúc của mỗi phần tử trong bảng trang một trường ghỉ nhận thời điểm truy xuất mới nhất, và thêm vào cấu trúc của CPU một bộ đếm Mỗi lần có sự truy xuất bộ nhớ, giá trị của counter tăng lên 1 Mỗi lần thực hiện truy xuất đến một trang, giá trị của counter được ghi nhận

vào trường thời điểm truy xuất mới nhất của phần tử tương ứng với trang

trong bảng trang Thay thế trang có giá trị trường thời điểm truy xuất mới

nhất là nhỏ nhất

Sử dụng stack: tổ chức một stack lưu trữ các số hiệu trang Mỗi khi thực hiện một truy xuất đến một trang, số hiệu của trang sẽ được xóa khỏi vị trí hiện

"hành trong stack va đưa lên đầu stack Trang ở đỉnh stack là trang được truy

xuất gần nhất, và trang ở đáy stack là trang lâu nhất chưa được sử đụng

Có ít hệ thống được cung cấp đủ các hỗ trợ phần cứng để cài đặt được

thuật toán LRU thật sự Tuy nhiên, nhiều hệ thống được trang bị thêm một bít tham khảo ( reference): một bít reftrence, được khởi gin là 0, được gắ một phần tử trong bang trang Bit reference cia mét trang được phần cổng đặt

giá trị 1 mỗi lần trang tương ứng được truy cập, và được phân cứng gán trở về

0 sau từng chu kỹ qui định trước

Sau từng chu kỳ qui định trước, kiểm tra giá trị của các bit reference, c6

với

thể xác định được trang nào đã được truy xuất đến và trang nào không, sau

khi đã kiém tra xong, các bịt reference được phần cứng gán trở về 0 Với bít

reference, có thê biết được trang nào đã được truy xuất, nhưng không biết

được thứ tự truy xuất Thông tin khô

xắp xi LRU khác nhau.

2

số hiệu trang bit valid-invalid | dirty bit bit reference

tình 2.3 Câu trúc một phần tử trong bang trang

Thuật toán với các bit reference phu try

Tiếp cận: Có thể thu thập thêm nhiều thông tin về thứ tự truy xuất hơn

bằng cách lưu trữ các bịt references sau từng khoảng thời gian đều đặn: với

mỗi trang, sử đụng thêm § bịt lịch sử (history) trong bảng trang sau từng

khoảng thời gian nhất định (thường là100 millisecondes), một

được phát sinh, và quyền điều khiển được chuyển cho hệ điều bình Hệ điều hành đặt bit reference cia méi trang vào bit cao nhất trong § bít phụ trợ cũatrang đồ bằng cách đây các bít khác sang phải 1 vị trí, bỏ luôn bít thấp

nhất Như vậy 8 bít thêm vào này sẽ lư u trữ tình hình truy xuất đến trang

trong 8 chu kỳ cuối cùng Néu gia tri cia 8 bit 12 00000000, thì trang tương

ứng đã không được đùng đến suốt 8 chu kỳ cuối cùng, ngược lại nếu nó được đùng đến ít nhất 1 lần trong mỗi chu kỳ, thì 8 bịt phụ trợ sẽ là 11111111 Một

trang mà 8 bít phụ trợ có giá trị11000100 sẽ được truy xuất gần thời điểm hiện tại hơn trang có 8 bít phụ trợ là 01110111 Nếu xét 8 bít phụ trợ này như

một số nguyên không dấu, thì trang LRU là trang cô số phụ trợ nhỏ nhất

phải được chọn sao cho việc cập nhật là nhanh nhất có thể

LRU là thuật toán cache được sử dụng rộng rãi nhất, bởi vì LU coi các trang cô chi phi (cost) va kích thước không đổi mục đích của LRU là tối

.ưu hoá tỷ lệ hit Ưu điểm của LEU là khai thác được đặc tính cục bộ của truy nhập Nhược điểm của LRU la b6 qua sự thay đổi về chỉ phí và kích thước

của trang, cũng như 7U không tính đến tần suất của các truy nhập

watermak cao th giá trị ngưỡng là nhỏ hơn

1.4.3 Vấn để thay thế Cache

‘Web proxy xác định một khu vực bộ nhớ cache giới hạn, dành để lưu

trữ của một số đối tượng Web Nếu khi khu vực bộ nhớ cache gần day, thi sé

có quyết định thay thê một số đối tượng mới hơn đề lưu lại Do đó, việc

xefresh các đối tượng Web lưu trữ "phải được xác định theo quy định cụ thể

và trong thuật ngữ Web caching một đối tượng được coi là cũ khi server gốc

phải liên lạc để xác nhận sự tồn tại của bản sao cache Việc đối tượng cũ hay

không xây ra đo sự thiếu thông tin của cache của server về những thay đôi của đối tượng gốc Mỗi proxy cache server phải được gia cố bằng sự cạnh tranh của các đối tượng cũ cụ thể Các thông số quan trọng nhất tương ứng với thuộc tính của từng đối tượng lưu trữ được tóm tắt trong Bang 2.1

Bang 2.1 Các thuộc tính hiữu ích nhất của mỗi đối tượng lưu trữ ¡

Tham so Mô tả

si Í server mà đổi tượng đang lưu trữ

bị kích thước của đối tượng (KBytes)

t thời gian đối tượng bị khóa

fa thời gian đối tượng được lưu trữ

h thời gian sửa đôi cuối cùng của đối tượng

29 StalRatio; =

Trong đó: tử số tương ứng với khoảng thời gian từ thời điểm đối tượng được lưu trữ đến thời điểm xác định cuối cùng của đối tượng và mẫu số là tuổi cache của đối tượng tức là nô quyết định thời gian mà đối tượng vẫn

trong bộ nhớ cache Điều này luôn đúng khi StalRatio; > 0 va hiện tạ -c> 0

Gia tri StalRatio; càng giãm thì đối tượng ï càng cũ, từ đó suy ra nó đã ở lại

trong bộ nhớ cache khoảng thời gian dài hơn

‘Dinh nghia 2.2 Tn sé déng dynamic frequency cita cac déi tượng lưu

De,

khi đô ƒ¡ là thước đo để đánh giá tần suất truy cập của một đối tượng (Bảng

2.1) Đối tượng nào lớn hơn giá trị của /2ynFegr là đối tượng được truy cập

gần nhất

Định nghĩa 2.3 Tốc độ thu hồi retrieval rate đối twong cache

L3 Rotate

của kết nối đến server s RetRate; đại điện cho chi phí liên quan khi lấy một đối tượng từ máy chủ lưu trữ ban đầu của nó

"Định nghĩa 4: Hàm hoạt động action funtion

act;= 0 néu i bi xóa khỏi bộ nhớ cache

trong 46 Jat, là độ trễ đề mở một kết nối đến server s và öand, là băng thông

J trong các trường hợp khác

Tóm tắt bài toán: nếu là số lượng các đối tượng trong bộ nhớ cache

và C là tổng công suất của các khu vực bộ nhớ cache, thì bài toán thay thé cache li

MAXIMIZE 0 tet, StalRato x DEES

với SŠ ae xb,<C

trong đồ Dearie được sử đụng như là một yếu tổ trọng lượng kết hợp với

từng đối tượng được lưu trữ, vì nó liên quan tần suất truy cập của đối tượng

và tốc độ thu hồi của nó

"hay thế bộ nhớ cache LRU dựa trên luật Temporal Locality Rule trong 46 các đối tượng Web mà không được nhắc đến trong thời gian gần đây, thì dự

kiến sẽ không được tham chiều một lần nữa trong tương lai gần LRU được

sử đụng rộng rãi trong các cơ sở dữ liệu và đựa trên Web ứng dụng Vĩ dụ

‘trong Squid, LRU được sử dụng cùng với một số thông số nhất định như một watermark thấp và một watermark cao để kiểm soát mức độ sử đụng bộ nhớ

cache Khi mức độ sử đụng đĩa bộ nhớ cache gần với các watermark thấp

(hường được coi là 00%) thì các đối tượng Web được thanh lọc từ bộ nhớ toàn nội dung bộ nhớ cache Ngưỡng này là tự động đánh giá đựa trên kích thước bộ nhớ cache hiện hành, và dựa trên vatermarks thấp và cao Khi kích thước bộ nhớ cache hiện tại là gần hon véi watermark thap thi gid tri ngưỡng

là lớn hơn, ngược lại khi kích thước bộ nhớ cache hiện tại là gần hơn với cache sẽ lưu trữ ít hơn, trong khi đó khi mức độ sử dụng đĩa gần với các

'watermark cao (thường được coi là 95%) thì bộ nhớ cache sẽ thay thể các đối

tượng Web đó nghĩa là các đối tượng Web lọc từ bộ nhớ cache đồ được lưu

trữ nhiều hơn Có một số đối tượng nên được xóa khỏi bộ nhớ cache

Dinh nghĩa 2.5 ( Ngưỡng LRU): Một giá trị được xác định là ngưỡng

cần thiết để ước lượng thời gian đự kiến cần thiết khi có thể thay thế hoàn

Mô tả thuật toán: thay trang lâu nhất chưa được truy xuất

Lỗi trang: xây ra khi truy xuất đến một trang không có trong bộ nhớ

hay địa chỉ không hợp lệ Chỉ xét trong trường hợp trang không có trong bộ nhớ (bộ nhớ chính)

Quá trình truy xuất trang:

31

- Bước 1 Truy xuất đến trang không có trong bộ nhớ chính

- Bước 2: Gửi tín hiệu đến hệ điều hành

- Bước 3: Hệ điều hành tìm trang trong bộ nhớ phụ

- Bước 4: Nạp trang/ thay trang vào bộ nhớ

- Bước 5: Cập nhật

- Bước 6: Truy xuất lại bộ nhớ phụ

policy = new RemovalPolicy;

* Initialize the URL data *

”* Allocate the needed structures *

Irủ_đata = (LruPolicyData *)xcalloc(1 sizeof(*Iru, dat)

đình 2.4 Thuật toán thay thé cache LRU

2.5 Các thuật toán dựa trên LRU trong WWeb caching

Cache đã được giới thiệu và áp đụng trong nguyên mẫu và hệ thống

thông tin đựa trên Web thương mại để giảm tổng thể băng thông và khã năng

gia tăng lỗi của hệ thống Bài viết này trình bày một cách theo dõi các thuật

toán thay thé bộ nhớ cache Web dựa trên ý tưởng thuật toán Least Recenly Used(LRU) Luin văn trình bày và mỡ rộng thuật toán LRU thông thường

‘bing cach xem xét các tham chiếu đến các đối tượng Web như một thông

quan trọng cho việc thay thế nội đung bộ nhớ cache Các thuật toán được xác nhận và thử nghiệm trên phần mềm Squid proxy cải đặt trên server Các thông

số của Cache và tỷ lệ byte hít rate cho thấy rằng các thuật toán thay thế đã giúp cãi thiện nội dung b6 nhé cache