Pull to refresh

Comments 41

Если резко возрастёт нагрузка, то ввод в работу новых инстансов не позволит распределить старые сессии между новыми и старыми инстансами.
Важный момент. Спасибо!
Это получается, что везде, где используются map, есть риск OOM.
есть кэш ristretto — там вроде без мапов
Внутри тоже map и тоже есть удаление/добавление в него. Поэтому не очень понятно, как поможет против пожирания памяти map.

Монструозненько и есть пути попроще. В базе пишем триггер, который делает NOTIFY в момент обновления сущности. На app серверах делаем LISTEN и обновляем кеши. Если обновлений << чтений, то работает на ура.


Если триггеры религия не позволяет, то notify можно делать руками, в транзакции обновления. Бонусом получим +1 к консистентности — notify пойдёт до клиентов только если транзакция успешно завершилась.


Если обновлений поровну с чтениями и модель сложная, то я вам поздравляю, у вас самый сложный случай. Это уже из области real time игр, биржевой торговли и т.п. Тоже можно сделать хорошо и быстро, но это уже долго и сложно и нужно сразу об этом думать.

А если произошла потеря связи с БД, кратковременная, но в течении неё произошла нотификация, как проверить, что кэш содержит актуальные данные?
Способ стандартный и обычный для распределенных систем. Делаем две вещи: добавляем колонку version и sequence с названием versions. При каждом обновлении берем из versions версию и пишем ее в колонку version. То есть каждая запись получает уникальный, возрастающий номер, который атомарно увеличивается на каждое обновление. Каждый кеш периодически опрашивает базу на предмет совпадения версий. Если в базе больше, то нужно перечитать все данные с больше версией. При получении сообщения нужно проверить версию и если она не «версия кеша + 1» то нужно перечитывать данные из базы. Версии пришло сообщение с версией «меньше версии кеша» то такое сообщение нужно игнорировать.
1. А если произошло удаление записи?
2. А что с консистентностью кэша и БД между периодами опроса базы?
3. Зачем перечитывать в кэш все данные с бОльшей версией? Кэш должен содержать только то, чем пользуемся, а не на авось.
Ваш алгоритм при учёте всех моментов становиться гораздо сложнее моего, а преимущество только одно — нет Redis.
Ваш алгоритм при учёте всех моментов становиться гораздо сложнее моего, а преимущество только одно — нет Redis.

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

1. А если произошло удаление записи?
2. А что с консистентностью кэша и БД между периодами опроса базы?
3. Зачем перечитывать в кэш все данные с бОльшей версией? Кэш должен содержать только то, чем пользуемся, а не на авось.

Записи помечать как удаленные, чистить раз в месяц. Консистентность будет eventual, также как и у вас. Кеш можно не перечитывать, а сбрасывать.

В вашем решении должен выполнятся инвариант — «Если в базе лежит объект версии X, то в редисе либо пусто, либо лежит объект версии X». Но у вас сначала обновляется база, затем чиститься редис и параллельно с этим кто-то в редис может писать. Все это происходит на разных машинах. Поэтому рано или поздно в редисе и кешах будет одно, а в базе другое.

Например, у нас есть два сервера. Сервер 1 и 2 только что стартовали, кеш у них пустой, запись версии X1 в базе уже есть. Далее на сервер 1 одновременно приходит два запроса на обновление и чтение записи, на сервер 2 приходит запрос на чтение той-же записи. Вот такая последовательность событий:
— Поток читатель сервера 1 читает из базы версию записи X1
— Поток читатель сервера 2 читает из базы версию записи X1
— Поток писатель сервера 1 комитит в базу версию X2
— Поток писатель сервера 1 чистит редис и кеш
— Поток читатель сервера 1 добавляет запись в кеш и в редис
— Поток читатель сервера 2 добавляет запись в кеш и в редис

Итого — в базе обновленная запись, а в кеше и в редисе старая. Причем на всех серверах. И так будет до тех пор, пока кто-то не обновит запись или кеш не протухнет.
Сброс кэша, возможно только из-за одного обновлённого элемента, не самая хорошая идея. С учётом того, что soft-удаление, по сути, тот же update, с вытекающим отсюда изменением versions в БД то возможна такая последовательность событий:
— обновили запись в БД
— БД отправила нотификацию
— проверили versions в БД,
— выявили несоответствие и сбросили кэш
— получили и обработали нотификацию с одним элементом

Частота такого «ложного» сброса кэша будет зависеть от того, как часто обновляют/удаляют записи и того, как часто проверяется versions в БД.

Насчёт описанного вами примера, да, такого возможно. Но решение простое — при добавлении в кэш сразу делать разный UUID между тем, что в Redis и тем, что в кэше. Тогда при следующем обращении к кэшу, будет выявлена эта разница и будет выполнено обновление кэша. Да, это чуть-чуть снизит производительность, поскольку даже при отсутствии супер быстрого обновления параллельно с добавлением в кэш, будет выполняться один лишний запрос в БД. Но при этом не надо следить за версиями в БД, выполнять сброс кэша, добавлять тригер в БД или менять запросы. А все изменения в кэше будут точечные, только для конкретных элементов.
Кеш нужно сбрасывать только если коннект потеряли.

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

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

У этой проблемы нет решения потому, что нет транзакционного обновления редиса и БД, а это значит, что разные читатели будут видеть неконсистентные данные, что-то уже в базе, чего-то еще нет в редисе. А это в свою очередь значит, что вам нужно как-то решать эти конфликты. С учетом того, что у вас все могут писать в базу и в редис и вас типичная задача на распределенный консенсус между кешами, редисом и базой. Причем каждый узел у вас read-write. Оно просто так не решается и очень редко быстро работает.

В предложенном мной решении все обновления сериализуются базой и все узлы будут видеть все события в одном и том же порядке. Единственно что может быть — прочитали версию X1 из базы и тут же прилетело обновление X1 или вообще что-то еще более старое. Все узлы пишут и читают одну и ту же базу, благодаря ACID все они видят одну и ту же картину.

Генерируемый UUID не имеет никакого отношения к ID-объекта в БД. Я мог бы вместо него использовать CRC объекта, чтобы отслеживать изменения, но генерировать UUID дешевле, чем CRC считать.
В Redis лежит пара: ID-объекта (ключ)<->UUID (значение)
В кэше лежит: ID-объекта (ключ)<->UUID+содержимое объекта.

Сколько бы не было писателей в Redis, всё изменения будут видны по изменению UUID, при обновлении старая пара ID-объекта (ключ)<->UUID (значение) будет удалена, и добавлена новая (ID-объекта тот же, а UUID другой). Если проскочило другое обновление, всё равно не совпадёт UUID в Redis и локальных кэшах и все серверы запросят БД.

Кеш нужно сбрасывать только если коннект потеряли.

Хорошо, вы периодически делаете запрос versions, запрос прошёл, значит связь есть, а versions отличается (нотификация ещё не долетела или не обработана), что делать будете? Добавлять таймаут ожидания нотификации?
Генерируемый UUID не имеет никакого отношения к ID-объекта в БД. Я мог бы вместо него использовать CRC объекта, чтобы отслеживать изменения, но генерировать UUID дешевле, чем CRC считать.

Это понятно, что не имеет отношения. UUID генерируется же писателем в базу, который очищает редис и локальный кеш. Затем читается читателем (одним или несколькими одновременно) и так попадает в редис, верно?

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

Хорошо, вы периодически делаете запрос versions, запрос прошёл, значит связь есть, а versions отличается (нотификация ещё не долетела или не обработана), что делать будете? Добавлять таймаут ожидания нотификации?


Если прилетела нотификаця с версией X, то из базы гарантировано будет прочитана версия >=X. Эти гарантии дает нам комит транзакции в БД. Если пришла нотификация о старой версии или о версии, которая уже есть в кеше, то она, конечно, просто игнорируется. Ничего ждать не нужно.
Это понятно, что не имеет отношения. UUID генерируется же писателем в базу, который очищает редис и локальный кеш. Затем читается читателем (одним или несколькими одновременно) и так попадает в редис, верно?


Нет, не верно. UUID не пишется в БД, он используется только в Redis и в кэше. UUID генерируется при записи в Redis.

Если прилетела нотификаця с версией X, то из базы гарантировано будет прочитана версия >=X. Эти гарантии дает нам комит транзакции в БД. Если пришла нотификация о старой версии или о версии, которая уже есть в кеше, то она, конечно, просто игнорируется. Ничего ждать не нужно


Последовательности событий:
— делаете update, транзакция прошла, отправили нотификацию
— делаете запрос versions, запрос прошёл, значит связь есть
— versions отличается, сбрасываем кэш
— прилетает нотификация

Что делать, чтобы зря не сбрасывать кэш?
Нет, не верно. UUID не пишется в БД, он используется только в Redis и в кэше. UUID генерируется при записи в Redis.

Тогда все еще хуже. Я предлагаю вам уже на практике увидеть все граничные условия. Боюсь их будет достаточно. Вот обратил внимание.
Если UUID не совпадает, то удаляем объект из in-memory кэша, берём из БД, добавляем в in-memory кэш с UUID из Redis.


Удаляем из кеша, берем из БД и добавляем в редис это 3 разные операции. Будет ли все работать, если между этими шагами будут проходить часы, и сотни запросов на другие сервера, а не миллисекунды?

Последовательности событий:
— делаете update, транзакция прошла, отправили нотификацию
— делаете запрос versions, запрос прошёл, значит связь есть
— versions отличается, сбрасываем кэш
— прилетает нотификация

Не так,
— делаете update, транзакция прошла, отправили нотификацию
— пришла нотификация, прочитали базу, обновили кеш, если версия большее чем та, что в кеше;
Или так
— делаете update, транзакция прошла, отправили нотификацию
— делаете запрос versions, добавляем в кеш все, чего в нем нет.
— пришла нотификация, ее версия уже есть в кеше, нотификацию можно пропустить

Кеш сбрасывается только если коннект к БД потерян, то есть мы могли не увидеть какие-то нотификации. В остальных случаях нотификация приводит к обновлению кеша только если мы ее еще не видели. Кеш видел все нотификации с версиями <= максимальной версии в кеше.

Удаляем из кеша, берем из БД и добавляем в редис это 3 разные операции. Будет ли все работать, если между этими шагами будут проходить часы, и сотни запросов на другие сервера, а не миллисекунды?


Аналогичный вопрос можно задать, будет ли всё работать если между завершением транзакции в БД и обработкой полученной нотификации пройдут часы?

— делаете update, транзакция прошла, отправили нотификацию
— делаете запрос versions, добавляем в кеш все, чего в нем нет.
— пришла нотификация, ее версия уже есть в кеше, нотификацию можно пропустить


Тогда если произошло обновление всей БД (пессимистичный вариант), всю БД и придётся запрашивать (запрос всего, что старше versions в кэше). И это полбеды, другая проблема, что запрашивается то, что или уже протухло в кэше, или вот-вот протухнет или вовсе не было в кэше.

В моём варианте, из БД всегда запрашивается только то, чем пользуются клиенты сервиса.

Кеш видел все нотификации с версиями <= максимальной версии в кеше.

Но недостаток, что надо всем сервисам, проверять, а есть ли у них в кэше объект из нотификации. Т.е. обновили объект в БД, но на чтение его никто не запрашивает, в кэше его нет, но нотификацию обработать надо (поискать объект в кэше) и после обработки сменить versions кэша.
Аналогичный вопрос можно задать, будет ли всё работать если между завершением транзакции в БД и обработкой полученной нотификации пройдут часы?

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

В моём варианте, из БД всегда запрашивается только то, чем пользуются клиенты сервиса.

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

Но недостаток, что надо всем сервисам, проверять, а есть ли у них в кэше объект из нотификации. Т.е. обновили объект в БД, но на чтение его никто не запрашивает, в кэше его нет, но нотификацию обработать надо (поискать объект в кэше) и после обработки сменить versions кэша.

Найти объект в хештаблице это примерно 200 ns (наносекунд), если нужно в память ходить. Сравнить его версию еще 10 ns. Сменить версию кеша еще 200 ns, если ждать пока в память все попадет.

Конечно рассылка NOTIFY это своего рода write amplification, который можно игнорировать пока обновлений относительно мало, о чем я сказал в самом начале. Если объекты меняются очень часто, то нужно делать sticky sessions, event sourced модель данных и много много чего еще.
А что в моем варианте мешает делать так же? Если коннект потерян, значит данные в кеше неверные. А что с этим делать, сбрасывать кеш или перезагружать его или перезагружать только часть, решается по месту.

В вашем варианте есть асинхронность обработки NOTIFY и проверки связи с БД. Я уже выше написал, вы неизбежно будете сталкиваться (особенно с ростом количества транзакций и количества экземпляров сервиса), что NOTIFY ещё не обработали, а VERSIONS запросили.
И будете ли вы удалять или перезагружать и то и другое плохо. В первом случае вы просто будете регулярно удалять валидный кэш, что приведёт к нагрузке на БД на время наполнения кэша. Во втором случае вы сделаете запрос в БД всего, что >=VERSIONS в кэше, а значит запросите и то чего нет в кэше, и то что в следующую секунду протухнет, и опять-таки нагрузите БД и ваш сервис громадным и скорее всего избыточным запросом.
Даже если вы решите перед выполнением запроса пройтись по кэшу и для запроса указать только реально содержащиеся данные, всё равно есть риск, что к моменту выполнения запроса часть данных из кэша уже устареют. Т.е. получаем запрос на авось, а не нужных данных.

При получении сообщения нужно проверить версию и если она не «версия кеша + 1» то нужно перечитывать данные из базы.

А здесь тоже интересно. Какие данные? Все что => VERSIONS? Или те, что есть в кэше? Но только часть из них протухнет, пока запрос делали.
Зачем вы придумываете сложности так где их нет? Вот код.

void GetEntity(string id)
{
    if (!_cache.TryGetValue(id, out var entity))
    {
        lock(_cacheLock)
        {
             if (!_cache.TryGetValue(id, out entity))
             {
//maybe put a placeholder for frequent entity that is not 
//in the database anymore and fail before taking lock 
//or hitting a database
                 entity = _dao.LoadEntity(id);
                 if (entity != null)
                 {
                      _cache[id] = entity;
                 }
             }
        }
    }
}

//Happens on every update
//Reload one entity at most.
//If entity is not in the cache - does nothing
//When NOTIFY("1", 1) arrive it could load entity with 
//version 10.
//This is ok, NOTIFY("1", 2)..NOTIY("1", 10) will be ignored
//since cache already has up-to-date data.
void OnNotify(string id, long version)
{
//assuming updates do not happen all the time
//then this is not contented lock, taking such lock cost 
//about 50 ns. Loading 4 bytes from RAM cost 200 ns.
    lock(_cacheLock)
    {
//is this something we are interested in?
        if (_cache.TryGetValue(id, out var entity))
        {           
//stop if we already loaded this update from the db.
            if (entity.Version >= version) return;
 
            var updatedEntity = _dao.LoadEntity(id);
            if (updatedEntity?.Version > entity.Version)
            {
                _cache[id] = updatedEntity;
            }
//deleted or marked as deleted if(updatedEntity.Deleted)
            else  
            {
//or mark as removed
                 _cache.Remove(id); 
            }
       }
    }
}

//happens at most once a week, probably once a year.
void OnReconnect()
{
    lock(_cacheLock)
    {
        _cache.Clear(); 
//or reload everything from cache
//or do nothing
//or reload hot entities as defined by your stats
//or do something else if that make sense
    }
}

void UpdateEntity(Entity entity)
{
    using var tx = StartTx();
//Atomically increment entity version
//Use proper TX isolation level!
//UPDATE ... SET version = version + 1 RETURNING version;
    UpdateEntity(tx, entity);
//NOTIFY cache_channel id, version;
    Notify(tx, entity.Id, entity.Version);
    Commit(tx);
}

Возможно и нет сложностей, но я не вижу:
  • проверку связи с БД
  • проверку, что нет пропущенных нотификаций

Зато вижу, что после получения нотификации делается запрос в БД по принципу «мне повезёт» и данные в кэше не протухнут к моменту ответа.

Бд гарантированно вернёт более новую версию чем есть в кеше, что и как тут протухнет? Проверка связи с бд это try catch вокруг вызовов бд, опустил для краткости.

В кэше протухнет — ttl истёк, объект удалили из кэша. Вернётся значение которое уже не нужно, поскольку нечего обновлять в кэше. Конечно можно добавить его снова в кэш, но это уже избыточность.
Кажется это тривиально решается с помощью локов и/или атомарных операций, деталь реализации.
Не очень понятно, как это тривиально решается. Максимум возможно исключить запрос из БД тех объектов, которые в данный момент удаляются из кэша. Ну запросите вы объект, который есть в кэше и конкретно сейчас не протух. А сразу после обновления в кэше запустится процедура очистки протухших объектов. И ваш обновлённый объект попадёт под удаление (не пользуется им никто). А если так получилось с несколькими экземплярами сервиса? Сколько «нужных» запросов прилетит в БД?
В общем, принципиально вопрос не решается, как запрашивали на авось, так и будете. Это основная идея приведённого вами алгоритма «у меня есть обновление! ну давай, может пригодится».
Кастомный маршалинг тоже не подошел по скорости? Все-таки, отдельные in-memory кэши на каждый экземпляр — довольно расточительно.
Если вы о чём-то вроде github.com/valyala/fastjson, то нет, не подошло. Скорость особо не возросла. К тому же, для анмаршашлига требуется, чтобы были явно указаны типы полей структуры. Соответственно требуется сначала создать промежуточный тип, анмаршалить в него, а потом скопировать уже в реально используемый тип. Т.е. по сути двойная аллокация.
Нет, я имею ввиду маршалинг/анмаршалинг, написанный оптимальным образом самостоятельно.

Это не гибридный кеш, а многоуровневый. Вернее вы добавили ещё два уровеня к десятку существующих.

Уровень я добавил только один, а Redis это средство синхронизации.

Получается, что все запросы за уже уделёнными объектами будут ходить в БД

Только один раз для каждого инстанса.
А какую-то другую сериализацию в Redis можно было использовать кроме JSON? Какой-то бинарный формат?
Я тоже думал, что конвертирование в бинарную форму будет производительнее. Погуглив и проверив понял, что напротив, оказывается медленнее.
Я смотрел в сторону Binary Serializer
protobuf в Redis нет, есть конечно какие-то сторонние модули, особо не прижившиеся, а непонятно что мне DevOps точно не позволят запускать)
Если есть что-то, что позволит в Redis использовать protobuf3, с интересом посмотрю.
байтслайсы в редис кладутся спокойно — маршалиш структуру в []byte{} и go-redis.Set(«key», value)

```redis strings are binary-safe``` :)
Да, ошибся, байтслайсы кладутся.
Но у меня в исходной структуре часть полей это интерфейсы. У protobuf3 есть тип Any, но это равносильно interface{}, а мне-то надо MyInterface. Не говоря уже о том, что у меня уже есть описанная структура, и мне надо её обрабатывать, а попытка подружить с тем, что сгенерируется в описании для protobuf3 также приведёт к снижению производительности из-за необходимости множества промежуточных копирований.

так к слову — protobuf не самый быстрый, есть flatbuffers

Точно же, забыл совсем, хотя используем но не с го.

Sign up to leave a comment.

Articles