Improve performance of a recursive method with Redis

Recursive method are very useful to process for example, parent/child relations and build organization trees.

But for complex trees is very frequently to encounter performance problems, specially if the tree is build for every request.

In my case, the hierarchical tree is composed on two sql table (node and relations); the problem was that with a large number of nodes and  relations, the performance slow down drammatically.

In my case,  the solution that I’ve adopted is to use Azure Redis Cache to store the nodes of the tree and StackExchange.Redis as client library.

First of all, I use EF Code First and I’ve two tables, node and relations; migrations are enabled and the Seed Method of Configuration class is overridden to populate the database with test datas:

internal sealed class Configuration : DbMigrationsConfiguration<OrganizationTree.DataLayer.Context>
{
public Configuration()
{
AutomaticMigrationsEnabled = false;
}

protected override void Seed(OrganizationTree.DataLayer.Context context)
{
...
context.SaveChanges();
}
}

The RedisCacheRepository is responsible to managing access to redis cache:

public class RedisCacheRepository<TObject> : ICacheRepository<TObject> where TObject : class
{
IDatabase _cache;

public RedisCacheRepository(IDatabase cache)
{
_cache = cache;
}

public void InsertOrUpdate(string key, TObject obj)
{
string val = JsonConvert.SerializeObject(obj);
_cache.StringSet(key, val);
}

public async Task InsertOrUpdateAsync(string key, TObject obj)
{
string val = JsonConvert.SerializeObject(obj);
await _cache.StringSetAsync(key, val);
}

public void InsertOrUpdate(string key, IEnumerable<TObject> objects)
{
var items = objects.Select(obj => (RedisValue)JsonConvert.SerializeObject(obj)).ToArray();
_cache.SetAdd(key, items);
}

public async Task InsertOrUpdateAsync(string key, IEnumerable<TObject> objects)
{
var items = objects.Select(obj => (RedisValue)JsonConvert.SerializeObject(obj)).ToArray();
await _cache.SetAddAsync(key, items);
}

public TObject Get(string id)
{
TObject obj = null;
string cachedObject = _cache.StringGet(id);
if (cachedObject != null)
{
obj = JsonConvert.DeserializeObject<TObject>(cachedObject);
}

return obj;
}

public async Task<TObject> GetAsync(string id)
{
TObject obj = null;
string cachedObject = await _cache.StringGetAsync(id);
if (cachedObject != null)
{
obj = JsonConvert.DeserializeObject<TObject>(cachedObject);
}

return obj;
}

public IEnumerable<TObject> GetList(string id)
{
IEnumerable<TObject> objs = new List<TObject>();
var items = _cache.SetMembers(id);

if (items.Count() > 0)
{
objs = items.Select(item => JsonConvert.DeserializeObject<TObject>(item));
}

return objs;
}

public async Task<IEnumerable<TObject>> GetListAsync(string id)
{
IEnumerable<TObject> objs = new List<TObject>();
var items = await _cache.SetMembersAsync(id);

if (items.Count() > 0)
{
objs = items.Select(item => JsonConvert.DeserializeObject<TObject>(item));
}

return objs;
}

public void Invalidate(string id)
{
_cache.KeyDelete(id);
}

public async Task InvalidateAsync(string id)
{
await _cache.KeyDeleteAsync(id);
}
}

The class TreeNodeService is responsible to build the organization tree and accept in the constructor two parameters, the EF context and the cache database.

public TreeNodeService(DbContext dbContext, IDatabase cache)
{
_nodeRepository = new Repository<Node>(dbContext);
_relationRepository = new Repository<Relation>(dbContext);
_cacheRepository = new RedisCacheRepository<TreeNode>(cache);
}

The LoadTree method load the entire tree structure, while GetChilds method load the childs of a specific node. This method checks if the node is already cached, if it’s not it retrives from database. The GetChildsFromDatabase method load the childs, which are placed in the cache if not present.

public async Task<TreeNode> LoadTree(Guid idTopNode)
{
return await GetTree(idTopNode);
}

public async Task<IEnumerable<TreeNode>> GetChilds(TreeNode treeTopNode)
{
IEnumerable<TreeNode> childNodes = await _cacheRepository.GetListAsync(treeTopNode.Node.Id.ToString());
if (childNodes.Count() > 0)
{
return await Task.Run(() => GetChildsFromCache(treeTopNode).ToList());
}
else
{
IEnumerable<TreeNode> childsTopNode = await Task.Run(() => GetChildsFromDatabase(treeTopNode).ToList());
await _cacheRepository.InsertOrUpdateAsync(treeTopNode.Node.Id.ToString(), childsTopNode);
return childsTopNode;
}
}

private async Task<TreeNode> GetTree(Guid idTopNode)
{
Node topNode = _nodeRepository.FirstOrDefault(n => n.Id == idTopNode);
TreeNode treeTopNode = new TreeNode();

if (topNode != null)
{
treeTopNode.Node = topNode;
treeTopNode.Childs = await GetChilds(treeTopNode);
}

return treeTopNode;
}

private IEnumerable<TreeNode> GetChildsFromDatabase(TreeNode parentTreeNode)
{
List<Relation> relations = _relationRepository.Find(r => r.IdParent == parentTreeNode.Node.Id).ToList();

foreach (Relation rel in relations)
{
TreeNode childTreeNode = new TreeNode();
childTreeNode.Node = rel.Child;
childTreeNode.Parent = parentTreeNode;

childTreeNode.Childs = GetChildsFromDatabase(childTreeNode).ToList();

if (childTreeNode.Childs.Count() > 0)
{
_cacheRepository.InsertOrUpdateAsync(childTreeNode.Node.Id.ToString(), childTreeNode.Childs);
}

yield return childTreeNode;
}
}

private IEnumerable<TreeNode> GetChildsFromCache(TreeNode parentTreeNode)
{
parentTreeNode.Childs = _cacheRepository.GetList(parentTreeNode.Node.Id.ToString());

foreach (TreeNode childTreeNode in parentTreeNode.Childs)
{
childTreeNode.Childs = GetChildsFromCache(childTreeNode).ToList();
yield return childTreeNode;
}
}

For business requirements, this class stores in the cache tree nodes separately, but to maximize performances it’s possible to purge the complete tree with a single key.

You can find the project here.