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

Question

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

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

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

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

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

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

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

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

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

---

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

Thanks

Answer 1

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

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

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

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

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

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

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

--- EDIT ---

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

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