Cache, external memory ve streaming

RAM modelinde O(n) olan iki yapı cache miss yüzünden farklı hızdadır. Array traversal locality sağlar; pointer chasing düzensiz erişir. Disk modelinde block transfer sayısı önemlidir. External merge sort belleğe sığan run'lar oluşturup çok yollu birleştirir; B-tree fanout I/O azaltır. Cache-oblivious tasarım belirli block size bilmeden locality hedefler.

LRU cache, hash map ve doubly linked list ile expected O(1) lookup/update sağlar. OrderedDict aşağıda bu sözleşmenin küçük örneğidir. Cache correctness; eviction, TTL, invalidation, stale data ve concurrency ile birlikte düşünülür. Cache stampede için single-flight veya jitter kullanılabilir; bunlar her tutarlılık modeline aynı uygulanmaz.

LSM tree ardışık write ve compaction kullanır; write amplification, read amplification ve space amplification takası vardır. Streaming'de bütün girdiyi tutmadan sonuç üretirsin. Reservoir sampling sabit k örneği düzgün seçer; online algorithms geleceği bilmez. Ölçümde warm/cold cache, p95 latency, allocation ve adversarial dağılımlar ayrı raporlanır.

from collections import OrderedDict
cache=OrderedDict(A=1,B=2)
cache.move_to_end("A"); cache["C"]=3
if len(cache)>2:cache.popitem(last=False)
assert list(cache)==["A","C"]