Cache và cấu trúc phân tán

Software Engineering

36

Ngoc Dao viết ngày 21/03/2016

Lập trình viên quá cố người Mỹ Phil Karlton có câu nổi tiếng:

There are only two hard things in Computer Science: cache invalidation and naming things

Tiếp theo bài Cache cho web ở server, bài này chúng ta bàn cách giải quyết một số vấn đề thường gặp với cache khi phân tán hệ thống ra nhiều máy để tăng scalability. Hi vọng những chỉ dẫn trong bài này sẽ có ích khi bạn muốn lựa chọn hoặc tự viết thư viện cache.

Có nên replicate cache?

Khi bạn có nhiều máy thì có 2 cách lưu cache: replicate cache ra nhiều máy để máy nào cũng lưu toàn bộ cache, hoặc cắt nhỏ cache ra để mỗi máy chỉ lưu phần nhỏ của cache. Thường không nên replicate cache, lí do:

• Bản chất của cache (trừ cache ở cấp cực thấp như cache của CPU) là kết quả tính toán từ dữ liệu thô nào đó, chỉ vì quá trình tính toán mất thời gian nên mới phải cache lại để kết quả có thể dùng đi dùng lại nhiều lần, đỡ mất công tính toán lại. Do đó cache có thể tái tạo lại được từ dữ liệu thô, chẳng may thỉnh thoảng có mất đi cũng không sao, chẳng việc gì phải replicate. Có replicate thì hãy replicate dữ liệu thô.
• Bản chất của việc dùng chiêu thức cache là muốn tăng tốc độ đọc dữ liệu, nên dữ liệu phải nằm trong RAM. Bản chất của replicate là copy dữ liệu. Giả sử bạn có 100 máy mỗi máy RAM 4GB. Nếu dùng RAM cache có replicate thì tối đa hệ thống mặc dù có đến 100 máy cũng chỉ lưu được tối đa 4GB dữ liệu. Còn nếu không dùng replicate mà cắt dữ liệu ra để phân tán ra 100 máy, thì hệ thống có thể lưu được 100x4BG dữ liệu.
• Khi dữ liệu thô thay đổi ở 1 máy nào đó thì phải xoá cache đi tính toán tạo lại. Nếu dùng replicate thì sau khi tạo lại cache phải đồng bộ hoá nó trên tất cả các máy. Cần biết rằng replicate là quá trình rất chậm nhất là nếu nó dùng thuật toán Xác nhận 2 pha và phải replicate ra đến 99 máy khác.

Làm sao khi cache trở thành rác?

Bạn dùng Recycle Bin trên Windows hoặc Trash trên Mac bao giờ chưa? Dữ liệu không phải là tạm còn có lúc xoá, thì dĩ nhiên dữ liệu cache chắc chắc là tạm sẽ có lúc phải xoá, nếu không sẽ không còn chỗ chứa.

Khi xoá, ta muốn xoá dữ liệu lâu ngày không được sử dụng. Do đó cần dùng thuật toán LRU, thường được hiện thực hoá LRU bằng priority queue. Chú ý thuật toán này rất khó hiện thực hoá hiệu quả về dung lượng bộ nhớ và tốc độ xử lí nếu dùng ngôn ngữ cấp cao như Ruby hoặc Erlang. Nếu muốn dùng LRU với ngôn ngữ cấp cao, nên hiện thực hoá nó bằng C (ví dụ dùng Judy cho hiệu quả) rồi nối nó vào chương trình ngôn ngữ cấp cao.

Làm sao phân tán cache ra nhiều máy?

Cache nằm trong bộ nhớ, mà cấu hình máy bình thường thì bộ nhớ chỉ vào khoảng vài GB. Nếu hệ thống của bạn cực lớn thì không thể lưu cache trên một máy duy nhất mà phải lưu trên nhiều máy. Đây chính là chủ đề của Bảng băm phân tán cố định (consitent DHT), trong đó thuật toán dễ thực hiện nhất có lẽ là Ketama.

Tuy vậy, chỉ áp dụng DHT được khi số lượng cache server chỉ tăng hoặc chỉ giảm, rất phức tạp và nguy hiểm nếu lúc tăng lúc giảm sống chết không biết đâu mà lường, nhất là khi hệ thống chạy sau load balancer. Do đó, cách đơn giản nhất và an toàn nhất là xoá tất cả cache khi số lượng cache server thay đổi, vì dù sao cache cũng chỉ là dữ liệu tạm có thể tái hiện lại được.