Distributed Cache with Jest Testing

Building a distributed cache is a common requirement in modern applications to improve performance and reduce database load. This challenge asks you to implement a simplified distributed cache using TypeScript and thoroughly test it using Jest. The goal is to create a cache that can store and retrieve data across multiple nodes, simulating a distributed environment.

Problem Description

You are tasked with implementing a DistributedCache class in TypeScript. This class should provide the following functionalities:

• constructor(nodes: string[]): Initializes the cache with a list of node addresses (strings). These represent the locations where cache data will be stored.
• set(key: string, value: any): Stores a key-value pair in the cache. The cache should distribute the data across the nodes using a simple consistent hashing strategy (see Notes).
• get(key: string): Retrieves the value associated with a given key from the cache. If the key is not found, it should return undefined.
• delete(key: string): Removes a key-value pair from the cache.

The cache should simulate a distributed environment. While you don't need to implement actual network communication, you do need to simulate the distribution of data across multiple nodes. The nodes array represents the available cache servers. The consistent hashing strategy should determine which node a given key is assigned to.

Key Requirements:

• Consistent Hashing: Implement a simple consistent hashing algorithm to map keys to nodes. A basic approach is to use the modulo operator (%) on the key's hash code (e.g., key.hashCode() % nodes.length) to determine the node index.
• Node Simulation: The cache should internally maintain a data structure (e.g., a Map) to represent the data stored on each node. Each node is represented by a Map<string, any>.
• Error Handling: The get and delete methods should handle cases where the key is not found gracefully, returning undefined for get.
• Testability: The code should be designed with testability in mind, making it easy to mock dependencies and verify behavior in Jest tests.

Expected Behavior:

• set should distribute keys across the nodes based on the consistent hashing algorithm.
• get should retrieve data from the correct node based on the consistent hashing algorithm.
• delete should remove data from the correct node.
• If a key is not found, get should return undefined.

Edge Cases to Consider:

• Empty nodes array in the constructor. Should throw an error.
• Duplicate keys. The last set operation should overwrite previous values.
• Large number of nodes. The consistent hashing should still function correctly.
• Keys with unusual characters or lengths. The hashing function should handle these gracefully.

Examples

Example 1:

Input:
nodes = ["node1", "node2"]
set("key1", "value1")
set("key2", "value2")
get("key1")
Output: "value1"
Explanation: Assuming consistent hashing maps "key1" to "node1" and "key2" to "node2", get("key1") retrieves the value from "node1".

Example 2:

Input:
nodes = ["node1", "node2", "node3"]
set("key1", "value1")
set("key2", "value2")
set("key3", "value3")
delete("key2")
get("key2")
Output: undefined
Explanation: Assuming consistent hashing maps "key1" to "node1", "key2" to "node2", and "key3" to "node3", deleting "key2" removes it from "node2".  `get("key2")` then returns `undefined`.

Example 3:

Input:
nodes = []
set("key1", "value1")
Output: Error thrown (e.g., "Nodes array cannot be empty")
Explanation: The constructor should throw an error if the nodes array is empty.

Constraints

• The number of nodes can range from 1 to 100.
• Keys are strings, and values can be of any type.
• The consistent hashing algorithm should be simple and efficient. Performance is not a primary concern for this challenge, but avoid excessively complex hashing functions.
• The set operation should complete within a reasonable time (e.g., less than 100ms).
• The get and delete operations should also complete within a reasonable time.

Notes

• You can use a simple hashing function like key.hashCode(). JavaScript doesn't have a built-in hashCode() method, so you can use a polyfill or a simple string hashing algorithm. For example: function hashCode(str) { let hash = 0; for (let i = 0; i < str.length; i++) { hash = (hash << 5) - hash + str.charCodeAt(i); } return hash;}
• The consistent hashing strategy is crucial. Ensure that keys are distributed relatively evenly across the nodes.
• Focus on the core functionality and testability. You don't need to implement features like replication, persistence, or advanced consistency protocols.
• Write comprehensive Jest tests to cover all the functionalities and edge cases. Test the consistent hashing behavior to ensure keys are mapped to the correct nodes.
• Consider using Map objects in TypeScript to represent the data stored on each node. This provides efficient key-value lookups.
• The error handling for an empty nodes array should be explicit (e.g., throwing an Error object).