Русский
Русский
English
Статистика
Реклама

Кеширование

2R2L кеширование

23.10.2020 18:08:20 | Автор: admin
Кеширование широко освещенная и известная тема. Но и в ней могут появляться новые решения. В частности в области высокоуровневых продуктов (например, в веб-разработке). Столкнувшись с недостатками классического подхода, я попробовал вывести идеальную схему кеширования для случая, когда актуальность данных не является критической. Потом я попробовал найти описание подобной схемы, а лучше готовые решения. Не нашел. Поэтому назвал ее сам 2R2L (2 Range 2 Location) двух-диапазонное двух-пространственное кеширование. Хотя наверняка оно уже где-то применяется.

Началось все с простой задачи отобразить пользователю новинки неких товаров с учетом его индивидуальных предпочтений. И если с получением новинок проблем не было, то соотнесение новинок с предпочтениями (анализ статистики) уже создавал ощутимую нагрузку (для примера определим ее в 4 секунды). Особенность задачи состояла в том, что в качестве пользователей у нас могут выступать целые организации. И нередки случаи, когда одномоментно (в течение 2-3 секунд) на сервер прилетает 200-300 запросов, относящихся к одному пользователю. Т.е. генерируется один и тот же блок сразу для многих пользователей.

Очевидное решение надо кешировать в RAM (не будем подвергать СУБД насилию, заставляя отрабатывать большой поток обращений). Классическая схема:

  1. Пришел запрос
  2. Проверяем кеш. Если данные в нем есть, и они не устарели просто отдаем их.
  3. Данных нет => генерируем выдачу
  4. Отправляем пользователю
  5. Дополнительно складываем в кеш, указывая TTL

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

Также отметим, что при индивидуальных кеш-значениях количество записей может вырасти на столько, что доступной ОЗУ сервера просто не хватит. Тогда логичным выглядит использование локального HDD сервера в качестве хранилища кешей. Но мы сразу теряем в скорости.

Как же быть?

Первое, что приходит в голову: было бы здорово хранить записи в 2 местах в RAM (часто запрашиваемые) и HDD (все или только редко запрашиваемые). Концепция горячих и холодных данных в чистом виде. Реализаций такого подхода множество, поэтому останавливаться на нем не будем. Просто обозначим эту составляющую как 2L. В моем случае она успешно реализуется на базе СУБД Scylla.

Но как избавиться от просадок в моменты, когда кеш устарел? А здесь мы и подключаем концепцию 2R, смысл которой заключается в простой вещи: для кеш-записи надо указывать не 1 значение TTL, а 2. TTL1 метка времени, которая означает данные устарели, надо бы перегенерировать, но использовать еще можно; TTL2 все устарело настолько, что использовать уже нельзя.

Таким образом получаем немного иную схему работы кеширования:

  1. Пришел запрос
  2. Ищем данные в кеше. Если данные есть и не устарели (t<TTL1) отдаем пользователю, как обычно и больше ничего не делаем.
  3. Данные есть, устарели, но можно использовать (TTL1 < t < TTL2) отдаем пользователю И инициализируем процедуру обновления кеш-записи
  4. Данных нет совсем (убиты по истечении TTL2) генерируем как обычно и записываем в кеш.
  5. После отдачи контента пользователю или в параллельном потоке выполняем процедуры обновления кеш-записей.

В результате мы имеем:

  • если кеш-записи используются достаточно часто, пользователь никогда не попадет в ситуацию ожидаем актуализации кеша он всегда будет получать уже готовый результат.
  • если правильно организовать очередь актуализаций, то можно добиться того, что в случае нескольких одновременных обращений к записи с TTL1 < t < TTL2, в очереди будет находиться только 1 задача на обновление, а не несколько одинаковых.

В качестве примера: для ленты новинок можно указать TTL1 = 1 час (все же не сильно интенсивно новый контент появляется), а TTL2 1 неделя.

В простейшем случае код на PHP для реализации 2R может быть таким:

$tmp = cache_get($key);If (!$tmp){$items = generate_items();cache_set($items, 60*60, 60*60*24*7);}else{$items = $tmp[items];If (time()-$tmp[tm] > 60*60){$need_rebuild[] = [to=>$key, method=>generate_items];}}// отдаем данные пользователюecho json_encode($items);// поскольку данные пользователю уже отправлены, можно и повычислятьIf (isset($need_rebuild) && count($need_rebuild)>0){foreach($need_rebuild as $k=>$v){$tmp = ['tm'=>time(), 'items'=>$$v[method]];cache_set($tmp, 60*60, 60*60*24*7);}}

На практике, конечно, реализация, скорее всего, будет посложнее. Например, генератор кеш-записей отдельный скрипт, запущенный в качестве сервиса; очередь через Rabbit, признак такой ключ уже есть в очереди на перегенерацию через Redis или Scylla.

Итого, если объединить двух-диапазонный подход и концепцию горячие/холодные данные, как раз и получим 2R2L.

Спасибо!
Подробнее..

Кешируем CRUD в IndexedDB

28.04.2021 00:09:16 | Автор: admin

Допустим, у нас есть бекенд, который умеет хранить какие-то сущности. И у него есть апи для создания, чтения, изменения и удаления этих сущностей, сокращенно CRUD. Но апи на сервере, а пользователь забрался куда-то глубоко и половина запросов валится по таймауту. Не хотелось бы показывать бесконечный прелоадер и вообще блокировать действия пользователя. Offline first предполагает загрузку приложения из кеша, так может быть и данные брать оттуда?

Предлагается хранить все данные в IndexedDB (допустим, что их не очень много), и по возможности синхронизировать с сервером. Возникает несколько проблем:

  1. Если Id сущности генерится на сервере, в базе, то как жить без Id, пока сервер недоступен?

  2. При синхронизации с сервером, как отличать сущности созданные на клиенте от удаленных на сервере другим пользователем?

  3. Как разрешать конфликты?

Идентификация

Идентификатор нужен, так что будем его создавать сами. Для этого прекрасно подходит GUID или `+new Date()` с некоторыми оговорками. Только когда придет ответ от сервера с настоящим Id, надо везде его заменить. Если на эту свежесозданную сущность уже ссылаются другие, то эти ссылки тоже надо поправить.

Синхронизация

Изобретать велосипед не будем, посмотрим на репликацию баз данных. Смотреть на нее можно бесконечно, как на пожар, но вкратце, один из вариантов выглядит так: помимо сохранения сущности в IndexedDB, будем писать лог изменений: [time, 'update', Id=3, Name='Иван'], [time, 'create', Name='Иван', Surname='Петров'], [time, 'delete', Id=3]...

При получении с сервера свежих данных, мы можем сравнить их с существующими и вычислить аналогичный лог изменений на сервере. После этого объединить логи и отправить необходимые изменения на сервер, если интернет еще не пропал, и только после этого записывать изменения в IndexedDB. И не забыть обновить Id.

Конфликты

Конфликт - это не спор между двумя пользователями, чья точка зрения правильная, и поочередное исправление одной и той же записи до посинения. А вот ситуация, когда пользователи довольны и видят каждый свою версию - конфликт, а конкретно неконсистентность. Непрерывной консистентности в веб приложениях достичь несложно - при каждом изменении блокировать всех клиентов, кого это изменение касается, пока они все не подтвердят получение. Это никому не нравится, поэтому приходится идти на компромис: ладно, пусть иногда пользователи видят разное, но если все замрут и перестанут вносить изменения, то через некоторое время у всех будет одно и то же. Для этого придумали термин Eventual Consistency.

Оказалось, что ее можно достичь незаметно для пользователя, но не так просто. Можно использовать Operational Transformations (OT) или Conflict-free Replicated Data Types (CRDT) но для них придется довольно радикально поменять формат обмена данных с сервером. Если это невозможно, то можно на коленке сделать CRDT на минималках: добавить в сущность поле UpdatedAt и записывать в него время последнего изменения. Это не избавит от всех конфликтов, но снизит их количество на порядок.

Итак, при объединении двух логов группируем их по Id сущности и дальше работаем в каждой группе отдельно. Если в одном из логов есть операция удаления, то оставляем только ее. Пользователь, удаливший запись наверняка имел на это веские основания и не хотел бы, чтобы запись вдруг возродилась. Никто не любит зомби кроме зомби. Если в одном из логов есть операция создания сущности, то в другом логе должно быть пусто, ведь Id уникальный, ага. С изменениями немного сложнее - нужно посмотреть на время последнего изменения сущности в каждом из логов. Сравнить. И выбрать тот лог, в который изменение пришло позднее. Last write win. Проверим Eventual Consistency: если все пользователи перестанут вносить изменения и подключатся к интернету, у всех будут сущности последней версии. Отлично.

function mergeLogs(left, right){    const ids = new Set([        ...left.map(x => x.id),        ...right.map(x => x.id)    ]);    return [...ids].map(id => mergeIdLogs(        left.filter(x => x.id == id),        right.filter(x => x.id ==id)    )).reduce((a,b) => ({        left: [...a.left, ...b.left],        right: [...a.right, ...b.right]    }), {left: [], right: []});}function mergeIdLogs(left,right){    const isWin = log => log.some(x => ['create','delete'].includes(x.type));    const getMaxUpdate = log => Math.max(...log.map(x => +x.updatedAt));    if (isWin(left))        return {left: [], right: left};    if (isWin(right))        return {left: right, right: []};    if (getMaxUpdate(left) > getMaxUpdate(right))        return {left: [], right: left};    else        return {left: right, right: []};}

Эпилог

Реализации не будет, потому что в каждом конкретном случае есть свой дьявол в деталях, да и реализовывать тут по большому счету нечего - генерацию идентификатора и запись в indexedDB.

Конечно, CRDT или OT будут лучше, но если нужно сделать быстро, а на бекенд не пускают, то сгодится и это поделие.

Подробнее..

Recovery mode Vela умный кеш для time series и не только

11.07.2020 10:23:53 | Автор: admin

У нас в финтехе, нам часто приходится обрабатывать довольно массивные объемы данных курсов обмена валют. Мы получаем данные из разных источников, и каждый из них имеет собственное представление о том, как экстраполировать значения курсов на завтра, послезавтра, следующий месяц и даже следующие три года. Если бы кто-то умел предсказывать курсы правильно, впору было бы закрывать бизнес и просто тупо менять деньги туда-сюда. Некоторые источники пользуются большим доверием, некоторые поставляют сплошь мусор, с редкими вкраплениями почти правильных значений, но зато для экзотических пар. Наша работа заключается в том, чтобы просеять эти десятки тысяч значений в секунду и определить, что именно показать заказчикам. Нам нужно отфильтровать единственное правильное значение из тонны грязи и ила, как это делают фламинго на обеде.


Фламинго


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

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


Допустим, мы собираем курсы для трех пар валют. Простейшее определение Vela для хранения актуального состояния будет выглядеть как-то так:


defmodule Pairs do  use Vela,    eurusd: [sorter: &Kernel.<=/2],    eurgbp: [limit: 3, errors: 1],    eurcad: [validator: Pairs]  @behaviour Vela.Validator  @impl Vela.Validator  def valid?(:eurcad, rate), do: rate > 0end

Обновление значений


Vela.put/3 функция последовательно сделает следующее:


  • вызовет validator на значении, если таковой определен (см. главку Валидация ниже);
  • добавит значение либо в ряд хороших значений, если валидация закончилась успешно, или в служебный ряд :__errors__ в обратном случае;
  • вызовет сортировку если sorter определен для данного ключа, или просто положит значение в голову списка (FILO, см. главку Сортировка ниже);
  • обрежет ряд в соответствии с параметром :limit переданном при создании;
  • вернет обновленную структуру Vela.

iex|1 > pairs = %Pairs{}iex|2 > Vela.put(pairs, :eurcad, 1.0)# %Pairs{..., eurcad: [1.0], ...}iex|3 > Vela.put(pairs, :eurcad, -1.0)#%Pairs{__errors__: [eurcad: -1.0], ...}iex|4 > pairs |> Vela.put(:eurusd, 2.0) |> Vela.put(:eurusd, 1.0)#%Pairs{... eurusd: [1.0, 2.0]}

Также Vela имплементирует Access, так что можно для обновления значений воспользоваться любой из стандартных функций для глубокого обновления структур из арсенала Kernel: Kernel.get_in/2, Kernel.put_in/3, Kernel.update_in/3, Kernel.pop_in/2, and Kernel.get_and_update_in/3.


Валидация


Валидатор можен быть определен как:


  • внешняя функция с одним аргументом (&MyMod.my_fun/1), она получит только значение для валидации;
  • внешняя функция с двумя аргументами, &MyMod.my_fun/2, она получит пару serie, value для валидации;
  • модуль, имплементирующий Vela.Validator;
  • конфигурационный параметр threshold, и опционально compare_by, см. главку Comparison ниже.

Если валидация прошла успешно, значение добавляется в список под соответствующим ключом, в обратном случае кортеж {serie, value} отправляется в :__errors_.


Сравнение


Значения, сохраняемые в этих рядах, могут быть любыми. Чтобы научить Vela их сравнивать, необходимо передать compare_by параметр в определение ряда (если только значения не могут быть сравнены стандартным Kernel.</2); этот параметр должен иметь тип (Vela.value() -> number()). По умолчанию это просто & &1.


Также, в определение ряда можно передать параметр comparator для вычисления значений дельт (min/max); например, передавая Date.diff/2 в качестве компаратора, можно получить правильные дельты для дат.


Другим удобным способом работы является передача параметра threshold, который определяет максимально допустимое отношение нового значения к {min, max} интервалу. Поскольку он задан в процентах, проверка не использует comparator, но все еще использует compare_by. Например, чтобы указать пороговое значение для времени дат, необходимо указать compare_by: &DateTime.to_unix/1 (для получения целочисленного значения) и threshold: 1, в результате чего новые значения будут разрешены, только если они находятся в band интервале от текущих значений.


Наконец, можно использовать Vela.equal?/2 для сравнения двух кешей. Если значения определяют функцию equal?/2 или compare/2, то эти функции будут использованы для сравнения, в противном случае мы тупо используем ==/2.


Получение значений


Обработка текущего состояния обычно начинается с вызова Vela.purge/1, который убирает устаревшие значения (если validator завязан на timestamps). Затем можно вызвать Vela.slice/1, которая вернет keyword с именами рядов в качестве ключей и первым, актуальными значениями.


Также можно воспользоваться get_in/2/pop_in/2 для низкоуровнего доступа к значениям в каждом ряду.


Приложение


Vela может оказаться чрезвычайно полезной в качестве кеша временных рядов в стейте процесса типа GenServer/Agent. Мы хотим никогда не использовать устаревшие значения курсов, и для этого мы просто держим процесс с состоянием, обрабатываемым Vela, с валидатором, показанным ниже.


@impl Vela.Validatordef valid?(_key, %Rate{} = rate),  do: Rate.age(rate) < @death_age

и Vela.purge/1 спокойно удаляет все устаревшие значения каждый раз, когда нам требуются данные. Для доступа к актуальным значениям, мы просто вызываем Vela.slice/1, а когда требуется небольшая история по курсу (весь ряд целиком), мы просто возвращаем его, уже отсортированным, с провалидированными значениями.




Удачного кеширования временных рядов!

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru