понедельник, 24 сентября 2012 г.

Кэширующий декоратор на деревьях выражений

Совсем недавно возникла такая задача. Предположим у нас есть класс, предоставляющий доступ к некоторым удаленным ресурсам. Поскольку эти ресурсы расположены достаточно далеко, то результатами методов провайдера являются задачи (объектами класса Task или Task<T>).

public interface ICustomProvider

{

    Task<int> GetNextId();

    Task<string> GetCustomerName(int id);

    Task<Order> GetOrder(int orderId, string customerName);

}

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

Таким образом, задача сводится к поддержке кэша, в котором ключом будет идентификатор операции со всеми ее параметрами, а значением – объект Task. При этом кэш будет автоматически «инвалидироваться» по завершению операции. Задача довольно просто решается «в лоб»: для этого достаточно создать класс идентифицирующий операцию (например, OperationId), а затем в каждом методе создать идентификатор по имени метода и переданным аргументам, и проверить наличие элемента в кэше, прежде чем начинать новую асинхронную операцию.

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

Автоматическое получение идентификатора операции

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

Одним из способов решения этой задачи является использование деревьев выражений (Expression Trees), с которыми мы уже знакомились при обсуждении визуализации деревьев выражений. Анализ дерева выражений во время исполнений позволит получить все необходимые данные для идентификации операции типобезопасным образом.

public Task<Order> GetOrder(int orderId, string customerName)

{

    // Делегируем всю работу методу "GetOrderImpl" и

    // разбираем полученное дерево выражений

    Expression<Func<Task<Order>>> expression =

        () => GetOrderImpl(orderId, customerName);

 

    var methodCallInfo = ProcessMethodCall(expression);

 

    lock(_syncRoot)

    {

        // Проверяем наличие элемента в кэше

        Task cachedTask;

        if (_outstandingTasks.TryGetValue(methodCallInfo, out cachedTask))

        {

            return (Task<Order>) cachedTask;

        }

 

        // Запускаем асинхронную операцию и добавляем ее в кэш

        var task = expression.Compile()();

        _outstandingTasks[methodCallInfo] = task;

 

        // Подписываемся на продолжение задачи и удаляем ее из кэша по завершении

        task.ContinueWith(t =>

                              {

                                  lock(_syncRoot)

                                  {

                                      _outstandingTasks.Remove(methodCallInfo);

                                  }

                              });

 

        return task;

    }

}

 

private Task<Order> GetOrderImpl(int orderId, string customerName)

{}

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

Теперь осталось самое главное: нужно разобрать создаваемое дерево выражений для получения идентификатора операции:

public static MethodCallInfo ProcessMethodCallExpression<TResult>(

    Expression<Func<TResult>> expression)

{

    var methodCall = expression.Body as MethodCallExpression;

    Contract.Assert(methodCall != null,

        "ProcessMethodCallExpression supports only method call expressions");

 

    // methodCall.Arguments содержит коллекцию выражений со всеми аргументами,

    // которые нужно «вычислить» для получения актуальных значений

    var arguments = from arg in methodCall.Arguments

                    let argAsObj = Expression.Convert(arg, typeof(object))

                    select Expression.Lambda<Func<object>>(argAsObj, null)

                        .Compile()();

 

    var parameters = arguments.ToArray();

 

    return new MethodCallInfo(methodCall.Method, parameters);

}

MethodCallInfo представляет собой простую структуру с двумя полям MethodInfo и Arguments, а также семантикой значения (т.е. два экземпляра этой структуры с одинаковым набором аргументов будут эквивалентными):

public struct MethodCallInfo

{

    public readonly MethodInfo MethodInfo;

    public readonly object[] Arguments;

 

    public MethodCallInfo(MethodInfo methodInfo, object[] args)

    {}

 

    // Методы Equals и GetHashCode реализованы с помощью

    // StructuralComparisons.StructuralEqualityComparer;

}

Основная же работа в методе ProcessMethodCallExpression заключается в обработке аргументов объекта MethodCallExpression; поскольку аргументом метода может быть не просто константное выражение вида () => Foo(42,”Some string”), но и выражения вида () => Foo(GetId(), ProcessSomething()), то вместо того, чтобы завязываться только на константные выражения, производится преобразование всех аргументов к Expression<Func<object>> с последующим их вычислением.

Кэширующий декоратор

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

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

public sealed class CachedCustomProvider : ICustomProvider

{

    private readonly Dictionary<MethodCallInfo, Task> _cache =

        new Dictionary<MethodCallInfo, Task>();

    private readonly object _cacheSyncRoot = new object();

 

    private readonly ICustomProvider _customProvider;

 

    public CachedCustomProvider(ICustomProvider customProvider)

    {

        Contract.Requires(customProvider != null);

 

        _customProvider = customProvider;

    }

 

    public Task<Order> GetOrder(int orderId, string customerName)

    {

        return GetFromCacheOrUpdate(() => _customProvider.GetOrder(orderId, customerName));

    }

 

    private Task<T> GetFromCacheOrUpdate<T>(Expression<Func<Task<T>>> expression)

    {

        // Получаем идентификатор операции

        var methodInfo = ExpressionParser.ProcessMethodCallExpression(expression);

 

        lock(_cacheSyncRoot)

        {

            Task cachedTask;

            if (_cache.TryGetValue(methodInfo, out cachedTask))

            {

                return (Task<T>) cachedTask;

            }

 

            // Получаем задачу

            var newTask = expression.Compile()();

            _cache[methodInfo] = newTask;

 

            // Подписываемся на продолжение и удалем ее

            newTask.ContinueWith(t =>

                    {

                        lock (_cacheSyncRoot)

                            _cache.Remove(methodInfo);

                    });

 

            return newTask;

        }

    }

     

}

(Ну вот, а вы думали, что паттерны проектирования – это никому не нужная ерунда!:) )

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

После этого, добавить кэширование в качестве аспекта поведения нашего кастомного провайдера будет очень просто:

ICustomProvider cachedProvider =

    new CachedCustomProvider(new CustomProvider());

var t1 = cachedProvider.GetOrder(42, "John Doe");

var t2 = cachedProvider.GetOrder(42, "John Doe");

// t1 и t2 - указывают на один и тот же объект

Использование деревьев выражений для юнит тестов

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

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

public class CachedCustomProviderTests

{

    [TestCaseSource(typeof(CustomProviderObjectMother), "GetCustomProviderTestData")]

    public void Test_Calling_Method_Twice_Will_Return_The_Same_Result(string method, object[] arguments)

    {

        // Arrange

        ICustomProvider customProvider = new CachedCustomProvider(new CustomProvider());

        var methodInfo = typeof (ICustomProvider).GetMethod(method);

        Assert.IsNotNull(methodInfo,

            string.Format("ICustomProvider does not contain method '{0}'", method));

 

        // Act

        // Вызываем наш метод дважды подряд

        var task1 = (Task) methodInfo.Invoke(customProvider, arguments);

        var task2 = (Task) methodInfo.Invoke(customProvider, arguments);

 

        // Assert

        Assert.IsTrue(ReferenceEquals(task1, task2),

                "Two subsequent calls to CachedCustomProvider should return the same objects");

    }

}

 

public class CustomTestCaseData : TestCaseData

{

    public CustomTestCaseData(MethodCallInfo callInfo)

        : base(callInfo.MethodName, callInfo.Arguments)

    { }

}

 

public class CustomProviderObjectMother

{

    public static IEnumerable<CustomTestCaseData> GetCustomProviderTestData()

    {

        // Этот код аналогичен следующему:

        // yield return new TestCaseData("GetOrder", new object[] {42, "John Doe"});

        yield return new CustomTestCaseData(

            ExpressionParser.ProcessMethodCallExpression(

                (ICustomProvider cp) => cp.GetOrder(42, "John Doe")));

 

        // Вызываем оставшиеся методы аналогичным образом

    }

}

В данном случае используется паттерн “Object Mother”, который представляет собой особый случай фабричного метода. Подобный объект может быть использован повторно, а также может содержать дополнительные проверки полноты данных (например, что метод GetCustomProviderTestData возвращает тестовые данные для каждого метода интерфейса ICustomProvider).

Что мы узнали

  1. Паттерны проектирования придумали не зря и им можно найти применение в реальных проектах.
  2. Использование «метапрограммирования» на основе деревьев выражений может существенно упростить количество кода и повысить его сопровождаемость.
  3. Парсинг информации о вызове отлично подходит для реализации кэширования вообще и кэширующих декораторов в частности.
  4. Использование приведенных здесь инструментов оправдано тем, что они используются в ограниченном контексте (в тестах и в реализации кэширующего декоратора); неправильное или чрезмерное использование деревьев выражений приведет к обратному результату и усложнить сопровождаемость за счет своей сложности.
  5. Параметризованные тесты – это отличная штука, которая идеально подходит для тестов группы методов, а использование строготипизированной «рефлексии» может помочь в формировании тестовых данных.

Дополнительные ссылки

  1. Весь код доступен на github (с тестами и примерами)

UPDATE:

Вернул кэш с ConcurrentDictionary на обычный Dictionary + lock, поскольку делегат, передаваемый методу GetOrAdd может вызываться несколько раз. Также обновил реализацию на гитхабе и вместо простого получения аргументов путем компиляции каждого выражения, добавил ExpressionVisitor, выполняет нужную работу в раз 80 быстрее (эти изменения более объемные, поэтому в коде статьи я их не отражал, за подробностями в код на гитхабе).

21 комментарий:

  1. @Vyacheslav: чего-то твои комменты в спам попали;)

    Обновил примеры, вернул туда объявление этих полей.

    ОтветитьУдалить
  2. Извиняюсь за спам, сразу не отыскал в примерах что это Dictionary<>. Тогда, как мне кажется, Remove из неё в ContinueWith будет происходить не из-под лока и поэтому не безопасно. Вот если это свой словарь, в который передаётся тот же sync root, то будет кажется нормально.

    ОтветитьУдалить
  3. Да, конечно, я забыл lock. У меня первая версия вообще была осознанно потонебезопасная, вообще без блокировок, потом блокировки в основном теле добавил, а в "продолжении" - забыл.

    Спасибо, поправил.

    ОтветитьУдалить
  4. А теперь можно приступить к одному из самых интересных (для меня в последнее время) - попробовать переписать вообще без локов :о)) А то, чесслово, как-то неприятно смотреть на код с локами, когда вокруг столько прекрасных средств обойтись без :о))

    ОтветитьУдалить
  5. Это и правда интересная задача, хотя в данном конкретном случае это будет исключительно ради интереса, поскольку кэшируются длительные операции, время выполнения которой исчисляется секундами.

    Осваиваешь low lock/lock free техники? И чем, кстати, потом тестируешь? Chess?

    ОтветитьУдалить
  6. Ну если GetCustomerName… секундами, то да, "улучшать" не надо :о))

    Да и по сравнению даже с просто удалённым вызовом в таком простом случае конечно что-то ещё изобретать излишне, хотя CuncurrentDictionary<,> уже будет проще для чтения (для тех кто хоть примерно себе представляет что это такое) - никаких вроде бы специальных синхронизаций вообще нет - "чище" что ли получается.

    До лок-фри мне ещё как до городу Парижу пешком зимой из Иркутска, но уж да, больно хочется освоить. А освоить без применения не получается :о)

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

    ОтветитьУдалить
  8. И правда легче стало! А теперь, что бы понять, почему меня никто почти не любит, напомню, что _cacheSyncRoot тоже можно удалить из определения класса :о)

    ОтветитьУдалить
  9. Кстати, а не правильно ли делать return task.ContinueWith(…)?

    ОтветитьУдалить
  10. :DDD Удалил лишний syncRoot.

    Вернуть task.ContinueWith(...) не выйдет, поскольку ContinueWith возвращает не исходную задачу, а уже продолжение, тип которой Task, а не Task, так что последующее приведение типов упадет с ошибкой.

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

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

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

    ОтветитьУдалить
  12. >>Основная же работа в методе ProcessMethodCallExpression заключается в обработке аргументов объекта MethodCallExpression; поскольку аргументом метода может быть не просто константное выражение вида () => Foo(42,”Some string”), но и выражения вида () => Foo(GetId(), ProcessSomething()),

    Ну если ProcessMethodCallExpression вызывается только из такого кеширующего провайдера, то никаких GetId()/ProcessSomething() быть не может. Ведь по логике методы провайдера просто должны передать свои аргументы в ProcessMethodCallExpression. никаких выражений. Да и вообще лично меня коробит (1 + (количество аргументов)) компиляций на каждый вызов метода ICustomProvider

    ОтветитьУдалить
  13. @Viacheslav: пришлось вернуть старый код и использовать Dictionary + lock. См. апдейт.

    @jack: Да, это и правда сурово. Я померил производительность и ужаснулся. Я поменял код на ExpressionVisitor, для подавляющего большинства случаев быстрее стало раз в 80. См. апдейт.

    ОтветитьУдалить
  14. Sergey Teplyakov, я так понимаю проект Chess закрыт и не развивается протестировать TPL или PLinq с его помощью не получится...

    ОтветитьУдалить
  15. @Никита: таки да, похоже Chess уже не развивается.

    Интересно, а что есть подобное хорошее?

    ОтветитьУдалить
  16. "Офтоп": Тут смотри какое дело: сейчас ты добился того, что все "клиенты" ждут, пока кто-то один получит данные, а потом очистит кеш, но зато вызов происходит строго один раз. В условиях, когда "клиентов" много это, зачастую, не самая лучшая стратегия. Логически-практически требовать строго одного вызова необходимости нет, мы же всего лишь экономить пытаемся.

    ConcurrentDictionary вынуждает распараллелить [иногда] запросы (вызывая valueFactory тогда, когда это, вроде бы, и не нужно) и это выгодно - многие автомобилисты предпочитают плохо ехать (сделав крюк), чем хорошо стоять в пробке ;о) Но это, конечно, уже не имеет никакого отношения к теме статьи. Всего лишь стратегия против тактики :о)

    ОтветитьУдалить
  17. Прикольная идея возвращать task результатом? Это че-то не новое? Никогда раньше не видел.

    Насчет проблемы с ключем для dictionary на основе имени и т д. Не думаю, что это вообще проблема.

    Завели по полю для каждого метода и проблемы нет.

    class Service {
    private Task methodACache;
    public Task< object> MethodA()
    {
    if (methodACache == null) { ... }
    return methodACache;
    }

    private Dictionary< string, Task< object>> methodBCache = new...;
    public Task< object> MethodB(string name)
    {
    if (methodBCache.ContainsKey(name)) ...
    // ну в общем понятно...
    }

    И для поля и для dictionary, код легко выносится в хэлперы.

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

    private readonly object methodAKey = new object();
    ну или строку или Guid

    Параметры метода (которые будут частью ключа) сложно потерять при рефакторинге.

    ОтветитьУдалить
  19. @80InchNail: Возвращать таску с результатом - это уже не такое уж и новое. Это так называемый Task-based Async Pattern, который появился с выходом .NET 4.0, а в .NET 4.5 стал по-сути, стандартом.

    НИЧЕГО СЕБЕ, по полю для каждого метода и нет никаких проблем!! Тем более, что нужно будет 2 поля, для кэша и ключа, и еще гору кода сделать, чтобы решение было потокобезопасным.

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

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