数ヶ月前にElmでコンシステント・ハッシュ法を扱うためのelm-consistent-hashingというモジュールを公開した。

こんな感じで使える。詳しくはテストを見るといいと思う。

let
    ch =
        ConsistentHashing.new Replica.default (Node.new "node1")
            |> ConsistentHashing.add (Node.new "node2")
            |> ConsistentHashing.add (Node.new "node3")
            |> ConsistentHashing.add (Node.new "node4")

    nextNode =
        ConsistentHashing.getNode (Key.new value) ch
in
-- ...

コンシステント・ハッシュ法についてはWikipedia以外にもこのQiitaの記事も詳しい。

qiita.com

コンシステント・ハッシュ法というと分散システムで使われるイメージが強いので、作った自分もフロントエンドで使い所があるのかは謎だが、いずれElmがサーバーサイドをやれるようになったらきっと広く使われるようになるだろう。

このモジュールは初めての公開モジュールだったが、作るにあたっていくつか工夫した部分がある。

パフォーマンスを考えたコレクション型の選択

Elmはデフォルトのコレクション（[]とかで作られるやつ）がList型になっているが、Listは内部では線形リストになっている。

elm-consistent-hashingでも最初はなにも考えずに内部の仮想ノードのコレクションをList型でよしとしてしたが、コンシステント・ハッシング法では次に割り当てるノードを計算する際にソート済みの仮想ノードから検索を行うため、検索は二分探索のほうが効率が良くなる。

仮想ノードは基本的に数が多いので、ここの検索効率はいい感じにしておきたい。したがってランダムアクセスに優れるArrayに置き換え、内部の実装は以下のようにした。ギリギリ末尾再帰になっていないのがちょっと悲しい。

{-| Looks up the nearest key by recursive Binary Search.
This is way better in performance using linear search with List in case of many keys.
-}
findInternal : Int -> Int -> Maybe Node.Node -> Key.Key -> Keys -> Maybe Node.Node
findInternal beginIndex endIndex currentNode key (Keys keys) =
    if beginIndex > endIndex then
        currentNode

    else
        let
            median =
                beginIndex + (endIndex - beginIndex) // 2
        in
        keys
            |> Array.get median
            |> Maybe.andThen
                (\( medianNode, medianKey ) ->
                    if Key.toString medianKey < Key.toString key then
                        findInternal (median + 1) endIndex (Just medianNode) key (Keys keys)

                    else
                        findInternal beginIndex (median - 1) (Just medianNode) key (Keys keys)
                )

なお、ElmにおけるListとArrayの違いはこのQiitaの記事が詳しい。 https://qiita.com/philopon/items/1a74e434520a06327064#arrayqiita.com

Elmの素晴らしいところはListモジュールがそもそも添字アクセスの関数を標準では提供していないところだ。 そもそもListは線形リストだから添字アクセスするものではない、だから添字アクセスしたければArrayを使え、という思想が標準モジュールの設計から伝わってくる。

とはいえ、デフォルトのコレクションがList型なのでArray型を使うには必ずデータを総なめするコストがかかる。場合によってはこの計算量は無視できないので、敢えてListで添字アクセスをするという選択肢のほうがよい場合もある。正直、このあたりはアプリケーションやらモジュールの性質によるので一概に答えを出すのは難しい。

たとえばelm-consistent-hashingにおいては、ノードを追加するappend関数内部でノード追加後のソートを実行するためにArray型になっているものを一旦List型に変換し直している。しかし、モジュールデザインとして「ノードの追加というのはそう頻繁に行われないだろう」と想定して、敢えてノード追加時の計算コストを許容してArrayを採用している。

{-| Internal data structure of Keys is Array, but as an interface, List might be more generic, handy to use.
Plus, `append` is less likely to be called by users, so here probably won't be any performance issue.
-}
append : List ( Node.Node, Key.Key ) -> Keys -> Keys
append keys (Keys currentKeys) =
    keys
        |> (++) (Array.toList currentKeys)
        |> List.sortBy (Key.toString << Tuple.second)
        |> Array.fromList
        |> Keys

non-emptyなインターフェイス

new関数はもともとは初期化時に追加するノードをListで受け取るようなインターフェイスになっていた。

let
    ch =
        ConsistentHashing.new 
            Replica.default 
            [ Node.new "node1"
            , Node.new "node2"
            , Node.new "node3"
            , Node.new "node4"
            ]
in
-- ...

しかし、このインターフェイスでは空のノード配列を初期化時に渡せてしまう。

ノードが存在しない状態をこのようにして作れることは嬉しくない。なぜなら常にノードが空である場合を常に考慮しないといけなくなるため、必然的にほとんどの操作関数の戻り値をMaybe型にせざるを得なくなってしまう。

したがって、初期化時のnew関数が必ずひとつのノードを取るようにした。

{-| Creates a new ConsistentHashing data
`new` function only takes one initial node at first. This interface is like non-empty list which aims to ensure one node always available at least for distribution.
If you want, you can add some more nodes one by one using `add` function.
-}
new : Replica.Replica -> Node.Node -> ConsistentHashing
new replica initialNode =
    -- ...

こうすることでノードが空でない状態というのが約束できるため、ConsistentHashing型のデータが存在する場合にはノードも必ずひとつは存在することが決まりMaybe型の登場回数を抑えられる。

このような「空でない状態」を表現するには、別の方法として幽霊型をつかう手もある。実際に幽霊型を使って「空でないリスト」を表現する方法は以下のQiitaの記事が詳しい。

qiita.com

一方でノードの削除時にはMaybeを返すようにしている。

{-| Removes a node
This function returns Nothing if all nodes were removed.
`remove` function internally run linear removing of all replicated virtual nodes so that it possibly results in huge computation cost in case you give a big number of Replica.
-}
remove : Node.Node -> ConsistentHashing -> Maybe ConsistentHashing
remove node (ConsistentHashing { replica, nodes, keys, head }) =
    -- ...

最後の一つを残してすべてのノードを削除することができないようなインターフェイスにしてもよかったが、new関数における「常にひとつは生きたノードが存在している」に対して、remove関数でノードを削除する際に「常にひとつのノードが生きている」というのは、なにかしらの大規模な障害が起きるケースではありえないこともあるだろうと考えてMaybeを選んだ。

大事故が起きたときにはすべてのノードがダウンしている可能性もあるし、その場合にはすべてのノードが削除され、割り当てることはできない状態なのでNothingとなる。