Obsidian 4.0.0 Launch: Deno GraphQL caching solution

Server-side cache invalidation added to Deno’s first GraphQL caching solution

Introduction

Obsidian is Deno’s first GraphQL caching solution, providing client-side caching for React components using a browser cache and server-side caching for Oak Routers using a Redis cache.

Performant Caching in Mind

Since GraphQL responses can be arbitrarily large and nested, there is potential for these API calls to be expensive. Introducing a GraphQL caching strategy to the system’s architecture provides a cheaper alternative to making a GraphQL call: a cache check.

Request Time = Cache Check (Hit Rate) + Service Call Time (1 — Hit Rate) + Cache Write (1- Hit Rate)

Obsidian optimizes request time by minimizing the number of expensive service calls and maximizing the hit rate.

Managing both cache space and cache consistency is the most challenging aspect of caching as prioritizing one over the other has trade offs. Obsidian 4.0.0 introduces a robust cache invalidation strategy and a complimentary cache eviction strategy for server-side caching.

Problem and Challenge

Cache invalidation

Suppose a query for all sci-fi movies in a database is made, is not in cache, and is added to cache. A subsequent mutation (i.e., create, update, or delete) to one of those sci-fi movies makes the entire cached response stale. Mutations introduce a challenge for a static cache — a change in a small chunk of data can invalidate all of the cache if it affects other pieces of data.

Cache eviction

When cache is out of memory, a decision must be made on what is evicted to make space. The two strategies explored were Least Recently Used (LRU) and Least Frequently Used (LFU) policies. Since Obsidian is configured for a read-heavy environment, LRU was selected as the default cache eviction policy.

Solution and implementation

Prioritization

There are only two hard things in Computer Science: cache invalidation and naming things — Phil Karlton

The priorities for cache invalidation and eviction were to: 1) minimize the number of expensive service calls and 2) maximize the cache hit rate. Engineering decisions were made through the lens of these priorities.

Restructured server-side caching logic

Obsidian follows robust conditional logic to account for the five major caching scenarios:
1) Query is cached, and no references were evicted
2) Query is cached, and at least one reference was evicted
3) Query is not cached, and it’s a read query
4) Query is not cached, and it’s a delete mutation
5) Query is not cached, and it’s a create or update mutation

Figure 1: Overall server-side cache logic flow diagram

Functional flow diagram

Our functional flow, visualized below, is centered around three core functionalities:
1) response normalization
2) response transformation
3) cache invalidation

Figure 2: Redesigned function flow of server-side caching logic which incorporates cache invalidation

Normalization Algorithm

The backbone of the new server-side caching logic is the recursive normalization algorithm. An arbitrarily nested GraphQL response is flattened into an object of unique reference string keys and their corresponding objects in constant time.

Response Transformation

After running a GraphQL query, Obsidian will transform the response object into a nested object of references, created by normalization. These references point to smaller-sized pieces of data that are written to cache during the transformation process.

Transformation is necessary so mutations will only invalidate these smaller-sized pieces of data rather than the original response object. After caching data for a specific read query, all subsequent read calls will simply reconstruct a response from the accurate partial data in cache rather than fetching from the database.

Figure 3: Obsidian flattens the original GraphQL response object (top left) into normalized objects (top right), and transforms it into an object of references (bottom right) to be stored in cache.

Cache Invalidation

Obsidian detects if a GraphQL query is a mutation based on relevant properties in the query’s associated Abstract Syntax Tree. The mutation is further characterized as a create, update or delete operation based on the shape of the response object and the existence of its associated hash in cache.

Obsidian performs the following conditional logic:

1. In the case of a read query, the GraphQL response is transformed into an object of reference and cached with its query string as the Redis hash. Furthermore, each reference object is cached with its reference string as the Redis hash.
2. In the case of a delete mutation, the references are abstracted from the GraphQL response and invalidated from cache through deletion.
3. In the case of either a create or update mutation, each reference object is cached with its reference string as the Redis hash. If the reference already exists, it is overwritten with the updated value.

Cache eviction

Typically, LFU is set as the default cache eviction strategy because of its ease of implementation in Redis and optimization of cache hit rate. By keeping only the most frequently accessed data in cache, LFU often increases hit rate and decreases miss rate.

However, Obsidian 3.3 defaults to LRU because it better complements the new cache invalidation strategy. Since the references will be read more often than the GraphQL responses themselves, LRU prevents the response object from being evicted even if they are less frequently used than their reference components.

Getting Started

Try out Obsidian’s exciting new features with our easy-to-use demo. You can read our documentation to start incorporating Obsidian in your own app. You can reference our technical brief for further details on how Obsidian works under the hood.

Obsidian is an open-source product produced under the tech accelerator Open Source Lab. We welcome contributions and feedback via GitHub.

Other articles on Obsidian:

Obsidian 1.0
Obsidian 2.0
Obsidian 3.0
Obsidian 3.1
Obsidian 3.2
Obsidian 4.0 Technical Brief

Co-authored by Team Obsidian:

Sardor Akhmedov| GitHub

Michael Chin| GitHub | LinkedIn

Dana Flury| GitHub

Yogi Paturu| GitHub | LinkedIn