Posts

Parallel Database Systems: The Future of High Performance Database Systems

データベースの処理性能を上げる手段として、特殊なハードウェアをもちいたり、メモリやディスクを共有した複数のコンピュータを使ったりするよりも、安価で単純に実装できることから、汎用的なコンピュータによる水平パーティションのシェアードナッシング構成を支持した。 論文が発表された1992年の時点でTeradataやTandem NonStopなどのパーティンション化されたデータベースがある。

Chain Replication for Supporting High Throughput and Availability

ストレージサーバーに順番をつけ、順にオブジェクトを複製することで、ストレージサービスの一貫性を維持しつつスループットと可用性の向上をはかる。 ここでのストレージサービスは、オブジェクトを保存し、クエリに対して一つのオブジェクトを返し、アトミックに一つのオブジェクトを更新できるものをさす。 また、一貫性は、オブジェクトごとにクエリと更新を直列的に適用し、更新につづくクエリが更新内容結果になることを意味する。 末尾のサーバーがクエリを受信し、該当するオブジェクトをクライアントに返す。 先頭のサーバーが更新リクエストを受信し、順にサーバーのオブジェクトを更新し、末尾のサーバーが更新の結果をクライアントに返す。

Implementing Remote Procedure Calls

Xeroxのプログラミング環境Cedarのために開発されたRPCを解説した84年の論文である。 RPCの開発目的は、分散コンピューティングを簡単に実装できるようにする、通信時間を短くする、通信をセキュアにすることの3点である。 RPCは大部分でMesaが使われた。

Dremel: Interactive Analysis of Web-Scale Datasets

Dremelは2006年からGoogle社内で利用されているDWHで、社外にはBigQueryとして提供されている。 列指向の形式でデータを保存し、SQLに似た言語のクエリでデータを検索できる。 Dremelは、サーバーのクラスタを木構造に組織し、ルートで受理したクエリの処理を下層のサーバに分配し、その結果を集約することで処理を分散し高速化をはかる。

Is Rust Used Safely by Software Developers?

crates.ioに登録された15,097個のクレートにおけるunsafeキーワードの使用状況を調べた。 調査したクレートは、調査を開始した2018年9月時点でcrates.ioに登録された全クレートの81%にあたる。 unsafeを含むクレートは、そのうちの29%だったが、依存するクレートにあるunsafeも対象にすると、50%におよぶ。 crates.ioの総ダウンロード数のうち90%を占める473個の有名なクレートに限定すると、60%のクレートunsafeが含まれる。 2018年9月から2019年6月までの10ヶ月間でunsafeの使用傾向に変化はなく、unsafeの数が少し増えただけであった。 unsafeの用途の大半はunsafeで修飾されたRustの関数を呼び出すためだった。 なお、コンパイラで生成されたunsafeキーワードは集計に含まれていない。

Design Tradeoffs for SSD Performance

HDDの処理性能を測定するシミュレーションソフトDiskSimをSSD向けに改造し、SSDの設計における選択肢の分類と選択にともなうトレードオフを報告した。 主要な選択肢は、論理アドレスと物理アドレスのマッピング、ページサイズ、オーバープロビジョニング、複数のpackageでcontrollerに接続するピンを共有するgangingがある。

Program Comprehension and Code Complexity Metrics: An fMRI Study

コードの複雑さのメトリクスがコードを理解する難しさの指標になるかは疑問視されてきた。 19人の被験者に16個のソースコードを読ませ、関数の返り値を回答してもらい、作業中の脳の状態をfMRIで観察することで、メトリクスと回答時間、正答率、脳の活性状態の相関関係を調べた。 メトリクスと主観的な評価を比較するために、回答後に被験者にコードの複雑さを評価してもらった。 調べたメトリクスは、41種類あり、コードの行数(LOC), 語彙の多さ(Halstead), とりえる実行パスの数(McCabe), 依存するデータの数(DepDegree)の4種類に大別できる。 相関関係をケンドールの順位相関係数\(\tau\)で評価し、相関なし(\(\tau <0.1\)), 弱い(\(0.1 < \tau < 0.3\)), 中(\(0.3 < \tau <0.5\)), 強い(\(0.5<\tau\))とみなす。

回答と脳の活性状態と相関関係にあったメトリクスはDepDegreeだったが、被験者の主観的な評価のほうが強い相関がみられた。 LOC, Halstead, DepDeegreeは回答時間や正答率と弱い〜中程度の相関があった。 この3つのメトリクスは脳の活性度合いと弱から中の相関があり、活性度合いと正答率には強い相関、回答時間には弱から中の相関があった。 一方、主観的な評価は、メトリクスと弱い相関があり、問題の正答率や脳の活性状態と強い相関関係があった。

The UNIX Time-Sharing System

デニス・リッチーとケン・トンプソンによるPDP-11/40, /45, /70で採用されたUnixのファイルシステムとコマンドラインインターフェースの解説である。 PDP-11は1971年2月から運用がはじまり、当初はアセンブリ言語で実装されていたが、1973年の夏にCで再実装された。 ファイルシステムは、UNIXの最も重要な役割に位置づけられ、特殊ファイルによるI/Oデバイスの抽象化、外部ディスクのマウント、ファイルの権限、i-nodeをふくむ多くの特徴が今日まで引き継がれている。 2人は、UNIXの設計に影響したものとして、プログラマとして対話的なインターフェースを望んでいたこと、ハードウェアの低い性能ゆえにソフトウェアの設計を洗練させる必要があったこと、ソースコードをUNIX上で編集し簡単にプログラムを変更できたことをあげている。

What helped, and what did not? An Evaluation of the Strategies to Improve Continuous Integration

TravisTorrentにある100件のプロジェクトで10種類のCIのテクニックを定量評価した。 テクニックは、不要なビルドやテストをスキップするか、実行順序を優先づけるものかに分かれる。 前者は計算資源の消費を減らすこと、後者は失敗するケースを早めに実行することを目的にする。 もっとも成功するテストやビルドをスキップできたテクニックは、コードに変更のないケースをスキップするものだったが、同時に失敗するテストを多く見落とした。 実行順序を優先付ける手法で最も性能のよかったテクニックは、Thomasらのもので、シグネチャやコメントで学習したトピックモデルを使い直前に実行したテストと違うトピックのテストを実行する。

Don't Do That! Hunting Down Visual Design Smells in Complex UIs against Design Guidelines

2020年5月時点のマテリアルデザインの公式ドキュメントから93種類の不吉な匂いを洗い出し、71種類の匂いを検出するツールUIS-Hunterを開発した。 文中に"don’t"や"caution"があることとUIの画像があることを条件に不吉な匂いを選び、9,286個のアンドロイドアプリにある7,497のUIを調べたところ、2,587個のアプリから1つ以上の不吉な匂いのあるUIが見つかった。 UIS-Hunterは、FigmaやAndroid Studio Layout EditorなどのモックアップやAndroid UI AutomatorやSeleniumのスクリーンショットから不吉な匂いを解析し、UIのソースコードを必要としない。 9,286個のアプリの60,756のUIで検出性能を評価したところ、precisionが0.81, recallが0.90だった。