Concurrency & Asynchronous Performance Questions

Requirements & constraints:

• Functional: insert(key), remove(key), contains(key), iterate-in-order (weakly consistent), snapshot views (point-in-time).
• Non-functional: high concurrency, low-latency reads, reasonable memory, GC or manual reclamation environment, scalable to millions of keys.

High-level options

• Concurrent skip list (e.g., Java ConcurrentSkipListMap): lock-free/optimistic pointer-based with O(log n) expected ops, excellent for read-heavy workloads and natural in-order iteration.
• Lock-coupling B-tree (concurrent B+ tree): node-level locks, better cache locality and range-scan throughput for large datasets, higher write amplification.

Design proposal

1. Core DS: a layered approach with a concurrent skip list as primary (simplicity + builtin in many runtimes) or a concurrent B+tree for very large on-heap datasets requiring compact nodes.
2. Concurrency strategy:
   • Skip list: use lock-free / optimistic algorithms (marked pointers, CAS on next pointers). Readers (contains, iterate) are wait-free or lock-free; writers use CAS to splice nodes.
   • B+tree: fine-grained exclusive locks per node with lock-coupling for structural changes; readers acquire shared locks where supported or use optimistic reads validated by node version counters.
3. Iteration semantics:
   • Weakly consistent iterator implemented by traversing next pointers without global locks; skip-list’s lock-free traversal tolerates concurrent inserts/removes and may reflect some but not all concurrent updates.
4. Snapshot views:
   • Lightweight snapshot: increment global epoch and capture head pointer + versioning metadata; iterate following nodes that have version <= snapshot epoch.
   • Strong snapshot: copy-on-write persistent layer (e.g., path-copying B-tree) or produce a copy-on-write snapshot structure for long-lived consistent views.
5. Memory reclamation:
   • In GC languages: rely on GC but use marked/retired flags to avoid ABA.
   • In manual memory: epoch-based reclamation or hazard pointers to prevent freeing nodes still visible to iterators/writers; combine with deferred free lists per thread.
6. Trade-offs:
   • Lock-free skip list: excellent read throughput and low latency; writers contend on CAS hotspots and can suffer retries under heavy writes.
   • Lock-coupling B-tree: better write locality, fewer pointer overheads, better range-scan throughput; more complex locking and possible writer-induced blocking for readers.
   • Snapshots: cheap epochs provide weak consistent point-in-time; full persistent snapshots cost memory and CPU.
7. Recommendations:
   • Default: concurrent skip list with hazard-pointer/epoch reclamation; provide two snapshot APIs: cheap epoch snapshot (weakly consistent) and optional full copy for strict isolation.
   • For very large data or heavy range scans: use node-sized B+tree with lock-coupling and versioned reads.
8. Observability & testing:
   • Stress tests with synthetic workloads (read/write ratios), linearizability tests for single-key ops, and long-running iterator/snapshot correctness tests.
9. Metrics to monitor: op latency tail, CAS failure rates, GC/pause times (if GCed), memory reclaimed backlog, snapshot creation time and memory.

This design balances simple, high-performance reads (lock-free skip list) with options for stronger snapshots and alternative B+tree implementation when range throughput or memory density requirements dominate.

Requirements and constraints:

• Sort very large arrays entirely in RAM on a multi‑core server (N cores, large L3 caches).
• Low latency and high throughput for many concurrent requests.
• Stable resource usage, good worst‑case behavior, minimal synchronization overhead.
• Memory footprint should remain reasonable; prefer in‑place or low extra memory.

High‑level options compared: Parallel Quicksort (task-parallel with partitioning), Sample Sort (distributed bucket/sample‑based), Parallel Merge Sort (divide-and-conquer merging with local sorts).

Comparison (load balancing, cache locality, synchronization, scalability)

1. Parallel Quicksort

• Load balancing: Pivot quality drives balance. Random pivots or median-of-medians reduce imbalance, but worst-case skew can create hot threads. Work-stealing mitigates imbalance by scheduling smaller partitions dynamically.
• Cache locality: Good for local partitions — in-place partitioning accesses contiguous regions, benefiting caches. However, recursive partitioning leads to many small working sets that may thrash higher-level caches if not tuned.
• Synchronization costs: Low per-partition (task queue + work-stealing). Partition phase requires few atomic ops; minimal global barriers.
• Scalability: Good for moderate cores with careful pivoting and work-stealing, but suffers if pivoting repeatedly creates very uneven partitions or deep recursion causing thread starvation.

2. Sample Sort

• Load balancing: Excellent when samples are representative — choose p*log p samples and pick splitters so buckets are balanced with high probability. Provides near-uniform work distribution across cores.
• Cache locality: Bucketing requires scattering elements to bucket buffers — can hurt locality unless done in block/batched moves and local buffers per thread. After redistribution each core sorts contiguous bucket, restoring good locality.
• Synchronization costs: Redistribution needs coordination to compute bucket offsets (prefix sums) — global synchronization but limited (one or few barrier points). After redistribution, minimal sync.
• Scalability: Very good for many cores and NUMA domains if splitters account for per-node differences and redistribution is optimized. Extra memory for buckets and sample arrays required.

3. Parallel Merge Sort

• Load balancing: Straightforward: divide into N chunks, sort locally, then perform pairwise merges. Balancing relies on initial chunk sizes; cost of merges depends on data distribution (equal sizes simpler).
• Cache locality: Local sorts have good locality. Merging streams accesses sequential memory, good for caches but merging large streams creates streaming patterns that may not reuse cache lines.
• Synchronization costs: Merging stages often require global barrier at each merge level or coordinated merging; can be done with parallel multiway merge algorithms to reduce barriers but complexity increases.
• Scalability: Good and predictable; overhead grows with number of merge levels (log N). For very large core counts, merge coordination and memory traffic (reading/writing full arrays multiple times) can limit scalability.

Recommendation for production in‑memory sort service
Choose a hybrid Sample Sort tuned for the platform, with these justifications:

• Predictable load balancing: Sampling+splitters yields near-uniform bucket sizes, avoiding worst-case imbalance common in quicksort.
• High scalability: One redistribution step then fully parallel local sorts—scales to many cores and multiple NUMA nodes when splitter selection is NUMA-aware.
• Controlled synchronization: Only a few global steps (sampling, prefix-sum for offsets); rest is embarrassingly parallel.
• Cache & memory optimizations: Implement per-thread local buffers to batch writes into destination buckets, do in-place local sorts (e.g., introsort) on buckets for cache friendliness, and minimize memory copies by writing buckets into preallocated contiguous ranges. Use block partitioning and radix-based pre-bucketing for key types where applicable.
• Fault/worst-case handling: If sampling indicates skewed distribution, fall back to recursive sample refinement or localized parallel quicksort for the heavy bucket.
• Engineering practicality: Sample sort maps well to production needs: stable throughput, predictable resource usage, easier to tune for NUMA and SIMD optimizations. Provide metrics and adaptive tuning: sample size, bucket count, fallback thresholds.

Operational considerations

• Make bucket count ~ k * core_count (k between 1–4) to improve granularity.
• Use work‑stealing for local-sort tasks inside large buckets.
• Pin threads per NUMA node; select splitters per node or perform hierarchical sample sort to reduce cross‑node traffic.
• Instrument and autotune sample size, buffer sizes, and bucket strategy in production.

This hybrid sample-sort with pragmatic fallbacks gives the best combination of load balance, scalability, moderate synchronization, and cache-aware performance for a production in‑memory sorting service.

GOAL:
Provide a thread-safe, performant LRU cache for high concurrency on mobile.

DESIGN OPTIONS:

1. ConcurrentHashMap + Doubly-linked LRU list with locks

• Use ConcurrentHashMap for storage and maintain an LRU list protected by a small lock (or ReentrantLock). On access, update list under lock.
• Pros: simple, good concurrent read; Cons: LRU updates still bottlenecked by single lock under extreme write-heavy workload.

2. Segmented (striped) cache

• Partition keys into N stripes (shards). Each shard has its own HashMap + LRU list and lock. Map key → shard by hash.
• Pros: reduces contention, preserves near-LRU per-shard; Cons: global LRU is approximate.

3. Lock-free read path + write serialization

• Use ConcurrentLinkedHashMap pattern—atomic references for nodes and CAS updates (complex to implement). Prefer libraries if available.

MEMORY PRESSURE HANDLING:

• Maintain cache size by byte/entry count; evict LRU entries on insert.
• Hook into OS memory pressure callbacks to aggressively trim cache.
• Use soft/weak references carefully (Android GC can reclaim unexpectedly).

TESTING APPROACH:

• Unit tests for correctness (put/get/evict) and invariants.
• Concurrency stress tests using ThreadPool executor that simulates heavy concurrent gets/puts and verifies no corruption and total size constraints.
• Fuzz tests to randomize operations and compare with single-threaded reference LRU.
• Use race detectors / thread sanitizers in debug builds where possible.

RECOMMENDATION:

• Use segmented cache (e.g., 16 shards) with ConcurrentHashMap per shard and a simple lock-protected LRU list per shard. This balances performance and implementation complexity while giving predictable evictions and low contention.

ADDITIONAL:

• Consider using an existing tested library (Caffeine for Java) adapted for mobile if acceptable. Instrument metrics for hit/miss rate and lock contention.