Out-of-memory

Question 1

Disk

Answer 1

traditional storage medium
* rotating magnetic disk
* large (random) seek times
* can overwrite in place
* cheap but slow

Question 2

Solid State Drives (NAND Flash)

Answer 2

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

Question 3

NAND Flash Organization

Answer 3

• 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

Question 4

Zoned NameSpaces (ZNS)

Answer 4

• 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

Question 5

Persistent Memory Failure Atomicity

Answer 5

• PMem stores are buffered in the CPU caches
• programs cannot prevent eviction
• but can force eviction using explicit cache write-back or flush instructions

Question 6

FP-Tree

Answer 6

• 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

Question 7

Btree

Answer 7

• 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

Question 8

Log-Structured Merge Trees (LSM)

Answer 8

• 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

Question 9

Important Optimizations

Answer 9

• 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

Question 10

Why do we need cache coherency protocol?

Answer 10

to provide the illusion of a single main memory

Question 11

what cache coherency protocol did we discuss in the lecture?
what does this acronym stand for?

Answer 11

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

Question 12

what guarantees does C++ give you when a data race occurs?

Answer 12

sequencial consistency

Question 13

• what are the default ordering guarantees for std::atomic

Answer 13

non-atomic loads and stores are not reordered around atomics

Question 14

• how many bytes can be atomically handled on x86-64?

Answer 14

atomic operations only work on 1, 2, 4, or 8 byte data that is aligned

Question 15

• what memory ordering does x86-64 use?

Answer 15

Total Store Order

Question 16

• what locking algorithms did we discuss in the lecture?

Answer 16

Coarse-Grained Locking, Lock Coupling,Optimistic, Optimistic Lock Coupling, Read-Optimized Write Exclusion, Lock-free list

Question 17

what different kinds of non-blocking algorithms are there?

Answer 17

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

Question 18

what does ROWEX stand for? what does it guarantee?

Answer 18

Read-Optimized Write Exclusion
consist ist wait free,
insert/remove traverses list only once

Question 19

• why do we need specialized memory reclamation techniques?

Answer 19

because when a node is deleted from lock free data structure, some readers can still access it

Question 20

• what memory reclamation techniques did we discuss?

Answer 20

Reference Counting, Epoch-Based Memory Reclamation, Traditional Hazard Pointers, Shared Concurrent Counters

Question 21

• what is the ABA problem?

Answer 21

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)

Question 22

• what additional data does optimistic lock coupling require?

Answer 22

update counter

Question 23

• why is the B-Tree more difficult to synchronize than the ART?

Answer 23

for insert/delete there are two cases:
1. single-node change (common case)
2. structure modification operation (during split/merge: infrequent)

Question 24

how can we synchronize structure modification operations on a B-Tree?

Answer 24

Optimistic Lock Coupling

Question 25

• with OLC, what issues might a reader encounter during reads in a node?

Answer 25

• infinite loops: one has to ensure that the intra-node (binary) search terminates
  in the presence of concurrent modifications

Question 26

what 2 key ideas make the Bw-Tree possible?

Answer 26

Key Idea #1: Deltas
→ No updates in place
→ Reduces cache invalidation.
Key Idea #2: Mapping Table
→ Allows for CAS of physical locations of pages.

Question 27

why do we need sentinel nodes in the split ordered list?

Answer 27

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

Question 28

• what is the main challenge in achieving crash-persistence on PMem?

Answer 28

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

Question 29

• what is a usual maximum fill factor for a (open/chaining) hash table?

Answer 29

open: 70-80%
chaining: 90-95%

Question 30

how many cache misses can you expect in a large (open/chaining) hash table
for one lookup?

Answer 30

chaining has at least two dependent
memory accesses (often cache
misses) for hit

Question 31

what effect causes exponential probe sequence length growth in open addressing?

Answer 31

clustering effect

Question 32

• what can cause a displacement in cuckoo hashing to fail?

Answer 32

cycle while rearrangement

Question 33

• what is the average / worst-case performance of open addressing / chaining?

Answer 33

O(1), O(n)

Question 34

why is a B-Tree usually faster than a binary tree?

Answer 34

because it has n nodes and n+1 children, which make the tree height smaller and disk access faster

Question 35

• how deep is a B-Tree with node size b and N entries?

Answer 35

logb(N/b)

Question 36

describe a use-case where chaining might be faster than open addressing

Answer 36

when data is sorted