URL Copied

Sử dụng Memory cache trong hệ thống CDN30 Aug 2019 | Đức Lê

Để giải bài toán truy cập đồng thời vào kho dữ liệu media, hệ thống CDN đã được xây dựng với nhiệm vụ cung cấp dữ liệu đến với người dùng một cách nhanh chóng, hiệu quả và “tiết kiệm”.

Vậy hệ thống CDN là gì?

Đó là một hệ thống gồm nhiều cụm server được đặt tại các vị trí địa lý khác nhau. Thay vì phải kết nối trực tiếp đến máy chủ gốc (origin server), người dùng có thể kết nối đến server CDN (edge server) gần nhất với mình. Sau đây là một số lợi ích chính khi sử dụng hệ thống CDN:

- Tăng tốc độ load image, video và audio: Người dùng kết nối đến edge server ở miền Bắc sẽ nhanh hơn là khi kết nối trực tiếp đến origin server ở miền Nam.

- Tiết kiệm băng thông của origin server: thường thì băng thông của origin sẽ đắt hơn nhiều so với băng thông của các edge server. Chúng ta chỉ tốn tiền băng thông này khi bị miss cache ở edge server.

- Giảm tải cho origin, load balance giữa các CDN Servers: Một origin server duy nhất không thể chịu nổi tải của hàng ngàn user truy cập đồng thời. Do đó, khả năng scale ra nhiều edge server là một đặc điểm nổi bật của hệ thống. Điều này càng cần thiết khi sản phẩm ngày càng phình to.

Do đó, khả năng caching của edge server sẽ là yếu tố quyết định đến chất lượng của hệ thống. Trong đó, Disk Cache sẽ ảnh hưởng đến tính chất “tiết kiệm băng thông”, còn Memory Cache sẽ đảm bảo cho việc người dùng có thể truy xuất thông tin một cách nhanh nhất. 

Mô hình cơ bản của một hệ thống CDN 

Trong phạm vi bài viết này, chúng tôi xin chia sẻ một số kinh nghiệm khi xây dựng và làm việc với hệ thống Memory Cache.

Memory Cache

So sánh với các nguồn tài nguyên khác (database, đĩa, API), bộ nhớ có lợi thế rất lớn về tốc độ truy cập. Server hiện tại đang sử dụng RAM cache để lưu lại những file nhỏ và có độ phổ biến (lượng truy cập) cao. Việc sử dụng RAM cache có thể giúp server phục vụ hot file một cách nhanh chóng, giảm lượng truy cập xuống đĩa và origin server, đặc biệt là khi lượng truy cập tăng vọt. 

Về cơ bản, Memory Cache là một hashtable dạng key - value. Key của mỗi file được mặc định là URL dùng để truy cập đến file đó, và value là binary data của file. Sử dụng hashtable (std::unordered_map) thay cho red-black tree (std::map) cho thời gian truy cập tốt hơn đối với độ dài key không quá lớn. So sánh chi tiết có thể tham khảo trong hình dưới. 

Khi cache đầy, object vừa mới được truy cập sẽ được xem xét đẩy vào cache nếu object đó có đủ độ ưu tiên, đồng thời loại ra khỏi cache phần tử có độ ưu tiên thấp nhất. Mỗi chiến thuật cache có cách tính độ ưu tiên cho object khác nhau. LRU (Least Recently Used) là chiến thuật cache phổ biến nhất; từ nền tảng đó chúng tôi đã cải tiến và áp dụng một chiến thuật cache phức tạp hơn là CLFUS​​ ​ (CLOCK​ ​ Least​ ​ Frequently​ ​ Used​ ​ by​ ​ Size).

LRU Cache 

LRU là chiến lược cache cơ bản nhưng có nhiều ứng dụng. Chiến thuật này quan tâm đến thời gian gần đây nhất mà object được truy cập. Một object vừa được truy cập sẽ luôn được đẩy vào cache, đồng thời object không được truy cập lâu nhất sẽ bị loại. Cài đặt LRU sử dụng linked list cho phép các thao tác get​, put​, remove​ được thực hiện trong độ phức tạp O(1).

CLFUS Cache

Chiến thuật này sử dụng ý tưởng từ một số chiến lược kinh điển như CLOCK, LRU và LFU. CLFUS có một số đặc điểm như:

  • Cân bằng giữa thời gian xuất hiện (recentness), tần suất truy cập và kích cỡ của object để tối ưu tỉ lệ hit vào cache.
  • Tuy phức tạp nhưng không gây ra nhiều CPU overhead. Các chi phí này chỉ lớn hơn LRU một chút do các phép thực hiện có độ phức tạp trung bình​​ O(1).
  • Không gây ra nhiều chi phí overhead cho bộ nhớ, không quá 20 bytes cho mỗi object được lưu. 

Thông​​ tin​ ​object trong CLFUS

CLFUS lưu key và thông tin của các object trong 2 danh sách LRU là Cache List và History List. Cache List chứa thông tin về object được cache và nằm trên bộ nhớ, trong khi đó History List chứa thông tin về những object đã được truy cập gần đây và có khả năng được đẩy vào cache. Thông tin về object được lưu bao gồm:

  • Key khóa của object
  • Hit số lần truy cập trong một CLOCK
  • Size kích cỡ của object
  • Time thời gian được đẩy vào cache

Thao​ ​tác​ ​GET

Object nằm trong cache khi đươc truy cập sẽ tăng giá trị của hit, đồng thời object đó được chuyển lên đầu của Cache List. Nói cách khác, object khi được hit sẽ được chèn vào vị trí “mới truy cập” (most recently used). 

Phần quan trong là khi một object mới (từ đĩa, từ API, …) được xem xét chèn vào cache. Thao tác này thực hiện theo các bước sau: 

Bước 1. Nếu object có trong Cache List, cập nhật hit, chuyển object lên đầu của Cache List. Chuyển đến bước 6.

Bước 2. Nếu object chưa từng xuất hiện (không có trong History List), chèn vào History List.

Bước 3. Khi đã chắc chắn object (gọi là candidate) nằm trong History List, cập nhật hit và thực hiện so sánh với phần tử (gọi là victim) nằm ở cuối Cache List (least recently used object) để quyết định xem candidate có được cache trong bộ nhớ hay​ ​ không. 

Giá trị cache (độ ưu tiên) của mỗi object được tính theo công thức cache_value = hit / size. Theo công thức này không những số lần hit mà độ lớn của object cũng được xem xét.

Bước 4. Nếu candidate có giá trị cache lớn hơn, nó sẽ được chèn vào đầu Cache List. Victim bị xóa khỏi Cache List và chèn vào đầu History List. 

Bước 5. Nếu candidate có giá trị nhỏ hơn, nó sẽ được chèn lại vào đầu History List. Victim sẽ không bị loại khỏi Cache, reset giá trị hit về 0 và chèn lên đầu Cache List 

Bước 6. Kết thúc

Clock​ ​tick

Mỗi chu kì đồng hồ xảy ra khi có object (victim) bị xem xét loại khỏi cache. Khi đó, phần tử cuối (least recenty used) trong History List sẽ được xem xét loại khỏi History List. Nếu nó có giá trị hit lớn hơn 1, hit sẽ bị reset về 0 và chèn lại object này vào đầu History List. Nếu không, nó sẽ bị xóa khỏi History List. Mục đích của các chu kì đồng hồ là nhằm giúp cache không bị đầy bởi những object chỉ xuất hiện một lần, đồng thời giảm độ ưu tiên của những object đã lâu không được truy cập. 

Testing

Hệ thống cài đặt trên server có cấu hình 4GB RAM, 4 core 4 thread, 2.4GHz per core, băng thông mạng 11 MBs. Dung lượng RAM được sử dụng là 1GB và dung lượng đĩa sử dụng 5GB. Bài test thứ nhất sẽ so sánh performance khi thực hiện truy xuất các file dạng ảnh tới Edge Server và Origin Server.

Nhìn vào bảng dưới ta có thể thấy khi file càng lớn thì tốc độ trả về của Edge Server càng hiệu quả hơn so với Origin Server. 

Bài test thứ hai sẽ là về khả năng chịu tải và hiệu năng của Edge Server so với Origin Server. Load test mô phỏng hành vi truy cập của client bằng cách sử dụng hàm phân phối Zipf. Zipf distribution chỉ ra số lần truy cập của item phổ biến nhất xấp xỉ gấp đôi item phổ biến thứ 2, xấp xỉ gấp 3 lần item phổ biến thứ 3, … Nói cách khác, phần lớn lượng truy cập tập trung vào một số item phổ biến nhất, trong khi những item ít phổ biến hiếm khi được truy cập. Zipf’s law cũng là hàm thường xuyên được sử dụng để đánh giá các hệ thống cache. 

Kết quả của bài test này không chỉ cho thấy tốc độ truy xuất cao của Cache Server mà còn là khả năng chịu tải tốt so với Origin Server. 

 

#Cache #Contentdeliverynetwork

Related jobs