Web以前を思い出させるEthereumのDApp開発

90年代以前のプログラミングを思い出させるDApps開発

パブリックチェーンに放流するDAppを書いていますと、ちょっとしたことに割りと多目のGasを必要とすることがわかり、驚いた次第です。これまで、Erisやなんかのプライベートチェーン向けの開発が中心だったので、実感として分かりませんでした。ちょっと大きめの2次元配列を作るだけで何百円(Gas PriceをGas Stdと同じとして)とかかり、PHPとRDBで適当に組んでいた間、データ量や計算量を軽視する悪癖を身に付けたような気がします(笑)

パブリックチェーン向けのDAppの開発は、計算量やデータ量を割りと細かく気にしながら書くという意味で、C言語全盛の90年代に活躍していたプログラマーは、懐かしい気持ちになるかもしれませんね。あるいはゲームを開発しているような方は、現在進行形でこの手の問題と格闘されているかも。

Web系しかやったことがない人は馴染みが薄い、純粋アルゴリズム系やデータ構造系の知識、ビット演算の知識などがあると、節約がしやすくなります。DBが気づかないところでいろいろやってくれていたことに、気づくかもしれません。

オンチェーンでオーダーブックマッチングを行う解説記事

https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

オーダーブックをオンチェーンで保存・実行する方法の記事

ブロックチェーンへのうまいデータ格納方法を調べていて見つけたのが、この記事です。株などのオーダーブックを、Ethereumブロックチェーン上にすべて保持してマッチングを処理する方法について、解説しています。データの更新があるトランザクションの場合、Gasを必要としますので、その量をいかに少なく済ませる実装にするかというものです。この記事から、要点を解説します。

オーダーブックですので、買い注文と売り注文をマッチングさせることになります。Web+DB環境など非分散システム上で普通に組むと、データを次のように価格から注文数へのマップとして持たせることになります。

そして、プログラム言語がJavaならTreeMap(よく知らないですけど)、PHPなら配列を使って実装することになります(というかDBに入れますけどね、普通)。

このマッピングに使うデータ構造は、一般的にTree(木)、とりわけ順序木というものになります。木・・・どうなんすかね、こういう名前付けの世界。自然にあるものをこういう抽象的な世界に持ってきて使う文化は、私は好きですけど。

オーダーブックのデータをTreeに格納した状態(出典:https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

各ノードの数字が価格です。マッチする売り注文を探すのは、木からある価格を持つノードを探す処理です。これは順序木といって、あるノードの左はそのノードの数より小さい数を持つノードだけ、右は逆に大きい数を持つノードだけを、子ノードとして持つ、そういう木構造です。

で、引用もとの記事のいうように、木構造がソリューションとして理想的なのは、平均的なケースでしかないと。オーダーブックの仕様に注文の削除があるので、そのとき最悪の場合木全体を書き換えないといけなくなってしまいます(木というのは、そういうデータ構造です。興味がある方は、データ構造の解説書などを見てみてください)。大量のWriteが発生するので、Gasも高額になってしまいます。

じゃあ、他にいい方法はないか?次に例として出ているのが、連結リストです。

オーダーブックのデータを連結リストに格納した状態(出典:https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

連結リストなら、更新のとき書き換える箇所は一定です(挿入・削除する要素と、その前後の繋ぎ直しだけ)。

しかし、やっぱり連結リストにも問題があります。注文をたくさん出すユーザーがいると、その人が原因で、ほかのユーザーがGasを多く支払わないといけない状態になってしまうのです。これは、連結リストは走査するとき、リストの一方の端から順にたどるしかないことが理由です。上の図で ”1.23 ” の価格のところへ行くには、 “1.20” から2つ移動する必要があります。その分のコストが請求されるのです。

こういったGas消費量節約の問題を、ビットマップを用いてうまく解決する方法が紹介されているので、次回解説します。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です