Skip to content

readme.ru.md

Latest commit

 

History

History
299 lines (238 loc) · 31.1 KB

readme.ru.md

File metadata and controls

299 lines (238 loc) · 31.1 KB

CByteCache

Байтовый вытесняющий in-memory кэш, базирующийся на cbyte библиотеке. Написан как замена bigcache, но кардинально отличается от него организацией хранения данных и множеством дополнительных функций, облегчающих работу в хайлоад проектах.

Как работает

Модель хранения данных bigcache основана на хэш-таблице map[uint64]uint32 для хранения ключей и огромных слайсов []byte для хранения данных. Это прекрасно помогает для нивелирования GC нагрузки, но избыточно с точки зрения экономии памяти - так, однажды выделенный избыток памяти, никогда не будет освобождён. Для проектов с переменной нагрузкой это весьма неоптимальный подход, т.к. память будет простаивать без пользы.

cbytecache использует ту же структуру для хранения ключей, но непосредственно байтовое хранилище использует диаметрально противоположный подход - память разделена на небольшие арены фиксированного размера, а данные распределяются между ними. Арены по необходимости могут выделяться, использоваться и освобождаться, что позволяет в каждый момент времени использовать ровно столько памяти сколько необходимо. А для того, чтобы GC не аффектил производительность как кэша, так и системы, арены используют библиотеку cbyte для маскировки от GC. С точки срения GC арена это просто структура, состоящая из числовых полей и располагающаяся в стеке. Таким образом GC не будет никак проверять эту структуру.

На более высоком уровне, кэш разделён на шарды, называемые бакетами (bucket). У каждого бакета есть своя хэш-таблица индексов и очередь арен. Это единственные указатели в кэше, поэтому когда GC начинает проверять кэш, то он увидит несколько хэш-таблиц и слайсов примитивных структур и не будет ничего знать про огромные объёмы памяти, располагающиеся в невидимой для него области. Очередь арен памяти будет рассмотрена в отдельном разделе ниже.

Очередь арен памяти

Как уже упоминалось, cbytecache является вытесняющим кэшем, а в качестве минимальной единицы выделяемой памяти используется арена. Все арены, выделяемые в пределах одного бакета, хранятся внутри специальной структуры, называемой очередью арен. Причём последовательность арен в хранилище buf не отображает реальную последовательность в очереди. Каждая арена имеет prev/next индексы, указывающие на соседние арены и они могут быть произвольными в пределах хранилища. Таким образом, очередь арен представляет собой двусвязный список, но без указателей.

Когда наступает очередной цикл вытеснения устаревших данных, то определяется стартовый и конечный индексы арен, содержащих устаревшие данные. Затем эти арены "переносятся" в конец очереди и считаются свободными, а их память далее перезаписывается новыми данными по необходимости. Таким образом, очередь арен реализует циклическую очередь, причём делает это очень дёшево - происходит замена нескольких prev/next индексов у арен.

Рассмотрим это на простом примере. Пусть у нас будет очередь, состоящая из 10-и арен и заполненная на 3/4:

buf:    ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
        │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
          ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
          │   │   │   │   │   │   │   │   │   └─────────────────────────────────────────────────────────────────────────────────────┐
          │   │   │   │   │   │   │   │   └────────────────────────────────────────────────────────────────────────────┐            │
          │   │   │   │   │   │   │   └───────────────────────────────────────────────────────────────────┐            │            │
          │   │   │   │   │   │   └──────────────────────────────────────────────────────────┐            │            │            │
          │   │   │   │   │   └─────────────────────────────────────────────────┐            │            │            │            │
          │   │   │   │   └────────────────────────────────────────┐            │            │            │            │            │
          │   │   │   └───────────────────────────────┐            │            │            │            │            │            │
          │   │   └──────────────────────┐            │            │            │            │            │            │            │
          │   └─────────────┐            │            │            │            │            │            │            │            │
          └────┐            │            │            │            │            │            │            │            │            │
               │            │            │            │            │            │            │            │            │            │
queue:       ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐
             │ ▒▒▒▒ │     │ ▒▒▒▒ │     │ ▒▒▒▒ │     │ ▒▓▓▓ │     │ ▓▓▓▓ │     │ ▓▓▓▓ │     │ ▓▓▓▓ │     │ ▓▓░░ │     │ ░░░░ │     │ ░░░░ │
             │ id 0 │◄┐ ┌►│ id 1 │◄┐ ┌►│ id 2 │◄┐ ┌►│ id 3 │◄┐ ┌►│ id 4 │◄┐ ┌►│ id 5 │◄┐ ┌►│ id 6 │◄┐ ┌►│ id 7 │◄┐ ┌►│ id 8 │◄┐ ┌►│ id 9 │
        x ◄──│ p -1 │ └─┼─│ p  0 │ └─┼─│ p  1 │ └─┼─│ p  2 │ └─┼─│ p  3 │ └─┼─│ p  4 │ └─┼─│ p  5 │ └─┼─│ p  6 │ └─┼─│ p  7 │ └─┼─│ p  8 │
             │ n  1 │───┘ │ n  2 │───┘ │ n  3 │───┘ │ n  4 │───┘ │ n  5 │───┘ │ n  6 │───┘ │ n  7 │───┘ │ n  8 │───┘ │ n  9 │───┘ │ n -1 │──► x
             └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘
legend:
▒ - expired data space
▓ - used space
░ - free space

Как видно, у очереди:

  • арена #0 является головой очереди (head)
  • арена #9 является хвостом очереди (tail)
  • арена #7 является актуальной (actual)
  • пусть прошло какое-то количество времени и первые три арены содержат только устаревшие данные, т.е. арена #3 является нижней границей полезных данных (low)

Произошло выселение устаревших данных, в результете имеем вот такое состояние очереди:

buf:    ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
        │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
          ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
          │   │   └───┼───┼───┼───┼───┼───┼───┼─────────────────────────────────────────────────────────────────────────────────────┐
          │   └───────┼───┼───┼───┼───┼───│───│────────────────────────────────────────────────────────────────────────┐            │
          └───────────┼───┼───┼───┼───│───│───│───────────────────────────────────────────────────────────┐            │            │
                      │   │   │   │   │   │   └──────────────────────────────────────────────┐            │            │            │
                      │   │   │   │   │   └─────────────────────────────────────┐            │            │            │            │
                      │   │   │   │   └────────────────────────────┐            │            │            │            │            │
                      │   │   │   └───────────────────┐            │            │            │            │            │            │
                      │   │   └──────────┐            │            │            │            │            │            │            │
                      │   └─┐            │            │            │            │            │            │            │            │
               ┌──────┘     │            │            │            │            │            │            │            │            │
               │            │            │            │            │            │            │            │            │            │
queue:       ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐     ┌──────┐
             │ ▒▓▓▓ │     │ ▓▓▓▓ │     │ ▓▓▓▓ │     │ ▓▓▓▓ │     │ ▓▓░░ │     │ ░░░░ │     │ ░░░░ │     │ ░░░░ │     │ ░░░░ │     │ ░░░░ │
             │ id 3 │◄┐ ┌►│ id 4 │◄┐ ┌►│ id 5 │◄┐ ┌►│ id 6 │◄┐ ┌►│ id 7 │◄┐ ┌►│ id 8 │◄┐ ┌►│ id 9 │◄┐ ┌►│ id 0 │◄┐ ┌►│ id 1 │◄┐ ┌►│ id 2 │
        x ◄──│ p -1 │ └─┼─│ p  3 │ └─┼─│ p  4 │ └─┼─│ p  5 │ └─┼─│ p  6 │ └─┼─│ p  9 │ └─┼─│ p  8 │ └─┼─│ p  9 │ └─┼─│ p  0 │ └─┼─│ p  1 │
             │ n  4 │───┘ │ n  5 │───┘ │ n  6 │───┘ │ n  7 │───┘ │ n  8 │───┘ │ n  7 │───┘ │ n  0 │───┘ │ n  1 │───┘ │ n  2 │───┘ │ n -1 │──► x
         │   └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘     └──────┘
         │                                                                                              └────────────────────────────────┘
         │                                                                                                               ▲
         └───────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

legend:
▒ - expired data space
▓ - used space
░ - free space

Поменялись prev/next индексы:

  • low.p = -1 , т.е арена #3 стала новым head
  • tail.n = head.id , т.е. старый head стал рядовой ареной посередине очереди
  • low-1.n = -1 , т.е. low-1 стало новым tail
  • арены #0, #1, #2 стали свободными, т.к. теперь лежат после actual
  • а буфер buf остался неизменным, никакого реального движения элементов в нём не произошло

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

Настройка

Кэш инициализируется посредством заполнения специальной структуры Config. Ниже будут рассмотрены все поля конфига и даны объяснения как их изменение повлияет на поведение кэша.

Capacity и ArenaCapacity

Параметры Capacity и ArenaCapacity задают соответственно общую ёмкость кэша и ёмкость каждой арены. Оба параметра можно опустить, в этом случае кэш будет безразмерным, а ёмкость арены будет 16 КБ по умолчанию.

Задавать эти параметры можно посредством MemorySize констант, например так: Capacity: cbytecache.Gigabyte * 5.

Hasher

Хранить ключи кэша в исходном строковом виде нецелесообразно, т.к. это указатели, а мы хотим избежать внимания GC. Поэтому мы их преобразовываем в uint64 хэши с помощью параметра Hasher. Он должен реализовывать одноимённый интерфейс

type Hasher interface {
	Sum64(string) uint64
}

и является обязательным параметром. Цель его наличия в конфиге - возможность повлиять на количество коллизий. Если выбранный Hasher генерирурет слишком большое количество коллизий, то вы вольны выбрать другой.

Buckets

Количество бакетов в кэше. Это обязательный параметр и он должен быть обязательно больше 0. Не рекомендуется задавать очень большой размер для ненагруженных кэшей, т.к. это приведёт к перерасходу памяти.

ExpireInterval и ExpireListener

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

Необязательный параметр ExpireInterval должен содержать реализацию интерфейса Listener куда будет направлен элемент (Entry) кэша. Может быть полезным для кэшей с post-expire логикой.

EvictInterval и EvictWorkers

Эти параметры регулируют выселение элементов из кэша. EvictInterval устанавливает как часто должно срабатывать выселение. Рекомендуется задавать этот параметр меньше, чем ExpireInterval, в противном случае будет много промахов кэша по причине устаревания элементов. Допустимо задавать маленький интервал, т.к. это дешёвая операция. Впрочем, интервал меньше одной секунды не имеет никакого смысла.

Параметр EvictWorkers ограничивает количество потоков, которые будут осуществлять выселение в каждом бакете. Задавать значение больше, чем Buckets не имеет смысла. Рекомендуемое значение - 2 и более раз меньше Buckets.

VacuumInterval, VacuumWorkers и VacuumRatio

cbytecache умеет освобождать память, в которой более не нуждается. Это весьма полезное свойство для проектов с переменной нагрузкой. VacuumInterval и VacuumWorkers по поведению аналогичны Evict* параметрам, замечу только, что VacuumInterval не следует делать слишком уж маленьким. Это приведёт к большому числу выделений/освобождений арен, что способно повлиять на скорость записи в кэш.

Параметр VacuumRatio устанавливает какую часть памяти, доступную для освобождения, следует освободить. Так, при значении 0.25, бакет размера 100 МБ и свободными 20 МБ памяти, освободит и отдаст ОС 5 МБ памяти. Диапазон значений [0.0..1.0]. Задавать как слишком маленькие, так и слишком большие значения следует по необходимости. Рекомендуются средние значения.

ResetWorkers и ReleaseWorkers

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

CollisionCheck

Этот параметр заставит кэш при записи проверять коллизии хэшей. Факт коллизии будет отображён в логе (параметр Logger) и/или в метриках (параметр MetricsWriter).

DumpWriter, DumpInterval и DumpWriteWorkers

Одним из важнейших требований, которым не удовляетворял bigcache, является потеря данных кэша при рестарте приложения. cbytecache имеет такую возможность, хотя она не явлется обязательной.

Параметр DumpWriter должен реализовывать одноимённый интерфейс куда будет направлен каждый неустаревший элемент кэша. Библиотека bytecache не содержит из коробки никаких реализаций дампера, но есть отдельная библиотека cbcdump, которая содержит реализацию FS для дампа на диск. Вы вольны написать любую другую реализацию, для дампа в облачное хранилище например.

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

Параметр DumpWriteWorkers задаёт количество потоков записи дампа. Один поток занимается запиьсю дампа одного отдельного бакета, так что не имеет смысла задавать это значение больше, чем Buckets.

DumpReader, DumpReadBuffer, DumpReadWorkers и DumpReadAsync

Набор параметров из предыдущего раздела описывает как дамп пишется, а этот набор задаёт как происходит чтение.

Параметр DumpReader должен реализовывать одноимённый интерфейс, который будет читать из дампа элементы до тех пор, пока чтение не завершится ошибкой (запланировано io.EOF, но может быть любая другая).

Параметр DumpReadBuffer задаёт сколько прочитанных элементов могут ожидать записи в кэш.

Параметр DumpReadWorkers задаёт количество потоков чтения из дампа. Один поток одномоментно способен записывать прочитанный элемента только в один бакет, поэтому не имеет смысла задавать этот параметр больше, чем Buckets.

Параметр DumpReadAsync позволяет указать, что кэш должен восстанавливать данные из дампа асинхронно, таким образом кэш сразу после инициализации будет доступен для использования, а чтение дампа не будет блокировать основной поток приложения.

MetricsWriter

Вторым важным требованием к кэшу, которому не удовляетворял bigcache, является покрытие кэша метриками. По умолчанию, единственное что мы знаем про кэш, так это то, что его размер не больше HardMaxCacheSize. Мы не знаем ни количество записанных данных, ни их размер, не можем оценить как интенсивно кэш потребляет память, с какой скоростью пишет/читает данные, ... Приходится дополнительно описывать метрики и вызывать их совместно с методами кэша, а это неудобно. И даже в этом случае внутренее состояние кэша является чёрным ящиком - неизвестно, с позиции TSDB, общий объём кэша, размер занятой/свободной памяти.

Параметр MetricsWriter должен реализовывать одноимённый интерфейс. Представленные методы позволяют покрыть метриками каждое событие внутри кэша. Библиотека содержит две коробочные версии MW:

Как следует из названий, первый логирует все события и бесполезен для production, второй же полностью рабочий и пригоден для прода. Аналогично, вы можете написать свою реализацию для нужной TSDB.

Использование

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

Простая инициализация

import (
	"time"

    "github.com/koykov/cbytecache"
    "github.com/koykov/hash/fnv"
    "github.com/stretchr/testify/assert"
)

cache, _ := cbytecache.New(DefaultConfig(time.Minute, fnv.Hasher{}, cbytecache.Megabyte * 100))

_ = cache.Set("foobar", []byte("entry body bytes ..."))
entry, _ := cache.Get("foobar")
assert.Equal(t, entry, []byte("entry body bytes ..."), "entry mismatch")

Детальная инициализация

import (
    "time"

    dumpfs "github.com/koykov/cbcdump/fs"
    "github.com/koykov/cbytecache"
    "github.com/koykov/hash/fnv"
    metrics "github.com/koykov/metrics_writers/cbytecache"
	"github.com/stretchr/testify/assert"
)

conf := cbytecache.Config{
    Capacity: cbytecache.Megabyte * 100,
    Hasher: fnv.Hasher{},
    Buckets: 128,
    ExpireInterval: time.Second * 30,
    EvictInterval: time.Second * 5,
    VacuumInterval: time.Second * 10,
    DumpWriter: &dumpfs.Writer{
        FilePath: ("dump/example.bin",
        Buffer:   cbytecache.Megabyte,
    },
    DumpReader: &dumpfs.Reader{
        FilePath: "dump/example.bin",
    },
    MetricsWriter: metrics.NewPrometheusMetricsWP("my_cache_key", time.Millisecond),
}
cache, _ := cbytecache.New(&conf)
_ = cache.Set("foobar", []byte("..."))
entry, _ := cache.Get("foobar")
assert.Equal(t, entry, []byte("entry body bytes ..."), "entry mismatch")