はてなブックマーク

読書: 計算量とマスター定理 マスター定理の意味を押さえたい。周辺を整理して押さえた上で漸近計算量の見積もりをやれるようになりたい。 マスター定理は分割統治法による時間計算量を求める定理です。分割統治法では下のような漸化式が出てくることがしばしばある。 \[ \begin{aligned} T(n) = & \begin{cases} aT(n/b) + f(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c,n_0,a \ge 1, b \gt 1 \end{aligned} \] ここでは \( f(n)\) は正則関数が想定されています。 この式に対して時間計算量\( T(n)\)の陽関数を求めるために使われる定理がマスター定理です。 マスター定理では適用に分岐

少し前にちょっとだけ出た HTAP というバズらなかったバズワード。 MariaDBは押している(?)。 HTAP はインメモリデータベースよりも曖昧で産業よりな言葉だ。 あいまいな言葉だけどインメモリデータベースより広く 新しいデータベース を指す用語なので今回は使ってみる。 HTAP の目標と関連実装の雰囲気をSIGMOD'17 のチュートリアルから知れる。 学術的な整理ではないし非難も多いけど、いくつかの実装へリファレンスがあり勉強のとっかかりになった。 今回は HTAP の一応の目標や出てきた背景と関連したインメモリデータベースとかの列挙をしてみる。 HTAPの背景 HTAP はラムダアーキテクチャから進歩するぞ！的なスローガンになっている。 ラムダアーキテクチャはApache StormのNathan Marzがデータを処理する流れについて提案したアーキテクチャ。 これはデータ処

去年の夏前くらいにDDDまわりの勉強していた。でこのメモを書いていたので少し直して晒してみる。 前回の続編。 前回、戦術的モデリングの最後に「実装ではアプリケーションレベルでの難所があるよなぁと思った」と書いたのでその辺りを考える。 難しさは主にトランザクションにある。 トランザクションはアプリケーションレベルの概念でドメインでは直接は扱わない。 ドメイン駆動設計(DDD)でドメインレベルで関連する概念に集約がある。 今回はまず一貫性境界となる集約とライフサイクルに関わるファクトリとリポジトリについて考えてみる。 集約やファクトリ・リポジトリによる表現が扱いにくさを生む側面について考える。 そのあとサブコンテキストごとにサービス化を行うマイクロサービス(MS)・サービス指向アーキテクチャ(SOA)で出てくる問題について触れる。 最後に、コード実装上の選択肢で悩みがちなところをまとめておく。

SQLite3 の勉強を放置しているうちにSQLite4が出ていた。 なので今回はThe Design Of SQLite4の超訳(すっとばし)と補足を書く。 SQLite3 を読んでSQLiteは標準のB-Treeを基盤に仮想テーブルを使って色々なデータ構造をSQLで糊付けする抽象化層ライブラリってイメージを持っていた。 SQLite4 は各コンポーネントの責任範囲を明確にして全体を単純に扱えるようにしている印象を受けた。 例えば、プラガブルなストレージエンジンの採用は、データモデル(トランザクション・データ構造)を処理全体で一貫するように強制させている。 これは元々あったテーブル単位でのデータ構造切り替え(仮想テーブル)よりトランザクションのサポートなどが単純化され扱いやすくなると思えた。 また実行環境オブジェクトは複数のDB接続をユーザー側で明示的に管理しないといけなくしている。 参

HTTP, TCPで検索・分析を実施できる分散検索クラスタ Elasticsearchは、様々なユースケースを解決する、分散型RESTful検索/分析エンジンです。 予期した結果やそうでないものまで検索できるようにデータを格納するElastic Stackの中核です。 ElasticsearchはHTTPで操作できるLuceneクラスタみたいなもので。構造型データ・非構造型データ・地理情報・メトリックなど広く扱える。 検索以外にもAggregation, Suggestionも提供されている。 今回は後で調べやすくなるように基本的な資料のリンクをまとめて概念を整理する。 その後で他のエコシステムとの繋がりや周辺ツールについて紹介する。 最後に運用上の注意事項や実際の利用の参考資料を載せる。 基本的な情報収集場所 下に各種資料が集められてるので公式ドキュメントの他に読んでおくといい。 Els

SQLiteではレジスタ型仮想マシンのバイト命令がBTreeを操作している。 またバイトコード生成はLALR(1)構文解析器の(cmd)非終端記号の還元時(reduce)に生成されていた。 仮想マシンは仮想データベースエンジン(VDBE)と呼ばれておりBTreeコンポーネントを操作する。 今回はバイトコード実行時のVDBEの挙動を調べる。 命令(OpCode)や変数が多くて辛いため、簡単なSQLを実際に追いながら命令や変数を説明する形で進める。 仮想マシンの動きを追う準備 仮想マシンの動きを追う2.8をベースにしている資料がある。 今更だけど、これを読むのが早い気がする。ただ3系と2系では一部の命令(ResultRow, Callback)が異なる。 各命令資料はOpCodeにまとまっている。 用語の事前準備 まずは頻出する概念の説明をしておく。 仮想データベースエンジン(VDBE) 命令

今回やった事は以下の3つ。 ログ・メトリック・イベントの保管・監視をする目的と必要な機能を整理 監視にまつわるSaaSを集めて眺めた 機能を比較して面白そうな事や注意した方が良さそうな事を考えてみた やってみた感想 感想は下に並べておく。詳細は読む必要はあまりない。 監視・通知の目的自体について 監視・通知の目的や技術については綺麗に整理できなかった いくつか体系的な知識がある事が分かったので勉強しておきたい 監視について 面白そうな事や需要がありそうな領域で未実装な事がたくさん残っていそう 仮想化が進むと監視対象の追加や除去などメンバーシップ管理が複雑になるので勉強しておきたい(いい記事があった) システムに依存する関係で、新しい設計方針やワークフローや依存インフラが出るたびに必要な領域が増える感じがする 用件を真面目に考えたり、OSSの採用や内製を検討せずにSaaSを選ぶなら下が無難だ

dstatのコマンドオプションが多くて便利なので定番の組み合わせを整理してまとめた。 使えるオプションの確認 以下のコマンドでdstatについて調べられる。 これによると機能拡張は/usr/share/dstat/にモジュールを置けば良さそう。 ミドルウェア作ったらdstat用のpluginを提供するの良さそう。 # ヘルプを表示する $ dstat -h # 使えるモジュールを一覧表示する $ dstat --list internal: aio, cpu, cpu24, disk, disk24, disk24old, epoch, fs, int, int24, io, ipc, load, lock, mem, net, page, page24, proc, raw, socket, swap, swapold, sys, tcp, time, udp, unix, vm /us

JSON Schema を使ってみた。今回の内容は2つ。 JSON Schema への参考資料のリンクを整理する PHPでバリデーションのサンプルをメモする JSON Schema について JSON はJavaScriptのオブジェクト表現をベースにしたデータ記述言語で様々なデータ構造を記述できる。 データがあると型・メタ情報を扱いたくなる。JSONデータに対するスキーマ定義の仕様が幾つかある。 JSON Schemaは有力候補の1つ。 JSON Schema 資料集 公式ドキュメントは以下のdraftへのリンクを掲載している。 JSON Schema: core definitions and terminology JSON Schema: interactive and non interactive validation JSON Hyper-Schema: Hypertext