пятница, 23 апреля 2010 г.

Локальная memoization в RESTAS

Memoization - мощная техника оптимизации/кэширования, когда результат функции сохраняется и в последующем используется вместо повторного вычисления функции. Изначально, я планировал использовать эту технику для построения каркаса для кэширования в рамках RESTAS (впрочем, когда я размышлял об этом, то ещё не знал этого термина). Правда, для кэширования в веб-приложениях данный подход должен быть модифицирован: функции, которые всегда для одних и тех же входных данных возвращают один и тот же результат на практике являются экзотикой, а вот функции удовлетворяющие этому условию в течении некоего ограниченного промежутка времени встречаются весьма регулярно. Т.е. имеет смысл говорить об memoization, которая ограничена по времени, я даже придумал термин - soft memoization :) В общем, я погрузился в размышления как совместить всё это с ключевыми проблемами кэширования:
  • Контролем за размером кэша
  • Устареванием кэша
  • Согласованностью кэша
  • Проблемой согласованного доступа
И решил посмотреть что на тему memoization есть в мире Common Lisp. Нашёл пару пакетов, которые реализуют дизайн, предложенный ещё Peter Norvig и понял, почему эта техника практически не применяется. Шутка в том, что дизайн от Peter Norvig основан на возможностях Common Lisp (предлагается динамически мемоизировать уже существующие функции за счёт манипуляций с symbol-function) и при этом мало совместим с реальной практикой программирования на Common Lisp :) Действительно, применять memoization для тривиальных случаев не очень интересно, а memoization для функций, зависящих от других просто опасно - интерактивное переопределение какой-либо функции может скомпрометировать все ранее вычисленные результаты. Размышляя на тему возможности отслеживания зависимостей (например, с помощью sb-introspec) и пришёл к выводу, что практически полезное решение построить не так уж и просто и необходима более тщательная проработка.

Собственно, на эту тему я сейчас стал думать для разрешения довольно простой ситуации. На сайте lisper.ru информации о пользователе после входа сохраняется в зашифрованном cookie, который, естественно, надо расшифровывать при обработке запроса. Ситуация осложняется тем, что информации о пользователе используется при поиске подходящего маршрута и операция расшифровки может быть инициирована достаточно много раз, а это не самая дешёвая операция. Очевидно, что во время обработки одного запроса достаточно расшифровать cookie всего один раз, но совершенно не понятно, где можно было бы сохранить эти результаты. Делать специальное решение именно для этой проблемы мне очень не хочется и я решил, что данная проблема должна решаться как проблема кэширования, а RESTAS должен предоставлять общую инфраструктуру. Тут всплыли описанные выше проблемы и стало понятно, что я не могу быстро и просто предложить хорошее решение.

Просматривая в очередной раз разделы посвященные кэшированию в книге "Профессиональное программирование на PHP" от Джордж Шлосснейгл я обнаружил, что он рассматривает в том числе memoization (правда, не использует данный термин) и показывает, что данная техника может быть весьма полезна даже без сохранения мемоизированных данных между запросами (хм, я был удивлен, интересно, как часто в литературе по PHP можно встретить сравнительный анализ эффективности алгоритмов "хвостовая рекурсия" vs. memoization? в этой книге это есть!). Т.е. подход, при котором memoization локальна относительно обработчика запроса является полезной, просто реализуемой и не имеет серьёзных проблем, связанных с возможность компрометации данных в результате изменения среды.

Именно это я сейчас и реализовал. Для каждого запроса поддерживается своя *memotable*, в которой сохраняются результаты вызовов функций, объявленных с помощью restas:define-memoized-function, что позволило исключить многократную расшифровку cookie достаточно общим способом.

2 комментария:

  1. Интересная тема. А если всё-таки попытаться интроспективно, наверное, хватило бы отслеживать все вызовы из мемоизируемой функции, храня под них некую таблицу, и перевычисляя, если func из таблицы не-eq текущему symbol-function 'func ?

    ОтветитьУдалить
  2. @ander-skirnir
    Я ещё буду думать об этом, ибо было бы интересно всё таки заюзать общий подход для проблемы кэширования, но пока чего-либо утверждать определённо не могу. Надо думать.

    ОтветитьУдалить