Quần Cam

Cache stampede—Hiện tượng chất đống cache

Caching là một kĩ thuật tăng tốc mà hầu như mọi kĩ sư phần mềm đều cần biết. Tuy vậy, đôi khi caching vẫn có thể mang lại cho bạn những vấn đề phiền toái khác khác. Một trong số đó là cache stampede, hay còn gọi là dogpile effect (tạm dịch: hiệu ứng chất đống).

soccer dogpile

Chuyện kể rằng

App Forza Football có một chức năng tên là Calendar: chức năng này hiển thị tất cả trận đấu trong một ngày. Mỗi trận đấu trên calendar chứa các thông tin như tỉ số, số thẻ đỏ, video. Dữ liệu của calendar phải là “live” với data latency là 1 giây. Có nghĩa là 1 giây sau khi Messi ghi bàn cho FC Barcelona, tỉ số trên calendar phải được cập nhật.

Forza Calendar

Trên mobile client, cứ mỗi X (từ 10—180 tùy vào setting của user) giây, sẽ poll dữ liệu từ Calendar API để lấy cập nhật.

Logic của API này không thực sự phức tạp, chỉ là lọc trận đấu theo ngày và kiểm tra trận nào có video highlight. Cái khó nằm ở khối lượng công việc của nó khá nặng, đồng thời đây là endpoint được truy cập nhiều nhất hệ thống. Những lúc cao điểm như vòng chung kết World Cup, vòng cuối Ngoại Hạng Anh, hay sau khi có đội hình ra sân trận chung kết Champions League, chục ngàn RPS (request per second) là hoàn toàn có khả năng, chưa tính những endpoint khác.

Performance của hệ thống cũ lúc đó (dùng Ruby on Rails nếu bạn quan tâm) chỉ xử lý được khoảng 35 RPM (request per minute), và phụ thuộc nặng nề vào Varnish Cache (tui có viết một bài về monitoring Varnish nè) để handle high load. TTL của mỗi cache entry được đặt rất cao để tránh cache miss. Mỗi khi nhận được update, hệ thống sẽ purge cache để đảm bảo data được cập nhật. Tuy vậy nó vẫn hay chết lên chết xuống.

Khi xây dựng hệ thống backend mới, endpoint này đặt mục tiêu tối ưu hóalow data latency lên hàng đầu. Dựa trên hai mục tiêu này, endpoint được hiện thực và tụi tui chạy load test cho nó.

Không ngoài dự đoán, mặc dù được Đảng, Nhà nước, tập thể các giáo sư, bác sỹ trong và ngoài nước tận tình cứu chữa, gia đình hết lòng chăm sóc và tối ưu mọi thứ liên quan: loại bỏ N+1 query, nén dữ liệu ở HTTP, và cài những database index cần thiết, kết quả load testing vẫn lẹt đẹt với max RPS khoảng 70 (chạy trên con AWS c5.xlarge). Khối lượng công việc để hoàn thành một request vẫn là quá nặng. Giải pháp dùng cache để tăng tốc đã được tính tới.

Hệ thống mới viết bằng Elixir chạy trên Erlang VM, nên ETS gần như là lựa chọn mặc định cho cache. Nếu bạn chưa biết, ETS là một in-memory key-value storage được ship chung với Erlang. Tạm hình dung là bạn có sẵn Redis ngay trên app khi bật Erlang VM. Mặc dù vậy, cách ví von này không hoàn toàn đúng. Ừ thì tui mâu thuẫn vậy đó, ahihi.

Dùng cache dễ như trở bàn tay. Đầu tiên ta thử lấy dữ liệu trong cache. Nếu có data, trả nó về ngay. Nếu không có data, ta thực thi thao tác để lấy dữ liệu. Ta bỏ dữ liệu lấy được vào trong cache và trả nó về. Đây được gọi là cache-aside pattern.

def fetch_data() do
  case @cache.get(key) do
    {:ok, data} ->
      data

    :error ->
      data = do_expensive_work()
      @cache.put(key, data, time_to_live = 1_000)
      data
  end
end

Cache stampede—Hiện tượng chất đống

Sau khi gắn cache, performance của API có khá khẩm hơn, nhưng vẫn khá tệ với max RPS đạt tầm 165. Đặc biệt tệ nhất lúc app mới start. Bởi vì lúc đó mọi request đều bị miss cache nên cùng nhau đè database ra mà gọi. Đa số query đến database đều timed out, request fail thảm hại. Người ta gọi đây là hiện tượng cache stampede hay hiệu ứng dogpile (tạm dịch: chất đống).

Giải pháp cho cache stampede thường được chia làm 3 hướng:

1. Dùng lock

Ta có thể dùng lock để tránh lặp đi lặp lại một tác vụ nặng khi cache miss xảy ra hàng loạt:

  1. Request A nào đó sẽ giành được lock.
  2. Các request không giành được lock sẽ đứng yên và chờ.
  3. Khi request A hoàn thành tác vụ, nó sẽ ghi kết quả vào cache.
  4. Các request còn lại đọc từ cache.

2. Cache warming

Thay vì để cho cache miss xảy ra, ta luôn update lại cache trước khi nó expire. Một worker có thể được set up để chạy và update lại cache khi nó sắp expire, hoặc chạy định kì.

3. Dự đoán cache expiration

Cache của bạn có thể đoán rằng, vào thời điểm X, một key nào đó có thể sẽ cần phải được update lại, dựa trên data thu thập được từ những expiration trước đó.

Giải quyết

Sau khi bàn bạc, team quyết định chia làm 2 nhóm thử nghiệm cache warming và cache locking. Cách thứ 3 không thực sự áp dụng được trong bài toán của tụi tui (có trời mới biết khi nào Messi sẽ ghi bàn 🙄).

Cache warming

Thoạt đầu giải pháp này có vẻ rất triển vọng. Cache của calendar bị phân mảnh bởi ngày của calendar, quốc gia và UTC offset của user (cache key là (date, country, utc_offset)). Về lý thuyết cache có thể được warm cho mọi tình huống, bởi những thông tin này đều có sẵn:

  • User thường chỉ luẩn quẩn duyệt calendar của các ngày trong tuần.
  • Toàn thế giới có khoảng 200 nước.
  • Toàn thế giới có 37 UTC offset sẵn dùng.

Tuy nhiên sau một hồi chạy giả lập, Doctor Strange dự đoán cache warmer của tụi tui sẽ phải chạy 37 * 200 * 7 = 51,800 tình huống, trong đó không có tình huống nào chạy xong trong vài giây. Thay vì chết bởi high load, app sẽ chết bởi warmer trước. End game!

Cái khó ló cái khôn. Sau khi phân tích traffic, tụi tui thấy rằng 95% request của hệ thống đến từ 20 nước có nhiều user nhất. Đồng thời mỗi nước chỉ dùng 1-2 time offset, trừ nước Mĩ và mấy cái offset ba phải của mấy ông Ấn Độ (GMT+5:30 🙄). Nhờ vậy, số cache cần được warm giảm xuống còn khoảng 200.

Đúng là sau khi có warmer, performance của API tốt lên hẳn. Max RPS trên một host đo được lên gần 300 RPS . Liệu có thể kết luận rằng bài toán đã được giải quyết?

Thật ra tụi tui đã quá lạc quan:

  • Cache nằm ngay trong app, để cho đơn giản, cache warmer cũng nằm trong app. Lúc warmer chạy sẽ ảnh hưởng đến performance chung (chiếm dụng CPU, database, HTTP connection trong pool, vv).
  • Load testing được chạy cho chỉ một endpoint, nhưng ở production sẽ có thêm request cho những endpoint khác. Để cho kết quả đo lường được chính xác, ta phải load test với các user story thật. Khi dùng user story, quả thật performance không còn được lấp lánh như trước.
  • Hơn nữa, cache warmer không đáp ứng được yêu cầu về data latency. Để bớt chiếm dụng tài nguyên của những request khác, cache warmer chỉ được chạy mỗi 30 giây.

Kết luận là, dù cache warmer giảm bớt được tác hại của cache stampede, nó không thực sự chạy tốt.

Cache locking

Một nhánh khác của team chuyển sang hướng dùng lock. Locking được kì vọng sẽ giải quyết được gốc rễ của cache stampede. Nếu chạy đúng, những request tương đồng trong cùng một thời điểm sẽ chỉ được thực hiện một lần, ùn tắc sẽ không xảy ra.

Implement locking với Elixir/Erlang không quá khó nếu muốn nói là khá dễ. Vì bên trong process code được thực thi tuần tự, ta có thể hiện thực locking bằng một lock process, với mã giả của hàm acquire như sau:

defmodule Cache.Lock do
  use GenServer

  # code omitted for brevity.

  def handle_call({:acquire, key}, from, %{keys: keys} = state) do
    if key in keys do
      # lock owned by other processes, wait.
      store_caller(key, from)
      {:noreply, state}
    else
      # lock acquired successfully.
      {:reply, :ok, %{keys: [key | keys]}}
    end
  end

  defp store_caller(key, from), do: ...
end

Process trong trường hợp tui đang nói là process trong Elixir.

Khi một process owner đoạt được lock, nó sẽ tiến hành tính toán rồi ghi vào cache. Những process đến sau sẽ phải chờ. Lock process sẽ lưu PID của những process chờ này lại để xử lý khi lock được release. Sau khi ghi dữ liệu vào cache, owner sẽ release lock. Khi đó, những process chờ sẽ nhận được lệnh retry. Chúng sẽ lấy data từ cache, lúc này đã sẵn dùng.

“Chờ” trong máy ảo Erlang chỉ đơn thuần là tạo một timer và … không làm gì cả, nên overhead hầu như không có.

Với locking, việc đảm bảo lock sẽ được release trong mọi tình huống là vấn đề sống còn. Nếu không release, những requests đến sau sẽ không thể thực hiện được, vì chúng không bao giờ giành được lock.

Một câu hỏi thường được tụi tui hỏi đi hỏi lại khi hiện thực cache locking là: Khi lock owner bị crash, ta sẽ xử lý như thế nào?

Trước tiên ta cần phải release lock. Hàm Process.monitor/1 (xem thêm trong bài Elixir/Erlang, Actors model và Concurrency) được dùng để monitor lock owner. Khi lock owner crash, một message tên là DOWN sẽ được gửi đến, lock process sẽ release lock mà owner này đang giữ.

Với những process đang chờ, khi owner crash, cũng sẽ xử lý như là chính chúng nó crash. Bởi suy cho cùng, owner cũng thực hiện task cho chính những process này.

CloudFront

Sau khi áp dụng locking cho cả những endpoint dùng cache khác và chạy load testing với user story, performance đo được đã là rất tốt.

Tuy nhiên để tăng tốc hơn nữa , tụi tui đặt thêm Amazon CloudFront lên trước các API server đặt ở Châu Âu. Thứ nhất là CloudFront đỡ được gần 50% load. Thứ hai là nó là một content delivery network (CDN) với service trải rộng khắp thế giới, đảm bảo trải nghiệm cho user ở châu Á, Châu Đốc và một số châu liên quan.

Bài viết này sẽ giúp tôi tăng lương như thế nào?

Bài viết này không giúp bạn tăng lương, nhưng hi vọng nó đã cung cấp cho bạn một số thông tin về cache stampede.

Cache stampede là hiện tượng khi high load xảy ra, cache bị miss hàng loạt làm cho thao tác tốn kém được thực hiện nhiều lần, ảnh hướng xấu đến performance của hệ thống.

Để fix cache stampede, bạn thường có 3 hướng giải pháp:

  1. Dùng lock.
  2. Cache warming.
  3. Dự đoán khi nào cache expiration.

NGUY HIỂM! KHU VỰC NHIỀU GIÓ!
Khuyến cáo giữ chặt bàn phím và lướt thật nhanh khi đi qua khu vực này.
Chức năng này hỗ trợ markdown và các thứ liên quan.

Bài viết cùng chủ đề

ExUnit capture log và Erlang IO system

Bài viết giải thích cách IO system trong Erlang vận hành và một số ứng dụng của nó.

Elixir - Ngôn ngữ được viết bằng macros

Macro không những là một trong những viên gạch giúp bạn meta-program với Elixir, mà nó còn là công cụ giúp Elixir meta-program … chính nó nữa.

IO data và Vectored IO

Bài viết giới thiệu về IO data, Vectored I/O và tối ưu hóa hệ thống dùng Elixir bằng cách tận dụng Vectored I/O.