How to make any immutable data structure distributed

In this post we'll build our own distributed data structure from first principles. The version developed here is a little simpler than theSeqused in the "real" version of the library. We'll get to the realSeqin Part 5 of this article.

First, let's look at a simple in-memory tree data structure and understand how it can be modified to represent data spread across multiple nodes. Here's the in-memory version:

structural type SimpleTree a

structural type SimpleTree a
  = One a
  | Empty
  | Two (SimpleTree a) (SimpleTree a)

ASimpleTreeis eitherSimpleTree.Empty,a leaf:SimpleTree.One,or a branch:SimpleTree.Two.All the leaves and subtrees in aSimpleTreeare references to values which are in local memory on the same machine. If instead we want it to contain references to values that may exist at another location, we can write the following instead:

structural type src.Tree a

structural type src.Tree a
  = Tree.Two
      (distributed.Value (src.Tree a))
      (distributed.Value (src.Tree a))
  | Empty
  | Tree.One (distributed.Value a)

All we've done here is wrap each branch and leaf of the tree in a data type,distributed.Value,which represents alazyvalue at a possibly remote location.

With this simple type definition, we can now implement functions like a distributedmap,reduce,and so on without needing to write any networking or serializationcode.

Let's try it for oursrc.Tree.This will be instructive!

stub.Tree.map : (a ->{Remote} b) -> src.Tree a ->{Remote} src.Tree b

stub.Tree.map : (a ->{Remote} b) -> src.Tree a ->{Remote} src.Tree b
stub.Tree.map f = cases
  src.Tree.Empty -> src.Tree.Empty
  Tree.One valueA -> todo "🧐 hmmm, apply f to Value"
  Tree.Two leftValue rightValue ->
    todo "something recursive goes here 🤨"

We know we'll need to pattern match on the data constructors ofsrc.Treeand perform a recursive call of some kind, but now that the leaf and branch are both wrapped indistributed.Value,what should we do? There are two ways to do this that typecheck.

The first is not what quite what we want but it's instructive nonetheless. It makes ample use ofValue.get : distributed.Value a ->{Remote} ato force the lazydistributed.ValueandValue.pure : a -> distributed.Value afor creating a remote value from an in-memory value:

eager.Tree.map : (a ->{Remote} b) -> src.Tree a ->{Remote} src.Tree b

eager.Tree.map : (a ->{Remote} b) -> src.Tree a ->{Remote} src.Tree b
eager.Tree.map f = cases
  src.Tree.Empty -> src.Tree.Empty
  Tree.One valueA -> Tree.One (Value.pure (f (Value.get valueA)))
  Tree.Two leftValue rightValue ->
    use Value get pure
    use eager.Tree map
    Tree.Two
      (pure (map f (get leftValue))) (pure (map f (get rightValue)))

To see why this isn't what we want, let's look at the documentation ofValue.getandValue.pure:

Value.get

Obtain theadenoted by thisdistributed.Value.

A few properties:

• Value.get (Value.pure a) Universal.== a
• Value.get (Value.at loc a) Universal.== a
• f (Value.get v) Universal.== Value.get (Value.map f v)

Value.pure

Create an in-memorydistributed.Value.

Satisfies the property:Value.get (Value.pure a) Universal.== a

We'resummoningthe value from a potentially remote location withValue.get,and thenValue.purecreates a value in memory at the location where it's called. Our implementation ofeager.Tree.mapwill thus end up sending the entire tree to the original caller of the function, applying the function there, and storing the resulting tree in memory at that location. That's no good--presumably the whole reason we're using a distributed data structure is the data is too big to fit in memory on a single machine.

The version ofmapwe want will do its work lazily, when the resultingsrc.Treeis forced, and it will do the mapping in parallel at the locations where the data lives rather shipping everything to thecaller.

A good rule of thumb when implementing functions likeTree.mapis tonever callValue.get.Instead we will useValue.mapto lazily apply a functionat the location where the remote value lives.

src.Tree.map : (a ->{Remote} b) -> src.Tree a -> src.Tree b

src.Tree.map : (a ->{Remote} b) -> src.Tree a -> src.Tree b
src.Tree.map f = cases
  src.Tree.Empty -> src.Tree.Empty
  Tree.One a     -> Tree.One (Value.map f a)
  Tree.Two l r   ->
    use src Tree.map
    l' = Value.map (Tree.map f) l
    r' = Value.map (Tree.map f) r
    Tree.Two l' r'

While you can perhaps see how this code typechecks, what this code does is a bit brain-bending. First, because oursrc.Tree.mapfunction does not callValue.get,src.Tree.mapis just the blueprint for the data transformation, not the transformed data itself. Not until the tree is evaluated (by say, thereducefunction we'll cover in Part 3) does any mapping actually happen. This laziness gives us fusion

Morever, because we are usingValue.map,the function will be applied at the location where the data lives, rather than shipping the entire tree to the caller and applying the transformation function there.

.> pull git@github.com:unisonweb/website:.articles.distributedDatasets .article1

ex1.Tree.reverse : src.Tree a -> src.Tree a

ex1.Tree.reverse : src.Tree a -> src.Tree a
ex1.Tree.reverse = cases
  Tree.Two left right ->
    use Value map
    use ex1.Tree reverse
    l = map reverse left
    r = map reverse right
    Tree.Two r l
  remainder           -> remainder

ex3.Tree.fromList : [a] -> src.Tree a

ex3.Tree.fromList : [a] -> src.Tree a
ex3.Tree.fromList = cases
  []  -> src.Tree.Empty
  [a] -> Tree.One (Value.pure a)
  as  ->
    use Value pure
    use ex3.Tree fromList
    (left, right) = List.halve as
    Tree.Two (pure (fromList left)) (pure (fromList right))