FOSS でハードウェア開発を行う

ハードウェア開発につかうツールチェインはベンダー製ソフトウェアが多いが、 利用する FPGA によっては FOSS ツールチェインでも可能なようだ。 Fomu に載っている iCE40 はビットストリームの解析が完了しているため、 すべての工程を FOSS ツールで完結で…

Fomu 事始め

USBスロットに収まるサイズののFPGAデバイスで6000円ぐらいでCrowd supplyで購入できる。 自分の場合はストックがあったので、発注してからUPSで3日ぐらいで届いた。 搭載しているFPGAはLatticeのiCE40UP5kというものを積んでいるらしい。 全然わかっていな…

CMU 15-445 Logging Protocols + Schemes

バッファプールの書き出しは2つのポリシーに分解できる Steal はコミット前のデータを書き出すか Force はコミット時にダーティなデータを書き出すか Shadow paging master copy と shadow copy を作って、書き込みを shadow に行い、commit 時にスワップす…

CMU 15-445 Multi-Version Concurrency Control

MVCC は複数バージョンを持つことで、writer は reader をブロックせず、reader は writer をブロックしない writer がロックを取っていても reader は前のバージョンを読めば良いのでブロックされない 逆に read していても writer は新しいバージョンを作…

CMU 15-445 Timestamp Ordering Concurrency Control

Timestamp Ordering Concurrency Control optimistic な方法 2PL がロックを使ってserializableになるのに対して、serializableでないならアボートしてリトライする トランザクションの実行時にタイムスタンプをふって、自分が触ったオブジェクトが、より新…

EFI system partition を拡張する

EFI system partition(ESP) の容量が足りなくて、ファームウェアアップデートが失敗したので拡張した。 今回は、ESP の後ろに別のパーティションが存在し、そのままではパーティションのサイズ変更ができなかった。 そのため、ESP を空き領域に作り直して内…

CMU 15-445 Two-Phase Locking Concurrency Control

dependency graph はスケジュールを与えられたときにserializeかどうかを判定する方法 クエリをserializeに実行するにはどうするか? lock を使う 2 Phase Locking grow phaseとshrink phaseがある 前者ではロックを取ること、後者は開放することしかできな…

CMU 15-445 Concurrency Control Theory

トランザクションの性質としてACIDがある 一番簡単な方法はシングルスレッドで実行して、データベースファイルをコピーして、書き換えてスワップすること Aを守る方法としては shadow paging と logging がある schedule について serial schedule とはトラ…

The Ubiquitous B-Treeを読んだ

B+-Treeのデリート時のロジックがいまいちわからなかったので、B+-Treeに最初にフォーマルに言及したというこの論文を読んだ。 この論文自体はサーベイみたいな感じで、B-Treeのアルゴリズムやそのバリエーションなどを記載している。 複数ユーザーが平行に…

CMU 15-445 Query Optimization

query rewrite rule based optimizer 一般に可能なクエリの書き換えを行う selection は可能な限り先に行うと上で扱うデータ量が減る cost based optimizer 実データをもとにクエリプランを考える データの分布を一様分布として扱うと楽だけど実際はそんなこ…

CMU 15-445 Joins

特にequal joinを扱う N =num of outer table blocks, M = inner nested loop join simple nested loop join outer table のタプルごとにinterのblockを舐める block nested loop join outer tableのblockごとにinterのblockを舐める 仮にouterを保持してお…

CMU 15-445 Sorting + Aggregationsのメモ

データがメモリに収まらない場合を想定する Sorting 結果セットをページ内でソートしてディスクに書く 2つのソート済みページを取り出して比較してページを埋めて、溢れたらディスクに書く 利用するページは入力2つ、出力1つで3ページしか使わない Aggregati…

CMU 15-445 Query Processingのメモ

processing model iterator/volcano model タプルを一つ一つ返すモデル materialization model 一気にデータを返すモデル vectorized model バッチでデータを返すモデル optimization zone map page内のタプルにアグリゲーションを予め行ったページを記録し…

CMU 15-445 Hash Tablesのメモ

ここ最近のRDBはhashに次のものを使っている murmurhash cityhash farmhash clhash static hashing linear probe hashing コリジョンがあればその後ろの空きスロットを使う robin hood hashing 自分が入りたかったところからいくつ追い出されたかの値を持っ…

CMU 15-445 Buffer Poolsのメモ

buffer poolの要素をframeという in memory heap file の page がそのままメモリに乗ったもの page table は in memory データ構造で page id から frame を参照するもの 複数スレッドから触るので適切に pin する コンテンションになりやすいのでよく分割さ…

CMU 15-445 Database Storage Iのメモ

ハードウェアページは典型的には4kb この単位で書き込む場合、all or nothingで書ける DBのファイルはheap fileをよく使う ページ単位で読み書きできるAPI heap fileの実装はpage dictionaryをよく使う link listだと効率が悪い page layoutはslotted pageを…

systemd-resolvedで特定ドメインのDNSSEC検証を無効にする

arch linuxのsystemd 239から、systemd-resolvedでDNSSECでの検証がデフォルトで有効になったらしい。 手元の環境では、自分で所有しているが、実際に存在する名前を使って権威サーバを立てているために、DNSSECでの検証が失敗してアドレスが引けない問題が…

distrobuilder で lxc 用のイメージを作る

lxc 3.0 ではコンテナイメージ作成に使われていたテンプレートスクリプトが削除されて、 https://github.com/lxc/lxc-templates に移動された。 今後は distrobuilder を使うのがおすすめらしい。 ということで distrobuilder でイメージを作ってみる。 dist…

linux kernel library で遊ぶ

AsiaBSDCon 2018 で linux rumpkernel についての発表があったらしく気になっていた。 Linux rumpkernel - ABC2018 (AsiaBSDCon 2018) from Hajime Tazaki www.slideshare.net 当日は参加していないのでわからないが、linux kernel をライブラリとして使って…

Ceph storage backend bluestore について

分散オブジェクトストレージ Ceph はそのバックエンドとして、ファイルシステムを使う filestore の他に、ブロックデバイスを使う bluestore をサポートしている。 bluestore については公式ブログの記事 や slideshare に概要がある。 大雑把に書くと、メタ…

LevelDB のルックアップ

今更という感じだが、LevelDB について調べた。 table_format にあるように、LevelDB の SST の中身は block に分かれている。 block のなかは key-value の組が複数個入っている。 block ではキーのプレフィックスを圧縮したり block そのものを圧縮してい…

Transactional write の調査: MySQL 編その2

前回は主に redo log を調査した。 InnoDB ではいわゆる redo log は MTR によって実装されていることがわかった。 今回はロールバック周りを見ていく。 redo log があれば ACID を実装することが可能なのは SQLite で調べたとおりだが、InnoDB は MVCC なの…

Transactional write の調査: MySQL 編

引き続き trx write の実装について調べていく。 今回は MySQL を見ている。 MySQL はめちゃくちゃたくさんログを書いているしどれが何をしているのかというのは初見ではわかりにくい。 実際にトランザクションに関係するログは、innodb_log_* 系で設定する …

Transactional write の調査: SQLite wal 編

今回は、SQLite の wal モードについて調べた。 こちらもドキュメントが豊富で、以下の2つが参考になる。 Write-Ahead Logging Database File Format wal モードは、redo log のみを使って永続化を行っている。 書き込みの時に以下のような動作を行う。 wal …

Transactional write の調査: SQLite rollback journal 編

プログラミングをしていると、電源断などの障害時でも不整合が起こらないようにデータを保存したいという要求がしばしばある。 通常こういう要求は DBMS やライブラリなどで担保することになるわけであるが、データ自体が DBMS に収まらない場合、 2 phase c…

64ZiB ほしい!

SCSI プロトコルでは、デバイスの容量を取得するために、READ CAPACITY(10) や READ CAPACITY(16) を提供している。 これらのコマンドは、Logical Block Address(LBA) とロジカルブロックのバイト数でのサイズを返すことができる。 (10) と (16) の違いは、…

VirtIO と TCMU

VirtIO は準仮想化のフレームワークで、ゲストOSで特別なハードウェアを用意して VMM と直に通信する方法を提供してくれる。 実装的には virtqueue というメモリ空間をゲストと VMM で共有することでデータ送受信を可能にしているらしい。 ここまでは良いの…

tcmu と IO スケジューラ

前回、tcmu でブロックデバイスを作ってみたが、思ったより性能が出なかった。 IO completion が遅いのだと思ってスレッド化してみたが、もとより少々遅くなってしまった。 ところがふと、IO スケジューラを確認してみると、cfq スケジューラを使っているこ…

tcmu でブロックデバイスを作る

tcmu は LIO のバックエンドの一つで、UIO を使って SCSI をコマンドをユーザーランドと通信する。 ドキュメントがかなり詳しく書いているのでわかりやすい。 https://www.kernel.org/doc/Documentation/target/tcmu-design.txt SCSI コマンドやデータのやり…

NBD で複数ソケットを使う

NBD では 4.10 から一つのブロックデバイスに対して複数のソケットをアサインすることができるようになった。 github.com github.com 前回使ったコードを適当に変更して複数ソケットをマルチスレッドでさばくようにした。 また fio で適当に計測してみた。 #…