この記事はスタンバイ Advent Calendar 2021の17日目の記事です。

はじめまして！

さて、突然ですがみなさんは膨大なCIDRのリストから自分の持つIPがどのCIDRに該当するか知りたくなったことはありますか？
私はあります。

まずはこのリストをご覧ください。先日iCloudに実装されたプライベートリレーのegressサーバのIPのリストです。

今回はこのリストの中から特定のIPがどこのサーバから来たものかをScalaを使って解決していきます。

方法としてパッと思いつくのはこのリストを順番に検証していけばいつかIPに該当するCIDRを見つけられますが、当然リストの後ろになればなるほど見つけるのに時間がかかりとても実用的ではありません。

そこで、あらためてIP(v4,v6)を構造として考えると、一つの階層に0から65535まで65536個の枝を持った木構造を持っているものと考えることができます。木構造であれば、一つのサブネット(枝)を特定しつつ、絞り込むことができるので効率よく見つけられそうです。

ということで、このリストの構造をIPアドレスのルーティングにもよく使われている木構造のひとつ「LC-Trie」を下のように実装してみましょう！


sealed trait Trie[+A] {
  def insert[B >: A](key: Array[Int], value: B): Trie[B] =
    Trie.insert(this, key, value, 0)

  def entries(prefix: Array[Int]): List[(Array[Int], A)] =
    Trie.entries(this, prefix)
}

case class Node[V](
    value: Option[V],
    char: Int,
    left: Trie[V],
    mid: Trie[V],
    right: Trie[V]
) extends Trie[V]

case object Leaf extends Trie[Nothing]

object Trie {
  def apply[V]: Trie[V] = Leaf

  private def entries[A](
      root: Trie[A],
      prefix: Array[Int]
  ): List[(Array[Int], A)] =
    get(root, prefix, 0) match {
      case None => Nil
      case Some(node) =>
        values(node, prefix.dropRight(1))
    }

  private def get[A](
      root: Trie[A],
      prefix: Array[Int],
      step: Int
  ): Option[Trie[A]] =
    root match {
      case Leaf => None
      case node: Node[A] if node.char > prefix(step) =>
        get(node.left, prefix, step)
      case node: Node[A] if node.char < prefix(step) =>
        get(node.right, prefix, step)
      case node: Node[A] if step < prefix.length - 1 =>
        get(node.mid, prefix, step + 1)
      case node: Node[A] => Some(node)
    }

  private def values[A](
      node: Trie[A],
      prefix: Array[Int]
  ): List[(Array[Int], A)] =
    node match {
      case Leaf => Nil
      case node: Node[A] if node.value.isDefined =>
        ((prefix :+ node.char), node.value.get) +: (values(
          node.left,
          prefix
        ) ++ values(
          node.mid,
          prefix :+ node.char
        ) ++ values(node.right, prefix))
      case node: Node[A] =>
        values(node.left, prefix) ++ values(
          node.mid,
          prefix :+ node.char
        ) ++ values(node.right, prefix)
    }

  private def insert[A](
      root: Trie[A],
      key: Array[Int],
      value: A,
      step: Int
  ): Trie[A] =
    root match {
      case Leaf =>
        val node = Node(None, key(step), Leaf, Leaf, Leaf)
        insert(node, key, value, step)

      case node: Node[A] if node.char > key(step) =>
        val left = insert(node.left, key, value, step)
        node.copy(left = left)

      case node: Node[A] if node.char < key(step) =>
        val right = insert(node.right, key, value, step)
        node.copy(right = right)

      case node: Node[A] if step < key.length - 1 =>
        val mid = insert(node.mid, key, value, step + 1)
        node.copy(mid = mid)

      case node: Node[A] =>
        node.copy(value = Some(value))
    }
}

Node を一とつの単位として、再起的に枝(サブネット)の探索を実行し値の大小によって左右に振り分けながらNodeを蓄積していき、木構造を作っていきます。

あとは、CSVファイルの読み込んだ結果を元にこの Trie を作り、目的のIPを指定すればほぼ1msでIPがどこの枝(サブネットの entries )のものであるか見つかられるようになります！

以上です！