MovableTypeへの投稿は、メールでやっているんだけど、 通常のメールアドレスと、MovableType投稿用のアドレスが似ているので、 Thunderbirdのアドレス補完で、自分宛にメールを出すつもりが、 MovableTypeに投稿されるというトラブル発生。 投稿用処理の条件を厳しくして、Cc:,Bcc:付きといった 投稿は無視するようにしてみた。

B木、B+木の紹介で教科書に記載されている一般的な話はほとんど紹介できたので、 今日は最近のデータベースにからむ技術動向を紹介。

B木とファイルシステム

前回のB木のネタの応用ネタということで、最近のファイルシステムにB,B+が採用されいている 事例を紹介。NTFS(Windows),ReiserFS(unix),B*木を使ったHFS(Mac OS X), データ検索機能のついたWinFSなどの事例を紹介。

データベースエンジンの動向

データベースシステムには、関係データベース、XMデータベース、オブジェクトデータベースがある。(追記)

関係データベースでは、データベースの構成が変更になると、移行処理が大変。 柔軟なデータベースの構造に対応できるようにしたい。

⇒XMLデータベース。XMLを扱うための機能を持つデータベース。 XMLのツリー構造をそのままデータ構造として持つ物。

構造化された複雑なデータを扱う場合には、オブジェクト指向のプログラム言語が利用される。 しかしデータベースは表を元にした表現なので、複雑なデータ構成だと、 それに応じたSQLを発行しないといけない。 このため、プログラマーはオブジェクト指向とRDBの表の考え方の違いを考えながら プログラムを作る必要がある。

⇒オブジェクトデータベース(オブジェクト指向データベース)、データベース自体がオブジェクト指向

データベースを扱うからには情報とシステムも巨大

データベースでは、巨大な個人情報を扱うのがあたりまえ。 SQLインジェクションといったセキュリティ問題をきちんと理解しておかないと、 金銭的な被害も大きくなることを十分意識すべき。

巨大なシステムは、止める事ができない。 しかし、ソフトを作ったり耐故障性能の高いシステムを、 小さい案件で個別に組むのは、手間やコストがかかる。 サーバを借りて動かすことが多い。

サービスの形態で、SaaS(Software as a Service),PaaS(Platform as a Service), IaaS(Infrastructure as a Service)等がある。 最近は、貸し出すサーバが仮想化されたサーバ群で動かし、利用者がどこのサーバで動いているのか意識せずに利用できるようになってきた。⇒クラウドシステム。

クラウドを用いたPaaSでは、Google App Engine , Windows Azuru などが注目されている。 クラウドを用いたIaaSでは、Amazon EC2 あたりが注目されている。

学科の予算にて、4EI,5EIの教室にプロジェクタが付けられた。 映像ケーブルの配線を壁埋め込みとかにすると、工事費がかさむ事から、 無線LAN接続のプロジェクタ(EPSON-EB-1725)が導入された。 無線LANにはアドホック接続で行われ、パソコンに専用ソフトを入れておけば、 映像系の配線なしで使うことができる。 専用ソフトも、Win/7/Vista/XP/2000,Mac OSX/SnowLeopard/Leopard…と幅広く用意されており、 ダウンロードページから導入できる。

簡単と思って実験したら、１つだけ不便なことが…. アドホック接続でつながってしまうので、プロジェクタ接続中は無線LANが使えない…. じゃあLAN接続は有線で….やっぱり配線かよ… 授業でネットしながら説明したいときは、必要画面全部ウィンドウを残しておかないとダメあるね。

追記：(2010/01/25)
WiFiプロジェクタの接続がアドホックだけというのは不便だと思っていて、 製品のマニュアルを読んでみた。 すると、インフラストラクチャモードもちゃんとあった。(あたりまえか…) ということで、学科内には無線LAN環境がそれなりに整っているので、それにつなげればいい。 とおもって、さっそく作業と思ったが『まだリモコンが納品されていない…』とのことで、 作業中断となっちゃった。

学内でのハンディ端末として使い始めていた iPod touch だけど、 先日よりいきなりApple以外のアプリがすべて動かなくなった。 "iphone アプリ起動しない"と手抜きのキーワードで検索すると、 DRMの認証の問題といった情報が見つかる。対応方法は社外アプリを一旦全部消す！ と書いてある。ひとまず初体験なので、全消しした。(有料アプリもあったけど…) でも、よくよく調べてみると、"App Store"で何らかのソフトをインストールすると 起動できるようになると書いてある。次回からは、この手でいこう。

んで、実は2日後にも同じ症状になってしまった。 明確な原因はよく分からないけど、RSS閲覧用にgoogle リーダ対応の無料版を 入れていたけど、起動時によく落ちていた。だから、たぶんコイツが原因だったように思う。 でも改めてこのダメreaderのダメっぷりを紹介しようと探すんだけど、アプリが見つからない。 評判悪くてすぐに消されたんだろうな….

malloc() + free() による動的メモリの管理方法について説明を行う。 理解を簡単にするために、確保領域が固定サイズであったときのフリーリストを説明する。

フリーリストとは、free() によって開放された領域をリスト構造で保存しておき、 malloc() 要求があったら、フリーリストの先頭から再利用する手法。 簡単な手抜き実装であれば、初期状態で巨大なmalloc用配列を準備しておき、 その領域すべてをフリーリストとして繋げておけばいい。

通常のmallocは、引数として確保するメモリのbyte数を指定することができるため、 前の説明のように簡単な状況とはならない。 free()によって開放されたメモリ領域はfreelistに保存されるが、 リストにつなぐ際に隣り合った再利用領域は併合される。 malloc()で、フリーリスト内に適切なサイズのメモリブロックが無い場合は、 それより大きい領域を探し、分割される。 このため、malloc+freeの順序が最悪であれば、メモリ空間にヒープホールなどが発生してしまう(メモリの断片化:フラグメンテーション)。

関連する雑談として、同じ断片化(フラグメンテーション)ということで、 ハードディスクの断片化について説明する。 ハードディスクで断片化が発生すると、ムダなシーク時間・回転待ち時間が発生し、 アクセス速度が低下する。 Windowsなどでは、デフラグツールが一般的で、 この処理を行うとハードディスクの実体を覚えている場所を移動させ、 連続したセクタにデータが並ぶように再配置してくれる。

前回の2次元の座標変換に引き続き、3次元表示について説明を行う。 ただし、グラフィックス処理では、大量のデータ処理から命令の効率よい実行が 求められることが多いので、最適化についても説明を行う。

最適化

C言語のプログラムが機械語に変換されて実行されるが、コンパイル＆リンクの間に、 最適化という「効率よく命令が実行するように命令を組み替える処理」が行われる。 オプティマイザによる自動の最適化も重要だけど、複雑なプログラムでは プログラマ自身も最適化を考慮しておくべき。

• CPUの高速化に比べ主記憶(DRAM)のスピードは遅い。このため、キャッシュメモリ(SRAM)を 活用し、利用頻度の高いデータは極力キャッシュに保存されるように命令を書き換えたり、 CPU内のレジスタを極力使うように最適化が行われる。
• 繰り返しの中で変化しない値を何度も計算で求めるのは効率が悪い。 ループの中で変化しない計算はループ前に求めるように最適化をすべき。
• 8bitコンピュータを用いた組み込み系では、CPUが整数の乗算/除算命令が無かったりする。 このため、乗算除算を極力行わないようにすべき。 また、もう少しマシな組み込み系でも、CPUに浮動小数点演算機構が組み込まれていなかったりする。こういうプロセッサでは、浮動小数点演算も極力行わないようにする。
• 最近のコンピュータでは、a*b+c*dといった積和演算や、byteデータ数個に同じ演算を施すといったことが多く、CPUが専用の計算命令を持っている。こういうプロセッサでは、 こういう命令を極力使うように最適化が行われる。

3次元表示

ｎ データを視覚的に表示する場合、3次元表示は重要であり、 簡単な表示では、等軸測投影や2軸測投影といった方法がとられる。 2軸測投影をさらに簡略化した方法で斜軸投影もあるが、 座標軸が直交していないので表示が歪んで見える場合もある。

3次元で見えるためには、遠近法も重要であり、簡単な図法では2消点透視図がとられる。 実際には、投影面と視点による縮小表示などが行われる。

しかし、ここまでの話では、物体の表示座標を求めているだけ。 グラフィックスでは、このあと、陰面処理・光源処理(シェーディング)・テクスチャマッピングといった、 処理が行われる。

総合情報処理センターに置かせてもらっているサーバの、バックアップ強化で機材が増え、ラックにまとめる。５台だもんなぁ〜。 裏の配線も、短めのEtherケーブルに差し替えたり、結束バンドで配線を固定したり、キーボード＆モニタ切替え装置を入れたり….。 おかげで、かなりすっきりした構造になった。 ただ、緊急連絡システムのメインサーバは、稼働状況もあって、まだ床置きのまま。 利用者が少ないときを狙ってラックにまとめれば、完成。

上に乗っけたモニタも含めると、高層建築状態なので、地震があったらちょいと怖いんだけど…

追記:2010/01/18 、メインサーバを利用状況が低いのを見て、ラックにのっける。 さらに、上に乗っけていたモニタをキーボード台に下ろす。

データベースの内部構造の話として、B木とB+木について説明を行う。

B木

B木は、位数Nの場合、2N個のデータ部(d_i)と、 2N+1個の次のノードへのポインタ(p_j)で、 １ノードが構成される。 i番目のポインタp_iの先には、d_i-1より大きく、 d_iより小さいデータを格納する。 また、１つのノード内のデータ件数は、N以上、2N以下を満たすように構成する。

データの挿入などを行うことで、1ノード内のデータ件数が2N個を越える場合、 追加データを含めた2N+1個の中央の値を上位に昇格させ、ノードを2つに分割する。 昇格先の上ノードもあふれる場合は、再帰的に同じ処理を繰り返す。

データあふれで昇格&分割の説明(wikipediaより引用)

同様に、データ削除の場合も、1ノード内データ件数がNを下回る場合も、 2つのノードを併合などの処理を行う。

B+木

B木では、追加削除が容易ではあるが、全データの順次処理をする場合、 再帰処理などが必要になったりするため、データのシーケンシャルアクセス・ランダムアクセスが 苦手である。データベースでは、複数テーブルの全データで直積といった処理も多いことから、 次々と処理を行うためのヒントが必要となる。

このため、末端のノードにおいて、シーケンスセットと呼ばれるリスト構造を作っておく。 末端のデータをリストでつないだ情報を持つことで、データ順の順次アクセスが容易となる。

参考教科書では、シーケンスセットをノードとは別に保存する説明で記載されているが、 WikipediaのB+木の説明では、末端ノード同士を横方向に接続するだけの図で説明されている。 この辺は、実装方法の異差かな???

バックアップ対策用に導入したNASのためのバックアップ処理を記述したけど、 確認すると予想外のバックアップが発生している。 月初めの日曜だけバックアップを取りたかったので、crontab にて、

#時 分 日 月 曜
0   3 1-7 * 0   root ...backup-script...

を記載した。『1~7日でかつ曜日が日曜日』のつもりだったんだけど、1~7の毎日バックアップが実行されている。よくよく man 5 crontab を見ると、他の項目と違い、月日付と週日付の両指定は"or" だった。

注意: コマンド実行の日は 2 つのフィールドで指定できる — 月内日および曜日である。 もし両方のフィールドが制限指定 (* 以外) であると、 いずれかのフィールドが現在時刻と合った時にコマンドが実行される。 (man 5 crontab より)

しかたがないので、曜日指定を抜いて、"0 3 1 * * root …"の設定とした…. 平日夜中の３時、負荷かけないでね…

追記:2010/01/14 予定外で実行された、バックアップで中身をみると、差分バックアップなのに、大量の記録が 記載されている。でも、ほとんどディレクトリ。更新日付だけの記録なんだろうか….

この数年、高専の3年生はこの時期、『全国高専到達度試験』というものが実施されます。 全国の高専の学習内容の理解度の違いを見るためなんだろうけど、 数学と物理の試験が、1/13日の午前に実施されました。 実施方法は、入試とほぼ同じで90分の内容。学校によって教える内容の違いもあり、 いくつかの領域に分けられ、最初から教えていないものは問題から除外される。

どちらにしろ、直接的に自分の成績には影響しないため、中には適当にマークシートに 書いている人も若干いる様子。だけど、数学・物理の先生も、学校の評価にかかわることもあり、 到達度試験と同様の範囲のレポートを課題にしたりと、ちょっと苦労されているみたい。