44. Caching part 2
Tiếp tục bài trước, bài này tôi sẽ tổng hợp những kiến thức về disbuted cache và cache replacement/invalication
Link bài 1: Caching part 1
Caching phần 2
- Distribted cache
- modulus sharding
- range-based sharding
- consistent hashing
- Cache replacement and invalidation
- Cache replacement: LRU, LFU
- Cache invalidation: TTL, invalidation event
4. Distributed cache là gì? [1]
Phần này chủ yếu sẽ tóm lược nội dung của bài viết A Crash Course in Caching - Part 2 trên blog ByteByteGo. Xem link ở phần Reference
Ở phần trước, ta nói đến cache trên remote server. Nếu chỉ dùng 1 server, thì không có chuyện gì để nói. Tuy nhiên, khi dữ liệu cần cache lớn, ta phải cache trên nhiều server khác nhau. Lúc này, ta có distributed cache.
Trong distributed cache, mỗi node sẽ chỉ lưu trữ 1 phần dữ liệu. Khi client yêu cầu, cache system cần biết tìm dữ liệu ở node nào.
Có nhiều cách cho việc phần chia dữ liệu giữa các node, bao gồm modulus, range-based và consistent hashing. Lưu ý rằng, việc chia dữ liệu này đều dựa vào key (dữ liệu có dạng key-value). Giả sử key của chúng ta là user_id
Modulus
Với phương pháp modulus, gọi n là tổng số server. Việc xác định key nằm trên server nào được tính bằng công thức: hash(user_id) % n.
Phương pháp này đơn giản, nhưng yêu cầu phải redistribute cache khi tăng hoặc giảm số lượng server. Điều này sẽ gây gánh nặng lên database khi có quá nhiều cache miss. Nghiêm trọng hơn, có thể gây crash hệ thống.
Range-based
Với phương pháp này, key sẽ được chia thành nhiều range khác nhau, mỗi range sẽ được map vào 1 node nhất định.
Vd: Node 1 khi min_user_id <= user_id < 10 Node 2 khi 10 <= user_id < 20 Node 3: 20 <= user_id < max_user_id
Range-based sẽ phù hợp với 1 số trường hợp, khi mà dữ liệu được group hoặc partition vào 1 range cụ thể.
Tuy nhiên, vì số lượng node được xác định trước dựa vào range, rất khó để scale. Khi scale, cần phải re-define lại range này. Đồng nghĩa với việc có nhiều miss cache.
Từ đó, có thể thấy 2 phương pháp trên, modulus và range-based, tuy đơn giản nhưng khó scale. Khi scale, yêu cầu phải redistribute data.
Consistent hashing
Để không phải redistribute nhiều dữ liệu, ta cần 1 phương pháp mà ở đó việc chọn node không liên quan trực tiếp tới số lượng server. Consistent hashing cho phép ta thực hiện điều này.
Key và node sẽ được map vào 1 vòng tròn với vị trí xác định. Vòng tròn này gọi là hash ring. Để cho dễ hiểu, vòng tròn là 360 độ. Nếu giá trị của node sau khi hash là 90 độ, thì node đó nằm ở vị trí 90 độ trên vòng tròn. Tương tự cho key.
Để xác định key thuộc về node nào, từ vị trí của key, di chuyển theo chiều kim đồng hồ, gặp node nào đầu tiên, thì key thuộc về node đó. Lưu ý, quy ước chung là sẽ đi theo chiều kim đồng hồ. Nếu có đi ngược cũng không ảnh hưởng.
Ví dụ.
Hình trên mô tả Hash ring và lấy từ link [2]. Gọi A, B, C là vị trí của các node. Lúc này, Jane và Kate sẽ thuộc node C. John và Steve thuộc node B. Bill thuộc node A.
Với phương pháp này, thêm hoặc bỏ 1 node, chỉ ảnh hưởng phần dữ liệu được lưu trữ trên node đó mà thôi. Không cần phải redistribute toàn bộ dữ liệu.
5. Cache replacement and invalidation
Tại sao cần phải có cache replacement? Vì cache storage là có giới hạn và nó chỉ lưu được 1 phần của dữ liệu. Cho nên, ta buộc phải ra quyết định nên giữ/hoặc bỏ những object nào để tối ưu hóa performance.
LRU (Least Recently used) [3]
Thuật toán phổ biết nhất cho cache replacement. Như tên đã gợi ý, nó sẽ remove những item ít được sử dụng gần đây nhất.
Với mỗi lần sử dụng item, thuật toán sẽ đưa item lên đầu của list. Do đó, những item ít được sử dụng gần đây nhất sẽ bị đẩy xuống cuối list. Khi list full hoặc tới 1 ngưỡng nào đó, những item ở cuối list sẽ bị loại bỏ.
LFU (Least Frequently Used) [4]
Về ý tưởng, những item ít được sử dụng nhất sẽ bị remove khi cache full. Để làm điều này, ta cần có 1 counter để theo dõi mức độ được sử dụng của các item.
LFU nghe có vẻ hợp lý nhưng khi thêm 1 item mới vào cache, item này chưa có counter hoặc counter thấp và giả sử rằng, item này sẽ được dùng thường xuyên sau đó. Với LFU, item sẽ bị remove rất nhanh sau đó bởi nó vừa được thêm, và counter còn thấp. Vấn đề này khiến LFU ko được sử dụng rộng rãi như LRU
Cache Invalidation
Cache validation là quá trình remove hoặc update cache data khi nó không còn valid nữa (bị cũ so với data trong database).
Thông thường, mỗi cache item sẽ đi kèm với 1 giá trị time-to-live (TTL). Khi TTL expires, cache item sẽ bị remove hoặc update mới.
Tuy nhiên, việc chọn TTL sao cho phù hợp là 1 bài toán khó. TTL thấp sẽ dẫn đến việc gọi database quá nhiều. TTL cao sẽ làm tăng nguy cơ client dùng data cũ, dẫn đến kết quả bị sai.
Nếu sử dụng in-process cache và deploy trên nhiều server, sẽ phải đảm bảo cache đồng bộ, consistency giữa các server.
Ngoài kỹ thuật TTL còn nhiều hạn chế, ta có thể sử dụng Event-based invalidation. Kỹ thuật này sẽ trigger 1 events dựa trên những hành động cụ thể như update databse hoặc thay đổi data. Tuy việc thực hiện sẽ hơi phức tạp nhưng event-based invalidation sẽ chính xác và hiệu quả hơn TTL. Tuy nhiên, cũng nên chú ý đến latency của event
Referene: