『みんなのデータ構造』でデータ構造の基礎を学んだ

データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。

みんなのデータ構造

日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。

内容

データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。

内容の依存関係 p.21より

大学の教科書のように、正確性を優先したハードコアな内容。

アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深さ優先探索と幅優先探索を扱う。また、各データ構造の応用・発展や実世界との照合も各章の末尾に添えられている。

自分の読み方

すでに理解しているデータ構造は一部あったが、メモを取ったり写経したりを経て通読するのに14時間ほどかかった。

理解が及ばない部分や、訳者まえがきで重要性があまり高くないとされていた一部（スケープゴート木とかトライ木とか）は読んだものの完全理解する前に先へ進んだ*1。

練習問題は全部やるとかなりハードなので1周目では問題を眺めつつ解法を想像するぐらいにして、2周目に復習としてやるぐらいが良いと思った。

数学

計算量の解析や定理の証明部分はけっこうハードコアで高校数学を復習しないとかなり厳しそうであった。最初は数式と向き合っていたがやりたかったデータ構造の学習から逸れそうなのでほどほどに読み飛ばすことにした。

苦しんだ一方、データ構造とそれを支える数学的背景の理解のために自分が数学のどの分野を学習すればよいのかが見えてよかった。特に確率論が弱い。

言語

本書に掲載されているコードはすべてC++だが、他言語でのプログラミング経験者なら書籍に掲載されているコードがC++であることは問題ない。

(2020-05-10 22:56 JST 追記) 訳者の方から他言語の実装や擬似コードもあるとのご指摘いただきました。ありがとうございます！

C++をメインの言語として利用していない自分にとってはむしろ、C++で書かれたアルゴリズムを慣れた言語に落とし込むことでより頭を使う写経になって良かった。

補助教材

本書は図とコードを豊富に載せているが、それでも挙動がピンと来ない場合はデータ構造やアルゴリズムの名前で検索したり、以下のサイトでアニメーションを見て視覚的に理解することに努めた。

yutaka-watanobe.github.io

visualgo.net

また、同時期に視聴していたCourseraのアルゴリズム講座で同種のデータ構造*2に出くわしたり、Courseraの課題を解く際に本書を参照したり、相互に補完しあって理解を深めることができた。同講座に関する感想は以下の記事にまとめた。

ohbarye.hatenablog.jp

印象に残ったところ

印象に残ったところの感想を少しだけおさらい。

「2章 配列を使ったリスト」「3章 連結リスト」

さすがにStackとかQueueとか理解しているだろと思って読み始めたところ、自分が理解しているのは抽象・インタフェースとしてのデータ構造とその使い方であって、内部実装まではイメージできていなかったことがわかって序盤から引き込まれた。

同じインタフェースでも内部実装を変えることで処理時間やメモリ効率が変わるのは当たり前のことなのだがそのプリミティブな実装を複数並べて比較することができて面白い。

「4章 スキップリスト」「5章 ハッシュテーブル」

スキップリスト、ハッシュテーブル、Treap、クイックソート等々…ランダム性を扱うデータ構造やアルゴリズムのかっこ良さが心で理解できた。

Skip Listやランダム二分探索木などを学んで乱択に感動しているので『数学ガール 乱択アルゴリズム』読み進めるぞ

— ohbarye (@ohbarye) 2020年4月24日

「6章 二分木」「7章 ランダム二分探索木」「9章 赤黒木」「10章 ヒープ」

木が多すぎてもはや森。

赤黒木の代償として実装が複雑という話が出てきており、これはSedgewick先生がCourseraの講座でも言っていたことを思い出した。特に2008年のLeft-Leaning Red Black Treeの発表以前、とあるデータベースプロバイダが赤黒木の削除の実装を誤ったために障害を起こしたという話。（木の高さを常に一定に保つことが保証されていないHibbard deletionを採用したので木の高さが高くなりすぎ、再構築のためにシステムダウンするほどだった）

「14章 外部メモリの探索」

B treeとデータベースの話がC言語でSQLiteのクローンを作るチュートリアルやった - valid,invalidで学んだ内容とリンクしており、知識の点が線になった感覚があってよかった。

感想

業務にて行き当たりばったりでデータ構造を学んできた身からすると、このように正確性を重視しつつ体系立てて基礎を学べる一冊があるのはありがたい。

この本で扱うのはシンプルなもののみだが、実世界のソフトウェアの骨子はシンプルなデータ構造の組み合わせでできているから、本書の内容を理解することは良いソフトウェアエンジニアになるために有用だ（本書の訳者まえがきより）…という主張もグッときた。

自分同様にデータ構造の基礎を学習したい人には無条件でおすすめする。

*1:本書の訳者まえがきにて、わからない部分は飛ばしてもよいとの言があり、勇気づけられる

*2:特にRed Black Treeは本家のSedgewick先生の解説が聞けるのでCourseraの講座を圧倒的におすすめしたい

『アルゴリズム図鑑 絵で見てわかる26のアルゴリズム』読んだ

目次を見て新しく学ぶことは少なさそうと思ったが、アルゴリズムの勉強を本当に初歩の初歩から始めようと思って読んでみた。

事実そんなに多くなかったものの「第4章 グラフ探索」「第5章 セキュリティのアルゴリズム」あたりは説明しろと言われたら答えに詰まりそうなところだったので良い復習になった。

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

コードも全く出てこないのでコレ一冊でアルゴリズム力が上がるというものでもないのでそこを求めるなら本書以外での演習が大事。この本に乗っているA*とかが自分にとってはまさにそうで、評価関数ちょっといじるだけで実行速度がそんなに変わるか？とかはコードを書いてみて確かめてみないと実感が湧かない。

とはいえ、図解は非常に丁寧でわかりやすいので、もし誰かにアルゴリズムを教えるとしたらこの本を見せながら話すと良いかもしれない。

Google Code Jam 2020 Round 1敗退

Googleが主催する競技プログラミングの大会 "Google Code Jam" に参加し、Round1で敗退しました。

codingcompetitions.withgoogle.com

Qualification Round (予選) -> Round 1 -> Round 2 -> Round 3 -> Final Round の5ステップがあるので、2つ目での敗退。先は長い。

Qualification Round

予選は30点以上の獲得で突破が確定します。 例年だと30点獲得には最初の2問を正解すれば良さそうだったのですが、今年は2問解くだけでは届かない配点になっていました。

43点での突破でした。

Round 1C

1500位以上で通過のところ、4559位での敗退でした。

1,2問目で得点したときに順位表を見ると1500位以内にいたので逃げ切れるかと思ったけど全くそんなことはありませんでした。最低でも2完していないと届かないランクだったので壁は高い。

最も輝いていた瞬間

全体的に問題を読み解くのが大変だったのでDeepLにめっちゃ頼りました。

来年はRound 1通過を目指すぞ!!

競技プログラミング始めた

今年の1月にAtCoderを始め、3ヶ月強ゆるく続けてきてようやく緑コーダーになりました。始めて半年以内には到達したいとぼんやり思っていたので良かった!!

動機

職業プログラマとして働いて5年以上経つわけだけどいまだに胸を張って「プログラミングが得意です」と言い切れない煮えきれなさがあり、これはなんだろうと考えていました。

ここでいう"プログラミングが得意"ってそもそもなんやねんというのはあるが、自分の中では「課題を見つけたり解決したり、ビジネスロジックをじっくり議論して考えつつ特定言語やフレームワークの上で実現していくスキル」、事業会社でWebサービスを開発していく中での中核となるスキルとは別で、前提条件と課題が与えられたときに論理的・数学的な思考によって手段を発想してスッとコードに書き起こせるような能力をイメージしています。

もちろんそれだけがプログラマとして必要なスキルではないことは承知しつつ、そういうことができる人を見て「この人プログラミング得意だな」と感じているので自分の中ではそのへんの欠乏感がありました。

そう思いつつ数年が経過した折、Quipperに競プロ勢の方が入社（現在青コーダー）し、社内で毎週競技プログラミングの練習をしているのを見かけて「これじゃん」と。

言語

最も手慣れたRubyで書いている。Rubyでこれまで使ったこと無いビルトインの機能を使ったり、業務で書くような可読性寄りのコードを書いたら計算量多すぎてTLEしたりして面白い。

「同じロジックを書いてもC++ならACするがRubyだと通らない」みたいなこともたまにあるようだけどその域には達していないのと、どんな言語でもACできないことは無いので言語は言い訳にならない。

公式や野良の解説は主にC++なので、文法を読める程度にしたりSTL (Standard Template Library) をさらっと眺めて写経したりしたがまだコンテストで使えるレベルではない。

今後

プログラミング得意ですと言えるようになるためこれからも続けていくが、そろそろ真面目に数学やアルゴリズムを学習していかないと伸び悩みそう。

当面は「2020年内に水色コーダーになる」のを目標とする!!

既存のRESTish APIエンドポイントにOpenAPI定義を足していく試み

昨年、とあるアプリケーションのフロントエンドリニューアルプロジェクト*1の際に取り組んだ課題について書きます。Ruby, Railsの話が出てきますがRESTish APIの定義をどのように管理するか、API定義が存在しない既存アプリケーションにどのようにドキュメントを足していくかという課題については言語・フレームワークを問わない内容です。

同プロジェクトでは以下のような状況であり、既存のAPIエンドポイントに関する情報をなんらかの形で提供したいというのがモチベーションでした。

• Single page applicationやモバイルアプリのバックエンドとして動作するRESTish API server (Rails) が存在する
• 同API serverの各APIエンドポイントに関するドキュメントが存在しない (または存在するが実装と一致しているか不明で信頼性が低い)
• フロントエンドエンジニアはAPIの仕様を知らない、かつAPIのコードリーディングには時間がかかる

欲しかったものは「APIのin/outについてきちんと"型"が定義されていること」「実装と乖離していないことの保証」「定義が常に参照可能であること」でした。

やったこと

OpenAPI 3の採用

フロントエンドエンジニアが最も慣れていて、かつ習得難易度とかエコシステムとか考慮して今後の運用にも耐えうるであろう記述形式としてOpen API 3を選択しました*2。

OpenAPIはWeb APIの仕様の記述形式です。または関連する周辺ツールです。かつてSwaggerと名乗っており今もその名を関した周辺ツールがたくさん残っていますが、現在はOpenAPIという名前でバージョン3が公開されています。バージョン2と3でだいぶ差がありますが、本記事ではOpenAPIというときにバージョン3を指すことにします。

OpenAPI 3によるAPI specificationの定義

同プロジェクトで必要とされたAPI群の定義をゼロから手動で書き起こしました。

初っ端から非人道的な話ですみません。自動化の道を探ったほうが良さそうにも一見思いました…が、自分もまったく詳しくないエンドポイントたちの中身を知らずに提供するのは望ましくない状況だったので、各エンドポイントのコードリーディングをしたりリクエストを投げて挙動を確認したりしながら書き起こすことで理解を得ました。

また、その過程で既存APIのバグ改修やパフォーマンス改善を行うこともありました。

定義が実装と乖離しないようにする

もともと存在していたYARDコメントがまさにそうだったのですが、記述形式がなんであろうと実装と乖離することが保証されていなければ信頼性は保てません。定義通りにAPIが動くことを継続的に検証する必要があります。

Rubyではcommitteeというgemがあり、これを利用してOpenAPI定義 (JSON or YAMLのファイル) に違反する挙動を検出できます。

また、既存APIに対して後追いで人間が記述する場合、その暖かみのある定義が間違っていないかどうかの検証にもなります。

テストで実装を検証する

committeeにはrequest validation, coercion, test assertion, stub機能などありますが同プロジェクトで使った機能はCommittee::Middleware::ResponseValidationのみです。これは名前の通りRack middlewareであり、アプリケーション（この場合は我々が提供するAPI server）のレスポンスを検証します。

test assertionをすべてのテストに都度書いていくのは面倒なため、API定義が書かれているすべてのエンドポイントについて自動的に検証を走らせるようにしています。OpenAPIによる定義が書かれていない場合は検証は行われません。

# config/environments/test.rb
Rails.application.configure do
  config.middleware.use(Committee::Middleware::ResponseValidation, schema_path: Rails.root.join("openapi/index.yaml"), raise: true)
end

committeeではエラーを検出した際のハンドラを自前で書くこともできますが、ここではシンプルにraise: trueを指定することでテストが単にfailします。たとえばこのようにテスト中にとあるエンドポイントにリクエストを発行するケースがあるとします。

describe "#GET /:language/api/users/:id", type: :request do
  let(:user) { create(:user, username: "butcher") }

  subject { get "/ja/api/users/#{user.id}" }
  
  it "returns 200" do
    subject
    expect(response).to have_http_status(200) 
  end
end

テストケースとしてはstatus codeを検証しているのみですが、middlewareがレスポンスを検証し、違反を見つけたら以下のようなエラーを吐きます。

  1) #GET /:language/api/users/:id
     Failure/Error: subject { get "/ja/api/users/#{user.id}" }

     Committee::InvalidResponse:
       true class is TrueClass but it's not valid integer in #/components/schemas/User/properties/is_teacher
     # ./spec/requests/api/users_spec.rb:160:in `block (3 levels) in <top (required)>'
     # ------------------
     # --- Caused by: ---
     # OpenAPIParser::ValidateError:
     #   true class is TrueClass but it's not valid integer in #/components/schemas/User/properties/is_teacher
     #   ./spec/requests/api/users_spec.rb:160:in `block (3 levels) in <top (required)>'

注意事項としては、この検証はrack middleware層で行っているのでcontroller specでは実行されないということです（もちろんrack middlewareレイヤも込みで動くrequest spec, feature specでは実行されます）。今どきcontroller spec…*3?とお思いかもですが古いアプリケーションらしく一部はcontroller specが生き残っていたのでこれを機にガッとrequest specへ書き換えたりもしました。

これでテスト実行時にOpen API specificationと実装の乖離に気づけるようになりました。

…本当でしょうか？

実はこの検証だけでは実装との乖離を完全に防ぐことはできません。用意されたテストデータに対してしかテストを行っていないためです。たとえば上記コードでは user というテストデータを生成してそのデータに基づいてレスポンスを返すAPIを検証していますが、もしこのデータが変わったとしてもAPIが定義通りに動くことは保証しません。開発者が想定した正常系ド真ん中のテストデータによってしか動かない可能性もあります。

ステージング環境での違反検出と通知機構の整備

開発者が想定していないデータをカバーしたいときや、レスポンスのパターンが複雑でテストデータを用意しきれないようなときはどうすれば良いでしょうか。

そのような場合はテストですべてをカバーしようとするのではなく、実際に動くアプリケーション or "リアル"に近いデータ or "リアル"に近いリクエストで検証するアプローチが有効です。

一例として、QAやプレビューとして利用するステージング環境*4でCommittee::Middleware::ResponseValidationを有効にします。ただし、違反検出時にstatus code 500を返すと他の開発者や社内ステークホルダー諸氏が困るので「定義違反は検知するがレスポンスには手を加えず素通りさせる」「API開発者が気付けるように検知した違反の通知機構を作る」ようにします。

# config/environments/production.rb
Rails.application.configure do
  if ENV["USE_COMMITTEE_RESPONSE_VALIDATION"]
    config.middleware.use(
      Committee::Middleware::ResponseValidation, schema_path: Rails.root.join("openapi/index.yaml"),
      error_handler: -> (ex, env) { Raven.capture_exception(ex, tags: { committee_response_validation: true }) },
      ignore_error: true,
    )
  end
end

ステージング環境はRAILS_ENV=productionの前提でconfig/environments/production.rbに設定を記述しています。middlewareのoptionとしてignore_error: trueによって「定義違反は検知するがレスポンスには手を加えず素通りさせる」を、error_handler: -> (ex, env) { Raven.capture_exception(ex, tags: { committee_response_validation: true }) }によって「API開発者が気付けるように検知した違反の通知」を実現しています。この例ではSentryにエラーを通知しています。

Sentryへの通知をSlackに流す

ステージングとはいえ用意されたテストデータよりも遥かにバリエーションがあるのでこれにより実装のバグやOpen API定義の間違いなどに気づくことができました。

書き忘れましたが、ステージング環境のDBのデータがproductionのdumpをリストアしてマスクしたものであればさらに盤石です。テストする環境が本番に近ければ近いほどより信頼性の高いテストができるというわけです。

Kent C. Dodds先生の発言を思い起こさせます。

The more your tests resemble the way your software is used, the more confidence they can give you.

— Kent C. Dodds 🔭 (@kentcdodds) 2018年3月23日

Swagger UIでいつでも参照できる状態にした

記述したAPI定義の参照容易性は大事です。

JSONまたはYAMLは定義そのものですが人間にとって可読性が高いものでは有りません。なのでdevelop branchが自動的にデプロイされるたびにSwagger UI (Open APIのviewer) で最新の定義がCOOOLな感じで見られるようにしました。

Swagger UIはこういうやつです

swaggerapi/swagger-uiのdocker imageを使っています。

おわりに

当初のゴールに対して以下のようにアプローチを行い、既存のRESTish API serverのドキュメント事情が"無"だったところを整備しました。

• 「APIのin/outについてきちんと"型"が定義されていること」 <= 何もなかったところにOpenAPI定義を書いた
• 「実装と乖離していないことの保証」 <= テストで実装を検証する + ステージング環境での違反検出と通知機構の整備
• 「定義が常に参照可能であること」 <= OpenAPI viewerの提供

そして次にゼロからRESTish APIサーバを立ち上げるプロジェクトがあればSchema Firstでやっていく強い気持ちを得ました。

また、同プロジェクトにおいてやってないこと、今後やれそうなこととしてはコードの自動生成、OpenAPI specificationの自動生成 (from YARD to OpenAPI, grape-swagger)、検知した違反の自動修正等が挙げられます。これらも面白そうですがまた別のお話。

*1:https://speakerdeck.com/ohbarye/migration-from-react-native-to-pwa に詳しいです

*2:実質RESTish APIに関する形式としてはデファクトといっても良いと思います。API Blueprint, RAML...懐かしい名だ

*3:https://everydayrails.com/2016/08/29/replace-rspec-controller-tests.html

*4:production環境で検証するというハードコアな道もありますが一歩間違えると大惨事なのでまずはステージング環境から始めると良いと思います

C言語でSQLiteのクローンを作るチュートリアルやった

2019年12月の冬休みに1週間程かけて"Let's Build a Simple Database"という、C言語でSQLiteのクローンを作るチュートリアルをやりました。この存在を教えてくれた同僚に感謝 :pray:

cstack.github.io

チュートリアルの内容

Richard Feynman先生の“What I cannot create, I do not understand.”という言葉が掲げられているように、データベースを作ることでデータベースをより深く理解することに主眼が置かれているチュートリアルです。

これは重要事項説明かつタイトル詐欺に関する謝罪なのですが… 残念ながらこのチュートリアルは完成しておらず、Part 13が2017-11-26に公開されたのを最後に更新が止まってしまっており、以下の13章しかありません。

• Part 1 - Introduction and Setting up the REPL
• Part 2 - World’s Simplest SQL Compiler and Virtual Machine
• Part 3 - An In-Memory, Append-Only, Single-Table Database
• Part 4 - Our First Tests (and Bugs)
• Part 5 - Persistence to Disk
• Part 6 - The Cursor Abstraction
• Part 7 - Introduction to the B-Tree
• Part 8 - B-Tree Leaf Node Format
• Part 9 - Binary Search and Duplicate Keys
• Part 10 - Splitting a Leaf Node
• Part 11 - Recursively Searching the B-Tree
• Part 12 - Scanning a Multi-Level B-Tree
• Part 13 - Updating Parent Node After a Split

なのでデータベースに関して網羅的に学べるわけではなく、内容は以下に限られます。SQLiteのクローンも完成しません…。

• ちょっとしたREPLの作り方
• In memoryでのデータ保存とディスクへの永続化
• page, pager, cursorといった抽象化
• B Tree (B+ Tree) がなぜデータベースのテーブルやインデックスに使われるのかの説明とその実装

とはいえ、データベースの内部実装でもとりわけ重要なB Tree周りの解説とハンズオンに大部分が割かれているのでB Treeを理解りたい人や、なんとなく理解った気持ちでいるけど実際にテーブルをB Treeで実装してみて深く知りたい人におすすめです。（ただ、チュートリアルの後半のNodeの分割や木の更新に関わる処理は地道な実装が多くてけっこう辛めでした）

また、スクラッチで巨大なアプリケーションを書くときに「小さく作る」「常に動く状態を保つ」といったプラクティスが実践されているのも良い点です。

登場するコードの全体像はすべてGitHubで確認できるのでC言語を書けなくても写経しながら読んでいけばだいたいなんとかなります。また、実装に対するE2EテストはRubyのRSpecで書かれています。

学んだこと

実施している最中のメモはこちら: Let's Build a Simple Database - ohbarye

B Tree (B+ Tree) がなぜデータベースのテーブルやインデックスに使われるのか

検索すれば以下のような先人の良い記事がたくさん見つかるのですが、B Tree自体の理解が浅かったときに読んでもいまいちピンと来ていませんでした。チュートリアルを通して手を動かしてB Treeの構造を実装してみることで具体的な探索処理などがイメージできるようになりました。

• 第7回 性能改善の鍵，インデックスの特性を知る～B-treeとハッシュ （1）B-tree ：SQLアタマアカデミー｜gihyo.jp … 技術評論社
• B TreeとB+ Treeの違い - Carpe Diem
• なぜBTreeがIndexに使われているのか - maru source

チュートリアルではB+ Treeを導入する際に高速な検索・削除・挿入といったメリットだけでなく、B+ TreeのNodeとして持つべき内部データ・メタデータなどのオーバーヘッドでfile sizeが肥大化するデメリットも併せて説明しています。

「SQLiteではB-Treeがテーブルとインデックスの両方に用いられている*1」という"知識"を持っていても、「なぜ他の選択肢、たとえば要素の参照・追加・削除がすべて平均的にはO(1)で行なえるハッシュテーブルではいけないのか」「どのようなトレードオフがあるのか」を説明できる程度までは"理解"していなかったことが浮き彫りになりました。

メモリレイアウトの工夫

ふだん高級言語でWebアプリケーションを書いているとあまり気にされないレベルのメモリの使い方について。

たとえば、ページサイズを4096 bytesにする。この数字はほとんどのコンピューターアーキテクチャの仮想メモリシステムで使用されるページと同じサイズであり、これらが同じおかげで余計な分割処理を行うことなくメモリに出し入れできる。他にもチュートリアルの簡便さのためにページ上限を決めたり、ページを超えて行を保存することを禁止することでページをまたいでのread / writeを避けたりしてるのですが、それがなぜかということも解説されています（ページをまたぐとメモリアドレスが隣接しない可能性が高いので大変になる）。

他にも、pagerにpage number Xを要求する => メモリに乗っているキャッシュから読むことを試みる => キャッシュミスが発生する => データベースファイルを読み取ることでデータをディスクからメモリにコピーする のようなフォールバック処理を書くことで、「あ〜、こういうときに処理が低速になるのか」と体感できたりします。

こうしたローレベルの工夫によりデータベース製品は性能や品質を実現しているという理解が得られました。

Vimをhex editorとして使う

作成するデータベースは終了時にfileにデータをdumpします。dumpされたデータファイルはただのバイナリファイルなので以下のようにして中を覗くことができます。

$ vim -b test.db

:%!xxd

insertしたデータがちゃんと入っていることや、想定したレイアウト担っていることが一応確認できる

パイプを使ったREPLのテスト

これも本筋ではないのですがREPLのテストをパイプを使っているのを初めて見たので学びがありました。

def run_script(commands)
  raw_output = nil
  IO.popen("./db test.db", "r+") do |pipe| # REPLを起動し、そのプロセスに繋がるpipeが得られる
    commands.each do |command|
      begin
        pipe.puts command # pipe越しにinsertとかselectのSQL commandを流し込む
      rescue Errno::EPIPE
        break
      end
    end

    pipe.close_write

    raw_output = pipe.gets(nil) # REPLプロセスの出力 (文字列) を得る
  end
  raw_output.split("\n")
end

it 'inserts and retrieves a row' do
  result = run_script([
    "insert 1 user1 person1@example.com",
    "select",
    ".exit",
  ])
  expect(result).to match_array([
    "db > Executed.",
    "db > (1, user1, person1@example.com)",
    "Executed.",
    "db > ",
  ])
end

さらなる課題

B Treeやデータベースの知識がつくと以下のような実践的記事や実製品の解説が力強く読めるようになりました。

• MySQL with InnoDB のインデックスの基礎知識とありがちな間違い - クックパッド開発者ブログ
• DBMSをGoで実装してみた - Sansan Builders Box
• InnoDBの実装について
  • B+Tree index structures in InnoDB – Jeremy Cole
  • On learning InnoDB: A journey to the core – Jeremy Cole

また、まだ実践していないのですが次のステップとしていくつか良さそうな教材があるのでメモしておきます。

• カーネギーメロン大学の講義
  • 個人が無償で公開している教材も良いが、きちんと広く深く学んでいくためには大学が公開しているコンテンツのほうが良さそう
• Database basics: writing a SQL database from scratch in Go | notes.eatonphil.com
  • このチュートリアルでは到達できなかったlexerやparserが学べそう
  • Golangなのもとっつきやすそう

*1:正確にはインデックスにはB-Tree、テーブルにはB+ Treeが使われている

「Coinhive 事件」についての意見書を書きました

高裁で逆転有罪になった「Coinhive 事件」についての意見書を書きました。なお、先に自分の意見は「同件にて被告の無罪を望む」側だということをはじめにことわっておきます。

意見書って何？

コインハイブ事件弁護団主任弁護人の平野先生のコメントを引用します。

このたび、ウェブやセキュリティ関連企業をはじめ、IT業界でご活躍の皆様に、意見書の執筆をお願いいたしたく存じます。意見書は上告趣意書と合わせて最高裁判所に提出します。

目的は「業界内の声を直接届けること」です。高裁判決に示された規範が先例となってしまうとどのような不利益が生じるか、不正指令電磁的記録があいまいに解釈適用されていくことがどれほどソフトウェアの開発を萎縮させるか、現場や経営の立場から、実情をもとにご意見をお寄せいただければと思っています。

詳しくは引用元のページをご覧ください。

www.hacker.or.jp

「業界内の声を直接届ける」役割に微力ながら貢献できればと思います。

締め切りはWebのフォーム提出が2020年4月1日午前0時まで。原本送付はこの2週間後までです。

やり方

手順は池澤あやかさんのNoteの記事を参考にしました。

note.com

だいたい同じですが自分の場合は以下のやり方で進めました。

1. 意見書の提出フォームからWordファイルをダウンロード
2. 手元のMacで内容を編集
3. 印刷して署名。捺印不要とのことで捺印なし。これが原本となる
4. スキャンしてPDF化。
5. 意見書の提出フォームにPDFを送付
6. 原本を封筒に入れ、ハッカー協会指定の住所に送付。切手はコンビニで購入してそのまま貼付けた

意見書の記述から発送までトータルで90分ほどかかりました。

感想

正直言うと意見書募集を見かけてからこれまで、手順がちょっと面倒なので後回しにしていました。あまりふだんしないタイプの作文をしたり原本を送付したり…。

僕と同じように高裁の判決に異議を持っていたり、モロさんを応援したいと思いつつも意見書の作成・提出を億劫だと感じている人も少なくないと思いますが、少しの手間を惜しんだことを最高裁判所で望まない結果が出た後で後悔するよりは遥かにマシだと自分は思いました。

繰り返しますが締め切りはWebのフォーム提出が2020年4月1日午前0時まで、原本送付はこの2週間後までです。思い立ったら後回しにせずに行動されると良さそうです。

参考にした記事/サイト

• コインハイブ事件について控訴審のご報告と意見書募集のお願い｜モロ｜note
• なんでコインハイブ事件が有罪だとヤバイの？人のPCでお金儲けしてたんだから有罪でしょ！って人に簡単に説明する ver 0.22｜せせり｜note
• 違法マイニングとされたcoinhiveの法と技術のはなし | ここは3.11後の日本
• 罪刑法定主義をわかりやすく解説 | 日本国憲法の基礎知識 -憲法の試験対策などにも-
• なぜ「逆転有罪」に？ コインハイブ裁判、東京高裁が無罪判決を棄却した３つのポイントを解説 - ねとらぼ

---

最後に参考までに自分の意見書の内容を貼っておきます。

法に疎いので頓珍漢なことを書いているかもしれませんが自分の意見として以下を主張しました。

• 高裁の判決に反対であるということ
• その理由は判決が刑法の拡大解釈であり、このような解釈がまかり通るとソフトウェア産業のみならず公益を害するような影響も起こり得るという予見

意見書の内容

私は日本国内にて勤務するソフトウェアエンジニアです。業務においてはWebサービスを開発し、趣味でもWebサービスの制作やオープンソースソフトウェアの開発に携わっています。業務・趣味のどちらにおいてもJavaScriptを用いています。

私自身はCoinhiveを使ったことはないのですが、報道で一連の事件を知り、自分の関わる業務および業界の行末と無関係ではないと考え、意見を申し上げます。

弊社の製品のみならず2020年の一般的なWebアプリケーションにおいてはごく一部を除いてJavaScriptが使用されております。警察庁のWebサイト https://www.npa.go.jp/ や最高裁判所のWebサイト https://www.courts.go.jp/saikosai/index.html においても使用されております。こうした状況においてCoinhive事件が有罪となった時に与える社会的な影響について述べます。

刑法第168条の2の中にて「閲覧者の意図に反する動作をさせるもの」（反意図性が認められるもの）が不正指令電磁的記録にあたると定義されていますが、Webサイトの閲覧者が訪問先のWebサイトにて供されるJavaScriptの動作を意図することは私のようなソフトウェアの専門家でも極めて困難です。

例えば上記サイトの警察庁のWebサイトに私が「台風19号の情報を知りたい」という意図で訪問したとします。するとGoogle AdSense（オンライン コンテンツから収益を得ることができるサイト運営者向けのサービス）に関するJavaScriptファイル（ https://cse.google.com/adsense/search/async-ads.js ）がWebブラウザに読み込まれ、訪問履歴が第三者に提供されます。これは訪問者の利便性とサイト運営者の収益を両立させるための仕組みではありますが、不正指令電磁的記録の拡大解釈をすれば、私の意図とは反する挙動をするため反意図性があり、また、この同Webサイトにアクセスした私のコンピュータ資源を私に断ることなく利用して収益を得ている可能性があるので反社会性がある、不正指令電磁的記録にあたると指摘をすることができます。高裁による判決はこのようなものであったと私は理解しております。

しかしこのようなことはあってはならないと私は考えます。上述のようにWebサイトにて動作するJavaScriptの大半は閲覧者の利便性とサイト運営者の収益・事業継続などを両立させるための仕組みとして存在しているからです。意図しない動作をしたからといって、コンピュータ資源を断りなく使用して収益を得たからといって、こうした仕組みを廃する方向に舵を切れば現代のWebサイトの大部分はその用を成すことができなくなり、ソフトウェア事業の多くが立ち行かなくなります。選挙や災害等の国民の生活に必要な情報をWebサイト等を通じて届けることもできなければ、COVID-19における感染拡大防止のために自宅で業務を行なったりオンライン学習したりすることもできません。私が従事する産業だけの問題ではなくなると考えております。

最後に私の意見をまとめます。

・刑法第168条の2および3の恣意的な運用、曖昧な基準や拡大解釈による処罰の横行について強く反対する ・犯罪とされる行為の内容、及びそれに対して科される刑罰を予め、明確に規定していない状態でのCoinhive有罪判決は罪刑法定主義に反すると考える ・これらの刑法が制定された本来の目的である悪質なコンピューターウイルスやハッキングの取り締まりに立ち返るためにも、最高裁では適正な判決を望む

以上