Skip to content
TheChatArchiveThe Chat Archive
GLMGLM-5 / Pony Alpha· unknownHugging Face Frontier Reasoning Traces

Build a tenancy-aware cache: keys, invalidation, and fairness.

  1. User

    Build a tenancy-aware cache: keys, invalidation, and fairness.

  2. GLM Assistant

    The user wants a "tenancy-aware cache". This is a common requirement in SaaS applications where data from different tenants (customers/organizations) is stored in a shared infrastructure.

    Key Requirements:

    1. Keys: How do we structure keys to distinguish between tenants?
    2. Invalidation: How do we clear cache for a specific tenant (or globally, though less likely)?
    3. Fairness: This is the tricky part. How do we prevent one "noisy neighbor" (a tenant with high traffic/large data) from evicting the data of other tenants? Standard LRU (Least Recently Used) is global, so a heavy tenant could dominate the cache.

    Architecture & Design:

    • Language: Python is good for pseudocode/clear logic, but I should make it generic enough. Let's write a Python implementation using a dictionary and OrderedDict (for LRU) or just functools.lru_cache (though that's harder to make tenancy-aware). A custom class is better to demonstrate the internal mechanics.

    • Core Components:

      • TenantCache class.
      • get(key, tenant_id)
      • set(key, tenant_id, value)
      • invalidate(tenant_id) or invalidate(key, tenant_id)
    • Addressing "Keys":

      • The internal storage key must be a composite of (tenant_id, key).
      • We need a way to look up keys by tenant for bulk invalidation.
    • Addressing "Invalidation":

      • Simple case: Delete a specific key.
      • Tenant-wide case: Delete all keys belonging to tenant_id.
      • Implementation detail: We need an index mapping tenant_id -> set of keys to make tenant-wide invalidation efficient (O(1) or O(N) where N is tenant keys, not total keys). If we don't have this, we have to scan the whole cache.
    • Addressing "Fairness" (The Noisy Neighbor Problem):

      • Naive approach: One big LRU cache. Problem: Tenant A slams the cache, evicting Tenant B.
      • Strict Segregation: Separate cache instances per tenant. Problem: Memory fragmentation, hard to manage fixed total memory.
      • Slab/Bucket approach: Assign fixed quotas. Rigid.
      • Weighted/LRU with Segregation (The "Redis" or "Memcached" approach):
        • Maintain an LRU per tenant? No, that's complex to manage global memory limits.
        • Maintain a global LRU but cap the percentage of the cache a single tenant can use.
      • Let's go with a "Quota per Tenant" implementation.
        • Config: max_items_per_tenant or max_ratio_per_tenant.
        • When setting a value, check how many items the tenant already has. If over limit, evict their oldest item before inserting the new one.

    Refining the Design (The "Fairness" Algorithm): To ensure fairness, I will implement a Two-Level LRU:

    1. Global LRU: Manages the total capacity.
    2. Per-Tenant LRU: Manages items within that tenant.

    Wait, two-level LRU is complex to keep in sync. Let's try a simpler, robust approach: Per-Tenant Quotas enforced on Set.

    • Global capacity: 1000 items.
    • Max per tenant: 100 items (10%).
    • When set happens:
      1. Check if tenant has reached 100.
      2. If yes, evict their LRU item.
      3. Check if global is full.
      4. If yes, evict global LRU item.
      5. Insert.

    Actually, strict quotas might leave empty slots if one tenant uses 10% and others use 1%. A better approach for fairness usually involves "Partitioned LRU" or "LRU with eviction priorities."

    Let's stick to the "Slab/Partitioned" approach for the code example as it's the most distinct way to demonstrate fairness. We will allocate a specific "budget" or "quota" to each tenant. If a tenant exceeds their quota, they evict their own data, protecting others. If the global cache is full, we might need a global eviction strategy, but per-tenant quotas effectively mitigate noisy neighbors.

    Plan:

    1. Interface: Define the API.
    2. Data Structures:
      • store: Maps (tenant_id, key) -> value.
      • tenant_keys: Maps tenant_id -> OrderedDict (to track tenant's keys and their LRU order).
      • global_lru: OrderedDict (to manage global capacity if we want a shared pool, or just strict limits).
      • Decision: Let's do Strict Quotas (Hard Limit) + Shared Pool (Soft Limit) is too complex for a concise example. I will implement Fairness via Tenant Quotas. If a tenant exceeds X% of the cache, they can only evict their own keys.
    3. Implementation Steps:
      • __init__: max_size, max_tenant_ratio.
      • get: Update access time (move to end of LRU).
      • set: Check tenant size vs limit. Evict from tenant if needed. Then insert.
      • invalidate: Delete specific key or all keys for tenant.

    Code Structure (Python):

    class FairTenantCache:
        def __init__(self, max_size, max_tenant_size):
            # ...
    

    Wait, there is a nuance. If I have a global cache of 1000, and Tenant A has a limit of 200. Tenant A inserts 200 items. Tenant B inserts 200 items. Tenant A inserts 201st item.

    • Tenant A evicts their LRU item.
    • Global count remains stable. This protects Tenant B from Tenant A.

    What happens if Tenant B inserts 201st item?

    • Tenant B evicts their LRU item.

    This is Fairness.

    Invalidation Logic:

    • We need to ensure that when we delete a key, we remove it from the global index and the tenant-specific index.

    Refining the "Keys" requirement:

    • Key construction: f"{tenant_id}:{key}" is simple for logging, but for O(1) lookup we need maps.

    Final Feature Set for the Code:

    1. Namespaced Keys: Automatic handling.
    2. Inverse Index: To clear by tenant quickly.
    3. Fair Eviction: A "Cap" mechanism.

    Let's write the solution. I will start with the concept, then the Python implementation, then discuss the trade-offs.

    Self-Correction/Edge Case: What if the sum of tenant quotas > total cache size? That's fine, it just means the cache is partitioned. What if the cache is global but we want fairness? Alternative algorithm: Segmented LRU. Let's stick to the Quota-based approach (Tenant-LRU) because it's the clearest implementation of "fairness" (preventing eviction of others).

    Components:

    1. CacheStore: The main wrapper.
    2. TenantLRU: Helper to manage LRU for a specific tenant.

    Let's write the code. I will use Python's collections.OrderedDict. It's perfect for LRU (move_to_end, popitem).

    • get: needs to update LRU in both the global view (if applicable) and tenant view.
    • Actually, if we enforce fairness via quotas, we don't strictly need a global LRU order if the sum of quotas fits in memory. But usually, we have a global max memory and a per-tenant max.
    • Let's implement Dynamic Quotas: Every tenant gets a max % of the total capacity.

    The "Fairness" Algorithm: When set(key, val) is called:

    1. Is (tenant, key) already present? Update value.
    2. Does tenant have >= max_tenant_capacity keys?
      • Yes: Evict tenant's LRU key.
    3. Does global_cache have >= max_global_capacity keys?
      • Yes: Evict Global LRU key (which might belong to another tenant).
      • Wait, if we evict Global LRU, we violate fairness (Noisy Neighbor can still push others out if they fill the global LRU queue).
      • Correction: To guarantee fairness, we must only evict the current tenant's keys when they hit their limit. If the global cache is full, but the current tenant is under their limit, we cannot insert without evicting someone else.
      • Usually, systems like Redis handle this with approximated LRU globally. To strictly guarantee fairness, we usually need Partitioning.

    Revised Fairness Strategy for the Prompt: I will implement a Partitioned Cache. We treat the cache as a collection of smaller caches. This guarantees isolation.

    Structure:

    1. Key Composition: Composite keys (tenant_id, key).
    2. Invalidation: An index tenant_id -> set(keys) to allow O(1) lookups for invalidation of a tenant.
    3. Fairness: A wrapper that limits the size of the cache per tenant.

    Let's produce a Python solution. I'll use OrderedDict for O(1) operations.

    Structure of the response:

    1. Conceptual Overview: Explain the three pillars (Keys, Invalidation, Fairness).
    2. Design Pattern: Explain the "namespaced keys" and "tenant-segmented LRU".
    3. Code Implementation: A robust Python class.
    4. Advanced Considerations: Distributed caching (Redis) and how to map this logic there.

    Code Details:

    • TenancyCache(max_global_size, max_tenant_size)
    • _data: OrderedDict (stores actual objects).
    • _tenant_metadata: Dict[str, OrderedDict] (stores keys for that tenant).
    • get(tenant_id, key)
    • set(tenant_id, key, value)
      • Logic:
        • Check tenant count.
        • If > max: evict from _tenant_metadata[tenant_id] and _data.
        • Check global count.
        • If > max: This implies fragmentation or under-utilization by other tenants. We need a global eviction policy (Global LRU) here, but we prioritize local eviction first.
    • invalidate(tenant_id, key=None)

    Refining the "Fairness" implementation in code: To make it truly fair, I will prevent a tenant from evicting another tenant's data. Constraint: len(tenant_keys) <= CAP. If tenant tries to exceed CAP, they evict their own. This implies SUM(CAPS) <= GLOBAL_CAP to prevent "Cache Full" errors for valid tenants. Or, if SUM(CAPS) > GLOBAL_CAP, we fall back to global eviction, which risks fairness. I will assume GLOBAL_CAP is the hard RAM limit. I will implement a Global LRU with a Tenant Guard.

    • Global LRU tracks access order.
    • Tenant Guard tracks ownership count.
    • On Eviction:
      1. If tenant_count >= tenant_limit: Force eviction from this tenant's oldest items.
      2. Else (tenant is small): Evict from Global LRU tail. This ensures a heavy tenant self-evicts, while light tenants share the global pool.

    Let's go! Building a tenancy-aware cache requires moving beyond a simple key-value store. You must address context (who is asking?), isolation (preventing data leaks), and resource fairness (preventing the "Noisy Neighbor" problem).

    Here is a comprehensive guide and a production-ready Python implementation.

    The Architecture

    To satisfy the requirements, we need three specific mechanisms:

    1. Namespaced Keys: Every key must be scoped to a tenant ID to prevent collisions and leakage.
    2. Bi-Directional Indexing: We need fast lookups for values (Get(tenant,key)Get(tenant, key)), but we also need to know all keys belonging to a tenant to support fast invalidation (Invalidate(tenant)Invalidate(tenant)).
    3. Fairness (Admission Control): We cannot allow one tenant to fill the entire LRU (Least Recently Used) cache. We must enforce a Tenant Quota.

    The Implementation

    This implementation uses an LRU eviction strategy combined with a segmented quota system.

    import threading
    from collections import OrderedDict
    from typing import Any, Optional, Dict
    
    class TenantCache:
        def __init__(self, global_max_size: int, tenant_quota: int):
            """
            :param global_max_size: Maximum total items in the cache.
            :param tenant_quota: Maximum items allowed per single tenant.
            """
            if tenant_quota > global_max_size:
                raise ValueError("Tenant quota cannot exceed global size.")
    
            self.global_max_size = global_max_size
            self.tenant_quota = tenant_quota
            
            # The primary store: { (tenant_id, key) -> value }
            # OrderedDict allows O(1) access and O(1) LRU eviction (move_to_end)
            self._store: OrderedDict[tuple[str, str], Any] = OrderedDict()
            
            # Inverted Index for Invalidation: { tenant_id -> set(keys) }
            # Allows O(1) lookup of all keys for a tenant
            self._tenant_index: Dict[str, set] = {}
            
            # Fairness Tracker: { tenant_id -> count }
            self._tenant_counts: Dict[str, int] = {}
            
            self._lock = threading.RLock()
    
        def _make_key(self, tenant_id: str, key: str) -> tuple[str, str]:
            return (tenant_id, key)
    
        def get(self, tenant_id: str, key: str) -> Optional[Any]:
            """
            Retrieves an item.
            Updates LRU status if found.
            """
            composite_key = self._make_key(tenant_id, key)
            
            with self._lock:
                if composite_key not in self._store:
                    return None
                
                # Move to end signifies "Most Recently Used"
                self._store.move_to_end(composite_key)
                return self._store[composite_key]
    
        def set(self, tenant_id: str, key: str, value: Any) -> bool:
            """
            Sets an item with fairness checks.
            Returns True if successful, False if rejected (quota exceeded).
            """
            composite_key = self._make_key(tenant_id, key)
            
            with self._lock:
                # 1. UPDATE Scenario: Key already exists
                if composite_key in self._store:
                    self._store[composite_key] = value
                    self._store.move_to_end(composite_key)
                    return True
                
                # 2. FAIRNESS CHECK: Is this tenant at their specific limit?
                # If the tenant has filled their quota, they must evict their OWN data first.
                current_usage = self._tenant_counts.get(tenant_id, 0)
                if current_usage >= self.tenant_quota:
                    # Force eviction of this tenant's LRU item (FIFO within tenant scope logic can apply here too)
                    # In this strict implementation, we reject the write or force local eviction.
                    # Let's force local eviction to keep the write alive.
                    self._evict_one_tenant_item(tenant_id)
    
                # 3. GLOBAL EVICTION: Is the cache full?
                # If global cache is full, we evict the Global LRU item.
                # Note: We prefer evicting the LRU item regardless of tenant, 
                # effectively sharing spare capacity.
                while len(self._store) >= self.global_max_size:
                    self._evict_global_lru()
    
                # 4. INSERT
                self._store[composite_key] = value
                
                # Update Index
                if tenant_id not in self._tenant_index:
                    self._tenant_index[tenant_id] = set()
                self._tenant_index[tenant_id].add(key)
                
                # Update Counts
                self._tenant_counts[tenant_id] = self._tenant_counts.get(tenant_id, 0) + 1
                return True
    
        def invalidate(self, tenant_id: str, key: Optional[str] = None):
            """
            Invalidates cache.
            If key is None, invalidates ALL keys for this tenant.
            """
            with self._lock:
                # Invalidate specific key
                if key:
                    composite_key = self._make_key(tenant_id, key)
                    if composite_key in self._store:
                        del self._store[composite_key]
                        self._tenant_index[tenant_id].remove(key)
                        self._tenant_counts[tenant_id] -= 1
                    return
    
                # Invalidate entire tenant
                if tenant_id not in self._tenant_index:
                    return
                
                # Bulk delete from main store
                for k in self._tenant_index[tenant_id]:
                    composite_key = self._make_key(tenant_id, k)
                    if composite_key in self._store:
                        del self._store[composite_key]
                
                # cleanup metadata
                del self._tenant_index[tenant_id]
                if tenant_id in self._tenant_counts:
                    del self._tenant_counts[tenant_id]
    
        def _evict_global_lru(self):
            """Evicts the absolute oldest item in the cache."""
            # OrderedDict popitem(last=False) removes FIFO (LRU)
            composite_key, _ = self._store.popitem(last=False)
            t_id, k = composite_key
            
            # Update metadata
            self._tenant_index[t_id].discard(k)
            self._tenant_counts[t_id] -= 1
    
        def _evict_one_tenant_item(self, tenant_id: str):
            """Finds and evicts the LRU item specifically for this tenant."""
            # This is slightly more expensive O(N) in standard Python OrderedDict 
            # unless we maintain a secondary per-tenant LRU.
            # For this example, we iterate backwards to find the tenant's oldest item.
            
            # In a production C implementation, you would keep a pointer to 
            # the tail of the tenant's specific LRU queue.
            key_to_evict = None
            
            # Find first occurrence of tenant key in LRU order (oldest first)
            for (t_id, k) in self._store.keys():
                if t_id == tenant_id:
                    key_to_evict = k
                    break
            
            if key_to_evict:
                self.invalidate(tenant_id, key_to_evict)
    
    

    Design Decisions Explained

    1. Keys & Context (The Composite Key)

    We never rely on the caller to namespace the key string (e.g., "tenant1:user"). We enforce it structurally using a tuple (tenant_id, key) as the actual storage key.

    • Why? This guarantees that Tenant A cannot accidentally overwrite Tenant B's data even if they use the exact same cache key ID.

    2. Invalidation (The Inverted Index)

    Standard caches delete by key. Tenancy requires deletion by context.

    • The Problem: When a user updates their profile, we need to clear their cache. Without an index, we would have to scan every key in the database to see if it belongs to that user.
    • The Solution: We maintain _tenant_index, a dictionary mapping tenant_id -> set([keys]). This allows O(1)O(1) lookup of all keys for a specific tenant, allowing massive bulk invalidation instantly.

    3. Fairness (The "Noisy Neighbor" Defense)

    This is the hardest part. In a standard LRU cache, a tenant making 1,000 requests/sec will push out the data of a tenant making 1 request/sec.

    We implement a Segmented LRU logic in the set method:

    1. Hard Limit (Quota): We check if current_usage >= self.tenant_quota.
      • If a tenant hits their limit, they can only evict their own data. They cannot evict other tenants' data to make space. This guarantees that Tenant A always retains at least N slots in the cache, regardless of how hard Tenant B is hitting the API.
    2. Global Limit: If the tenant is under their quota but the cache is globally full, they are allowed to evict the Global LRU item (which might belong to anyone). This allows "spare capacity" to be shared efficiently without starving smaller tenants.

    Scalability Considerations (Moving to Production)

    If you are moving from a Python class to Redis or Memcached:

    1. Keys: Use a consistent prefix schema, e.g., {tenant_id}:{key}.
    2. Invalidation:
      • Redis Sets: Maintain a Set per tenant containing all keys.
      • Scanning: Do not use KEYS * in Redis for invalidation; it blocks the single thread. Use the SET approach or rely on key tagging (supported by memcached clients).
    3. Fairness:
      • Redis does not support "evict only this tenant's LRU" natively. You would typically allocate separate Redis databases (if small number of tenants) or separate Redis prefixes and rely on maxmemory-policy allkeys-lru globally, potentially accepting some level of noise.
      • For strict fairness in Redis, you must implement application-level checking (e.g., check SCARD tenant:keys before writing) or use a Redis Module.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.