その手の平は尻もつかめるさ

ギジュツ的な事をメーンで書く予定です

NetworkManager 1.36においてL2TP/IPSecのトンネルが上手く張れない問題

linux vpn

NetworkManagerのversion 1.36においてL2TP/IPSecのトンネルを張ろうとすると上手く張れないという問題があります。
自分が使用しているUbuntu 22.04ではL2TP接続は標準では提供されていないのでnetwork-manager-l2tpパッケージをapt等でインストールする必要がありますが、この時に一緒に使用するNetworkManagerのバージョンによって当該問題が発生します。ちなみにNetworkManagerのバージョンは nmcli --version 等で参照可能です。
Ubuntu 22.04のpackage managerで利用可能なNetworkManagerのバージョンは1.36系であるため *1 だいたいこの問題を踏むことになると思われます。


症状としては network-manager-l2tp をインストールした上でL2TP/IPSec接続を試行すると以下のようなエラーメッセージが表示された上でどことも通信できなくなり、最終的にトンネル接続の確立がキャンセルされるというものが見られます。

NetworkManager[1134025]: xl2tpd[1134025]: handle_control: bad control packet!
NetworkManager[1134025]: xl2tpd[1134025]: network_thread: bad packet

L2TPやIPSecの設定に問題があるのかと思って色々と試してみたのですが改善せず、色々調べたところNetworkManagerの開発repositoryのissueに行き着きました:

これは既知の問題であるようで、

https://gitlab.freedesktop.org/NetworkManager/NetworkManager/-/issues/946#note_1406609

このコメントで示されているように、トンネルのために作成されるpppインターフェイスが「よくわからないIP」を持っていることに依るようです。
例示されているppp0の状態を借りて説明すると、

43: ppp0: <POINTOPOINT,MULTICAST,NOARP,UP,LOWER_UP> mtu 1400 qdisc fq_codel state UNKNOWN group default qlen 3
    link/ppp 
    inet 172.16.100.10 peer 63.2.5.44/32 scope global ppp0
       valid_lft forever preferred_lft forever
    inet 172.16.100.10/32 scope global noprefixroute ppp0
       valid_lft forever preferred_lft forever

トンネルの宛先 63.2.5.44/32 に対して 172.16.100.10 がpeerされていることが問題のようです。
というわけでトンネル確立試行中に ip a del 172.16.100.10 peer 63.2.5.44 dev ppp0 などとしてその不正なpeerを削除してあげると、正常にトンネルが張られて通信できるようになります。


めでたしめでたし......と行きたいところですが、このままではトンネルを張るたびに手動でpeerの削除コマンドを打たなければならないのでそれは面倒です。そもそもこの削除コマンドはトンネル確立処理中に打たなければならず、適切なタイミングでの実行が求められて大層面倒です。自動化しましょう。

NetworkManagerには発生するイベントに応じてスクリプトが呼ばれるという仕組みがあるのでそれを利用します。
/etc/network/if-up.d に実行可能なスクリプトを置いておくとインターフェイスがupした時に呼ばれるので、

#!/bin/bash

set -euo pipefail

if [[ "$IFACE" =~ ^ppp[0-9]+ ]]; then
  invalid_addr_json=$(ip -j addr show dev "$IFACE" | jq -r '.[0].addr_info[] | select(.scope == "global" and .address != null)')
  sudo ip a del "$(echo "$invalid_addr_json" | jq -r .local)" \
    peer "$(echo "$invalid_addr_json" | jq -r .address)/$(echo "$invalid_addr_json" | jq -r .prefixlen)" \
    dev "$IFACE"
fi

というようなスクリプトを 999-remove-invalid-peer-on-ppp-if みたいな名前で /etc/network/if-up.d 配下に置いておくと、L2TPトンネル確立の際に自動的に不正なpeerが除去されるので正常にトンネルが張れるようになります。jqはインストールしておきましょう。
ただし、他の用途でpppインターフェイスを利用する際にこのスクリプトが有効になっていると、意図せず動作をおかしくしてしまう可能性があるのでその点についてはご留意ください。
なおこの時、このスクリプトに実行可能なpermissionを与えていないと上手く動かないので注意が必要です。chmod 755 などとして与えましょう。

めでたしめでたし。それはそうとして ip コマンドの結果をJSONで出力する -j オプションは便利でよいですね。


ちなみに

https://gitlab.freedesktop.org/NetworkManager/NetworkManager/-/issues/946#note_1725575

このコメントにあるように、NetworkManager 1.40では直っている問題のようです。アップグレードできるならアップグレードしたほうが良いでしょう。Ubuntu 22.04のpackage managerにも入ってほしいですが、ちょっと難しそうなのでUbuntu 24.04を待つしかなさそうな予感がしています。Ubuntu 23.04ではNwtworkManager 1.42を利用しているので *2 24.04では修正版が使えるようになることを期待しています。

*1:see also: https://packages.ubuntu.com/jammy/network-manager

*2:https://packages.ubuntu.com/lunar/network-manager

Linux DesktopでIntelliJ IDEA 2023.1を4Kディスプレイ上で表示すると色々デカくなって困る

IntelliJ IDEAを2023.1にアップグレードして4Kディスプレイ上で起動したところ、スケールの設定がおかしいのかすべてがデカくなり、相対的に作業領域が狭くなって困っています。

たぶんLinux Desktopでだけ発生している問題のようで、同じような症状が既にレポートされていました。

https://youtrack.jetbrains.com/issue/JBR-5316/Wrong-large-IDE-scaling-on-4k-Screen

ひとまずのWorkaroundとしては起動オプションに-Dsun.java2d.uiScale=1.0を付けると良いとのこと。

直った (ように見える)！！ よかったよかった。

#yapcjapan YAPC::Kyoto 2023に行ってきた・喋ってきた

yapcjapan.org

2023年3月19日に開催されたYAPC::Kyoto 2023に参加してきました。もう2週間も前の話になるんですね......USに戻ってきてから色々あり、すっかりブログを書くのが遅くなってしまいました。

YAPC::Kyotoの様々な感想については「にゃんこ酒場.fm」で id:papix、id:karupanerura さんら運営の方々と喋ったPodcastが公開されているので是非お聴きくださいませ！

nyanco-sakaba-fm.hatenablog.com

面白かったトーク

ジョブキューシステムFireworqのアーキテクチャ設計と運用時のベストプラクティス

id:tarao さんの発表。Fireworqが発表されたあたりって、スケーラビリティが高くなおかつ複数の言語から良い感じで使えるジョブキューのプロダクトについて「何使えば良いんだろうねえ」って感じで決定版がいまいち無かった記憶があり、当時はResqueとかSidekiqとかを使ってたような気がしています (一部は古来からのTheSchwartzとかもあった気も......)。AWS使ってる人たちはSQSを使ってたのかもしれないですが。
そんな中、実務に耐えうるジョブキューエンジンであるFireworqが出てきたタイミングで「オオ！」となったのを今も覚えています。アーキテクチャも先鋭的で、なおかつ、はてな内で実際に使われているというところにも感動したものです。
当時は自分もジョブキューエンジンを作ろうとしており、それは未完に終わったのですが *1、そういったパッションがあったことを思い出すセッションとなりました。

しかし、今はKafkaとかAmazon Kinesisとかを個人的には使っちゃいがちでして。ジョブキュー界隈もこの数年でこなれたんだな〜という感想も同時に抱きました。

ORM - Object-relational mapping

id:onk さんの発表。ORMについてパターン分類しつつ体系的に説明し、かつ既存のPerlプロジェクトに対して大きなギャップを生まない形でORMを導入していくという実践的な発表でした。
PofEAA等、ORMについて解説している書籍は数あれどなかなか骨太 (というか単純に文量がすごい、あとonkさんも軽く言ってましたが20年前の書籍なので歴史がある) なものが多いので人に勧めにくい！　ので、このようにわかりやすくまとめてあるのは人に説明する時に助かってめっちゃ良かったです。
会場で「ORMがパフォーマンス悪いクエリ吐くと困らない？」と質問したのは僕で、

Perl の DB 周りのライブラリには基本的にどこで発行した SQL なのかをコメントで残す機能がある *5 ので、スロークエリの検知や集計さえできていれば発生した問題には対応できる。 また、集計や検知するためのサービスが現代では整っていて、自前で pt-query-digest 等で集計しなくても Performance Insight が教えてくれるので、頑張らなくても見つけられるんじゃないかと思っています。

今は移行直後なのでみんな SQL への脳内マッピングができる状態だけど、「ORM しか触ったことのない人」が増えた世界だと「発行される SQL を見てくれ！！」と言いたくなりそうですね。例えば Devel::KYTProf を入れて流れる SQL を眺めながら開発するよう働きかけるとか、それをやってもログだと眺める人が少ないのでブラウザ上にどうにかして表示するとかが必要になるかもしれません。

そもそも問題が発生しないようにするのは難しいよねー……。工夫はして防ぐけど、たまにやらかしが出うる、勝ち目の少ない戦いっぽいと思う。

https://onk.hatenablog.jp/entry/2023/03/27/003901

という回答をしていただき、これについては納得しました。とはいえ、自分としてはやはり多段JOINだのなんだのと複雑なクエリをORMだけで組ませようとすると理解不能かつパフォーマンスの悪いクエリが得てして吐かれることがある気がしてて、そういうものについてはSQLを手書きしつつオブジェクトにマッピングだけさせる、というハイブリッド戦略を採ることが多いかなあ......単に生SQLが好きという嗜好の話かもしれない。とはいえ「どれくらいの複雑性からそうするのか？」と問われるとそのへん感覚でやってるので、そのへんもうちょっと自分の中で言語化する必要があるのかもしれないなと思いました。

キーノート

id:onishiさんのキーノート。エモすぎる。はてなの社史からご本人のキャリアをなぞっての大河という感じで本当に良かったです。「なにをやるにも遅すぎるということはない」本当に良い言葉ですね。
この発表についてつべこべ言うのは野暮だと思うので、アーカイブ映像が公開されたら見ましょう。Must Watchという感じですね。

それはそうと懇親会でも言いましたが、スライドの発表メモに「ここで感極まる」というト書きをするのは反則ですよ *2。

自分のトーク

恐れ多くもゲストとして招待していただき発表することとなりました。シアトルから駆け付けての発表で、人生史上初の来日公演と相成りました。

docs.google.com

一般に「技術的負債」だの「レガシーコード」だのと呼ばれがちな「みなしごソフトウェア」について、あえて露悪的に「廃墟」と称すことにし「それは技術的負債ではない、このままではいけない、なんとかしなければならない、なんとかするぞ」という意気込みを表明するとともに実際になんとかして生き延びるための技法について散りばめた発表となっています。ここ数年はこのようなソフトウェアをやりまくる請負人として活動していたので、その間に得た知見をまとめた集大成となったのではないかと思います。中身としては「レガシーソフトウェア改善ガイド」や「レガシーコード改善ガイド」に書かれている内容も多く含まれてはいるわけですが......

質疑応答としては、

といったものが印象に残っており、一般に「廃墟をなんとかする」という活動は「停滞」に見えてしまいがちですよね。実際には停滞ではなく継続的な改善活動であり、ひいては事業を持続させるために必要な行動であると言えるはずなのですが、エンジニアリング活動の外から見ているとそう理解してもらうには一定のハードルがあるというか。結局、経営とちゃんとコミュニケーションして信頼関係を築いて理解してもらう、かつFour Keysのような実績を示して実測値によって理解してもらう、という営みが必要なのではないか、というのがここ最近の思いです。


さて、このトークの裏テーマは「個人技」でした。それが廃墟活動であるかどうかを問わず、ソフトウェアの開発や運用をするにあたっては「個の力」だけでは早晩限界が来てしまうため、チームで取り組んでいく必要があるというのは今さら言うまでも無いとは思います。一方、個人技が必要ではないかというとそうではないと思っていて「圧倒的な個人技」が不利な状況を打開するということは少なからずあると思っており、特に「廃墟をなんとかする」などといった馬力を求められるシチュエーションでは非常に価値があるものだと思っています。
ソフトウェアエンジニアリングという業界が成熟してきている証左だとは思いますが、ここ最近はチーム開発だとか組織運営だとかそういったトピックが巷で多く見られるようになりました。そういった状況から「個の力」が若干軽視されているのではないかという懸念があり、このトークでは個人技の価値や重要性、そしてその限界についての話題を意識的に盛り込みました。ぶっちゃけて言えば個人がその技を限界までプッシュしてこそチームでの活動が強化されるのであって、極限まで求めた個人技と個人技のせめぎあい、そしてその技の協調によって形成されるチームこそが最強のチームなのではないかという意識を持っており、そうありたいという思いが込められています。


それはそうとid:malaさんから「『廃墟をそのまま売り飛ばす』という解法が欠けているよ」と発表後に指摘され、なるほどとなりました。Good Point。ちなみに僕はそれまだやったことないです。


またLTもやりました。LTの資料はこちらです。

docs.google.com

github.com

^ を実装した時の話です。これを実装した時、この資料に書かれていたPrefix TreeによるIP Routing Tableのマッチングアルゴリズムを自力で編み出しており「うおおおお、やったー！！！」と万能感に包まれていたものですが、よくよく調べてみると既に存在する応用領域であり若干ガッカリしたという裏話があります。良く事前調査をしよう！！！

その他雑感

久々のオフラインカンファレンスで、久々に会う人たちと色々なお話ができて本当に良かったです。トークそっちのけで廊下で近況報告だったり、困り事の相談だったり、新しい技術の話だったりそういうことを沢山できて本当に楽しかったです。
また、発表中にリアルタイムで刺し込まれる質問 (a.k.a dan the question) があるのもオフラインならではですね。これも非常に面白かったです！
あとid:sfujiwaraさんに辻斬りのように投げていたpull requestについてのディスカッションもface to faceでできて良かったです。いつもお世話になっております〜みたいな感じで使っているソフトウェアの感想・感謝を直接伝えられるというのも良いですね。

また、id:nekokakさんの発表やid:onishiさんの発表など、キャリアに関する発表を見て考えが新たになったというのもあります。僕ももはや齢32、無茶が効く年齢はとうに過ぎ去り、いつまでこのような腕力にモノを言わせた暮らしができるのかとふと心配になることもあります。懇親会で誰かに言われた「暴力装置のようなキャリアにはいずれ限界が来る」という言葉には冷や水を浴びせかけられたような気持ちになりました。そういったキャリアに対する漠然とした不安のようなものは確かにあり、一方で腕力は失いたくはない。そんな折にYAPCには先輩エンジニアが多く参加しておられ、色々とキャリア相談みたいなことが懇親会等でできたのは非常に良かったです。しかしすっかり僕も歳を取った......



というわけで、YAPC::Kyoto 2023たいへん楽しかったです！　YAPCを運営してくださった皆様、参加者の皆様ありがとうございます！！　今後のYAPC::Japanも楽しみにしています。


ちなみにコレは発表前に飲んだ、会場前の自動販売機で売ってた100円のエナジードリンクです。コイツに僕は助けられたと言っても過言ではありません。しかし100円のエナジードリンクってマジですごいな。


KAYACさんが配ってたおみくじは "undef" でした。トーク直前にこれ引いて若干不安になるという一幕。面白かったです！


飲酒

無茶な飲酒もYAPCの華。

*1:Kafkaが台頭してきたので

*2:ジョークです

地獄！　YYYYMMDDだと思っていたらYYYYMDとして扱われていた情景

たとえば 2023111 という日付が登場した時、これは 20230111 とも 20231101 とも解釈がされうるということです。
にわかには信じがたい出来事ですが太古のコードを眺めているとそういうことがあります。大変ですね。これが生きるということと言うこともできるはずです。まあ俺が書いたコードじゃないし......

というわけでひとまず被害状況としてどういう日付が影響を受けるかサクっと確認してみましょう。ふつうに手で検証してもわかる話ではありますが、今日は街に雪が降ったのと元のコードがRubyだったのでRubyで書いて確認しました。

#!/usr/bin/env ruby
# coding: utf-8

require 'date'

dict = {}
d = Date.new(2023, 1, 1)
for day in 0..364
  yyyymd = (d + day).strftime('%Y%-m%-d')
  unless dict[yyyymd]
    dict[yyyymd] = []
  end

  yyyymmdd = (d + day).strftime('%Y%m%d')
  dict[yyyymd].append(yyyymmdd)
end

for yyyymd, yyyymmdds in dict
  if yyyymmdds.length() >= 2
    puts yyyymd => yyyymmdds
  end
end

{"2023111"=>["20230111", "20231101"]}
{"2023112"=>["20230112", "20231102"]}
{"2023113"=>["20230113", "20231103"]}
{"2023114"=>["20230114", "20231104"]}
{"2023115"=>["20230115", "20231105"]}
{"2023116"=>["20230116", "20231106"]}
{"2023117"=>["20230117", "20231107"]}
{"2023118"=>["20230118", "20231108"]}
{"2023119"=>["20230119", "20231109"]}
{"2023121"=>["20230121", "20231201"]}
{"2023122"=>["20230122", "20231202"]}
{"2023123"=>["20230123", "20231203"]}
{"2023124"=>["20230124", "20231204"]}
{"2023125"=>["20230125", "20231205"]}
{"2023126"=>["20230126", "20231206"]}
{"2023127"=>["20230127", "20231207"]}
{"2023128"=>["20230128", "20231208"]}
{"2023129"=>["20230129", "20231209"]}

1年のうち36日、つまりおよそ10%が影響を受けることがわかります。大変ですね。頑張りましょう。


[追記]

YAPC::Kyoto 2023で話します！　そしてチケットを今すぐに購入しましょう！！

YAPC::Kyoto 2023の採択トークが決まったようですね。面白そうなトークが沢山あってすごいですね。

blog.yapcjapan.org

僕のトークが採択されていない......というのはトリックで、今回は畏れ多くもゲストスピーカーとして招待されましたので、そちらの枠でお話しします。

blog.yapcjapan.org

何を話すかは実際まだ100%は固まってはいないのですが、仮決めとしては「ソフトウェアエンジニアリングサバイバルガイド: 廃墟を直す、廃墟を出る、廃墟を壊す、あるいは廃墟に暮らす、廃墟に死す」というタイトルでお話できれば良いかなと思案しているところです。

つまりはこういうことです。どういうことだ？


それはそうとして、そんなYAPC::Kyoto 2023ですがチケット販売が今月1月の31日までとなっています。

passmarket.yahoo.co.jp

今月中にチケットを買わないと参加ができないのです！　今、まさにこの瞬間、すぐに買いましょう！！！！！


買いましたか？　買いましたね。それでは会場でお会いいたしましょう！
京都は僕が今住んでいるシアトルから片道10時間ってところなのでギリ日帰り圏内なのが助かりますね。

GoのHTTPクライアントがAWS NLB配下にあるコンポーネントと通信するときに5-tupleが分散しないので特定のインスタンスにしか負荷分散されないという話題

golang

Microservicesのようなものを考えた際、Goで書かれたコンポーネントがHTTP(S)を使って他のコンポーネントと通信するという場合があると思います。
その「他のコンポーネント」がAWS NLBの配下にある時、GoのHTTPクライアントがTCPコネクションを使い回す場合があり、その状況においては特定のNLB配下のインスタンスにしかリクエストを割り振らない挙動をするという話題です。

NLB

プロトコル、ソースIP、ソースポート、宛先IP、宛先ポート、そしてTCPシーケンス番号に基いてフローハッシュアルゴリズムを用いて割り振り先のインスタンスを選択するようになっています。

ref:

For TCP traffic, the load balancer selects a target using a flow hash algorithm based on the protocol, source IP address, source port, destination IP address, destination port, and TCP sequence number. The TCP connections from a client have different source ports and sequence numbers, and can be routed to different targets. Each individual TCP connection is routed to a single target for the life of the connection.
https://docs.aws.amazon.com/elasticloadbalancing/latest/network/introduction.html

つまり、同一のTCPコネクションが継続的に張られている状態 (すなわち5-tupleが同じ状況) では、その上を通るHTTPリクエストは常に同じインスタンス (ターゲット) に割り振られることになります。

GoのHTTPクライアント

GoのHTTPクライアントは基本的にHTTP Keep-Aliveするようになっています。デフォルトのHTTPクライアントのTransportはhttp.Transportが用いられており、MaxIdleConnsあるいはMaxIdleConnsPerHostによってKeep-Aliveして使い回すコネクションの数をコントロールしています。

ref: https://engineers.fenrir-inc.com/entry/2018/11/12/153859

デフォルトではMaxIdleConnsは無制限 *1、かつMaxIdleConnsPerHostは2 *2 *3 となっています。
つまりデフォルトの状況では同一ホストに対して2並列コネクションまではKeep-Aliveが有効となり、それ以上の並列リクエストについては都度コネクションを張り切りするという挙動となります。

GoのHTTPクライアントからNLB配下のコンポーネントへリクエストを送る時

以上から、並列リクエスト数が少ない時 (すなわち MaxIdleConns あるいは MaxIdleConnsPerHost 以下の時) にTCPのコネクションがHTTP Keep-Aliveによりpersistentに保たれるため、固定のインスタンスにしかリクエストが割り振られないこととなります。たとえば高々1リクエストしか同時に捌かないような時 (つまり総リクエスト数が少ない時)、そのリクエストは常に一意なNLB配下のインスタンスに振り分けられることとなります。

なので並列リクエスト数が少ない時にNLBの配下にたくさんターゲットをぶら下げていても、大半のターゲットにはリクエストが振られず遊んでいる状況となるためまったくの無駄となります。なのでうまいこと並列リクエスト数に応じてスケールアウト・スケールインできるようになっていると良さそうですね。
(ただこれはリクエスト元のGoで書かれたコンポーネントのプロセス数にも依存するとは思っており、もし大量のプロセスがいる場合はプロセスあたりの並列リクエスト数が少なくてもうまいこと5-tupleが分散する (あるいはプロセス内のコネクションが暇すぎてKeep-Aliveが切れて都度ハンドシェイクする) のでNLB配下のターゲットについては分散するとは思いますが、そもそもリクエスト数が少ない時の大量のプロセスを上げているのはリソース過剰であるのでそこが無駄では、という見方もできる気がします。)
一方で突然リクエスト数が増えた時にスケールアウトをトリガーしたとして、果たして間に合うかどうかという話題はありますが......そうなってくると遊ぶのを織り込んで余剰なターゲットをあらかじめ上げておくしかないような気もしているところです。


それはそうとして、低並列の場合でもTCPコネクションを良い感じでラウンドロビンして5-Tupleを散らす (ついでに良い感じでTCPコネクションをプールしておく)、みたいな方法は無いものですかね。自分でTransportレイヤーを書くしか無いのでしょうか？　とはいえ並列リクエスト数が少ないということは総リクエスト数も少ないというわけで、その少ないリクエストをNLB配下のターゲットにまんべんなく割り振っても特に意味はないような気はしますね......ウーン。


[追記]
ありがたい助言:

なるほど、TCPレベルでのpoolをTransportレイヤで持つことを当初考えていましたが、HTTP Clientレベルでpoolすれば良いという気付きをいただきました。
[追記ここまで]

*1:MaxIdleConns controls the maximum number of idle (keep-alive) connections across all hosts. Zero means no limit. https://cs.opensource.google/go/go/+/refs/tags/go1.19.5:src/net/http/transport.go;l=192

*2:MaxIdleConnsPerHost, if non-zero, controls the maximum idle (keep-alive) connections to keep per-host. If zero, DefaultMaxIdleConnsPerHost is used.

*3:https://cs.opensource.google/go/go/+/refs/tags/go1.19.5:src/net/http/transport.go;l=58;bpv=1;bpt=1

IP Routing TableのGo実装 "go-iprtb" 書いた

golang

GoのIP Routing Tableの実装について調べてみたところ、だいたいOSのRouting Tableを操作する系のライブラリがヒットし *1、そうではなくユーザー側コードでRouting Table相当の実装・処理をしたい時に使えそうなライブラリがパッと見当たらなかったのでそれを書いたという次第です。


さて、GoでシンプルなRouting Table実装を書くのは実に簡単で、以下のように書くだけでほぼ期待通りに動くと思います。

type RouteEntry struct {
	Destination net.IPNet
	Gateway     net.IP
	NwInterface string
	Metric      int
}

routes := map[string]RouteEntry{}
// ここでroutesにrouteを登録する

// `target net.IP` がrouting tableに含まれているかどうかをチェックする
var matched RouteEntry
var everMatched bool
for _, r := range routes {
	if r.Destination.Contains(target) {
		if !everMatched {
			matched = r
			everMatched = true
			continue
		}

		matchedMaskLen, _ := matched.Destination.Mask.Size()
		newRouteMaskLen, _ := r.Destination.Mask.Size()
		if newRouteMaskLen > matchedMaskLen { // for longest match
			matched = r
		}
	}
}

fmt.Println(matched)

この実装の問題としてはlongest matchを考慮するためにはRouting Tableのエントリをすべて線形に走査する必要があるため、Routing Table中のエントリ数が増えれば増えるほど計算量が増える、ということが挙げられます。
したがってTable中のroutes全てを1つのPrefix Treeに落としこんでやることで、対象のアドレスについてその木のパスを1回走査するだけで対象アドレスがRouting Tableにマッチしているかどうかを判断することができ、これにより計算量を減らすことができるという狙いがあります。


例えば 10.0.0.0/8, 192.0.0.0/8, そして 192.128.0.0/9 という3つのサブネットを考えたとき、それぞれの2進数表記は以下のようになります。表にはサブネットに属するゲートウェイについても記載しています。

Subnet Subnet Binary Gateway
10.0.0.0/8 00001010 00000000 00000000 00000000 GW1
192.0.0.0/8 11000000 00000000 00000000 00000000 GW2
192.128.0.0/9 11000000 10000000 00000000 00000000 GW3

太字はサブネットマスクを適用した後のアドレスを表わしています。このアドレスビット列についてTrie木を構築していくと以下のようになります。

                 R
                / \
              /     \
            0         1
           /           \
          0             1
         /             /
        0             0
       /             /
      0             0
       \           /
        1         0
       /         /
      0         0
       \       /
        1     0
       /     /
 GW1 [0]   [0] GW2
             \
             [1] GW3

† R: Root Node
†† [n]: Terminal Node

そして対象アドレスを2進数にしてこの木に対して最長マッチをさせていくと以下のような結果が得られます ([ ]で囲われた箇所は終端ノードを表わしています):

Target IP Target IP Binary Found Gateway
10.10.10.10 0000101[0] 00001010 00001010 00001010 GW1
192.10.10.10 1100000[0] 00001010 00001010 00001010 GW2
192.192.10.10 11000000 [1]1000000 00001010 00001010 GW3
127.0.0.1 01111111 00000000 00000000 00000001 N/A


今回書いたライブラリでは上記で挙げたような木構造による実装をしたところ、以下のような性能改善を実現できました。

$ go test -bench=. -benchmem
goos: linux
goarch: amd64
pkg: github.com/moznion/go-iprtb
cpu: 12th Gen Intel(R) Core(TM) i7-1280P
Benchmark_PrefixTreeAlgorithm-20        18535410                81.68 ns/op           64 B/op          1 allocs/op
Benchmark_LinearSearch-20                6148155               192.1 ns/op            96 B/op          1 allocs/op
PASS
ok      github.com/moznion/go-iprtb     2.968s

速い！　良かったですね。
なお他にもroute消去時の枝刈りなど細々としたパフォーマンスのチューニングが入っていたりもします。

ぜひご利用ください。

*1:例: google/gopacket/routing, libp2p/go-netroute