Pythonでlsコマンドを実装したので、パフォーマンスを計測する②

はじめに

Pythonで ls コマンドを実装したので、パフォーマンス計測してみました。

Unixのtime コマンドを使うと、コードの内部実装に依存せずに、プログラムの実行時間を計測できます。 今回は、シェル内蔵の time とシステムの time を使って計測してみました。

Unixのtimeコマンドで計測する

Unix系の環境では、time コマンドを使って、プログラムの中に計測用のコードを書かなくても、 外側から実行時間やCPU使用時間を確認できます。

time には大きく分けて2つの種類があります。

  • シェルに組み込まれているシェル内蔵の time
  • 独立したコマンドとして提供されているシステムの time（/usr/bin/time）

シェル内蔵のtimeで計測する

Unixシェル（bash や zsh など）には、time が組み込みで用意されています。 このシェル内蔵の time を使うと、コマンドの実行時間を手軽に確認できます。

zshの time は外部コマンドではなく予約語として実装されており、 出力形式は TIMEFMT 変数で制御されます。

🔗 The Z Shell Manual – time reserved word https://zsh.sourceforge.io/Doc/Release/Shell-Grammar.html#index-time

🔗 The Z Shell Manual – Parameters Used By The Shell (TIMEFMT) https://zsh.sourceforge.io/Doc/Release/Parameters.html#index-TIMEFMT

$ TIMEFMT=$'real %*E\nuser %U\nsys  %S'.  
$ time pyls

real 3.295
user 1.15s
sys  0.41s
  • real: コマンドの呼び出しから終了までの経過（実）時間
  • user: ユーザー空間（カーネル関数以外）で消費されたCPU時間
  • sys: カーネル空間（カーネル関数）で消費されたCPU時間

userとsysを足せばCPUを使用した時間がわかります。 この値とrealの差は主にI/O待ちに相当します。
real, user, sysの定義は、POSIX の time ユーティリティで定義されている意味と同じです。

システムのtimeを使う

システムのtimeを使うと、より詳細な計測値を得ることができます。

-p オプションをつける

/usr/bin/time -v pyls

real 3.44
user 1.23
sys 0.40

/usr/bin/time を明示的に指定することで、 シェル内蔵ではなくシステムの time コマンドを使用できます。

-pオプションを指定すると、POSIX で定義された形式 （real / user / sys）で結果が出力されます。

-v オプションをつける

Linux 環境では、/usr/bin/time は GNU time として提供されています。

-vオプションをつけると、詳細な計測値を得ることができます。

$ /usr/bin/time -v pyls

Command being timed: "pyls"
        User time (seconds): 1.56        
        System time (seconds): 1.06     
        Percent of CPU this job got: 31%                
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:08.45 
        Average shared text size (kbytes): 0     
        Average unshared data size (kbytes): 0          
        Average stack size (kbytes): 0                         
        Average total size (kbytes): 0                               
        Maximum resident set size (kbytes): 148516          
        Average resident set size (kbytes): 0                                   
        Major (requiring I/O) page faults: 4                                    
        Minor (reclaiming a frame) page faults: 37222              
        Voluntary context switches: 101234                               
        Involuntary context switches: 49                                  
        Swaps: 0
        File system inputs: 0
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0

対応表

time の表示 rusage フィールド 意味
User time ru_utime ユーザー空間で消費した CPU 時間
System time ru_stime カーネル空間で消費した CPU 時間
Percent of CPU this job got ―（派生値） 平均 CPU 使用率（(user + sys) / real）
Elapsed (wall clock) time ― 開始から終了までの実時間
Average shared text size ru_ixrss unused
Average unshared data size ru_idrss unused
Average stack size ru_isrss unused
Average total size ― unused
Maximum resident set size ru_maxrss 実行中に使用した最大常駐メモリ量（ピーク RSS）
Average resident set size ― unused
Major (requiring I/O) page faults ru_majflt ディスク I/O を伴うページフォルト回数
Minor (reclaiming a frame) page faults ru_minflt I/O を伴わずに解決したページフォルト回数
Voluntary context switches ru_nvcsw I/O待ちなどで自発的に CPU を手放した回数
Involuntary context switches ru_nivcsw 時間切れなどで強制的に CPU を切り替えられた回数
Swaps ru_nswap unused
File system inputs ru_inblock ファイルシステム入力回数
File system outputs ru_oublock ファイルシステム出力回数
Socket messages sent ru_msgsnd IPC メッセージ送信回数
Socket messages received ru_msgrcv IPC メッセージ受信回数
Signals delivered ru_nsignals unused
Page size (bytes) ― システムのページサイズ
Exit status ― コマンドの終了ステータス

この計測値でわかること

  • CPU 使用率が低く、CPU を使えない待ち時間が多い
  • I/O 待ちが多く、CPU バウンドな処理ではない
  • ディスク I/O を伴うページフォルトはほぼ起きていない
  • メモリ不足も起きていない

まとめ

  • Unix のシステムユーティリティやシェル内蔵の time を使って、プログラムの実行時間やリソース使用状況を計測できることがわかった
  • time -v の各指標は getrusage(2) に基づいており、Linux では未管理（unused）な項目も、歴史的経緯により残っていることが分かった
  • 次は Python の cProfile を使って、関数単位での実行時間を測定してみる

参考リンク

PythonでシンプルなRDBMSを自作してみた

はじめに

データベースの内部構造を理解したくて、Database Design and Implementation のSimpleDBを参考に、Pythonでデータベースを作ってみました。

実装方針

  • SimpleDB（Java版）の実装を忠実に追う
    • 色気を出さず、まずは動くものを作ることを重視
  • Pythonの標準ライブラリのみを使用
    • Pythonの学習目的も兼ねているため

開発・動作環境

keiPyDBでできること

  • ファイルベースでデータ保存
  • SQLライクな構文で以下の基本操作に対応
    • CREATE TABLE
    • INSERT INTO
    • SELECT
    • UPDATE
    • DELETE
  • シンプルなトランザクション、ロック、ログ管理

苦労したこと

バッファとスロット管理

  • 空いていないスロットを空いていると計算間違いしてしまい、何度も同じ場所にデータを上書きしてしまう(*1)

SQLパーサのトークン処理

  • SELECT id FROM のFROMがどこかに行ってしまって処理できない(*2)

トランザクションでデッドロックが終わらない

今後やりたいこと

  • テストコードの充実（まだ足りない部分が多い）
  • 対話型インターフェースを作り、SQLを直接入力して動かせるようにする
  • TCP通信する
  • 自作のブラウザを作ってkeiPyDBを載せる

おわりに

  • オブジェクト指向なので当然かもしれませんが、メソッド一つ一つはとてもシンプルなものでできていると感じました。
  • なので、 DBの仕組みの学習にはなりましたが、Pythonの学習としては、あまり向いていなかったように思います。
  • 低レイヤーの処理の理解が追いつかず、デバッグに苦労しました。

ソースコード

GitHub - kei-kmj/keiPyDB

  • *1 スロットは、ページ内を固定長で区切った領域です。本来、空きスロットを探してそこにデータを書き込みますが、そのロジックが間違っていました。

  • *2 字句解析（Lexer）によって、SQL文をトークン列に分解し、構文解析（Parser）でトークンを処理しますが、意図しないトークンまで処理していました

Pythonのrange() は stop の数字を含まない

Pythonのrange(start, stop)は、stopの数字を含まない仕様になっています。たとえば、range(1, 5)は [1, 2, 3, 4] となり、5 は含まれません。 しかし、時々、stopが含まれると思ってコードを書いてしまうミスをするので、range()について調べました。

range()の仕様

Python の公式ドキュメントでは、range() について次のように説明されています。

class range(start, stop[, step])
step が正の場合、range r の内容は式 r[i] = start + step*i で決定されます。ここで、 i >= 0 かつ r[i] < stop です。

stopを含まないことがわかります。

Dijkstra のメモ "Why numbering should start at zero"

この stopを含まない仕様の利点は、Dijkstra の "Why numbering should start at zero" というメモに示されています。

このメモについては、Fluent Python で紹介されていたので読んでみました。原文は以下のリンクから参照できます。

Why numbering should start at zero - E.W. Dijkstra

Dijkstra は、なぜ1,2,3,4,をrange(1,5)と記述するのが理にかなっているか、以下の点について数学的に説明しています。

  • 要素数の計算が stop - start で求められる
  • 隣接する range() の境界をシンプルに連結できる
  • ゼロから始めることで、数学的な性質が整理され、分割や計算が容易になる

stopを含む場合と含まない場合の、自分の勝手なイメージ

※あくまでも、私の勝手なイメージです。

stopを含まない場合、連続している数字の途中で、お巡りさんが通行止めしていて、その先には進めないイメージ

stopを含む場合、数字は枠の中で与えられるイメージ

まとめ

通行止めしているお巡りさんのイメージで、今後stopの値を間違えずに済みそうです🐰

Gitがどのようにコンフリクトを検知するのか知りたくなったので、ソースコードを読んでみた

Gitを使用していると、リベースやチェリーピック、マージ操作などでコンフリクトに遭遇することがよくあります。今回は、最も一般的な、マージ操作で発生するコンフリクトについて、Gitのソースコードを通してその検知ロジックを調べてみました

コンフリクトについて

  • Gitでは、同じファイルの同じ部分に対して異なる変更が行われたとき、自動でマージできない状態になり、変更の内容が一致しない部分について開発者に手動で解決を求める

Fast-Forward マージの場合

  • 単純にブランチのポインタを前に進めるだけ。この場合、コンフリクトは発生しない
A---B---C  (main)
     \
      D---E (feature)
  • この場合、Gitはポインタを進めるだけでマージが完了する
A---B---C---D---E (main, feature)

3方向マージの場合

  • マージ元とマージ先が異なるブランチ履歴を持つ場合、Gitは3方向マージを実行し、新しいスナップショットを作成する
  • この結果、マージされた変更を指す特別なコミット（マージコミット）が生成される。このコミットは複数の親を持つという特徴がある 例：
A---B---C (main)
     \
      D---E (feature)

この場合、mainにfeatureをマージすると、新たにマージコミットFが作成される：

A---B---C---F (main)
     \       /
      D---E (feature)

同じファイルの同じ部分を両方のブランチで異なる変更を加えた場合、Gitは自動でマージすることができず、コンフリクトとして報告する

ソースコードを確認

3wayマージのエントリーポイント

ll_merge 関数は、3方向マージのエントリーポイントで、

  • Base（共通祖先、ancestor）
  • Ours（現在のブランチ、ours）
  • Theirs（マージ対象のブランチ、theirs）

の3つのバージョンを受け取り、マージドライバの関数ポインタを通じて、対象がテキストファイルであれば、ll_xdl_mergeが呼び出される

# merge-ll.c
enum ll_merge_result ll_merge(mmbuffer_t *result_buf,
         const char *path,
         mmfile_t *ancestor, const char *ancestor_label,
         mmfile_t *ours, const char *our_label,
         mmfile_t *theirs, const char *their_label,
         struct index_state *istate,
         const struct ll_merge_options *opts)
...
        driver = find_ll_merge_driver(ll_driver_name);
...
    return driver->fn(driver, result_buf, path, ancestor, ancestor_label,
              ours, our_label, theirs, their_label,
              opts, marker_size);

テキストファイルのマージ: ll_xdl_merge 関数

  • ll_xdl_merge は、テキストファイルの3方向マージを実行するために、xdl_merge 関数を呼び出す
# merge-ll.c
static enum ll_merge_result ll_xdl_merge(const struct ll_merge_driver *drv_unused,
            mmbuffer_t *result,
            const char *path,
            mmfile_t *orig, const char *orig_name,
            mmfile_t *src1, const char *name1,
            mmfile_t *src2, const char *name2,
            const struct ll_merge_options *opts,
            int marker_size)

...
        status = xdl_merge(orig, src1, src2, &xmp, result);
...

3wayマージの実行: xdl_merge 関数

# xmerge.c
int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
        xmparam_t const *xmp, mmbuffer_t *result)
{
    xdchange_t *xscr1 = NULL, *xscr2 = NULL;
    xdfenv_t xe1, xe2;
    int status = -1;
    xpparam_t const *xpp = &xmp->xpp;

    result->ptr = NULL;
  • orig（Base）、mf1（Ours）、mf2（Theirs）を受け取り、resultにマージ結果を格納する。
 if (xdl_do_diff(orig, mf1, xpp, &xe1) < 0)
        return -1;

    if (xdl_do_diff(orig, mf2, xpp, &xe2) < 0)
        goto free_xe1; /* avoid double free of xe2 */
  • Base（orig）と Ours（mf1）の差分を計算し、結果を xe1 に格納
  • Base（orig）と Theirs（mf2）の差分を計算し、結果を xe2 に格納
 if (!xscr1) {
        result->ptr = xdl_malloc(mf2->size);
        if (!result->ptr)
            goto out;
        status = 0;
        memcpy(result->ptr, mf2->ptr, mf2->size);
        result->size = mf2->size;
    } else if (!xscr2) {
        result->ptr = xdl_malloc(mf1->size);
        if (!result->ptr)
            goto out;
        status = 0;
        memcpy(result->ptr, mf1->ptr, mf1->size);
        result->size = mf1->size;
    } else {
        status = xdl_do_merge(&xe1, xscr1,
                      &xe2, xscr2,
                      xmp, result);
    }
  • Base vs Ours の差分がない（xscr1 == NULL）場合：Theirs（mf2）の内容をそのままマージ結果としてコピー
  • Base vs Theirs の差分がない（xscr2 == NULL）場合：Ours（mf1）の内容をそのままマージ結果としてコピー
  • Base vs Ours と Base vs Theirs の両方に変更がある場合：xdl_do_merge を呼び出して、3方向マージを実行
static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
        xdfenv_t *xe2, xdchange_t *xscr2,
        xmparam_t const *xmp, mmbuffer_t *result)

    if (level == XDL_MERGE_MINIMAL || xscr1->i1 != xscr2->i1 ||
        xscr1->chg1 != xscr2->chg1 || xscr1->chg2 != xscr2->chg2 ||
        xdl_merge_cmp_lines(xe1, xscr1->i2, xe2, xscr2->i2, xscr1->chg2, xpp->flags)) {
        /* conflict */
        int off = xscr1->i1 - xscr2->i1;    // Base の位置ずれを計算
        int ffo = off + xscr1->chg1 - xscr2->chg1; // Ours と Theirs の変更量のずれ

        i0 = xscr1->i1;
        i1 = xscr1->i2;
        i2 = xscr2->i2;

        if (off > 0) {
            i0 -= off;
            i1 -= off;
        } else {
            i2 += off;
        }

        chg0 = xscr1->i1 + xscr1->chg1 - i0;
        chg1 = xscr1->i2 + xscr1->chg2 - i1;
        chg2 = xscr2->i2 + xscr2->chg2 - i2;

        if (ffo < 0) {
            chg0 -= ffo;
            chg1 -= ffo;
        } else {
            chg2 += ffo;
        }

        if (xdl_append_merge(&c, 0, i0, chg0, i1, chg1, i2, chg2)) {
            xdl_cleanup_merge(changes);
           return -1; // エラー処理
        }
    }
  • Ours と Theirs の変更の範囲や行数、実際の内容などの条件を満たすとコンフリクトとみなす
  • コンフリクト範囲を計算し、コンフリクト情報をリストに追加。競合マーカーとして出力される

まとめ

  • Gitは、コンフリクトを検知する際に3方向マージを用いる
  • このプロセスでは、Base（共通祖先）、Ours（現在のブランチ）、Theirs（マージ対象ブランチ）の3つのバージョンを比較し、差分を計算する
  • xdl_do_diff関数でBaseと各ブランチの差分を計算し、それらの変更セットをxdl_do_merge関数で比較する
  • 変更セットの比較では、行やブロックの範囲、行ごとの内容の違いを精査し、Baseと異なる変更がOursとTheirsの両方に存在する場合をコンフリクトとして検知する
  • 変更範囲が重なっていなくても、行内容の一致を判定するアルゴリズムを用いて、より精密にコンフリクト判定できる

参考書籍/サイト

Gitの内部構造について調べたメモ

これまで、なんとなく、Gitは、ファイルの差分を記録して管理しているのかと思っていました。
しかし、調べてみると、そうではなかったので、Gitの内部構造や、ファイルの扱い方について調べてみました。

Gitの内部構造

スナップショットとは

定義

  • Gitにおけるスナップショットとは、特定時点でのプロジェクト全体の状態を保存したもの

    特徴

  • すべてのファイルの状態を記録
  • 変更がないファイルはリンクを再利用
  • 差分ではなく、ファイルの内容そのものを管理

Git - Gitの基本

Gitはファイルの変更のリストを格納するのではなく、全ファイルの状態をスナップショットとして保存します。変更がないファイルは、既存のスナップショットへのリンクを利用します。

Gitオブジェクトの構造

Gitは、データを以下の4種類のオブジェクトとして管理する：

  • Blobオブジェクト（ファイルの内容）
  • Treeオブジェクト（ディレクトリ構造）
  • Commitオブジェクト（スナップショットと履歴）
  • Tagオブジェクト（リリースポイントなど） これらのオブジェクトは、SHA-1ハッシュをキーとするキーバリューストアとして保存される

Commitオブジェクト

  • スナップショットのメタデータ（親コミット、Treeオブジェクト、作成者、メッセージ）を管理

    内容の例

$ git cat-file -p <コミットのSHA>
tree 9331f3d9b062bc6ec18dc0de9309efc19148a7b4
parent 71405db34c12239de3ebb45fbbeee89c85df4c47
author user <email@example.com> 1682205017 +0900
committer user <email@example.com> 1682205017 +0900

Initial commit
  • tree: このコミットが指し示すTreeオブジェクトのSHA。プロジェクト全体のディレクトリ構造とファイルを辿る起点になる
  • parent: 親コミットのSHA。このフィールドが存在しない場合、そのコミットは「初回コミット」。通常、履歴を辿る際に使用される
  • author: この変更を作成したユーザーとそのタイムスタンプ
  • committer: 実際にコミット操作を行ったユーザーとそのタイムスタンプ
  • コミットメッセージ: コミットの説明

Treeオブジェクト

  • ディレクトリ構造を表現し、Blobオブジェクトや他のTreeオブジェクトへの参照を保持

    内容の例

$ git cat-file -p <TreeオブジェクトのSHA>
040000 tree 346c1b96f170b020afaab6a930d7bc53e1a0bc82    src
100644 blob 09b3f2614e65059d80df6841c75eab8be6ef2ee7    main.py
  • 040000 tree: srcというディレクトリを指し示している。Treeオブジェクトは他のTreeオブジェクトやBlobオブジェクトをネストすることができる
  • 100644 blob: main.pyファイル。ファイルの中身はBlobオブジェクトによって管理される

Blobオブジェクト

  • ファイルの内容そのものを保存
  • 重複する内容はSHA-1ハッシュを再利用
  • 差分ではなく、完全なファイル内容を格納

内容の例

$ git cat-file -p 09b3f2614e65059d80df6841c75eab8be6ef2ee7 | xxd
00000000: 2321 2f75 7372 2f62 696e 2f65 6e76 2070  #!/usr/bin/env p
00000010: 7974 686f 6e0d 0a22 2222 446a 616e 676f  python.."""Django

Tagオブジェクト

  • 特定のコミットを指し示すオブジェクトで、リリースやマイルストーンを記録する際に使用される
  • 注釈付きタグは署名、メッセージ、作成者情報などを含むメタデータを保持し、タグオブジェクトとして保存される
  • 軽量タグ（SHA-1参照のみ）は、特定のコミットを指す単純なポインタ

注釈付きタグの例

  • 作成方法 $ git tag -a annotated-tag -m "This is an annotated tag"
  • 確認方法
$ git show annotated-tag
tag annotated-tag
Tagger: kei-kmj <kei-kmj@example.com>
Date:   Thu Jan 16 19:45:18 2025 +0900

This is an annotated tag

commit 6c23956defcd7710dc228014c4bb27c554ebfb04 (HEAD -> main)
Author: kei-kmj <kei-kmj@example.com>
Date:   Sat Jan 11 10:58:42 2025 +0900

    Block numberのバグ修正

軽量タグの例

  • 作成方法 $ git tag lightweight-tag
  • 確認方法
$ git show lightweight_tag
commit aefb43cc91a9b03720fbda2f1cb9127ed48cb838 (tag: lightweight_tag)
Author: kei-kmj <kei-kmj@example.com>
Date:   Thu Jan 16 19:51:00 2025 +0900

まとめ

  • Gitは、ファイルの差分ではなくスナップショットとしてデータを管理する
  • スナップショットは、特定の時点でのプロジェクト全体の状態を保存
  • Gitは、Blob（ファイル内容）、Tree（ディレクトリ構造）、Commit（スナップショットの履歴）、Tag（特定ポイントのラベル）という4つの主要なデータオブジェクトを使用する

参考にした書籍/サイト

Database Design and Implementation Second Editionの読書メモ

link.springer.com

を読んで、PythonでDBを実装するための読書メモです。

Chapter 1Database Systems

概要

  • データベースは、コンピュータ上に保存されたデータの集合体
  • データベースシステムは、
    • システムクラッシュや更新による矛盾を防ぐ
    • ロールバック
    • コミット
    • 高速アクセスのためのデータインデックス
    • 同時アクセスの制御
    • メインメモリキャッシュと永続データの同期管理
    • テーブルクエリを実行可能なコードに変換するコンパイラ
    • 非効率なクエリを最適化

を提供する

  • データベースアプリケーションは、データ取得処理を行い、組み込み型接続やサーバーベース型接続を通じてエンジンと連携する

Chapter 2 JDBC

PythonでいうところのSQLAlchemyか。今回は無関係なので省略

Chapter 3 Disk and File Management

概要

  • データベースエンジンは、ディスクやフラッシュドライブなどの永続的なストレージデバイスにデータを保存する
  • ディスクドライブはディスクへのアクセスを3段階で実行
  • ディスクドライブの動作が機械的なものであるため、動作が遅い
  • データベースシステムは、ディスクへのブロックレベルまたはファイルレベルのインターフェースのどちらかを使用することができる
  • 良い妥協策は、データをファイルに保存するが、ブロックレベルでファイルにアクセスすること

実装

  • SimpleDBデータベースは複数のファイルに保存される
  • テーブルやインデックスごとにファイルがあり、ログファイルや複数のカタログファイルもある
  • SimpleDBファイルマネージャは、これらのファイルへのブロックレベルのアクセスを提供する
  • BlockId、Page、FileMgrの3つのクラスを公開している

BlockIdクラス

  • ファイル名と論理ブロック番号によって特定のブロックを識別
  • 責務
    • ファイル名とブロック番号を管理し、これらを基にブロックを一意に識別する
  • 機能
    • ファイル名とブロック番号の取得（fileName() と number()）
    • 等価判定
    • toString
    • ハッシュコード生成

Pagesクラス

FileMgrクラス

Chapter 4 Memory Management

概要

  • データベースのLogMgrは、ログファイルを担当し、シーケンシャルアクセスのみをサポート。単純で最適化されたメモリ管理アルゴリズムを使用する
  • バッファBufferMgrはデータファイルを担当し、任意のアクセスをサポートする必要があり、複雑で高度なアルゴリズムが必要
  • 両マネージャは、ディスクブロックの読み書きを主記憶装置で効率的に管理
  • データベースの内容が主記憶装置より大きいため、ブロックをメモリに出し入れする必要がある

実装

LogIteratorクラス

  • 責務
    • ログファイルの各レコードを逆順（最新から最古）に読み取る機能を提供する
  • 機能
    • ログレコードの取得
    • 現在のブロックを切り替える
    • 逆順アクセス

LogMgrクラス

  • 責務

    • ログレコード管理とログファイル永続化

  • 機能

    • ログレコードの追加
    • ログのフラッシュ
    • ログの読み取り
    • 必要に応じて新しいログブロックを作成し管理

  • メモ

    • スレッドセーフの考慮

Bufferクラス

  • 責務

    • ディスク上の特定のブロックをメモリ内で管理し、データの効率的な読み書きと状態追跡を行う

  • 機能

    • メモリ上にページ（Page）を保持し、データを読み込んだり、変更を追跡したりする
    • 指定されたディスクブロック（BlockId）をバッファに関連付ける
    • 既存データがあれば、ディスクにフラッシュしてから新しいブロックを読み込む
    • バッファが利用中かどうか（ピン状態）を追跡
    • 修正されたトランザクションID（txnum）とログシーケンス番号（lsn）を記録
    • ディスクへの書き戻し（フラッシュ）
    • バッファの再利用

  • メモ

BufferMgrクラス

  • 責務
    • バッファプールを統括管理し、ディスクブロックに対するバッファの割り当て・解放を行い、リソースを効率的に配分
  • 機能
    • バッファの割り当て
    • バッファの解放
    • バッファ状態の追跡
    • 変更のフラッシュ

Chapter 5 Transaction Management

概要

  • データベースエンジンには、順序を維持し、データベースの整合性を確保する役割を持つ同時実行マネージャとリカバリマネージャが用意されている
  • 同時実行マネージャは、これらのトランザクションの実行を制御し、一貫性のある動作を確保する
  • リカバリマネージャはログへのレコードの読み書きを行い、未確定のトランザクションによって行われた変更が必要に応じて元に戻せるようにする

実装

  • トランザクションのメソッドは3つのカテゴリに分類される
    • トランザクションの寿命管理
    • バッファをクライアントから隠蔽
    • 必要なデータをバッファから取得し、クライアントに返却

RecoveryMgrクラス

ConcurrencyMgrクラス

  • 同時実行時、トランザクションの操作は交互に実行され、これをスケジュールと呼ぶ
  • コンカレンシーマネージャは、正しいスケジュールのみを実行するよう制御する
  • スケジュールは、直列スケジュールまたは直列化可能スケジュールである場合にのみ正しいと認められる

  • 責務

  • 機能

    • 共有ロック（SLock）と排他ロック（XLock）の取得
    • トランザクション終了時のロック解放
    • ローカルロック情報の追跡

LockTableクラス

Chapter 6 Record Management

概要

-トランザクションマネージャは、ディスクブロック上の指定された場所の値を読み書きすることができる - しかし、ブロック内にどのような値があるか、またそれらの値がどこに位置しているかについては把握していない - この役割はレコードマネージャが担う - レコードマネージャーは、データベースシステムの一部分であり、レコードをファイルに保存する - レコードマネージャーには、以下の3つの基本的な役割がある。 - レコード内のフィールドの配置 - ブロック内のレコードの配置 - ファイル内のレコードへのアクセス提供

実装

RecordPageクラス

  • 責務
    • １つのブロック内でのレコード操作（挿入、削除、読み書き）を管理し、レイアウトに基づくスロット操作を提供する
  • 機能
    • フィールドごとのレコードの読み取り・書き込み
    • スロットの状態管理
    • 新しいブロックの初期化

Schemaクラス

  • 責務
    • テーブルのフィールド情報（名前、型、長さ）を管理し、他スキーマとの統合やフィールド情報の取得を提供する
  • 機能
    • フィールドの追加（整数型、文字列型）
    • フィールドの型・長さ情報の取得
    • 他スキーマとの統合

Layoutクラス

  • 責務
    • テーブルレコードの物理的な構造（オフセットとスロットサイズ）を管理し、効率的なストレージ操作を可能にする
  • 機能
    • フィールドのオフセット管理
    • スロットサイズの計算
    • スキーマ情報を反映したレコード構造の提供

TableScanクラス

  • 責務
    • テーブル全体のスキャンとレコード操作（読み取り・挿入・更新・削除）を提供
  • 機能
    • テーブルのスキャン
    • レコードの挿入、削除、更新
    • レコード位置の追跡

Chapter 7 Metadata Management

概要

  • メタデータとは、データベースの内容を除いたデータベースに関する情報

実装

MetadataMgrクラス

  • 責務
    • テーブル、ビュー、インデックス、統計情報といったデータベースメタデータの管理
  • 機能
    • 各管理クラス（TableMgr, ViewMgr, IndexMgr, StatMgr）に操作を委譲

TableMgrクラス

  • 責務
  • 機能
    • テーブル作成
    • テーブルのスキーマ、フィールドオフセット、スロットサイズの復元
  • メモ
    たぶん、CREATE TABLE文がクライアントから送信されると、パーサで解析され、パーサから渡されたテーブル名とスキーマ情報を使って、MetadataMgrのcreateTableメソッドが呼び出される。 TableMgr.createTableに制御を移譲

StatMgrクラス

  • 責務
    • テーブルの統計情報（レコード数、ブロック数）の計算と管理
  • 機能
    • 統計情報の提供
    • 統計情報の計算

Chapter 8 Query Processing

概要

  • SQLは「何を取得するか（What）」を記述する
  • 「どのように（How）」データを取得するかについては指定
  • データベースエンジンが「どのように実行するか」を決定する際に使うのが、関係代数（Relational Algebra）

実装

Scanインターフェース

関係代数の各演算子のスキャン機能を統一的に定義し、抽象化

SelectScanクラス

  • 責務
    • 基となるスキャン（Scan）に対してフィルタリング機能を提供し、指定された条件（Predicate）に一致するレコードのみを返す
  • 機能
    • フィルタリング、データ取得、更新

ProductScan クラス

  • 責務
    • 2つのテーブルスキャンを基にデカルト積 (Cartesian Product) を生成する。CROSS JOIN
  • 機能
  • 2つのテーブルスキャン (LHS と RHS) を受け取り初期化
  • 順次スキャン
  • メモ
    このProduct Scanに、on句の内容でフィルターすると、INNER JOINやLEFT JOINが実装できる

Chapter 9 Parsing

概要

  • 構文解析器 は入力文字列が構文的に正しいかを確認し、構文解析ツリーを構築する
  • 字句解析器 は入力文字列をトークンに分割し、各トークンにはタイプと値がある
  • 構文解析ツリー の内部ノードは構文カテゴリ、リーフノードはトークンを表す
  • 構文解析アルゴリズムは文法ルールに従ってツリーを構築し、文字列が正しい場合にのみルートからツリーが作られる
  • アルゴリズムの複雑さは文法の複雑さに比例し、単純な方法として 再帰下降法 がある

実装

Parser クラス

Lexerクラス

  • 責務
    • SQL文を構成する要素（キーワード、識別子、区切り文字、定数など）をトークンに分割し、それぞれのトークンを解析して扱える形に変換する
  • 機能

InsertDataクラス

  • 責務
  • 機能
    • テーブル名の保存と取得
    • フィールド名をリストとして保持
    • 各フィールドに対応する値をリストとして保持

CreateTableDataクラス

  • 責務
    • CREATE TABLE 文に関連する情報を保持する
  • 機能
    • テーブル名の保存と取得
    • スキーマ情報の保存と取得

Chapter 10 Planning

概要

  • データベースプランナーは、クエリを効率的に実行するため、必要なブロックアクセス数、出力レコード数、フィールドの異なる値の数を推定する
  • 各クエリに複数の等価なクエリツリーが存在する場合、それらのコストを比較し、最も低コストのプランを選択してスキャンを作成する
  • プランはクエリツリーのコストを見積もるもので、実際のデータにアクセスせず、メタデータのみを使用するが、スキャンは実際にクエリを実行する

Planインターフェース

  • 責務
    • クエリの実行に必要な操作（Scan）の提供
    • クエリのリソース使用量に関する見積もり
    • クエリのスキーマ情報の提供
  • 機能
    • クエリの実行
    • ブロックアクセスの見積もり
    • 出力レコード数の見積もり
    • 特定フィールドの一意値の見積もり
    • スキーマの取得

TablePlanクラス

  • 責務
    • 指定されたテーブルに関する計画（Plan）を生成し、クエリの実行に必要な情報を提供すること
  • 機能
    • テーブルのレイアウトと統計情報を取得
    • クエリ実行
    • ディスクブロックアクセス数の見積もり
    • レコード数の見積もり

BetterQueryPlanner クラス

  • 責務
    • 直積演算（ProductPlan）の計画を生成する際に、異なる順序のコストを比較して最小コストの計画を選択する
  • 機能
    • テーブル/ビューごとの計画を作成
    • 直積演算のコストを比較して選択
    • SelectPlanとSelectPlanを追加して実行計画を返す

Chapter 11 JDBC Interfaces

省略

Chapter 12 続く。。。

Pythonとバイナリストリームについて調べたメモ

バイナリストリームとは

  • データをそのままバイト単位で扱うための仕組み
  • この形式では、データの内容が文字列やテキスト形式に変換されることなく、そのままの状態で処理される

テキスト ストリームとバイナリ ストリーム | Microsoft Learn

バイナリ ストリームは、1 バイトまたは複数バイトの任意の情報で構成されます。バイナリ ストリームに任意のオブジェクトに格納されている値を書き込むと、オブジェクトに格納された内容を正確に読み取ることができます。

Python におけるバイナリストリーム

  • Python では、バイナリストリームを扱う際に bytes 型や io.BytesIO クラスを使用する
  • これらを使用することで、ファイルやメモリ上のバイナリデータを効率的に操作できる

読み書き

with open("example.jpg", "rb") as f:  # "rb" は読み込みモード (read binary)
    binary_data = f.read()  # バイナリデータを読み取る
    print(binary_data[:10])  # 最初の10バイトを表示

io.BytesIO を使用したインメモリのバイナリストリーム

io --- ストリームを扱うコアツール — Python 3.12.8 ドキュメント

  • io.BytesIO クラスを使用すると、ファイルを使用せずにメモリ上でバイナリデータを扱うことができる
import io

# 初期データを持つバイナリストリームを作成
binary_stream = io.BytesIO(b"binary data example")

# データの読み込み
print(binary_stream.read())  # => b'binary data example'

# 新しいデータを書き込む
binary_stream.seek(0)  # ストリームの先頭に移動
binary_stream.write(b"new data")

# 更新後のデータを確認
binary_stream.seek(0)
print(binary_stream.read())  # => b'new dataxample'

まとめ

  • バイナリストリームは、データをバイト単位でそのまま扱う仕組みであり、Python では open() や io.BytesIO を使用して効率的に操作できる
  • io.BytesIO は、ファイルを使わずにメモリ上でデータを管理できるため、非テキストデータの処理や一時データの操作に利用できる