ショルツの自己紹介と機能の概要
今回は、私、スコットとTimeTreeのバックエンドエンジニアのショルツに来てもらってます。
ショルツ、軽く自己紹介お願いします。
はい、こんにちは。バックエンドエンジニアのショルツと申します。
今、公開カレンダーの開発をしておりまして、オーナーさん向けのテクノロジーの開発をしております。
今日はよろしくお願いします。
はい、ありがとうございます。オーナーさんっていうのは、公開カレンダーを公開してくれている方の社内での呼び名になっております。
はい、今日はですね、ショルツ、すごい数学ガチ勢だっていうのもあると思うんですけど、すごい面白い話が聞けるかなと思って。
で、まあちょっと話でまま、大丈夫かな。ちょっとあれだけど。
今回はですね、TimeTreeのアドベントカレンダー、今年もやってるんですけど、その記事の中でショルツが書いてきてくれた記事。
リンクは多分概要欄に貼ってくれてると思うんですけど、そちら後で気になる方読んでいただければと思うんですけど、
その記事をどういう話なんみたいな話をですね、ショルツに聞いていこうかなと思っております。
はい、ショルツこれ、そもそもどういう感じの機能を作ったときの話だったりとか、記事の内容の概要みたいなのを聞いてもいいですか。
はい、この機能はその公開カレンダーのその機能の中に、近くのお店を探すっていう機能がありまして、
グローバルメニューから検索があるんですけど、ユーザーさんがその場所にいるところから近いお店のカレンダーを探す機能っていうのがあって、
お店今、スーパーとかドラッグストアとかそういうお店のカレンダーがあって、そのカレンダーにカレンダーのチラシを予定として登録しているカレンダーというのがあって、
それを見つけるための機能という感じで開発をしておりました。
そうですね、タイムツリー使っていらっしゃる方だと、左上をタップ、IOSのUIで恐縮なんですけど、左上のほうからメニューが出てきて、その下のほうにおすすめの公開カレンダーっていうのがあるので、
もっと見るボタンを押してもらうと、近くのお店っていうのが出てきますので、それをするとですね、知っているお店いっぱいあるってなります。
ここのチラシあったんだみたいなのがいっぱいあって。
そうですね、移動経路の利用、位置情報の共有を許可してもらうと利用できる機能という感じになってますね。
なるほどですね、じゃあカレンダーのデータの中にお店の位置というか場所みたいなものがあって、それで使って検索するっていうことですね。
はい、おっしゃるとおりで。
タイムツリーはRailsで書いてるんですけど、これをGemを使って実現したという感じだと思うんですけど、どういうGemを使ったんですか?
大きく二つありまして、一つがGeoHashというもので、もう一つがQuadKeyっていうものですね。
あれ、GeoHashだっけ?GeoCoder?どっちだっけ?
GeoCoderか。
なぜか走り側が訂正するというね。
本当だ、GeoCoderでしたね。失礼しました。これずっとこのままになっちゃってたな、直さないと。
GeoCoderとQuadKeyというGemを二つ使ったっていうことなんですね。
そうですね、はい、GeoCoderですね。
GeoCoderは、ちょっと最初名前出たから最初の方聞くけど、GeoCoderっていうのはどういうGemなんですか?
GeoCoderは、今お話しした近くのお店検索っていう文脈だと、
井戸と経度のペアを二つ、二地点の井戸経度を渡してあげると、
その二地点の距離を計算してくれたりするライブラリーですね。
それ以外にも、いろいろ住所とか出したりとかもできる、結構便利なGemですね。
住所から井戸経度取れるみたいなやつなんですね。
そうですね、住所から井戸経度取れるし、逆もできるみたいですね。
井戸経度から住所を出すみたいなこともできるみたいです。
距離計算の手法と課題
なるほど、便利、すごい。
すごい便利ですね。
井戸経度で距離計算って結構地味にめんどくさいですよね。
そうですね、初めにこの機能開発するぞってなったときに、
角度の情報あるから、頑張ればバックエンドで直接計算をして返してあげることもできるなって思ったんですけど、
やってみると結構難しいというか、面倒な処理をすることが多いことがわかったので、
こういう一発で計算してくれるライブラリーがあるんだと思って飛びついた感じですね。
なるほどね。
単純に結構めんどくさいっていうか、地球が急面だというところでめんどくさいっていう。
そうなんですよね。
経度の方は、場所がどういう離れ方してても計算が楽なんですけど、
井戸が北とか南に触れれば触れるほど、位線が短くなっていくじゃないですか。
だからそれが悪さをしてですね、単純計算だとなかなか距離がずれてきちゃうみたいなのがあるんですよね。
日本だとそれなりに角度があるって感じなんですかね。
そうですね。結構北に長いので、ちょっと距離がずれてきちゃうみたいなのがありそうですね。
今のところこの機能は国内でのみ配られている機能ではあって、
正直距離の半径も今10キロという形で計算してるんですけど、
このカレンダーのチラシの情報を提供してくださっている会社さんとのツリーラスの中で、
大体10キロぐらいでみたいな感じできっちり10キロにしてくださいみたいな要求は特にないので、
正直日本国内っていうのもあったので、雑にっていうのは今自分が手元でパパッと実装できるような距離でも大きくは破綻はしないんですけど、
より手軽に正確な値が出るならっていう理由で選んだっていうのもあります。
なるほどね。この手のやつは結構パッと検索したら出てきたって感じなんですか?
そうですね。ジェームで移動経路から距離みたいな感じで計算検索して、
そしたら割と上位の方に出てきてくれましたね。
なるほどね。自分でやる場合はそれぞれ計算式があるので、それを実装して、
ラップして、メソッドを通してパッと呼び出せるようにしておけばいいかなっていうところもあるけど、
そこのメンテナンスコストってすごいかかるのかな?どうなんですかね?どう思います?
記事の中だと実装持ってるじゃないですか、このジオコーダーの中の実装も。
はい、持ってますね。
自分で書くときとライブラリを使うとき。
結構レビューの負荷もあると思いますし。
確かにね。
レビューの負荷と成果。
結構テスト。手元で書いたらテストを書く。
自分側のテストコードとしてこれがちゃんと動きますよっていうのを書かなきゃいけないと思うんですけど、
それを十分に保証するためのテストケースを十分に書くのは結構大変というか、
例えば東京と神奈川の地点でこれぐらいの精度ですっていうのだったらなんとなくみんなイメージつくと思うんですけど、
もうちょっと北の方でイギリスとロンドンとオクスフォードの距離がこれぐらいでっていうのって多分今のタイムスリーの社員さんとかだと確かにそれぐらいだねって言える人も。
なのでそのあたりの保証するって結構難しくなってくるのかなっていうのもあるかなと思いますね。
おだしょー なんか難しい計算式いっぱい書かれた答えがこうなりますって言われたら、まあはぁはぁってなっちゃうんですよ。
吉田 あってそうだ。よしみたいな感じでレビューしなきゃいけなくなりそうなんで。
おだしょー こういうんだから合ってるんだろうなみたいな感じになってレビューがレビューとして意味をなさない、検算できるといけないといけないって感じ。
おだしょー 直接計算するとなんだっけ、9面予言定理みたいな話で計算するって話があったんですけど。
吉田 そうですね。このジェムをその検討しているときに、検討している中で直接計算もできるなっていうのが、社内で相談というか話したときに出てきて、
ジャスティンがこういう方法もあるみたいですよっていうのを教えてくれて、で実際にジャスティンはその会社、どこだっけな、なんか2点間の距離計算してできたって言ってて、
すごいってなったんですけど、なんだっけ、この9面予言定理をですね、この三角関数、サインとコサインとアクコサインを使って出すっていう方法で、
これ記事にも書いたんですけど、ジオコーダーで使っている計算方法とは別の計算方法なんですよね、この9面予言定理の計算というのが。
おだしょー ちょっと違うんですよね。
ジオコーダーの計算方法の方が、なんだろ、2点の距離がすごいちっちゃいときも誤差が出にくい形になってる、なんだっけな、ハーバーサイン公式っていうのか、
ハーバーサイン公式っていうもので計算できるんですけど、ちょっとこれどうなんだろう、記事の内容そのまま喋っちゃってもいいのかな。
全然大丈夫、全然大丈夫。
高校生で勉強する数学の三角比で、タンジェントってあったじゃないですか。
ありました。
タンジェントって、2分のπ、90度で定義されない値、無限大にぴょーんって飛んでっちゃうグラフだと思うんですけど、
ここでジオコーダーで使ってる関数はアークタンジェントっていう関数で、タンジェントの逆関数なんですね。
ジオコーダーの機能
なので、どうしよう、具体的な話であれなんですけど、例えば1っていう値を入れると45度っていう角度が出てくる。
タンジェントって横の辺分の縦の辺だっけ。
底辺分の高さ。
底辺分の高さ。底辺分の高さだから、1だと45度になるよねってことですね。
そうですね。1分の1で、例えば√1 3分の1入れると30度、6分のπっていう値が返ってくるんですね。
これが分かると、距離がすごい短いときで、角度がすごい小さいときなんですね。
もうあれですよね、50メーター先みたいなイメージ。
そうそう。で、角度がすごい小さいとき、あれ逆になってるかな。いいのかな。ごめんなさい、ちょっとこれこんがらがっちゃってる。
だから距離がすごい小さいときも、この逆関数が潰れにくいっていう性質があるので、
はいはいはい。
こっちのほうがいいんですね。
きれいに出るっていうことを。
究明予言定理だと、アークコサインってコサインの逆関数使ってて、角度が0に近くなるとコサインは1に近づく。
1に近い数同士で縦算、引き算、掛け算してるので、1を超えちゃう場合が出てきちゃうんですよね、たまに。
丸め誤差とかで。
誤差によって、本当は大きくなきゃいけないところが逆転しちゃって小さくなってしまうって感じなのか。
そうです。
それで、それが影響して、1より大きい数をコサインの逆関数かませると定義できない。
そうか、偉いな。
コサインは1以下なので、実数の範囲の場合は。
なので、エラーが出てしまう可能性があるので、近い2点間の距離をするときは、タンジェントの逆関数を使ったほうがいいよねっていう話でこれを使ってるみたいでしたね。
なるほどですね。もうここまでの話でサインとかコサインとかタンジェントってことで、アレルギーで全身陣麻痺になってしまった人がいるかもしれないんですけど、細かい話はちょっと記事を読んでいただくとちゃんと識になってわかると思います。
サインとかコサインとか聞いただけでも泡吹いてしまう人は、ちょっと1回落ち着いていただいて、記事をゆっくり見ればわかるようになるかなと思うんですね。
地球の距離って、ものすごい短い距離で言えば、平面に近似してしまって、ピタゴラスの定理で出るんじゃねえかって思うんですけど、距離が遠くなれば遠くなるほど、地球の丸みが無視できなくなってきてしまうので。
それもやっぱり10キロぐらいで影響出てくる感じなんですかね。
そうですね。ちょっと10キロでどれくらい出るかみたいなのは確かめてはいないんですけど、より正確、楽に正確にできるんだったらそのほうがいいだろうっていう感じでアイディアをしているって感じですね。
エンジニアっぽいエピソードだ。正確のほうがいいよねっていうやつね。
正確のほうがそうですね。
QuadKeyの役割
なるほどです。ここまでがジオコーダー、2点間の移動経路から2点間の距離を出すというジムの話でしたね。もう一つがQuadKeyっていうのがあるって言ってましたけど、これはどういうジムなんですか。
今回この記事を書こうというか、開けるなって思ったのはどちらかというとこのQuadKeyのところが大きくて、QuadKeyの説明からいいのかな。
QuadKeyは移動経路に対してハッシュ値を返してくれるみたいなジムで、ハッシュ値が近いもの同士のその近さみたいなのを計算できる値になっているので、非常に便利でみたいな感じですかね。
なるほどね。そのハッシュって言っても結構記事に書いてあるのでいうと、文字列がどんどん精度を上げていけば長くなっていて、文字列で返してくれるみたいな感じ。
そうですね。より具体的に話すと、QuadKeyは実は4種類の文字しか出てこなくて、0123っていう4種類の文字だけからなるハッシュ値で、まずそのでっかい世界地図がありますと、世界地図を上下左右に4等分しますと。
4等分して、それぞれの地図の部分のことをタイルって呼ぶことにしたときに、それぞれ4枚のタイルに0123っていう名前をつけますと。
で、例えばその日本列島が含まれているタイルを、どうしよう、ちょっとこれ実際とは違うかもしれないんですけど、例えば1番のタイルに日本列島が入っているとしますと。
で、そしたらそのタイル1のタイルをもう1回4等分しますと。
で、さっきと同じように0123っていうラベルをつけてつけますと。
で、じゃあ今度はどうしよう、その4枚のタイルの中で東京都が入っているタイルが3番だとします。
0123なので。そしたらその東京都のタイル、東京都が含まれているその4分割した中の4分割したタイルは131313っていうタイルになると。
で、東京都の中で新宿が入っているものをみたいな感じで、ガンダムその右端に文字を付け足してタイルを小さくして長い名前で命名していくみたいな感じですね。
平たく言うと地球を4つに割って、4つに割って、4つに割って、4つに割って、ビャーってやっていくと、だいたい家の地下、家の辺りの番号が、例えば1330234、4はないのか、0に何とかってなって、4つに割ったうちの何番目、何番目、何番目、何番目、何番目、何番目ですよみたいな感じのデータをつけていくっていうやつですね。
めちゃくちゃロジカルに切った住所みたいな感じだけど、東京都、新宿区、西新宿、うち何丁目だっけ、6丁目だっけ、西新宿6丁目とかっていう形で会社のオフィスとか、住所は東京都っていびつな形してるけど、このロジックで言うと、4つに切っていくっていう、きれいに4つに切っていくみたいなロジックで切っていった住所みたいなイメージなのかな。
なるほどね。どうして検索しやすくなるんですかね。
そうすると、1個大きいタイル、1個のタイルに着目したときに、そのタイルを含んでいた1個サイズの大きいタイルを表す文字列って、その構成の仕方から右端の文字を1個取り払ったものになるんですよね。
なので、近いものっていうのは、左から何文字目まで一致しているかっていうので、近さを測ることができるんですね。
なるほど。それもまさに住所っぽいですよね。東京都、新宿区って言ったら近いなみたいな感じになるっていうのと一緒で、133だったらうちと近いなみたいな感じになるっていうことですね。
僕も例えるとき、実際の住所と例えるとすごいわかりやすかったですね。ありがとうございます。
そういう考え方でいうと、それが単純に数字になったってやつですね。
そうですね。そういうラベリングがされていると、これは単純にその値を今、このカレンダーの住所を表すテーブルに発色した値を入れるカラムがあるんですけど、
そのカラムに文字列のインデックスを貼る。そうすると、ただの文字列に入るインデックスって左側が一致しているときじゃないと、あまり効率いい検索ってできないんですけど、
この発色のエンコードの仕方から、左側が完全に一致している途中からライクを使った検索っていうのが効率よく検索できるようになっていくっていう。
なるほどですね。前方位置検索ですよね。だから、ちょっと適当なあれだけ、133っていうのがうちの、133001みたいなのが会社のオフィスの場所だとすると、
133ってSQLの用語になっちゃうけど、パーセントってすると、133の前方位置で取れるから、会社の近くに登録しているデータが取ってこれるみたいなイメージですかね。
そうですね。
なるほど。こんなのがあるんだっていう面白いですね。
そうですね。この仕組み自体はどこが最初に開発されたかみたいなところはちゃんと把握していないんですけど、
マイクロソフトとかが共有しているこのクワットキーのロジックの説明の図がまさに世界地図を何等分もするみたいな絵が描かれてて、
それで前方位置のインデックスが効くんだよっていう説明を見てすごい感動しましたね。すごい頭いいなって。
この仕組み自体は確かにすごい感動するというか、めんどくさとかインデックスどうするんだろうみたいな距離計算するときにめんどくさって思うところがこういうロジックで作られてるんだって感動するんですよね。
実際にはこのジェムはこの中に含まれるっていう、正方形領域の中に含まれるっていうタイプの絞り込みしかできないので、
タイムツリーの中では最初にお話ししたジオコーダーでクワットキーで絞り込んだカレンダーに対して今度はジオコーダーで距離を計算してその狭い範囲で距離ランキングを作るみたいなことをやってAPIで返しているっていう感じですね。
なるほど。確かにそういうふうにしてる。なるべく広的に近い距離ごとにランクインするっていうのはそういうロジックで作られたりとか。
もともとはクワットキーを導入する前は記事にも書いたんですけど、ただ全部のカレンダー、テンポ数がそんなに多くなかったので、
全ての2度程度を持っているカレンダーに対してユーザーさんとの距離を計算してみたいなことをやってたんですけど、ちょっとテンポの数がかなり増えてきてしまって、それはさすがにということになって、どうやって対象のカレンダーを絞り込んだらいいだろうっていうのを考えてこれを導入したっていう流れですね。
パフォーマンスの向上
量が多くなってきてパフォーマンス問題出てきたから、あらかじめ絞り込んどかないとできないよねみたいなことになったっていうことですよね。
このあたりサービスが成長するとそういう問題が起きてきて、技術的に解決しないといけない。面白い話かなと思って。
めちゃくちゃ面白いですね、これね。最初これ話見てたときは、昔ギガ人科なんかで見たんですけど、3語で全部の地名を表しますみたいな地図プロジェクトがあって。
なんか僕も見たことあります。
確かにプロジェクトの名前がWhat3Wordsっていう名前だったんですけど、1回聞いてさっぱり聞かなくなったなと思ったけど、でも確かにロジック的にはどの単語がどこに当たるのかとかそういうのが分かんなくて、
クワッドキーみたいなのが実務上は便利そうだなって思った感じでしたね。
そうですね。
話したように住所のもっとロジカルなバージョンっていうんですかね、正方形というか長方形なのか分かんないですけど、
そういう形で切り取っていって絞り込んでいくみたいなのが実務上は便利で、
実際の国とか国境だったり都道府県の県境みたいな感じでガタガタしてると距離とか測りづらいみたいな問題があると思うんで、
実務上はこういうほうが便利っていうのはありますよね。
そうですね。
なるほどね。面白いですね、なるほど。
これすごい自分でも開発してて面白いなって思いながら開発してましたね。
これ楽しいですね。今回開発で結構苦労したところとかあるのかなと思ったんですけど、どういうところで苦労しましたか。
苦労したところで言うと、さっきから僕が何回か言い間違いをしているジオハッシュっていうGEMも実際にありまして、
ジオハッシュもクワットキーと考え方は似ている。ほとんど同じなのかな。
ただその割り当て方が0,1,2,3っていう3文字を使うんじゃなくて、いわゆるハッシュというかランダムな文字列みたいな形になってて、
ランダムではないと思うんですけど、クワットキーよりは直感的ではないっていうのはちょっとあんま良くないけど、
ちょっと複雑なハッシュ値の割り当て方をしてて、
実際にいくつかのタイルに分けてそのタイルの近さみたいなのを計算できるっていう計算というか、
同じように見積もれる前方位置のインデックスが効くようなハッシュ値を使うようなものなんですけど、
苦労したところで言うと、そのクワットキーとジオハッシュが今回のタイムツリーのユースケースの場合は、
どっちの方がいいのかなっていうのを検証するところが結構難しかったかもですね。
ロジック的にはどっちでも動くけど、どっちの方がやりやすいかなみたいなところですかね。
そうですね。やりやすいっていうのと、どれくらいの精度とか、
あとAPIのレイテンシーがどれくらい同じ処理をするのに、どっちの方がAPIのレイテンシーが低いかみたいなのを確かめるみたいなところで、
ちょっとその値を書き換えたりする必要があったので、ちょっと苦労したかなっていう感じですね。
決め手となったのは結局パフォーマンスみたいなところなんですか。
実装の課題と結果
おっしゃる通りで、パフォーマンスが今回のユースケースに関してはクワットキーの方がかなり良かったので、どっちを選んだっていう感じですね。
なるほどですね。この辺りもいくつか候補がある中で、どれが最適なのかみたいなところで言うと、
直感と実際計測するのと全然違ったりすると思うし、計測するのは大変だしみたいな。
そうなんですよね。
データは別々に用意して、同じようなロードをかましてみたいなこととかやらないといけないので、
確かにそこら辺の準備をするのは大変そうだと思いますね。
そうですね。
そうですね。めちゃくちゃ今回面白い話が聞けたなと思ってます。
諸律、今日はありがとうございます。珍しくバックエンド編なんですけど、
バックエンドならではの裏側のデータをどう扱うかみたいな話が聞けて、すごい面白かったと思います。
諸律、ありがとうございました。
こちらこそありがとうございました。
では、今回のテクトークはこんなところにしようかなと思います。本当に諸律、来てくれてありがとうございました。
ありがとうございました。
