オブジェクト指向と演習
データ構造を扱うプログラムの書き方を説明してきたので、それらを便利に書くためのオブジェクト指向の入り口を紹介する。
データ指向のプログラム記述
名前と年齢のデータを扱うプログラムを書く時、私なら以下のようなプログラムを作成する。
このプログラムの書き方では、saitohというデータにset_NameAge() , print_NameAge() を呼び出していて、データに対して処理を加えるという雰囲気がでている。このようにプログラムを書くと、saitoh というデータに対して命令するイメージとなり、擬人化してset,printしろ…って命令しているように見える。
// 名前と年齢の構造体
struct NameAge {
char name[ 20 ] ;
int age ;
} ;
// NameAgeを初期化する関数
void set_NameAge( struct NameAge* p , char s[] , int a ) {
strcpy( p->name , s ) ;
p->age = a ;
}
// NameAgeを表示する関数
void print_NameAge( struct NameAge* p ) {
printf( "%s %d¥n" , p->name , p->age ) ;
}
void main() {
struct NameAge saitoh ;
set_NameAge( &saitoh, "t-saitoh" , 53 ) ;
print_NameAge( &saitoh ) ;
// NameAge の中身を知らなくても、
// set_NameAge(),print_NameAge() の中身を見なくても、
// saitoh を set して print する....という雰囲気は伝わるよね!!
}
このプログラムでは、例えば、データに誕生日も覚えたいという改良を加えるとしても、main の前のデータ構造と関数の部分は色々と書き換えることになるだろうけど、main の内部はあまり変わらないだろう。こういう状態なので、プログラムを作成するときには、データ構造とそれを扱う関数を記述する人と、データ構造を使う人(main内部を書く人)と、分業ができるようになる。
隠蔽化
このような記述では、データ構造の中身を知らなくても、main で、setしてprintして…という処理の雰囲気は分かる。さらに、set_NameAge()とか、print_NameAge() の処理の中身を知らなくても、設定するとか表示するとか…は予想できる。
これは、NameAge というデータをブラックボックス化して捉えていると見れる。データ構造の中身を知らなくてもプログラムを理解できることは、データ構造の隠蔽化という。また、関数の中身を知らなくても理解できることは、手続きの隠蔽化という。
オブジェクト指向プログラミング
前述のように、プログラムを書く時には、データ構造とそのデータを扱う関数を一緒に開発するのが一般的である。オブジェクト指向プログラミングでは、データ構造とその関数(メソッドと呼ぶ)をまとめてクラスと呼ぶ。
class NameAge {
private:
// データ構造の宣言
char name[ 20 ] ;
int age ;
public:
// メソッドの定義
void set( char s[] , int a ) { // 初期化関数
strcpy( name , s ) ;
age = a ;
}
void print() { // 表示関数
printf( "%s %d¥n" , name , age ) ;
}
} ;
void main() {
NameAge saitoh ;
saitoh.set( "t-saitoh" , 53 ) ;
saitoh.print() ;
}
このプログラムでは、saitoh というデータ(具体的なデータはオブジェクトと呼ぶ)に対して、set() , print() を呼び出している。
オブジェクト指向では、データに対して private を指定すると、クラス以外でその要素を扱うことができなくなる。これにより、クラスを設計する人と、クラスを使う人を明確に分けることができ、クラスを使う人が、クラス内部の変数を勝手に触ることを禁止できる。
プログラムを記述する時には、データ件数を数える時に、カウンタの初期化を忘れて動かないといった、初期化忘れも問題となる。オブジェクト指向のプログラム言語では、こういうミスを減らすために、データ初期化専用の関数(コンストラクタ)を定義することで、初期化忘れを防ぐことができる。
// コンストラクタを使う例
class NameAge {
// 略
public:
NameAge( char s[] , int a ) { // データ初期化専用の関数
strcpy( name , s ) ; // コンストラクタと呼ぶ
age = a ;
}
// 略
} ;
void main() {
NameAge saitoh( "t-saitoh" , 53 ) ; // オブジェクトの宣言と初期化をまとめて記述できる。
saitoh.print() ;
}
セキュリティ対策
2段階認証
前回授業の暗号化の説明でも解説したように、パスワードはブルートフォース攻撃をうければ、いつかはパスワードが破られる危険性がある。こういった対策で最も重要な方法が、2段階認証(多要素認証)である。
この方式では、通常のパスワード入力の後に、以下の様な方式でワンタイムパスワードを入力することでログインが可能となる。
- 携帯電話にテキストメッセージ(SMS)でワンタイムパスワードを送る。
- かかってきた電話の機械音声のワンタイムパスワードを伝える。
- 時間で変化するワンタイムパスワード生成アプリの数字を入力する。
- メールで送られてきたワンタイムパスワードを含んだURLにアクセスする。
- 認証画面に表示されたQRコードのURLにアクセスする。
SMSやワンタイムパスワードアプリは、携帯電話などを常に持ち歩いていることが本人確認となっている。このような方式では、携帯電話などを失くすとシステムが使えなくなるので、バックアップコード(非常時用のパスワード)の保存や、login先とは別のメールアドレスを登録してあることが重要となる。
CAPTCHA
最近では、フリーで取得できるメールアドレスをプログラムで動くロボットで生成し、そのアカウントを使ってspamを送るなどの手口が問題となっている。このため、接続してきた相手が人間か判定することがある。判定には、読みづらく加工された英字を入力させたり、パズルを解かせるといった方法が使われる。
セキュリティ
バッファオーバーフロー
クラッカーがサーバを攻撃する場合、サーバ上のプログラムの脆弱性を利用する。
サーバプログラムの脆弱性を利用する最も典型的な攻撃方法には、「バッファオーバーフロー」がある。
こういった問題が含まれるアプリケーションは危険であり、こういった脆弱性が見つかったらプログラムの更新が重要である。
マルウェア
ウィルスとは、パソコン利用者の上で動く、感染能力のある悪意のあるプログラム。機械語で書かれたものや、オフィスソフトのマクロ機能で動くものもある。パソコン内の情報を利用して、ウィルス付きメールを自動的に送ることが多い。
ウォームとは、脆弱性のあるネットワークプログラムに、バッファオーバーフローを引き起こすようなデータを送りつけて、ウィルスを送りつけたり、そのコンピュータを利用してネットワークを利用した攻撃を行うもの。
通常、インターネットからの攻撃を防ぐために、各組織ではFireWall(後述)を設置している。一方、FIreWallの内側では、防御されていることから内部のコンピュータからの攻撃には無防備であることが多い。そこで、FIreWall の内側のコンピュータに、メールなどの添付ファイルでマルウェアを送付・感染させることで、FIreWall内で被害が拡大することもある。
このような、FireWall 内部での感染・被害拡大を狙ったマルウェアは、トロイの木馬型と呼ばれる。
ボットとは、感染しても表面上は何もせず、クラッカーの動かすインターネットの掲示板などを監視し、そこに書かれた命令を見て spam 送信や、DoS攻撃を行うものがある。
DoS攻撃(Denial of Service attack) – サーバなどに大量のデータを送りつけたりすることで、サーバがその処理に手間取り、他の利用者のサービスに悪影響を引き起こさせる攻撃。
最近では、区別が難しいため、ウィルスやウォームと呼ばずマルウェアと呼ぶ。
ファイアウォール
サーバで動かしているプログラムにバッファオーバーフローのような不備が残っていて、全世界のどこからでもこういった不備があるプログラムに簡単に接続できたとしたら、極めて危険である。
サーバで動くプログラムは、接続するためのポート番号が決まっているので、相手のコンピュータのIPアドレスが分かったら攻撃を仕掛けてくるかもしれない。
FireWall は、これらの接続をできなくするための方法で、例えば学内のWebサーバへの攻撃を防ぎたいのなら、ルータで「宛先ポート番号が80のパケットは廃棄」といった設定をすればよい。また、危険な攻撃を加えてくるコンピュータのIPアドレスがわかっている場合は、「送信元IPアドレスXX.XX.XX.XXのパケットは廃棄」という設定をすればよい。こういった、ポート番号やIPアドレスを見てパケットを遮断するルータは、FireWall(防火壁)と呼ばれる。
よくある設定であれば、ポート番号23(telnet),137,139(Windows ファイル共有),513(リモートデスクトップ)を禁止など(ブラックリスト型)、基本は全面禁止だけどポート番号22(ssh)は許可(ホワイトリスト型)など。
セキュリティ対策
- OSの更新・インストールアプリケーションの更新
バッファオーバーフローのような脆弱性を更新するため。 - 不審なメールは開かない
添付ファイルにマルウェアがしかけられている可能性 - 危険なWebサイトをアクセスしない
OSやブラウザの脆弱性から、マルウェア被害の可能性 - パソコンで不要なサービスを動かさない
ファイル共有や、リモート接続のサーバを不用意に動かさない。 - ウィルス対策ソフトをインストール＆更新
ウィルス対策ソフトは、マルウェアのパターンを比較するだけ。新しいマルウェアの対策には、パターンの更新が重要
リモート接続と暗号化
リモート接続と暗号化について説明
リモート接続
サーバなどの管理をしていると、インターネットの先にあるコンピュータを操作したい場合が多い。こういった場合には、リモート接続機能を用いる。
リモート接続による相手側のコンピュータを操作する場合、相手側のコンピュータには リモート接続 用のサーバプログラムを起動しておく。こういったリモート接続を利用するのは、”unix” の利用者が多いが、”unix” では、サーバ のプログラムは、一般的にデーモン(daemon/守護神)と呼ばれる。
telnet と rlogin
telnet は、最も基本的なリモート接続の方法であり、TCP の 23 番ポートを使う。telnetのサーバ(telnetd)は、送られてくるタイプされた文字を unix の shell (キーボードでの命令を実行するプログラム) に渡し、shell の実行結果の文字を接続元に送り返す。
telnet のクライアントの基本的動作は、タイプされた文字を送って、受信した文字データを表示するだけなので、通信の動作の確認にもよく使われる。
例えば、Webサーバは、80番ポートに”GET /ページの場所”を送ると、HTMLデータが受信できる。
rlogin は、TCP の 513 番ポートを使うリモート接続用のソフトで、サーバで rlogind を起動しておく。unix で rlogin クライアントを使うと、リモート側で命令を実行したりファイルをコピーすることができる。
こういったリモート接続ができると、ネットワークの向こう側のコンピュータを自由に操作できる一方で、login のパスワードが破られるとコンピュータを悪用されたり情報を盗まれる可能性がある。
特に、telnet , rlogin では、通信の内容が暗号化されないため、パケット盗聴(後述)されると、サーバを悪用されてしまう。
このため、ルータや firewall では、ポート番号 23 , 513 などは、遮断するのが一般的である。
ssh(secure shell)
暗号化されない rlogin の通信を暗号化により安全に実行できるようにしたものが、ssh (secure shell) である。
ssh は、通常では TCP の 22 番ポートを使う。しかし、暗号化されていたとしてもパスワード破りなどの危険性があるため、ポート番号を変更したり、特定のコンピュータに対してのみ接続許可を与え、安全対策を行う。
リモートデスクトップ
Windows では、コンピュータの操作では、マウス操作が中心(GUI: Graphical User Interface)となる。これに比べ、telnet,rlogin,ssh などの方法では、キーボードによる操作が中心(CUI: Character User Interface)であり、初心者には難しい。こういう場合はリモートデスクトップ(remote desktop)が用いられる。
remote desktop では、サーバのディスプレイ画面の情報をクライアントに送り、クライアントの操作(キーボード入力やマウス操作)がサーバに送られ、サーバのコンピュータを自由に操作ができる。
sshやリモートデスクトップは、遠隔地のコンピュータを自由に操作できることから、様々なコンピュータを管理している場合、広く使われている。しかしながら、クラッキングなどの悪用の危険があるため、sshサーバ、リモートデスクトップサーバなどのソフトは、通常利用者は起動しないこと。
クラッキングなどを行う場合、ウィルスを使ってリモート接続のためのソフトを動かされると、相手のコンピュータを自由に使える。このような、本来の使い方ではない侵入経路は、バックドアなどと呼ばれる。
暗号化
Ethernet では1本の通信線を共有したり、WiFiのような無線通信では、通信データの盗聴が簡単にできてしまう。クラッカーは、通信データの中から”login, password” といった文字を検索し、その近辺の文字を探すことでパスワードを盗み出す。
このようなことを防ぐために通信データの暗号化は重要な方法である。
暗号化アルゴリズム
暗号化の最も原始的な方法が、置換式 と呼ばれる方法で、特定の文字を別な文字に変更する。rot13は、A→N,B→Oに置き換える暗号。コナン・ドイル原作のシャーロック・ホームズに出てくる踊る人形などもこれに相当する。これらの方法では、アルファベットの文字の出現頻度から元の文を想像することで解読されてしまう。
エニグマ(Enigma)は、第2次世界大戦でナチス・ドイツが用いたロータ式暗号機であり、置換式の解読方法が不可能であった。しかし、イギリスのアラン・チューリングが電気式の解読器を開発することで暗号解読が可能となった。この解読器が現在のコンピュータの原型となっている。
チューリングによる暗号解読は、映画「イミテーションゲーム」を参照。
最近では、様々な暗号化アルゴリズムが開発されており、古くは “DES, AES“といったアルゴリズムが使われていたが、コンピュータの性能の向上と共に、解読に必要な時間が短くなったことから、RSA といった新しい暗号化方式が考えられ、さらに暗号化の鍵を長くすることで解読に要する時間を長くするようになっている。
パスワード解読方法
ログインなどで使われるパスワードは、どのように破られるのだろうか？
- ブルートフォース攻撃：単純に全ての文字を試す方式。文字の組み合わせ問題なので、パスワード文字列長をNとした場合、数字だけ(10N)とか英字だけ(26N)といった組み合わせでは、短時間に解読されてしまう。数字,大文字,小文字,記号などを交えたパスワードが理想。
- 英単語辞書を用いた辞書攻撃：パスワードが長い場合、文字列の全ての組み合わせを試すには長い時間が必要となる。しかし、パスワードはユーザが記憶して使うことから覚えやすい単語が使われる。このため英単語辞書の文字を組み合わせることで、解読時間を短くできる場合がある。
- 漏えいパスワードによる辞書攻撃：サーバへのリモート接続などができてしまった場合、パスワード情報が盗まれる場合がある。この時、別なサイトに同じパスワードを使っていると、その漏えいしたパスワードで別のサイトも接続ができてしまう。これらのことから、同じパスワードを使いまわすことは避けるべきである。
- ソーシャル攻撃：パスワードには、簡単に覚えられるように自宅の電話番号、誕生日、家族の名前といったものを使う人が多い。このため、SNS で相手に友達登録をしてもうことで、こういった情報を手に入れ、パスワードを破る方法。最近の有名人の個人情報漏洩はこの手の攻撃が多い。
ソーシャル攻撃は、元クラッカーケビン・ミトニックが有名
攻撃が難しい暗号化へ
先に述べたような、login に使うパスワードなどは、ブルートフォース攻撃をうけると解読は時間の問題となる。これらの対策として毎回違う鍵(パスワード)を使えばいい。
- 暗号表：置換式で読み取られるのを防ぐために、置換する文字の表を沢山作っておき、別の方法でその度毎に置換表を変更する
- ワンタイムパスワード：使い捨てのパスワードをあらかじめ沢山作っておき、接続の度に次のパスワードを用いる方式。あるいは、時間から特殊な計算方法で生成されるパスワード。時間と共に変化するのでその度毎に違うパスワードとなる。毎回違うパスワードを入力するため、パスワード表を常に持ち歩いたり、入力が面倒なので数字だけを使うことが多く、この方法だけでは使いにくい。
公開鍵暗号方式
以前に使われていた暗号化の方式は、暗号化の鍵と復号化の鍵に同じものを用いる共通鍵方式であった。
しかし、この鍵をどうやって相手に渡すか…が問題となっていた。(鍵を相手に渡す瞬間のデータを盗聴されると危険)
このため、最近では公開鍵暗号方式が中心となっている。この方式は「暗号化するため専用の公開鍵」と、「暗号化を復号するための秘密鍵」をペアにして用いる。公開鍵は、暗号化するため専用なので、この鍵が他の人に見られても、暗号を復号することはできない。
公開鍵暗号方式では、RSA などが最も有名で現在広く利用されている。
動的メモリ確保(malloc()とfreelist)
C言語では、動的メモリ領域をどのように管理していくのか解説する。
局所変数とスタック
局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。
関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。
baz()の中で、「*((&c)+4) = 123 ;」を実行したら、bar()のxを書き換えられるかも…
動的メモリ領域とフリーリスト
動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。
この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。
mallocが一定サイズの場合
free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。
malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。
任意サイズのメモリ確保の場合
この図の一番下の赤部分は、次のメモリブロックへのポインタとブロックサイズの大きさが20byteの場合の例。
malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。
丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。
この例の最後の処理では、20byte,60byte,40byte,50byteが併合された例。併合後のブロックサイズは、すこしいい加減に書いてある。
使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、大きいメモリのmalloc()ができなくなる。
そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。
また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。
一般的には、上記のようにmalloc(),free()を行うが(K&Rのmallocアルゴリズム)、mallocのサイズが小さい場合には併合処理などは隣接確認などが手間がかかる。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。(dlmallocのアルゴリズム)
ヒープメモリの断片化
ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。
この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。
(補足) 断片化
断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。
上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。
B木とB+木とハッシュ法
B木
データベースのデータを扱う場合には、B木を用いることが多い。
複数のデータを格納するノードは、位数Nであれば、2✕N個のデータと、その間のデータを持つノードへの2N+1個のポインタで構成される。
ノードにデータを加える場合は、頻繁にノードのポインタの付け替えが発生しないように、データがN個を下回った時や、2N個を超える場合とする。ノード内のデータ数が2Nを超える場合は、均等に木構造が成長するように、中央値を上のノードに移動し、ノードを2分割する。
B+木とシーケンスセット
再帰的な木構造のB木では、特定のデータを探す場合には、O(log N)で検索が可能である。
しかしながら、直積のようなすべてのデータを対象とする処理を行う場合、単純なB木では再帰呼出しをしながらの処理を必要とすることから、複雑な処理が発生する。そこで、データ列を横方向にアクセスするための単純リストであるシーケンスセットをB木と並行して管理するデータ構造がB+木である。
データを検索する場合は、B木構造部を用い、全データ処理は、シーケンスセットを用いる。
ハッシュ法
ハッシュ表は、データの一部をとりだしてハッシュ値を求め、そのハッシュ値を番地とする場所にデータを保存する方法である。しかし、データの一部を取り出すため、異なるデータに対して同じハッシュ値となる場合がある。これをハッシュ衝突とよぶ。この際のデータの保存の方法から、2つの方式がある。
- オープンハッシュ法
ハッシュ表がすでに埋まっていたら、別の保存場所を探す方式。 - チェイン法
同じハッシュ値となるデータをリスト構造で保存する方法。
トランザクション処理
トランザクション処理
トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。
例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。
上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。
同時実行制御
複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。
- ロッキング方式(悲観的制御)
先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。- ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
- ロックの種類
ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。 - 2相ロッキングプロトコル
トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
- 時刻印処理(楽観的制御)
データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。
デッドロック
複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。
このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する。
データベースの物理設計
データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。
ディスク容量の見積もり
データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。
実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。
そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。
また、データベースへのデータの削除を行う場合、データが１つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。
このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。
一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い。
また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。
WWWとhttp
WWWとhttp
WWWとは、ティム・バーナーズ=リーによって作られたサービスであり、元々は研究データの論文やデータの共有のために作られた。この際のWebサーバのデータのやり取りのためのプロトコルがhttp(Hyper Text Transfer Protocol)であり、ポート番号80のTCPを用いたものであり、最近では通信を暗号化したhttps(ポート番号443)も多く使われる。
httpでは、文字データの中に画像や音声といった情報に加え、他のデータへのリンクを埋め込むことができる HTML(Hyper Text Markup Language) のデータがやりとりされる。このHTML形式のデータを表示するためのソフトは、ブラウザと呼ばれる。
URL
WWWのデータの場所を示すものが、URL(Uniformed Resource Locator)であるが、最近ではインターネットが複雑化しLocator という表現が難しいため、URI(Uniformed Resource Identifier)と呼ぶようになってきた。
URLは基本的に、スキーマ://コンピュータ名/サーバ内ファイル位置 といった文字で構成される。URL は、HTTP だけでなく、インターネットの情報の場所を記述するために使われており、httpやhttps以外にも使う。
http
httpのサーバ(Webサーバ)とブラウザでは、以下のような手順で処理が行われる。例えば http://www.ei.fukui-nct.ac.jp/~t-saitoh/index.html のページが表示されるまでを考えると、
- ブラウザのURL欄に、目的サイトのURLを入力。
- 基本的には、スキーマ欄に記載されたプロトコル(http)名から、ポート番号と通信方法(http)を決める。
- コンピュータ名部分(www.ei.fukui-nct.ac.jp)を DNS に問合せして、得られたIPアドレスのコンピュータに接続。
- httpの最も簡単な GET メソッドでは、Webサーバに、サーバ内のファイル位置(/~t-saitoh/index.html)を伝えると、Webサーバは指定された場所のファイルを返送する。
- HTML形式のデータが指定された場合、ブラウザはその HTML をどの様に表示するか判断しながら表示する。
このような予め保存されているWebページを返送する場合は静的ページと呼ばれる。サーバのデータベースなどを参照しながらページ内容を返送する場合は、動的ページと呼ばれ、CGI(Common Gateway Interface) という手法が使われたり、動的なページを表示するためのプログラム言語(例えばPHP)が使われる。
サーチエンジン
インターネットでは、大量のWebページが出現してきたため、自分の目的に応じてWebページを探す機能が必要となってきた。このような目的のWebページを検索してくれるシステムは、サーチエンジンと呼ばれる。
ディレクトリ型
最初に現れた検索システムは、ページ作者が自分のページのURLと内容となるキーワードを登録しておき、内容のカテゴリー別に、ページの紹介文章が表示されるディレクトリ型であった。(初期のYahoo)
しかし、登録するキーワード以外の文字で探そうとすると、情報を見つけることができない。
ロボット型
これらの問題を解決すべく登場したのが、Google のようなロボット型サーチエンジンである。
ロボット型の検索システムでは、クローラーとかロボットとか呼ばれるプログラムを使い、Webページの内容をダウンロードし、そこに記載された文字を使ってURLのデータベースを作成する。
- 与えられた URL の先のページをダウンロードする。
- ページ内の文字を単語に切り分けして、それぞれの単語とURLを関連付けてデータベースに保存
- ページ内にリンクが含まれていたら、そのURLで、この作業を再帰的に繰り返す。
サーチエンジンで検索が行われると、クローラーの処理で作られたデータベースに問い合わせ、見つかったURLの情報を表示する。
Googleなどでは、多くのユーザが探したいページを提供するために、たくさん使われている単語を重要語としたり、たくさんのページからリンクされているページを表示順上位に表示するような工夫をしている。(逆にページランキングを不当に上げるようなページ作りをする人もいるので注意が必要)
参照カウンタ法とガベージコレクタ
共有のあるデータの取扱の問題
リスト構造で集合計算おこなう場合の和集合を求める処理を考える。
struct List* join( struct List* a , struct List* b )
{ struct List* ans = b ;
for( ; a != NULL ; a = a->next )
if ( !find( ans , a->data ) )
ans = cons( a->data , ans ) ;
return ans ;
}
void list_del( struct List* p )
{ // ダメなプログラムの例
while( p != NULL ) { // for( ; p != NULL ; p = p->next )
struct List* d = p ; // free( p ) ;
p = p->next ;
free( d ) ;
}
}
void main() {
// リストの生成
struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
struct List* c = join( a , b ) ; // c = { 1, 1, 2, 3 }
// ~~~~~~~ ここは b
// a,b,cを使った処理
// 処理が終わったのでa,b,cを捨てる
list_del( c ) ;
list_del( b ) ;
list_del( a ) ; // list_del(c)ですでに消えている
} // このためメモリー参照エラー発生
このようなプログラムでは、下の図のようなデータ構造が生成されるが、処理が終わってリスト廃棄を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。
参照カウンタ法
上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。
参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。
- データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
- 処理の中で共有が発生すると、参照カウンタをカウントアップする。
- データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
int refc ; // 参照カウンタ
int data ; // データ
struct List* next ; // 次のポインタ
} ;
void list_del( strcut List* p ) { // 再帰で全廃棄
if ( p != NULL
&& --(p->refc) <= 0 ) { // 参照カウンタを減らし
list_del( p->next ) ; // 0ならば本当に消す
free( p ) ;
}
}
ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。
参照カウンタ法が用いられている事例をあげよ。
ガベージコレクタ
では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか？
最も簡単な方法は、処理が終わっても、使い終わったメモリを返却しない、方法である。ただし、このままでは、メモリを使い切ってしまう。
そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、
- すべてのメモリ空間に、「不要」の目印をつける。(mark処理)
- 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
- その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)
この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。
最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような生成され関数終了といったすぐに不要となる領域は、ガベージコレクタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。
メールヘッダとspam
メールヘッダ
メールを出すときには、宛先やタイトルや本文などの情報がついている。
From: foo@bar.jp 送信元のメールアドレス To: hoge@piyo.jp 送り先のメールアドレス Cc: hogehoge@bar.jp 送信内容を確認してもらうためのコピーの送り先 Bcc: hogefuga@bar.jp 送信相手にコピーしたことが見えないように送る時 Subject: 会議の議事録 メールのタイトル Date: 2019年 1月 9日 12:34:56 メールを送った時間 本文 -- 署名
送信相手に届くメールでは、上記以外にも様々な情報がつけられる。これらの情報を見ると、迷惑メールか確認することもある程度可能となる。
Received: from 送信元 by 受信サーバ Reply-To: 返信する際の送り先 Return-Path: 送信に失敗した時に送り返す先 DKIM-Signature: メールサーバの公開鍵署名 Received-SPF: 送信元のDNS情報など
spam
メールでは、送信時に送信者の認証をしないので、送信元の名前を偽ってメールを送ることが簡単にできる。このため、広告目的、ウィルス感染目的にメールがよく使われる。こういったメールは、一般的に spam と呼ばれる。
イギリスのコメディグループ・モンティパイソンが、コントの中で、しつこくspam,spam,spam,spam….と、騒ぐ様からspamと呼ばれるようになった。大文字のSPAMと書かないこと。(ランチョンミートの缶詰)
なぜspamが届くのか?
たぶん、メールを利用していると、誰でも spam が送られてきた体験があるはず。でも、自分のメールアドレスがどうやって、送信元に知られてしまったのだろうか？
インターネットで企業などでメールアドレスを記入して、そこから情報が漏れたのだろうか？実際、企業がクラッキングに会い、情報漏えいの場合もあるが、一般的には、“aaa”さん、”aab”さん、”aac”さんといったように、文字列の組み合わせを順次組み合わせてユーザ名を作って送っているだけである。当然、このような方法では、宛先不明のメールが発生するが、迷惑メールの送信業者はそんなことは気にしない。ただし、大量の迷惑メールを送ると、インターネットの接続業者に目をつけられてアカウント停止となるため、ウィルスに感染させたパソコンを遠隔操作してspamメールを送るのが一般的である。このため、以下のことはしないこと。
- 迷惑メールの送信元に抗議メールを送らない。(From欄にメールアドレスを勝手に使われる場合がある)
- “I Love You”とか”くじに当選しました”といったメールはその時点で怪しい。
- 怪しいメールを開封しない。(ウィルスなどが添付されている場合がある。)
- メールの中のリンクをクリックするのは危険。(有名企業名を偽って怪しいサイトに誘導される可能性)
