Out-of-memory Flashcards
Disk
traditional storage medium
* rotating magnetic disk
* large (random) seek times
* can overwrite in place
* cheap but slow
Solid State Drives (NAND Flash)
based on semiconductors (no moving parts), usually NAND gates
* nowadays directly attached to PCIe (M.2/U.2) through NVMe interface
* an SSD consists of many flash chips
* higher bandwidth than disk and much faster random access
NAND Flash Organization
- data is stored on pages (e.g., 4KB or 16KB)
- pages are combined to blocks (e.g., 2MB)
- not possible to overwrite a page, must erase the full block first
Zoned NameSpaces (ZNS)
- Zoned Names expose out-of-place nature of device
- device is split into zones, each zone can only be written to sequentially
- requires application to implement garage collection
- can reduce write amplification
Persistent Memory Failure Atomicity
- PMem stores are buffered in the CPU caches
- programs cannot prevent eviction
- but can force eviction using explicit cache write-back or flush instructions
FP-Tree
- persistent B-tree optimized for PMem
- inner nodes have conventional layout and are stored in DRAM
- on crash inner nodes are recovered from leaf nodes
- leaves are unsorted
- “fingerprints”: 1-byte hash at the beginning of the node speeds up search
Btree
- the standard out-of-memory data structure is the B-tree
- large fanout minimizes number of disk accesses
- usually combined with a buffer manager (i.e., page cache)
- fixed-size nodes work well with SSD/disk and cache
Log-Structured Merge Trees (LSM)
- LSM trees can improve write amplification (in particular for random-write
workloads) at the cost of read amplification - basic idea:
- out-of-place writes
- periodic merges of sorted runs
Important Optimizations
- in-memory Bloom filter for each run:
- only need to access run if Bloom filter has true or false positive
- depending on desired false positive rate, takes 4-16 bits per key
- partitioning: split runs into independent ranges
- reduces peak memory consumption
- makes large merges less invasive
- may reduce write amplification for non-random access patterns
- works for both merging policies
Why do we need cache coherency protocol?
to provide the illusion of a single main memory
what cache coherency protocol did we discuss in the lecture?
what does this acronym stand for?
MESI protocol, which has the following states:
* Modified: cache line is only in current cache and has been modified
* Exclusive: cache line is only in current cache and has not been modified
* Shared: cache line is in multiple caches
* Invalid: cache line is unused
what guarantees does C++ give you when a data race occurs?
sequencial consistency
- what are the default ordering guarantees for std::atomic
non-atomic loads and stores are not reordered around atomics
- how many bytes can be atomically handled on x86-64?
atomic operations only work on 1, 2, 4, or 8 byte data that is aligned
- what memory ordering does x86-64 use?
Total Store Order
- what locking algorithms did we discuss in the lecture?
Coarse-Grained Locking, Lock Coupling,Optimistic, Optimistic Lock Coupling, Read-Optimized Write Exclusion, Lock-free list
what different kinds of non-blocking algorithms are there?
wait-free: every operation is guaranteed to succeed (in a constant number of
steps)
* lock-free: overall progress is guaranteed (some operations succeed, while
others may not finish)
* obstruction-free: progress is only guaranteed if there is no interference from
other threads
what does ROWEX stand for? what does it guarantee?
Read-Optimized Write Exclusion
consist ist wait free,
insert/remove traverses list only once
- why do we need specialized memory reclamation techniques?
because when a node is deleted from lock free data structure, some readers can still access it
- what memory reclamation techniques did we discuss?
Reference Counting, Epoch-Based Memory Reclamation, Traditional Hazard Pointers, Shared Concurrent Counters
- what is the ABA problem?
a compare-and-swap on a pointer structure may succeed even though the
pointer has been changed in the mean time (from A to B back to A)
- what additional data does optimistic lock coupling require?
update counter
- why is the B-Tree more difficult to synchronize than the ART?
for insert/delete there are two cases:
1. single-node change (common case)
2. structure modification operation (during split/merge: infrequent)
how can we synchronize structure modification operations on a B-Tree?
Optimistic Lock Coupling
- with OLC, what issues might a reader encounter during reads in a node?
- infinite loops: one has to ensure that the intra-node (binary) search terminates
in the presence of concurrent modifications
what 2 key ideas make the Bw-Tree possible?
Key Idea #1: Deltas
→ No updates in place
→ Reduces cache invalidation.
Key Idea #2: Mapping Table
→ Allows for CAS of physical locations of pages.
why do we need sentinel nodes in the split ordered list?
deleting a node using CAS pointed to from a bucket does not work
(because it is also being pointed to from the list)
* solution: for every split bucket, insert a special sentinel node into the list
- what is the main challenge in achieving crash-persistence on PMem?
The main challenge in achieving crash-persistence on Persistent Memory (PMem) is ensuring that data is durably stored on the PMem, even in the event of power loss or system crash
- what is a usual maximum fill factor for a (open/chaining) hash table?
open: 70-80%
chaining: 90-95%
how many cache misses can you expect in a large (open/chaining) hash table
for one lookup?
chaining has at least two dependent
memory accesses (often cache
misses) for hit
what effect causes exponential probe sequence length growth in open addressing?
clustering effect
- what can cause a displacement in cuckoo hashing to fail?
cycle while rearrangement
- what is the average / worst-case performance of open addressing / chaining?
O(1), O(n)
why is a B-Tree usually faster than a binary tree?
because it has n nodes and n+1 children, which make the tree height smaller and disk access faster
- how deep is a B-Tree with node size b and N entries?
logb(N/b)
describe a use-case where chaining might be faster than open addressing
when data is sorted
