Caching Strategies & In-Memory Optimization Questions

1. Brief approach

• Use hybrid cache: critical writes = write-through (immediate network call + local cache update). Non‑critical writes = write-behind queue persisted locally (SQLite / Realm) and synced opportunistically. Ensure idempotency with client-generated UUIDs and sequence/version numbers. Resolve conflicts server-side with merge rules and client-side UI indicators for pending/unconfirmed items.

2. Pseudocode (Kotlin-style)

data class WriteOp(val id: String, val type: String, val payload: Map<String,Any>, val ts: Long, val version: Int)

class SyncQueue(val db: LocalDB) {
  fun enqueue(op: WriteOp) { db.insert(op) }         // persisted queue
  fun peek(): WriteOp? = db.firstPending()
  fun ack(id:String) { db.delete(id) }
  fun markFailed(id:String, reason:String) { db.updateStatus(id,"failed",reason) }
}

suspend fun performWrite(op: WriteOp, critical:Boolean) {
  // update local cache immediately (optimistic)
  LocalCache.apply(op)
  UI.showPending(op)                                  // show pending badge/state

  if (critical) {
    val resp = Network.post(op)                       // synchronous write-through
    if (resp.ok) { LocalCache.merge(resp.data); UI.confirm(op) }
    else { UI.showError(op); SyncQueue.enqueue(op) }  // fallback to queue
  } else {
    SyncQueue.enqueue(op)                             // write-behind
  }
}

suspend fun syncLoop() {
  for (op in SyncQueue.allPending()) {
    val resp = Network.postIfNotExists(op.id, op)    // idempotent server API
    if (resp.ok) { LocalCache.merge(resp.data); SyncQueue.ack(op.id); UI.confirm(op) }
    else if (resp.conflict) {
      val resolved = resolveConflict(op, resp.serverState)
      Network.postResolved(op.id, resolved)
    } else { SyncQueue.markFailed(op.id, resp.err) }
  }
}

fun resolveConflict(local:WriteOp, server:State): WriteOp {
  // example: field-level merge, server wins for protected fields, client for user edits
  return mergedOp
}

3. Key concepts & reasoning

• Persist queue to survive app restarts.
• Idempotency: include op.id and server API checks to ignore duplicates.
• Versioning/timestamps for deterministic conflict detection.
• Conflict strategy: prefer operational transform/CRDT for collaborative data; otherwise use field-level merge or last-write-wins with user review when ambiguous.
• UI: show per-item states: pending (spinner), synced (check), failed (error + retry), conflict (needs user resolution).

4. Complexity & edge cases

• Sync cost proportional to queue length; batch ops to reduce requests.
• Handle offline -> backoff retries, exponential backoff, and payload size limits.
• Ensure sensitive writes marked critical to avoid data loss.

5. Alternatives

• Use CRDTs for automatic merge; use server-ack streaming (WebSocket) for faster write-through confirmations.

Overview (mobile developer perspective)
When a user edits their profile on mobile, you can keep caches coherent using different strategies. Below I describe four options and trade-offs for a mobile-first product.

1) Client-side purge (on-write local invalidation)

• What: Immediately delete/update local cache after user saves; fetch fresh data on next read.
• Freshness: High for local view; remote may lag until next fetch.
• Latency: Very low perceived latency (instant UI update).
• Reliability: Works offline (stale remote until sync).
• Complexity: Low; easy to implement.

2) Write-through (synchronously update server + cache)

• What: Send update to server and update local cache only after successful server ack.
• Freshness: Strong (cache reflects confirmed server state).
• Latency: Higher write latency (wait for network). Can use optimistic UI to mask.
• Reliability: Depends on network; failures are surfaced immediately.
• Complexity: Moderate.

3) Write-behind with background sync (async commit + retry)

• What: Update local cache immediately, enqueue write to send in background (retry, exponential backoff).
• Freshness: Local UI fresh; server may be eventually consistent.
• Latency: Best UX (instant), server visibility delayed.
• Reliability: Good offline support; conflict resolution needed.
• Complexity: Higher (queueing, retries, conflict merge).

4) Server-driven push invalidation (push/notifications/WebSockets)

• What: Server pushes invalidation or updated profile to device(s) when change occurs elsewhere.
• Freshness: Very high across devices.
• Latency: Low for cross-device visibility.
• Reliability: Depends on push channel (APNs/FCM) and connectivity; may be delayed or dropped.
• Complexity: High (infrastructure, auth, handling intermittent connectivity).

Recommendation: combine approaches — use optimistic write-behind for fast local UX + client-side purge and background sync for offline resilience, and add server push for multi-device consistency where needed.

Clarifying assumptions

• App stores users, conversations, messages; offline reads/writes allowed per-device; server provides REST/gRPC with linearizable timestamps or causal metadata (optional).

Local data model (SQLite/Drift)

• users(id, name, metadata)
• conversations(id, title, participants, last_modified)
• messages(id, convo_id, sender_id, body, created_at, edited_at, local_status)
• tombstones(id, type, deleted_at)
• sync_queue(op_id, entity_type, entity_id, op_type, payload, created_at)

Sync metadata

• Per-record: last_modified_ts (server wall-clock), etag/version (server increment)
• Per-device: device_id, client_clock_skew, last_sync_token (a server token or vector)
• Optional: per-entity version vector for causal/CRDT-based merges

Conflict resolution policy

• Default: server-wins for structural metadata (membership), client-wins-with-merge for message bodies:
  • If both edit same message: merge heuristics (append edits + edited_at) or present UI to resolve.
  • For deletes vs edits: delete wins if delete_ts > edit_ts; otherwise resurrect with tombstone history.
• For stronger consistency: use OT or CRDT (RGA for message text).

Delta vs full sync

• Delta sync (preferred): use last_sync_token to fetch changed entities and tombstones. Pros: low bandwidth, fast. Cons: complexity, must store tokens.
• Full sync: simple, robust for rare offline clients. Pros: easy recovery. Cons: heavy data usage and slow.

Background sync triggers

• Connectivity change (Wi‑Fi/unmetered), app foreground, push notifications (silent), periodic background fetch (platform APIs), user actions (send/message).
• Throttle retries, exponential backoff, batch ops, and respect battery/data constraints.

Pros/cons of strategies

• Server-wins: simple, predictable, may lose client edits.
• Client-wins: preserves local work, risks overwriting remote authoritative data.
• Merge/Hybrid: best UX, moderate complexity.
• CRDT/OT: automatic conflict-free merges, highest complexity and storage/compute cost.

I would implement: local SQLite with a sync_queue and last_sync_token, delta sync via server tokens, hybrid conflict policy (merge + user-driven resolution), and background sync via silent push + connectivity events to balance UX and resource use.

Approach (brief)
Use a HashMap for O(1) key lookup and a doubly-linked list to track recency (head = most recent, tail = least). On get/put move node to head. Evict tail when capacity exceeded. For Android use Kotlin; make thread-safe with synchronized blocks or use ConcurrentHashMap + explicit locks.

Code (Kotlin)

class LruCache<K, V>(private val capacity: Int) {
    init { require(capacity > 0) { "capacity must be > 0" } }

    private data class Node<K, V>(var key: K, var value: V, var prev: Node<K, V>? = null, var next: Node<K, V>? = null)

    private val map = HashMap<K, Node<K, V>>(capacity)
    private var head: Node<K, V>? = null
    private var tail: Node<K, V>? = null
    private val lock = Any()

    fun get(key: K): V? = synchronized(lock) {
        val node = map[key] ?: return null
        moveToHead(node)
        return node.value
    }

    fun put(key: K, value: V) = synchronized(lock) {
        val node = map[key]
        if (node != null) {
            node.value = value
            moveToHead(node)
        } else {
            val newNode = Node(key, value)
            map[key] = newNode
            addToHead(newNode)
            if (map.size > capacity) {
                tail?.let { evict(it) }
            }
        }
    }

    private fun moveToHead(node: Node<K, V>) {
        if (node === head) return
        // detach
        node.prev?.next = node.next
        node.next?.prev = node.prev
        if (node === tail) tail = node.prev
        // attach at head
        node.prev = null
        node.next = head
        head?.prev = node
        head = node
        if (tail == null) tail = head
    }

    private fun addToHead(node: Node<K, V>) {
        node.next = head
        head?.prev = node
        head = node
        if (tail == null) tail = head
    }

    private fun evict(node: Node<K, V>) {
        map.remove(node.key)
        if (node.prev != null) node.prev!!.next = null else head = null
        tail = node.prev
        // help GC
        node.prev = null
        node.next = null
    }
}

Why O(1)

• HashMap provides O(1) lookup by key.
• Doubly-linked list allows O(1) insert, remove, and move operations by pointer updates. Combined, get and put perform a constant number of map and pointer operations.

Thread-safety & Android notes

• Synchronized(lock) ensures correctness across threads; for higher concurrency use ReadWriteLock or ConcurrentHashMap with a custom concurrent list. On Android prefer keeping cache accesses off the UI thread or use main-safe wrappers.

Framework / Goal
Measure client- and server-side cache effectiveness to reduce tail latency, save network bytes, and preserve battery. Track actionable metrics and use them to drive cache TTLs, sizes, and eviction policies.

Key metrics to collect

• Hit rate = hits / (hits + misses) — per endpoint, per device class, per network type.
• Miss rate = 1 - hit rate.
• Eviction rate = evictions / total cache entries — shows pressure.
• Tail latency (p95/p99) for requests served from cache vs origin.
• Network bytes saved = bytes avoided by serving cache.
• Freshness/staleness distribution = age of item at hit time.
• Error-on-miss (additional retries/errors) and battery impact proxy (time-to-first-byte on cellular).

How to collect & aggregate

• Client: instrument cache layer to emit lightweight events: {event_type, key_hash, size, age, network_type, device_tier, timestamp}. Use local batching and upload on charging/Wi‑Fi or when app active.
• Server: log cache lookup result, latency, bytes, and key metadata; aggregate in analytics pipeline (e.g., Kafka → OLAP).
• Aggregate by time window and dimensions (endpoint, network, device). Compute rolling p95/p99 and weighted hit rates.

Sampling & privacy

• Hash keys (HMAC with app secret) instead of raw keys; avoid PII.
• Sample a small percentage (e.g., 1–5%) of events for full detail; always send counters for totals and hits to preserve accuracy.
• Throttle on battery saver; respect platform privacy rules and user consent.

Drive config changes

• If global hit rate low but per-endpoint skewed, increase TTL or cache size for high-miss endpoints.
• Eviction rate high → increase memory/disk or tighten admission policy (LRU→LFU for hot items).
• If cached hits have stale age > allowed → shorten TTL or implement background refresh.
• Use A/B rollout: apply config change to a slice, compare hit rate, tail latency, and bytes saved before full rollout.

Implementation note: keep client telemetry tiny, use hashed keys and batch uploads, and run periodic automated analyses that recommend TTL/size adjustments.