# Fuzzy Logs

## Claims
- linear scaling
- weak consistency (is this a "claim")
- partition tolerance

## Problems w/ total order:
- expensive
  - passing mention that CORFU doesn't scale past 20 servers in two adjacent racks
- impossible (consistency w/ partitions)
  
![](fuzzyLog.png)

**color:** updates to a single shard, made of multiple chains

**chains:** totally ordered set of updates from a single region. Chains connected by causal dependencies.

Each server has:
- latest copy of local chains
- stale prefixes of other chains

**node append:**
- node added to local chain of specified color
- w/ outgoing cross-links to *last node seen by client of each remote chain* (same color)
- can be atomically appended to multiple (local?) colors, **transaction across shards**

"toggle between strong and weak consistency during partitions by switching regions"

linear scaling from:
- storing each color on a different replica set -> appends to single color in one phase
- serializable isolation for multi-color appends
- failure atomicity
- lazy cross-region sync


![](fuzzyAPI.png)
- `new_instance`: adding color to local
- `sync`: plays all local nodes not seen by app's previous sync, ordered by chain and cross-edges (causal)
- `append`: added to end of local totally-ordered chain, cross-edges to tail of each other chain (edges from a node define a snapshot)
- `trim`: GC nodes prior to snapshot

![](fuzzyEvolution.png)

----
## Implementation
- each color a single partition
- each partition replicated using *chain-replication*
- battery backed-up ram for servers
- local append to single color one phase (send it to the chain replication)
- local append to multiple colors requires two phases (Skeen's)
  - logical clocks
  - *phase 1:* send out multicast w/ proposed timestamp
  - replies return local timestamps
  - *phase 2:* send msg again w/ max of local or returned timestamps
  - order at all destinations with new timestamp
![](fuzzySkeen.png)
---

*Any protocol that provides a total order consistent with a
 linearizable order (i.e, if an update B starts in real time after
 another update A completes, then B occurs after A in the total order)
 is subject to unavailability during network partitions.*  

Is this true?


## Apps

- LogMap
  - single region, single color
  - `get` waits until a sync that started after sync issue, then accesses local state
  - `put` appends to log, then waits for `sync` to show it applied before returning
- ShardedMap
  - single region, *multiple* color
  - says linear scaling with linearizable put/get ops
  - why?  scaling because can scale colors with num servers
- AtomicLog
  - multiple colors, which are serializable (because underlying ops are serializable)
- TxMap
  - wants *strict serializability* (externalizable)
  - speculative intention *commit* appends
  - servers playing the intention node append *yes/no* for a specific color based on
    presence of conflicting ops im log between the original appends and the speculative commits
  - other servers only apply transaction if they see a *yes* for each color
- CRDTMap
  - CRDT: *conflict-free-replicated-data-type*
  - single color, async replication of remote chains
  - **convergence** through
- CAPMap
  - consistency
    - strong when to partition
    - causal otherwise
  - routes put through proxy in a *primary* region, if avail.
- RedBlueMap:
  - red ops routed through primary
  - blue ops not


## Multiple-color append
- to local chains
- operations within a single region are serializable
- appends in some serial order
  - linearizable if to a single color
  - not necessarily externalizable if to multiple colors

Difference between LogMap and ShardedMap?


Regions vs machines?

Guarantees of durability?
- when is an update "committed"?


## Comments, Questions
- (patrick) colors maybe difficult to  use
