A Distributed Hash Table (DHT) in F#: Recursion and Pattern Matching

This post is part of a series on the development of a distributed hash table (DHT) in F#.

You can find the previous posts at the following locations:
1. .NET Remoting in F#: A Start to a Distributed Hash Table
2. A Distributed Hash Table (DHT) in F#: Moving  from .NET Remoting to WCF
3. A Distributed Hash Table (DHT) in F#: Using Higher Order Functions for the Service Operation Calls

Joining the Node Cluster:

The simplest implementation defined in the Chord Protocol requires that each node only know about its successor node.  The circle of nodes, joined by each successor node association, makes up the node cluster. In order for a node to become part of the node cluster, it must execute a join request to any arbitrary node in the cluster.

The code that provides this functionality is provided below.  Note: The code base is getting too large to display in full.  The complete solution can be found at http://github.com/dmohl/Polyphony.

Part of ChordClient.fs

let rec FindSuccessorNode possiblePredecessorNode startingNode localNode (chordServerProxy:IChordServerProxy) =
    let valueOption = chordServerProxy.CallServer possiblePredecessorNode CommandType.Join [|localNode|]
    match valueOption with
    | Some value -> 
        let nodeNeighbors = value :?> NodeNeighbors
        match nodeNeighbors.PredecessorNode with
        | predecessorNode when possiblePredecessorNode = predecessorNode -> nodeNeighbors.SuccessorNode
        | _ when startingNode = nodeNeighbors.SuccessorNode -> 
            chordServerProxy.CallServer possiblePredecessorNode CommandType.UpdateSuccessorNode [|localNode|] |> ignore
            nodeNeighbors.SuccessorNode
        | _ when startingNode = "" ->
            FindSuccessorNode nodeNeighbors.SuccessorNode possiblePredecessorNode localNode chordServerProxy
        | _ -> FindSuccessorNode nodeNeighbors.SuccessorNode startingNode localNode chordServerProxy
    | None -> localNode

let JoinChordNodeNetwork localNode remoteNode (chordServerProxy:IChordServerProxy) =
    let successorNode = FindSuccessorNode remoteNode "" localNode chordServerProxy
    chordServerProxy.CallServer localNode 
        CommandType.UpdateSuccessorNode [|successorNode|] |> ignore
    successorNode    

Pattern Matching and Recursion:

Pattern matching and recursion are the two primary language features that are being used here.

Matt Podwysocki has a nice overview of pattern matching here.  Within that post he states:

"One of the interesting and more powerful features of the F# language is Pattern Matching.  Don't be tempted to think of them as simple switch statements as they are much more powerful than that.  Pattern matching is used to test whether the piece under test has a desired state, find relevant information, or substitute parts with other parts.  Most functional languages such as Haskell, ML, and OCaml have them, and F# is no exception to its support."  

Recursion and pattern matching often go hand in hand.  Recursion basically allows you to repeatedly call a function from within that same function.

In the code above, the function FindSuccessorNode is designated as a recursive function by the "rec" keyword.  A call is then made to a node to see if the two nodes should be associated.  The result of that call is then pattern matched against possible outcomes.  Depending on the match, the FindSuccessorNode is recursively called or the successor node is returned.


Part of ChordServer class in ChordServer.fs

        member x.RequestJoinChordNodeNetwork requestorNode =
            let result = 
                match requestorNode with
                | _ when requestorNode = x.node || x.node = x.successorNode ->
                    x.successorNode <- requestorNode 
                    BuildNodeNeighbors x.node x.node
                | _ when requestorNode > x.node && requestorNode < x.successorNode -> 
                    let requestorsSuccessor = x.successorNode 
                    x.successorNode <- requestorNode
                    BuildNodeNeighbors x.node requestorsSuccessor
                | _ -> 
                    BuildNodeNeighbors x.successorNode x.successorNode
            x.AddToFingerNodes requestorNode        
            result

Once again, pattern matching is the primary language feature being used.

Conclusion:

Pattern matching and recursion are two extremely powerful weapons in the functional programmer's arsenal. When combined, the possibilities are endless.