avatar

Derek Zeng

Loneliness is the gift of life

A case on performance optimization

One task I finished recently was to optimize the loading time of table of content(ToC). ToC is the most important API we are using. Currently, it loads the entire table of content before the initialization of the app. This obviously creates quite a bit of lag when the course is huge and it is not uncommon for Teachers to create large course that contains thousands of items.

Our previous version of content app doesn't have performance problem because it's not a single page app and it only loads ToC for currently viewing content each time.

Now for our new Single page app, besides using for loading table of content UI, the ToC is also used to populate several other things. For example, after loading the ToC, we want to mark the nodes which have downloadable children. We also want to count the total number of Topics (leave node) in the ToC.

I suggested making separate APIs for those dependent tasks for the sake of separation of concerns. But that requires too much work including publishing and maintaining APIs. Given the current code base, loading the entire ToC seems to be the most sensible solution.

So my proposed solution was to create a shallow version of the ToC api and use the shallow version on demand. To reduce the time to first UI, we load the shallow ToC first, which involves only the top most nodes. Soon after the shallow version loaded, I'll load the full ToC and and then update the dependent UIs. Basically it's double loading. This solution is supported by senior team members. So I went ahead and implemented it.

The data structure of the ToC is like a forest. Each tree is an module. Module can have Topics or Modules. The tree height is at most 3. But it can really have thousands of Topics located at any level.

In order to minimize API change, I reused the ToC API and added query parameters to tune the response. For the shallow loading, we added a shallowLoad boolean param. The shallowly loaded ToC would have the same top-down structure with unnecessary nodes/branches pruned.

Now, there are two major obstacles I need to tackle.

  1. Need to support client routing. This means when a child node is selected and the page is reloaded, the ToC UI also needs to show that node and all nodes up to the root.

  2. Need to work with different ToC operations at client side, i.e. add/delete/move/change node. Current implementation simply loads the entire ToC after each action.

To tackle the first one, I added a API query parameter for the selected node id. (Topic and Module share the same id space) When it's not null, I load that object first and then walk bottom up the tree. For every parent node I encounter, I also load its children modules and topics. The modules loaded this way will only contain simple attributes and will not be opened.

To do this on the server side, I have something like this: (use python for demo purpose)

def load_ToC_shallow(selected=None):
    selected_to_root = get_path(selected)
    roots = load_roots()
    for root in roots:
        load_tree_shallow(root, selected_to_root) # load in place
    return roots

def get_path(selected):
    obj = get_object(selected)
    path = []
    while True:
        if obj.is_module:
            path.append(obj)
        if obj.parent:
            obj = obj.parent
        else:
            break
    return path

def load_tree_shallow(root, path):
    if root.is_topic:
        return
    root.load_topics() # populate topics
    for module in root.modules:
        if path and module == path[-1]:
            # call recursively only when path is matched
            load_tree_shallow(module, path[:-1])

The second problem is quite tricky. For each relevant action taken, I need to shallowly load the ToC once. But at that moment, I already have a ToC in memory. So... I have to merge the new ToC into the old one.

I call it ToCCache.

Here I assume, the ToC from the response represents the latest partial ToC relevant to the action. Meanwhile, there was no other new actions taken on the ToCCache after the last shallow loading. Thus, if I merge it correctly, my ToCCache should still be up to date.

I have to consider Add/Delete/Move/Update actions. For each one, there is a merge strategy.

  1. For Add, the new partial response for added node with id k should be equivalent to load_ToC_shallow(selected=k). To merge it, I assume the parent of the node is unchanged, I'll just replace the selected node. (module or topic) Update Action is the same as Add.

  2. For Delete, if it's successful, no need to merge anything. I'll just remove the node and it's descendants from ToCCache.

  3. for Move, it's a bit tricky. The response will contain the selected node at its new position. Like add, I'll add it in there. At same time, I need remove the node from original position.

After worked on these merging strategies, I have another problem.

Because I'm doing double loading, I need to figure out a way to handle the second requests. The second requests is problematic because:

  1. the response may take a long time to come back. there may be other ToC operations happened during wait time. So when it's received, it's out of sync.

  2. the response contains the relevant information for dependent UI. I actually need a way to retain that information so later if user make changes, I can derive the correct state from ToCCache.

So I need to merge the full ToC too. But how?? One important observation is:

ToCCache obviously contains more up to date information than the second response, despite that it is possibly incomplete.

So the new merge strategy should be merge level by level, module by module, keep what already in the ToCCache, add module that only present in the full ToC. But wait, there is one issue. If there is a Move happened during the request time of full ToC, the absence of the moved node under its original parent need not to be filled in. Otherwise it will revert the move action. So to fix this, I need to keep track of the modules that are updated. So when I have one module that is updated, I'll skip looping into it's children.

Also since the modules are in an array. The order needs to be preserved as well. So when merging, I have to follow the order of the client ToC.

Now I have the entire ToC, I can traverse the tree to collect the dependent informations.

Problem solved.

All these code are packaged into a ToCCache class which ensures the minimal impact on the code base.

(End of article)