О давках с кэшем

Я часто оказываюсь в ситуациях, когда мне нужно кэшировать то или иное. Часто эти значения кэшируются на определенный период времени. Вы, вероятно, знакомы с этим шаблоном. Вы пытаетесь получить значение из кэша, если вам это удается, вы возвращаете его вызывающей стороне и заканчиваете. Если значения нет, вы извлекаете его (скорее всего из базы данных) или вычисляете и помещаете в кеш. В большинстве случаев это отлично работает. Однако если к ключу, который вы используете для записи в кэше, обращаются часто, а операция по вычислению данных занимает некоторое время, вы окажетесь в ситуации, когда несколько параллельных запросов одновременно получат промах в кэше. Все эти запросы будут независимо загружать из источника и сохранять значение в кеше. Это приводит к напрасной трате ресурсов и может даже привести к отказу в обслуживании.

Позвольте мне проиллюстрировать это на примере. Я буду использовать Redis для кеша и простой http-сервер Go сверху. Вот полный код:

package main

import (
    "errors"
    "log"
    "net/http"
    "time"

    "github.com/redis/go-redis/v9"
)

type handler struct {
    rdb *redis.Client
    cacheTTL time.Duration
}

func (ch *handler) simple(w http.ResponseWriter, r *http.Request) {
    cacheKey := "my_cache_key"
    // we'll use 200 to signify a cache hit & 201 to signify a miss
    responseCode := http.StatusOK
    cachedData, err := ch.rdb.Get(r.Context(), cacheKey).Result()
    if err != nil {
        if !errors.Is(err, redis.Nil) {
            log.Println("could not reach redis", err.Error())
            http.Error(w, "could not reach redis", http.StatusInternalServerError)
            return
        }

        // cache miss - fetch & store
        res := longRunningOperation()
        responseCode = http.StatusCreated

        err = ch.rdb.Set(r.Context(), cacheKey, res, ch.cacheTTL).Err()
        if err != nil {
            log.Println("failed to set cache value", err.Error())
            http.Error(w, "failed to set cache value", http.StatusInternalServerError)
            return
        }
        cachedData = res
    }
    w.WriteHeader(responseCode)
    _, _ = w.Write([]byte(cachedData))
}

func longRunningOperation() string {
    time.Sleep(time.Millisecond * 500)
    return "hello"
}

func main() {
    ttl := time.Second * 3
    rdb := redis.NewClient(&redis.Options{
        Addr: "localhost:6379",
    })

    handler := &handler{
        rdb: rdb,
        cacheTTL: ttl,
    }

    http.HandleFunc("/simple", handler.simple)
    if err := http.ListenAndServe(":8080", nil); err != nil {
        log.Fatalf("Could not start server: %s\n", err.Error())
    }
}

Давайте немного загрузим конечную точку /simple и посмотрим, что произойдет. Для этого я использую вегету.

Я запускаю вегета-атаку -duration=30s -rate=500 -targets=./targets_simple.txt > res_simple.bin. В итоге Vegeta выполняет 500 запросов каждую секунду в течение 30 секунд. Я представляю их в виде гистограммы результирующих кодов HTTP с интервалами по 100 мс каждый. Результатом является следующий график.

Когда мы начинаем эксперимент, кеш пуст — у нас там нет хранимых значений. Мы получаем первоначальную ажиотаж, когда к нашему серверу поступает множество запросов. Все они проверяют кеш, ничего там не находят, вызывают longRunningOperation и сохраняют его в кеше. Поскольку longRunningOperation требует ~500 мс для выполнения любых запросов, сделанных в течение первых 500 мс, в конечном итоге вызывается longRunningOperation. Как только одному из запросов удается сохранить значение в кеше, все последующие запросы извлекают его из кеша, и мы начинаем видеть ответы с кодом состояния 200. Затем шаблон повторяется каждые 3 секунды, когда срабатывает механизм истечения срока действия Redis.

В этом игрушечном примере это не вызывает никаких проблем, но в производственной среде это может привести к ненужной нагрузке на ваши системы, ухудшению пользовательского опыта или даже к отказу в обслуживании. Так как же мы можем предотвратить это? Ну, есть несколько способов. Мы могли бы ввести блокировку — любая ошибка в кэше приведет к тому, что код попытается установить блокировку. Распределенная блокировка — непростая задача, и часто она имеет тонкие крайние случаи, требующие деликатного обращения. Мы также могли бы периодически пересчитывать значение с помощью фонового задания, но для этого потребуется запуск дополнительного процесса, вводящего еще один процессор, который необходимо поддерживать и отслеживать в нашем коде. Этот подход также может оказаться неосуществимым, если у вас есть ключи динамического кэша. Существует еще один подход, называемый вероятностным досрочным истечением, и я хотел бы изучить его подробнее.

Вероятностное досрочное истечение

Этот метод позволяет пересчитать значение на основе вероятности. При извлечении значения из кэша вы также вычисляете, нужно ли вам восстановить значение кэша на основе вероятности. Чем ближе вы к истечению срока действия существующего значения, тем выше вероятность.

Я основываю конкретную реализацию на XFetch А. Ваттани, Ф. Чирикетти и К. Ловенштейна в книге Optimal Probabilistic Cache Stampede Prevention.

Я представлю новую конечную точку на HTTP-сервере, которая также будет выполнять дорогостоящие вычисления, но на этот раз при кэшировании будет использоваться XFetch. Чтобы XFetch работал, нам нужно хранить информацию о том, сколько времени заняла дорогостоящая операция (дельта) и когда истечет срок действия ключа кэша. Чтобы добиться этого, я представлю структуру, которая будет содержать эти значения, а также само сообщение:

type probabilisticValue struct {
    Message string
    Expiry time.Time
    Delta time.Duration
}

Я добавляю функцию, которая оборачивает исходное сообщение этими атрибутами и сериализует его для хранения в Redis:

func wrapMessage(message string, delta, cacheTTL time.Duration) (string, error) {
    bts, err := json.Marshal(probabilisticValue{
        Message: message,
        Delta: delta,
        Expiry: time.Now().Add(cacheTTL),
    })
    if err != nil {
        return "", fmt.Errorf("could not marshal message: %w", err)
    }

    return string(bts), nil
}

Давайте также напишем метод для перерасчета и сохранения значения в redis:

func (ch *handler) recomputeValue(ctx context.Context, cacheKey string) (string, error) {
    start := time.Now()
    message := longRunningOperation()
    delta := time.Since(start)

    wrapped, err := wrapMessage(message, delta, ch.cacheTTL)
    if err != nil {
        return "", fmt.Errorf("could not wrap message: %w", err)
    }
    err = ch.rdb.Set(ctx, cacheKey, wrapped, ch.cacheTTL).Err()
    if err != nil {
        return "", fmt.Errorf("could not save value: %w", err)
    }
    return message, nil
}

Чтобы определить, нужно ли нам обновлять значение на основе вероятности, мы можем добавить метод к вероятностномузначению:

func (pv probabilisticValue) shouldUpdate() bool {
    // suggested default param in XFetch implementation
    // if increased - results in earlier expirations
    beta := 1.0
    now := time.Now()
    scaledGap := pv.Delta.Seconds() * beta * math.Log(rand.Float64())
    return now.Sub(pv.Expiry).Seconds() >= scaledGap
}

Если мы все это подключим, мы получим следующий обработчик:

func (ch *handler) probabilistic(w http.ResponseWriter, r *http.Request) {
    cacheKey := "probabilistic_cache_key"
    // we'll use 200 to signify a cache hit & 201 to signify a miss
    responseCode := http.StatusOK
    cachedData, err := ch.rdb.Get(r.Context(), cacheKey).Result()
    if err != nil {
        if !errors.Is(err, redis.Nil) {
            log.Println("could not reach redis", err.Error())
            http.Error(w, "could not reach redis", http.StatusInternalServerError)
            return
        }

        res, err := ch.recomputeValue(r.Context(), cacheKey)
        if err != nil {
            log.Println("could not recompute value", err.Error())
            http.Error(w, "could not recompute value", http.StatusInternalServerError)
            return
        }
        responseCode = http.StatusCreated
        cachedData = res

        w.WriteHeader(responseCode)
        _, _ = w.Write([]byte(cachedData))
        return
    }

    pv := probabilisticValue{}
    err = json.Unmarshal([]byte(cachedData), &pv)
    if err != nil {
        log.Println("could not unmarshal probabilistic value", err.Error())
        http.Error(w, "could not unmarshal probabilistic value", http.StatusInternalServerError)
        return
    }

    if pv.shouldUpdate() {
        _, err := ch.recomputeValue(r.Context(), cacheKey)
        if err != nil {
            log.Println("could not recompute value", err.Error())
            http.Error(w, "could not recompute value", http.StatusInternalServerError)
            return
        }
        responseCode = http.StatusAccepted
    }

    w.WriteHeader(responseCode)
    _, _ = w.Write([]byte(cachedData))
}

Обработчик работает так же, как и первый, однако при попадании в кэш мы бросаем кости. В зависимости от результата мы либо просто возвращаем только что полученное значение, либо обновляем значение раньше.

Мы будем использовать коды состояния HTTP, чтобы определить один из трех случаев:

• 200 — мы вернули значение из кэша
• 201 — промах в кэше, значение отсутствует
• 202 – попадание в кэш, запуск вероятностного обновления

Я снова запускаю vegeta, на этот раз с новой конечной точкой, и вот результат:

Крошечные синие точки обозначают, когда мы фактически закончили досрочное обновление значения кэша. Мы больше не видим промахов в кэше после начального периода прогрева. Чтобы избежать первоначального скачка, вы можете предварительно сохранить кешированное значение, если это важно для вашего варианта использования.

Если вы хотите более агрессивно использовать кэширование и чаще обновлять значение, вы можете поиграть с параметром бета-версии. Вот как выглядит тот же эксперимент с бета-параметром, равным 2:

Теперь мы видим вероятностные обновления гораздо чаще.

В целом, это небольшой изящный метод, который может помочь избежать давки в кэше. Однако имейте в виду, что это работает только в том случае, если вы периодически извлекаете один и тот же ключ из кеша — в противном случае вы не увидите особой пользы.

Есть ли другой способ справиться с давкой из кэша? Заметили ошибку? Дайте мне знать в комментариях ниже!