Mariusz Krzanowski blog

Intensive cache miss

Introduction

It is common knowledge that using cache can speed a lot our applications. In this post I would like to focus on application design using cache. The simplest scenario using cache that I frequently see follows this algorithm.

Cache hit:
Cache hit

  1. Consume incoming request and evaluate cache KEY.
  2. Try to get information from cache using KEY.
  3. Wait for an answer.
  4. Information found ⇒ Send response back to requester.

Cache miss:
Cache miss

  1. Consume incoming request and evaluate cache KEY.
  2. Try to get information from cache using KEY.
  3. Wait for an answer.
  4. Information not found ⇒ ask ‘slow’ system for data.
  5. Wait longer for an answer.
  6. Update cache by received information and send response back to the requester.

The algorithm is simple, but this simplicity has a cost.

In the algorithm description I have additionally put the wait for an answer bit because every request to an external system, costs time. When your requests are evenly distributed in KEY usage, this algorithm works fine. Probably your clients will not complain. But what if you have a celebrity KEY, which is hit very often – a few hundred times per second?

Thought experiment

Let’s do a thought experiment. Let’s assume that for some reason cache is invalidated for a specific key. Your server just received about hundred requests for this specific key. What happens? All these requests will try to ask your cache for resource. All of them will miss and, as a consequence, they will ask ‘slower’ system for the same resource. At the end all of them will update cache for the same KEY with identical value. Something is wrong, don’t you think?

Solution

So how to solve this problem? Thirst, we have to think about following fact. It does not matter if we are asking cache or ‘slow’ system about resources, because it is always slower than accessing local data. It means than if we add small overhead at computational level it should not be a problem. Now we are ready to rethink data retrieval process and delegate it to specialized unit.

New process has the following steps:

  1. Consume incoming request and evaluate cache KEY.
  2. Check if there is a pending process of KEY retrieval.
    • YES there is a pending process ⇒ subscribe self to result.
    • NO there is no pending process ⇒ create new KEY retrieval process and subscribe self to result.
  3. Wait for a result from the retrieval process.
  4. Send response back to the requester.

Pending ‘process of KEY retrieval’ should execute subset of steps described at the beginning of this article. All ‘pending processes’ can be stored in local hash map. So we can quickly recognize O(1) if KEY retrieval process is already started. The count of pending processes stored in HashMap is less or equal to pending requests count, so if you have e.g. 10000 requests per second, it should contain maximum 10000 items. If multiple requests hit identical KEY, it means that you are saving more memory, and time. Below you can find a few reasons for that:

  • Responses from cache or ‘slow’ system are grouped by KEY (no duplication of data in memory).
  • Your requests that arrived in the middle of KEY retrieval process are not forced to execute full process themselves, but they can wait for already pending results. Statistically, they will wait shorter.
  • Your internal network does not transfer the same data between cache and your process multiple times.
  • Cache can handle more requests, because it is not asked for identical KEY repeatedly.
  • Your ‘slow’ system is not hit repeatedly with heavy queries when cache is invalidated during high traffic hours.

Proposed solution is not a silver bullet. Each system requires individual analysis. But what I described above should help you better understand problems of designing heavy traffic applications.

Previous

Idempotence in sending e-mail

Next

ConcurrentDictionary and race condition

2 Comments

  1. Piotr T.

    Panie Matrix, czy brał Pan pod uwagę scenariusz, w którym w trakcie tych 10000 żądań następuje modyfikacja danych źródłowych? Ja to widzę tak:
    1. Oryginalny scenariusz: połowa żądań dostanie starą wartość a druga połowa nową.
    2. Nowy scenariusz: wszystkie żądania dostaną starą wartość.

    Czy to jest problem – zależy od konkretnych wymagań.

    • Oczywiście, że brałem pod uwagę i taki scenariusz 🙂

      Prawda jest taka, że i pierwszy i drugi scenariusz zakłada nieświeżość danych, więc decyzja biznesowa nigdy nie będzie podejmowana na podstawie danych z cache. Cache zawsze zakłada jakąś nieświeżość danych. Zresztą jak wszyscy wiemy nawet transmisja danych przez sieć już może powodować ich nieświeżość (jakiś update w trakcie renderowania odpowiedzi). Standardem zatem jest, że decyzja biznesowa jest podejmowana, przy dostępie do źródła wiedzy o bieżącym stanie (agregatu).

      Aby drugi scenariusz był prawdziwy, to znaczy, że wszystkie żądania, muszą się wstrzelić dokładnie w ten sam slot czasowy, kiedy jest generowana “wolna” odpowiedź. Wówczas faktycznie wszystkie żądania dostaną w tym samym przedziale czasowym tę samą odpowiedź. Zaznaczam, że grupowanie następuje tylko w oknie czasowym stworzonym przez pierwsze żądanie. To czy okno będzie się rozciągać w czasie to już decyzja projektowa. Co za tym idzie? Jak tylko pierwsze żądanie się zakończy, to powstaje już nowe okno czasowe dla kolejnego żądania (grupy żądań), które nie wstrzeliło się w ten slot czasowy. Taka implementacja zakłada, że żądania przychodzące w tym samym oknie czasowym dostaną tę samą odpowiedź, bez przeciążania cache i “wolnego” systemu.

      Zadaniem artykułu jest nakreślenie alternatywy dla “standardowego” podejścia. Niestety nie ma uniwersalnego, rozwiązania przy systemach rozproszonych. Nie mniej znajomość w/w podejścia pozwala spojrzeć na problem z innej strony. Przy bardzo dużym obciążeniu i unieważnieniu cache w/w rozwiązanie, nie doprowadza do śmierci “wolnego” systemu, a może i całości. Przy “standardowym” podejściu jak wszystkie żądania trafią prawie na raz w pusty cache “wolny” system może zostać mocno obciążony.

      Jakby była potrzebna dokładniejsza analiza i szersza dyskusja w temacie, to zapraszam do kontaktu

Powered by WordPress & Theme by Anders Norén