Transactions

WNFS is transactional, lock-free, and concurrent. Updates are made atomically, and bundling multiple actions together is both allowed and encouraged. This is achieved by maintaining a local fork of the state, and only persisting it to the network (an irreversible comittment) when it is certain of its state. Bundling multiple states has many advantages, including lower synchronization overhead.
Mechanics
Out-of-Order Execution
To achieve concurrent speedups, execution of multiple actions are performed concurrently on forks of the current finalized head, and then linearized and merged (i.e. the well-used fork/join model). This is less efficient in serial, but has massive improvements in wall-clock time when multiple threads are available (as is common in IPFS).
This leverages two facts:
1.
The heavy operation is adding the leaves (files) to IPFS
2.
Concurrent operations are order-independent, and can be rearranged
Linearization
There are many ways to linearize concurrent updates, all different but equally valid. In the following image, the three sequences on the left are all valid linear orderings for the concurrent partial-order on the right:
Source: https://noti.st/expede/6IcxBY/tryranny-of-structurelessness#stLLlcf
Singleton FIFO Pipeline
We believe that the best tradeoff between raw execution speed and implementation complexity is to respect the order that the user pushes tasks into an optimistic FIFO queue. 
1
data Pending = Pending
2
  { forkedFrom :: CID
3
  , update     :: WNFS -> WNFS
4
  , wip        :: Promise WNFS
5
  }
6
​
7
data Linearizer = Linearizer
8
  { pending :: Map CID (Array Pending)
9
  , openTX  :: WNFS -> WNFS
10
  , paused  :: Bool
11
  , local   :: WNFS
12
  , remote  :: CID
13
  }
Copied!
New jobs are pushed into a promise at the end of the queue. Work begins immediately, forked from the current finalized HEAD. Jobs at the front of the queue await the promise.
This uses the compare-and-set strategy. WNFS avoids the ABA problem thanks to Merkelization: instead of comparing values (equality), it checks the root CID (identity).
When the front of the queue completes, it checks the finalized root CID of the proposed WNFS's previous root CID (i.e. "has anything changed under me while I was working?"). If the CIDs match, then this is the next finalized WNFS: place the WNFS in local, and (post-)compose the transaction's update with the openTX.
If they're different:
Restart the task
Push the restarted task to the back of the queue
Merge the first completed promise forked from the current local CID
Continue as normal
Further Optimization
If this proves to be a bottleneck, there are a number of optimizations that can be implemented. One such example is a work-stealing queue which applies deltas as their promises complete. 
This seems an unlikely bottleneck as it only applies when there are many concurrent updates being blocked by a large transaction at the head of the FIFO queue, which is an edge case at best.
Remote Synchronization
Push to Remote
When broadcasting the the local version, do the following:
Pause the transaction queue from merging (pause merging to local)
On receiving success response:
1.
Set the remote cache to the latest local root CID
2.
Set the openTX to the identity function
3.
Start the transaction queue (unpause local)
Pull from Remote
If WNFS is alerted to a new remote HEAD, it does the following:
1.
Pause the transaction queue from merging (pause merging to local)
2.
Set local and remote to the incoming update
3.
Re-run openTX on top of the new local (blocking, as if at the front of the queue)
4.
Resume merging (unpause local)
The merge operation is the same as followed during normal head synchronization.
JS API
What follows is a sketch of a JavaScript API for transactions. Note that these may be automatically retried, so avoiding side effects is strongly suggested (though not strictly required). It can be useful to log the number of retries to the console for debugging, or show some feedback to the user, for example.
atomic
atomic is the most flexible, yet lowest-level transactional method. 
It can be used to glue together multiple nested transactions, and provides all other methods are merely special cases of this method.
1
  /////////////////
2
 // Rough Types //
3
/////////////////
4
​
5
class Transaction = {
6
  id: string;
7
  
8
  iteration: number;
9
  maxRetries: number;
10
  
11
  abort: (msg: string) => void;
12
  failOn: (predicate: any => boolean, msg: string) => void;
13
}
14
​
15
type txConfig = {retries: number} | {rootTx: transaction}
16
​
17
type atomic = <value>(
18
    fn: {fs: WNFS, tx: transaction} => value,
19
    txConfig?: txConfig
20
  ): Promise<{tx: transaction, value: value}>
21
​
22
  ////////////////////
23
 // Example Sketch //
24
////////////////////
25
​
26
const me = "expede"
27
const photoData = ...
28
const nestedTx = async () => wnfs.atomic({fs, tx} => {
29
  // more transactional actions
30
})
31
​
32
await wnfs.atomic({fs, tx} => {
33
  fs.create(["photos", "vacation.png"], {
34
    metadata: {
35
      takenBy: me,
36
      latitude: 25.025885,
37
      longitude: -78.035889
38
    },
39
    data: photoData
40
  })
41
  
42
  fs.rm(["public", "photos", "holiday.gif"])
43
  
44
  // Nested transaction
45
  await nestedTx().bind(this) // or something
46
  
47
  fs.modify(["public", "documents"], {directory, metadata: oldMeta, tx} => {
48
    directory.contents.find()
49
​
50
    return {
51
      dir: [...directory, newFile],
52
      metadata: {...oldMeta, lastTouchedBy: me}
53
    }
54
  })
55
}).maxRetries(0)
Copied!
create
1
// The path will be the 
2
type create(path: path, data: Uint8Array, meta?: metadata): Promise<>
3
​
4
// Example
5
​
6
wnfs.create(["private", "Documents"], data,)
Copied!
modify
1
wnfs.modify(["favourites", "favs.yaml"], data => {
2
  if (data.length > 100) throw new Error("Data too long")
3
  const newData = data + " new stuff"
4
  
5
  if (newData.length < 10) throw new Error("String too short")
6
  return newData.toUpperCase() 
7
})
Copied!
remove
1
wnfs.remove(["favourites", "favs.yaml"])
Copied!
​

Synchronization

Next - File System

Distribution

Last modified 4mo ago

Export as PDF

Copy link

Contents

Mechanics

Out-of-Order Execution

Linearization

Remote Synchronization