Если вы не читали начало - то оно здесь.

Вкратце же, там я описал как начал строить свой “интернет магазин электроники”. Да, именно в кавычках ?. Потому что это не магазин совсем, а эксперименты по реализации части механик. Конкретно, подбора товаров по параметрам. Запустил первый блин комом и сейчас буду наш первый блин улучшать.

В любом случае, первую часть будет полезно почитать хотя бы из-за дельных комментариев (как всегда на Хабре). Там любезно объяснили, что этому всему есть научный термин - фасетный поиск. И что данная реализация соответствует паттерну EAV. Да и вообще этот велосипед уже изобрели. Но меня это, конечно же, не остановит ?. Что может быть прекрасней собственного велосипеда!

Есть еще надежда, что написанные статьи привлекут внимание тех, кто реализует подобное не как я - ради развлечения, а ради работы. Может они в комментариях поделятся своими замерами производительности, или какими-то подводными камнями. Было бы интересно.

Чиним блин, тот что комом

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

На картинке цифры говорят нам, что основная проблема это сервис получения настроек фильтров. Едва приняв нагрузку - сервер задохнулся. А уже при всего лишь 25 одновременных потоков - время ответа зашкалило за 2 секунды на запрос. И мы увидели, что добавление ядра хоть и позволило снизить время ответа ниже полутора секунд, но оно по прежнему больше секунды.

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

Разгоняем сервис получения настроек фильтров

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

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

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

Думаю все варианты хороши. Но первый (в БД) мне реализовывать кажется скучным. А второй вариант (на прокси) мне не нравится из-за необходимости развертывать дополнительную инфраструктуру на моем и без того перегруженном ноутбуке. Хотя на работе я наверное выбрал бы именно его.

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

Сервис получения настроек поиска принимает на вход один параметр - ИД элемента каталога - которых всего 12 вариантов. Поэтому этот кэш будет всего на 12 записей.

// GET: api/Attributes/5
[HttpGet("{catalogId}")]
public ActionResult<IEnumerable> GetAttribute(int catalogId)
{
    IEnumerable attributes;
    if (_cache.TryGetValue(catalogId, out attributes))
    {
        return Ok(attributes);
    }

    attributes = _context.Catalogs.Where(c => c.CatalogId == catalogId).SelectMany(c => c.Attributes).Select(a => new
    {
        Id = a.AttributeId,
        Name = a.AttributeName,
        TypeId = a.AttributeTypeId,
        Values = a.AttributeValues
                .Select(v => new
                {
                    ValueInt = v.ValueInt,
                    ValueNumeric = v.ValueNumeric,
                    ValueString = v.ValueString
                }).Distinct().Select(v => a.AttributeTypeId == 1 ? v.ValueString :
                                a.AttributeTypeId == 2 ? v.ValueInt.ToString() :
                                v.ValueNumeric.ToString()
        ).ToArray()
    }).ToList();
    _cache.Set(catalogId, attributes);
    return Ok(attributes);
}

Очевидно что первые обращения к серверу с пустым кэшем будут идти дольше. На графике вы их не увидите - я запускал тест на “прогретом” сервере.

Всего четыре строчки кода, а какой результат! Черный график “лег на землю” почти полностью. Теперь максимальное время ответа для аналогичной нагрузки при 24-х тестовых потоках снизилось практически на порядок.

Останавливаться на достигнутом я не намерен.

Разгоняем поиск по атрибутам

Ах, если бы можно было также просто кешировать результаты поиска… К сожалению, сочетание входных параметров слишком многообразно.

Боюсь тут придется менять всю систему алгоритм работы.

Повертев в голове разные варианты пришел к следующей структуре. Для быстрого построения ответа мне необходимо иметь список товаров для каждого значения фильтра. Тогда, для применения множественных фильтров, я смогу строить объединение/пересечение списков, т.е. делать Union/Intersect вместо OR/AND.

Прикинем сколько таких списков будет. Я планирую хранить их иерархически:

CatalogId/AttributeId/AttributeValue: <список товаров>

• элементов каталога у меня 12,

• атрибутов 177 (всего, а не в каждом каталоге),

• уникальных значений атрибутов набралось итого 3924

• и на нижних листах в среднем лежит список из 270 товаров (т.е. итого ~1 млн элементов)

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

Пробую реализовать. Структуру данных выбрал Dictionary, внутри Dictionary, внутри опять Dictionary, а на нижнем уровне List<int>. Т.е. вот так

private Dictionary<int, Dictionary<int, Dictionary<string, List<int>>>> _data;

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

private Dictionary<int, Dictionary<int, Dictionary<string, List<int>>>> InitData()
{
    var query = from p in _context.Products
            join v in _context.AttributeValueViews on p.ProductId equals v.ProductId
            select new { p.CatalogId, p.ProductId, v.AttributeId, v.Value };
    var data = new Dictionary<int, Dictionary<int, Dictionary<string, List<int>>>>();
    foreach (var item in query)
    {
        Dictionary<int, Dictionary<string, List<int>>> c;
        if (data.ContainsKey(item.CatalogId))
        {
            c = data[item.CatalogId];
        }
        else
        {
            c = new Dictionary<int, Dictionary<string, List<int>>>(); 
            data[item.CatalogId] = c;
        }
        Dictionary<string, List<int>> a;
        if (c.ContainsKey(item.AttributeId))
        {
            a = c[item.AttributeId];
        }
        else
        {
            a = new Dictionary<string, List<int>>();
            c[item.AttributeId] = a;
        }
        List<int> v;
        if (a.ContainsKey(item.Value))
        {
            v = a[item.Value];
        }
        else
        {
            v = new List<int>();
            a[item.Value] = v;
        }
        v.Add(item.ProductId);
    }
    return data;
}

Как искать по этой структуре - поясню на примере:
на входе
CPU Family=(‘Core i3’, ‘Xeon’)
Cores Total=(4, 6)
или в виде JSON

{
 "catalogId":"4",
 "filters":{
   "11":["Core i3","Xeon"],
   "12":["4","6"]
 }
}

• По структуре, на первом уровне, выбираем узел с catalogId=4 (напоминаю, поиск по Dictionary выполняется практически за константное время).

  • На втором уровне пойдет цикл по filters. Т.е. два оборота в нашем случае. На каждом обороте делаем поиск по attributeId сначала = 11

    • На третьем уровне ищем “Core i3” и получаем список из, условно, 270 идешек товаров.

    • Делаем аналогично для “Xeon”, и объединяем (Union) два списка. Они, по идее, полностью не совпадают и получим суммарный список из 540 (в среднем) int-ов (идешек товаров).

  • на втором круге attributeId = 12.

    • Аналогичная операция для количества ядер выдаст нам другой список из 540 int-ов.

  • Для получения итогового списка ищем пересечение двух списков (Intersect).

• Перед отправкой результата клиенту, идешки надо превратить в товары. Это один запрос на сервер БД, поиск по первичному ключу для списка ID.

По алгоритмической сложности, думаю, Union и Intersect в худшем случае будут иметь квадратичную временную сложность (от 270-540 элементов), всё остальное мелочь на их фоне. Значения 200-500 для квадратичной сложности не выглядят супер проблемой. Мой внутренний натуральный интеллект приблизительно оценивает суммарные затраты как “должно работать быстро”.

Впрочем, тесты сейчас всё покажут.

public IEnumerable<int> FilterProducts(ProductFilter f)
{
    if (_data.ContainsKey(f.catalogId) == false) return [];
    var c = _data[f.catalogId];

    IEnumerable<int> productIds = null;
    foreach(var item in f.filters)
    {
        if (c.ContainsKey(item.Key) == false) return [];
        var a = c[item.Key];
        IEnumerable<int> ids = new List<int>();
        foreach (var val in item.Value)
        {
            if (a.ContainsKey(val) == false) continue;
            var v = a[val];
            ids = ids.Union(v);
        }
        if (productIds == null)
        {
            productIds = ids;
        }
        else
        {
            productIds = productIds.Intersect(ids);
        }
    }
    return productIds??new List<int>();
}

В комментариях просили скорость обработки в запросах/секунду. Чуть поменяю тестовый план. Буду выполнять те же самые 3 запроса. Также в цикле. Но поставлю ограничение на, к примеру, 1000 суммарных оборотов. Опытным путем пришел к выводу что наибольшая скорость достигается при работе JMeter-а в 6 сессий. Таким образом делю 1000 на 6, получаю что мне надо поставить лимит в тестах на 166 циклов. А дальше JMeter сам посчитает и сумму и среднее…

Результат:
Generate Summary Results =   2988 in 00:00:04 =  681.1/s

Почти 700 запросов в секунду! Как тебе такое Илон Маск!

Чуть поправлю docker-compose.yml, добавлю еще один такой же инстанс с web api. Поправлю тестовый план, чтобы отправлял запросы по-очереди на оба инстанса. Удваиваю в тестовом плане количество сессий до 12 (и уменьшаю количество оборотов в два раза):
Generate Summary Results =   2988 in 00:00:03 =  916.6/s

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

Можно ли посчитать количество позиций соответствующих всем фильтрам

Не знаю как правильно называется эта опция. Проще показать на картинке

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

Уверен что квадратичное время работы Intersect существенно скажется на производительности.

Я попробовал, действительно скорость обработки запросов упала больше чем на порядок, до 40-45 запросов/сек.

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

После оптимизации скорость возросла
Generate Summary Results =   3000 in 00:00:09 =  318.4/s 

private static int IntersectSortedCount(IEnumerable<int> source, IEnumerable<int> target)
{
    var count = 0;

    var en1 = source.GetEnumerator();
    var en2 = target.GetEnumerator();
    bool hasMore1 = en1.MoveNext();
    bool hasMore2 = en2.MoveNext();

    while ( hasMore1 && hasMore2)
    {
        switch (en1.Current.CompareTo(en2.Current))
        {
            case -1:
                hasMore1 = en1.MoveNext();
                continue;
            case 1:
                hasMore2 = en2.MoveNext();
                continue;
            default:
                count++;
                hasMore1 = en1.MoveNext();
                hasMore2 = en2.MoveNext();
                continue;
        }
    }
    return count;
}

Конечно пришлось доработать много где, но по мелочи в основном.
Метод расчета количеств:

• обходит все атрибуты внутри заданного каталога,

• внутри опять цикл по всем значениям для атрибута

• у каждого значения атрибута есть соответствующий ему массив товаров. Делаем Intersect и считаем количество элементов результирующего набора.

• результат оформляю сразу как для UI формирования фильтров только с дополнительной цифрой количества.

public IEnumerable<FilterConfig> GetCounts(ProductFilter f, IEnumerable<int> productIds)
{
    if (_data.ContainsKey(f.catalogId) == false) return [];
    var c = _data[f.catalogId];

    List<FilterConfig> filtersCfg = new List<FilterConfig>();
    foreach (var a in c)
    {
        FilterConfig filterCfg = new FilterConfig();
        filterCfg.Id = a.Key;
        if (_attributes.ContainsKey(a.Key) == false) return [];
        MikesShop.Data.Models.Attribute attr = _attributes[a.Key];
        filterCfg.Name = attr.AttributeName;
        filterCfg.TypeId = attr.AttributeTypeId;
        List<FilterConfigValue> values = new List<FilterConfigValue>();
        foreach (var v in a.Value)
        {
            FilterConfigValue filterConfigValue = new FilterConfigValue();
            filterConfigValue.Text = v.Key;
            // filterConfigValue.Count = productIds.Intersect(v.Value).Count();
            filterConfigValue.Count = IntersectSortedCount(productIds, v.Value);
            values.Add(filterConfigValue);
        }
        filterCfg.Values = values.ToArray();
        filtersCfg.Add(filterCfg);
    }
    return filtersCfg;
}

В клиенте это выглядит вот так

Итого, имеем больше 300 запросов в секунду на, по сути, одном ядре. Еще ядро выделено под СУБД, но с учетом кэширования всего - нагрузка там минимальна.

Что же скажет внимательный читатель?
“А где же редактирование!” - скажет он.
И будет совершенно прав. Легко кэшировать данные которые не меняются. А попробуй-ка закешировать то, что регулярно редактируется.

Рукава по-прежнему закатанные. Раскатывать рано - продолжаем работу.

(продолжение следует)