# WAFL
All about freespace reclamation


WAFL
- Snapshots
    - data protection, replication, recovery
    - compression, de-duplication result in relatively more metadata
- updates free-space metadata (activemaps) on CP, rather than just making notation for future GC
- client ops recorded to non-volatile memory before responding


Definitions
- subblock points to a tree
- file is a tree
- activemap per tree
  - bitmap of block allocations,
     - consumes blocks
- consistency point (CP)
  - flushes all dirty buffers, inodes (hundreds of thousands) to disk
     - includes activemap
     - could make CP writes expensive
	      - want low cost, and smoothness
  - writes superblock
  - freed block can't be re-used until next CP
  
![COW](waflCOW.png)
  
activemap:
- *b<sub>j</sub>* `covers` block *b<sub>i</sub>* if bit *a<sub>i</sub>* in block *b<sub>j</sub>*
- activemap chains:
  - longest list of activemap blocks where *(i+1)<sup>th</sup>* block covers *i<sup>th</sup>* 
- (long chains are not easily formed because WAFL often allocates blocks that are colocated in the activemap)

![wafl activemap chains](waflChain.png)

chains broken:
- prefetch entire chain ???
- preemptively break chains by dirtying "first" block, future CP's break
- postpone free block by moving to *overflow file*  (append log)
  - "activemap chain of *n* elements gets broken down in at most *n* consecutive CPs"    ???


file deletion
- move file to hidden namespace
- incrementally delete blocks
- *aged files* are those written many times resulting in random allocation


the point of this paper: delete logging


![TLog](tlog.png)

TLog is binary tree
- insertions could cause the tree to rebalance
    - unpredictable costss

BFLog

accumulates delete-logged blocks
- appends to active log  (using tree again)
- inactive log sorted into sorted log
- sorted log "punched out" incrementally

append of each new block results in:
- one block being sorted and/or
- one block being merge-sorted and/or
- one block being punched out

Much more consisteent behavior.

