Elixir/Phoenix + Neo4j でお手軽！高速！経路探索

はじめに

聖夜に fukuoka.ex Elixir／Phoenix Advent Calendar 2019 兼 YAMAP エンジニア Advent Calendar 2019 24日目の記事がやって参りました🎅

🔺YAMAP 分析チームの松本です。元バックエンドエンジニアです。

YAMAP のバックエンドでは、応答速度やスケーラビリティの性能が要求されるケースでの選択肢として、Elixir/Phoenix を活用しています。

また従来より YAMAP では、登山計画時の便利機能として、経路探索システムが熱望されていました。

今回は

• グラフ構造をもつデータの探索を得意とする GraphDB Neo4j
• 応答速度に優れる Elixir/Phoenix
• 特に理由はないけどフロントは Elm

を利用し、お手軽かつ高速な経路探索システムを開発してみようと思います。

Neo4j とは

neo4j.com

実は僕は詳しくなくて、SNS での人間関係の探索などに使われる DB くらいのイメージです。 「A さんは最近サーフィンに興味があるので、友達の友達の範囲内で、サーフィンが趣味の人をサジェストする」等

経路もグラフ構造なので、経路探索にも向いているようです。

Elixir/Phoenix とは

特に説明不要かと思いますが、詳しくはこいつを見てくれ。

すごく

• 省リソースで
• 耐障害性が高くて
• 応答速度が早い

です。

問題設定

今回やることを定義します。 経路探索の舞台は、我らが「宝満山」にします。（福岡県）

↑地図の通り、

• Neo4j
  • n0 ~ 19 までの node を設定する
  • 実際の登山道に基づき、node 間の relationship を定義する（コースタイムも）
• Elixir/Phoenix
  • Neo4j へのデータ登録タスク
  • node 一覧を返却する api：GET /nodes
  • 経路探索 api：GET /routes/search?from=<from_id>&to=<to_id>
• Elm
  • 地図上に node を表示する
  • 2点を選択したら経路探索を実行
  • 結果のルートを表示する

が、今回やることです。

開発結果

始点と終点を選択すると、所要時間が短い順に、3つの経路がサジェストされます。 登山計画が捗る予感がする！🗻

開発詳細

Repository & Setup

Elixir/Phoenix

github.com

$ docker-compose build
$ docker-compose up phoenix

すれば動くはず。

Neo4j

↑の後、localhost:7474 を開くと Neo4j コンソールが見れるので、初期ユーザー / パスワード = neo4j / neo4j でログインできます。 その後パスワードを password に変更します。（Phoenix の設定合わせ）

Elm

github.com

$ elm make src/App.elm --output src/app.js
$ elm reactor --port=8002

すれば動くはず。 ちなみに僕はフロントも Elm も素人なんでクソコード勘弁して下さい😓

mix task で Neo4j にデータ投入

$ docker-compose run --rm phoenix mix import_seed_data

localhost:7474 で Neo4j のデータを確認すると、

宝満山の登山道のグラフ構造が確認できます。良いネ👍

データクリアしたい時は↓も用意してあります。

$ docker-compose run --rm phoenix mix clear_all_data

Neo4j 接続設定

Bolt.Sips を使いました。

github.com

config :bolt_sips, Bolt,
  url: "bolt://neo4j:7687",
  basic_auth: [username: "neo4j", password: "password"],
  pool_size: 10

検索実行

defmodule PhoenixNeo4jExample.Route do
  alias Bolt.Sips, as: Neo
  alias Bolt.Sips.Response
  alias Bolt.Sips.Types.Path
  alias Bolt.Sips.Types.Node

  ...

  def search(from, to) do
    query = cyper_query(:search, from, to)
    routes =
      Neo.conn()
      |> Neo.query!(query)
      |> parse_search_result
    {:ok, routes}
  end

  defp parse_search_result(%Response{records: records}) do
    records
    |> Enum.with_index
    |> Enum.map(fn({[_from, _to, %Path{nodes: nodes}, time], i}) ->
      %{
        node_ids: Enum.map(nodes, fn(%Node{properties: %{"id" => id}}) -> id end),
        total_time: time,
        color: @colors |> Enum.at(i)
      }
    end)
  end

  defp cyper_query(:search, from, to) do
    ~s"""
    MATCH (from:Node {id: '#{from}'}), (to:Node {id: '#{to}'}), path=((from)-[walk:WALK_TO*1..10]->(to))
    RETURN from, to, path,
    REDUCE(totalTime=0, w in walk | totalTime + w.time) as cost
    ORDER BY cost
    LIMIT 3
    """
  end

  ...
end

Bolt.Sips は Cyper query の DSL は用意せず、生クエリを書いて query! 関数で実行するスタイルでした。 僕は DSL 好きじゃないので良いと思いました。

また Bolt.Sips.Response はかなりネストが深い構造でしたが、Elixir のパターンマッチで、割とスッキリ処理できました。 実は久しぶりに Elixir を書いたのですが、やっぱり書き味が素晴らしいです😊

まとめ

Elixir/Phoenix + Neo4j で、お手軽かつ高速な経路探索システムを開発しました。 実際どれくらいの応答速度になるのかは、データを大量に入れて検証していきたいと思います。

Elixir はパターンマッチが強力で、データ処理言語としても有用であることは、fukuoka.ex の @piacere さんも言われている 通りだと思います。

僕はバックエンド出身の分析エンジニアとして、分析処理した結果を api でユーザーに配信して〜といったシステムを作りたくなる時もあるのですが、Elixir/Phoenix は一つの良い選択肢だと考えています。 耐障害性に優れる点も、スタートアップ企業のような開発リソースが潤沢ではない局面で、とても助かるんですよね。

ということで、久しぶりに Elixir に触れて楽しいクリスマスイブでした！ 達郎聴いて寝よ🎅🎸