Как эффективно хранить и читать иерархию из кэша

Question

Моя ситуация такова, что в настоящее время я храню иерархию в базе данных SQL, которая быстро приближается к 15000 узлам (5000 ребер).Эта иерархия определяет мою модель безопасности на основе позиции пользователя в дереве, предоставляя доступ к элементам ниже.Поэтому, когда пользователь запрашивает список всех защищенных элементов, я использую CTE для его повторения в БД (и выравнивает все элементы), который начинает показывать его возраст (медленно).

Иерархияменяются не часто, поэтому я попытался переместить его в оперативную память (redis).Имея в виду, у меня есть много подсистем, которые нуждаются в этом для вызовов безопасности, и пользовательский интерфейс для построения дерева для операций CRUD.

Первая попытка

Моя первая попытка сохранить отношения в виде пары ключ-значение (это то, как она хранится в базе данных)

       E
     /   \
    F     G
   / \   /  \
  H  I  J    K

mapped to:
    E - [F, G]
    F - [H, I]
    G - [J, K]

Поэтому, когда я хочу E и все его потомки, я рекурсивнополучить его дочерний элемент и его дочерний элемент с помощью ключей, и это позволит мне начать движение с любого узла.Это решение дало хорошее увеличение скорости, но с 15 000 узлов было приблизительно 5000 обращений к кэшу, чтобы перестроить мое дерево в коде (в худшем случае ... начиная с E. производительность зависит от местоположения начальных узлов, в результате чего суперпользователи видятхудшая производительность).Это было все еще довольно быстро, но казалось болтливым.Мне нравится тот факт, что я могу удалить узел в любое время, вынув его из списка ключей, не перестраивая весь кэш.Это также быстро освещалось для визуального построения дерева по требованию в пользовательском интерфейсе.

Вторая попытка

Моя другая идея состоит в том, чтобы взять Иерархию из базы данных, построить дерево и сохранить его в ОЗУ (redis), а затем вытащить всю вещь из памяти (она была размером примерно 2 МБ, сериализована).Это дало мне один вызов (не слишком болтливый) в redis, чтобы вытащить все дерево, найти родительский узел пользователей и спуститься, чтобы получить все дочерние элементы.Эти вызовы частые, и передача 2 МБ на сетевом уровне казалась большой.Это также означает, что я не могу легко добавить / удалить и элемент, не потянув дерево вниз, не отредактировав и не оттолкнув его назад.Кроме того, построение деревьев по требованию через HTTP означало, что каждый запрос должен был сбрасывать 2 МБ, чтобы получить только прямых потомков (очень мало при первом решении).

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

Спасибо

Answer 1

Позвольте мне предложить идею ...

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

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

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

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

--- РЕДАКТИРОВАТЬ ---

Если ваша база данных и драйвер ADO.NET поддерживают это, возможно, стоит изучить уведомления сервера, такие как SqlDependency для MS SQL Server * или 1035 * OracleDependency .

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

Answer 2

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

Для вашего примера (я буду использовать формат JSON):

E - {"direct" : [F, G], "all" : [F, G, H, I, J, K]}
F - {"direct" : [H, I], "all" : [H, I]}
G - {"direct" : [J, K], "all" : [J, K]}

Что ж, для суперпользователей вам все равно придется передавать много данных за запрос, но я не вижу способа сделать это меньше.

Answer 3

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