Design Query Cache

Task

Design a key-value cache to save the results of the most recent web server queries

Use Cases

• User sends a search request resulting in a cache hit
• User sends a search request resulting in a cache miss

Design

Query API

class QueryApi(object):
    # Attributes: memory_cache, reverse_index_service

def parse_query(self, query):
        # Clean up query, tokenize string, convert to boolean operations

def process_query(self, query):
        # Check cache. If no results, retrieve from index service and update cache

Node (atomic unit of query, results pair)

class Node(object):
    # Attributes: query, results

LinkedList (doubly linked list of node to track least recently used query result)

class LinkedList(object):
    # Attributes: head, tail

def move_to_front(self, node):
        # Move existing node to front of linked list

def append_to_front(self, node):
        # Append node to front of linked list

def remove_from_tail(self):
        # Remove node at the tail of linked list

Cache

class Cache(object):
    # Attributes: MAX_SIZE, size, lookup, linked_list

def get(self, query):
        # Get query results. Update node position to front of list.

def set(self, results, query):
        # Add query-results pair into key-values.
        # Remove oldest entry in list and add node to front of list.

Based on Donne Martin's System Design Primer