Introduction:
In today’s world, speed and efficiency in responding to requests are of paramount importance. Large-scale, high-traffic systems such as online stores, social networks, and banking services face substantial amounts of data and user requests. This high demand not only places a heavy load on servers and databases but can also significantly impact the user experience. In such cases, implementing a caching system can be an effective solution to improve performance and reduce the load on resources.
This article discusses implementing an advanced caching system that utilizes a combination of Hash Maps and AVL Trees for faster data access. Additionally, it employs a TTL (Time to Live) mechanism for data expiration management and automated data deletion, as well as input validation for enhanced security. This smart and secure caching system meets the essential requirements of large projects, providing a powerful solution for enhancing service speed and efficiency for users.
1. Implementing an AVL Tree with TTL
To manage data expiration, we extend the AVL class with a TTL field. This field specifies the expiration time for each data item and automatically deletes expired data.
// src/utils/avltree.ts
class AVLNode {
key: string;
value: any;
ttl: number; // Time to live
height: number;
left: AVLNode | null;
right: AVLNode | null;
constructor(key: string, value: any, ttl: number) {
this.key = key;
this.value = value;
this.ttl = Date.now() + ttl; // Expiry time
this.height = 1;
this.left = null;
this.right = null;
}
isExpired(): boolean {
return Date.now() > this.ttl;
}
}
export class AVLTree {
private root: AVLNode | null;
constructor() {
this.root = null;
}
private getHeight(node: AVLNode | null): number {
return node ? node.height : 0;
}
private updateHeight(node: AVLNode): void {
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
}
private rotateRight(y: AVLNode): AVLNode {
const x = y.left!;
y.left = x.right;
x.right = y;
this.updateHeight(y);
this.updateHeight(x);
return x;
}
private rotateLeft(x: AVLNode): AVLNode {
const y = x.right!;
x.right = y.left;
y.left = x;
this.updateHeight(x);
this.updateHeight(y);
return y;
}
private getBalance(node: AVLNode): number {
return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
}
insert(key: string, value: any, ttl: number): void {
this.root = this.insertNode(this.root, key, value, ttl);
}
private insertNode(node: AVLNode | null, key: string, value: any, ttl: number): AVLNode {
if (!node) return new AVLNode(key, value, ttl);
if (key < node.key) {
node.left = this.insertNode(node.left, key, value, ttl);
} else if (key > node.key) {
node.right = this.insertNode(node.right, key, value, ttl);
} else {
node.value = value;
node.ttl = Date.now() + ttl;
return node;
}
this.updateHeight(node);
const balance = this.getBalance(node);
if (balance > 1 && key < node.left!.key) return this.rotateRight(node);
if (balance < -1 && key > node.right!.key) return this.rotateLeft(node);
if (balance > 1 && key > node.left!.key) {
node.left = this.rotateLeft(node.left!);
return this.rotateRight(node);
}
if (balance < -1 && key < node.right!.key) {
node.right = this.rotateRight(node.right!);
return this.rotateLeft(node);
}
return node;
}
search(key: string): any {
let node = this.root;
while (node) {
if (node.isExpired()) {
this.delete(node.key);
return null;
}
if (key === node.key) return node.value;
node = key < node.key ? node.left : node.right;
}
return null;
}
delete(key: string): void {
this.root = this.deleteNode(this.root, key);
}
private deleteNode(node: AVLNode | null, key: string): AVLNode | null {
if (!node) return null;
if (key < node.key) {
node.left = this.deleteNode(node.left, key);
} else if (key > node.key) {
node.right = this.deleteNode(node.right, key);
} else {
if (!node.left || !node.right) return node.left || node.right;
let minLargerNode = node.right;
while (minLargerNode.left) minLargerNode = minLargerNode.left;
node.key = minLargerNode.key;
node.value = minLargerNode.value;
node.ttl = minLargerNode.ttl;
node.right = this.deleteNode(node.right, minLargerNode.key);
}
this.updateHeight(node);
const balance = this.getBalance(node);
if (balance > 1 && this.getBalance(node.left!) >= 0) return this.rotateRight(node);
if (balance < -1 && this.getBalance(node.right!) <= 0) return this.rotateLeft(node);
if (balance > 1 && this.getBalance(node.left!) < 0) {
node.left = this.rotateLeft(node.left!);
return this.rotateRight(node);
}
if (balance < -1 && this.getBalance(node.right!) > 0) {
node.right = this.rotateRight(node.right!);
return this.rotateLeft(node);
}
return node;
}
}
2. Enhanced Caching Service with TTL and Security Mechanisms
This service uses the AVLTree class to manage data efficiently and securely. It includes a basic validation mechanism for data security.
// src/cache/cache.service.ts
import { Injectable, UnauthorizedException } from '@nestjs/common';
import { AVLTree } from '../utils/avltree';
@Injectable()
export class CacheService {
private avlTree: AVLTree;
private authorizedTokens: Set<string> = new Set(['your_authorized_token']); // Simple validation example
constructor() {
this.avlTree = new AVLTree();
}
validateToken(token: string): void {
if (!this.authorizedTokens.has(token)) {
throw new UnauthorizedException('Invalid access token');
}
}
set(key: string, value: any, ttl: number, token: string): void {
this.validateToken(token);
this.avlTree.insert(key, value, ttl);
}
get(key: string, token: string): any {
this.validateToken(token);
return this.avlTree.search(key);
}
delete(key: string, token: string): void {
this.validateToken(token);
this.avlTree.delete(key);
}
}
3. Controller with Validation and TTL
The API controller uses the set, get, and delete methods to securely store and retrieve data.
// src/cache/cache.controller.ts
import { Controller, Get, Post, Delete, Body, Param, Query } from '@nestjs/common';
import { CacheService } from './cache.service';
@Controller('cache')
export class CacheController {
constructor(private readonly cacheService: CacheService) {}
@Post('set')
setCache(@Body() body: { key: string; value: any; ttl: number; token: string }) {
this.cacheService.set(body.key, body.value, body.ttl, body.token);
return { message: 'Data cached successfully' };
}
@Get('get/:key')
getCache(@Param('key') key: string, @Query('token') token: string) {
const value = this.cacheService.get(key, token);
return value ? { value } : { message: 'Key not found or expired' };
}
@Delete('delete/:key')
deleteCache(@Param('key') key: string, @Query('token') token: string) {
this.cacheService.delete(key);
return { message: 'Key deleted successfully' };
}
}
Practical Use Cases of the Caching System
Session Management for Authentication Systems:
Example: Banking and financial systems.API Caching for Reducing Request Load:
Example: Weather apps and currency exchange websites.Real-Time User Status Storage in Online Platforms:
Example: Messaging apps like WhatsApp or Telegram.Product Data Storage in Online Stores:
Example: High-traffic e-commerce platforms like Amazon.
These examples demonstrate that this caching system can significantly reduce database and server load, enhancing response times for users.
Conclusion
In this article, we designed and implemented an advanced caching system that combines AVL Trees and Hash Maps to enable fast data access and server performance optimization. The TTL mechanism provides automatic data expiration management, while token validation ensures adequate security.
This intelligent caching system is efficient and flexible, suitable for large-scale applications with dynamic and sensitive data, supporting scalable requirements in distributed architectures.
Top comments (0)