WWWとhttpとサーチエンジン
最初に、前回講義で説明が不十分だったメールの機能について説明のあと、Web の説明を行う。
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以外にも使う。
最近のブラウザは、スキーマ欄の”https://”やコンピュータ名の先頭の”www.”を省略することができる。また http は暗号通信を使わず危険であることから、警告メッセージが表示されたり、可能であれば https の通信に切り替えを試みられる。
http (Hyper Text Transfer Protocol) の流れ
httpのサーバ(Webサーバ)とブラウザでは、以下のような手順で処理が行われる。例えば http://www.ei.fukui-nct.ac.jp/~t-saitoh/index.html のページが表示されるまでを考えると、
- ブラウザのURL欄に、目的サイトのURLを入力。
- 基本的には、スキーマ欄に記載されたプロトコル(http)名から、ポート番号と通信方法(http)を決める。一般的な http 通信では、ポート番号には 80 を使う。
- コンピュータ名部分(www.ei.fukui-nct.ac.jp)を DNS に問合せして、得られたIPアドレスのコンピュータに接続。
- httpの最も簡単な GET メソッドでは、Webサーバに、サーバ内のファイル位置(/~t-saitoh/index.html)を伝えると、Webサーバは応答ヘッダ情報と応答本文の指定された場所のファイルの内容を返送する。(下図参照)
- HTML形式のデータが指定された場合、ブラウザはその HTML をどの様に表示するか判断しながら表示する。
このような予め保存されているWebページを返送する場合は静的ページと呼ばれる。サーバのデータベースなどを参照しながらページ内容を返送する場合は、動的ページと呼ばれ、Webサーバ内部でプログラムを動作させ、その結果のデータをブラウザに返す。
動的ページを生成するためのプログラム言語としては、様々な方法がある。(バックエンド言語)
- 言語 Perl による CGI(Common Gateway Interface)
- Webに特化した言語PHP
- サーバで 言語 Java を使ってページデータを生成(Apache Tomcat)
- サーバで 言語 JavaScript を使ってページデータを生成(Node.js)
また、最近のブラウザでは JavaScript を使って、Webページに表示される内容を動的に変化させることが多い。(フロントエンド)
https
httpでは、通信が平文で行われるため、同じサブネット内であれば通信内容を盗み見られる可能性がある。この通信を暗号化しながら行われるものが https である。ポート番号には一般的に 443 が使われる。暗号化通信は次週以降に説明を行う。
サーチエンジン
インターネットでは、大量のWebページが出現してきたため、自分の目的に応じてWebページを探す機能が必要となってきた。このような目的のWebページを検索してくれるシステムは、サーチエンジンと呼ばれる。
ディレクトリ型
最初に現れた検索システム(1994年)は、ページ作者が自分のページのURLと内容となるキーワードをサーチエンジンに登録しておき、内容のカテゴリー別に、ページの紹介文章が表示されるディレクトリ型であった。(初期のYahoo)
しかし、登録するキーワード以外の文字で探そうとすると、情報を見つけることができない。
ロボット型
これらの問題を解決すべく登場したのが、Google のようなロボット型サーチエンジン(1997年)である。
ロボット型の検索システムでは、クローラーとかロボット(あるいはボット)とか呼ばれるプログラムを使い、Webページの内容をダウンロードし、そこに記載された文字を使ってURLのデータベースを作成する。
- 与えられた URL の先のページをダウンロードする。
- ページ内の文字を単語に切り分けして、それぞれの単語とURLを関連付けてデータベースに保存
- ページ内にリンクが含まれていたら、そのURLで、この作業を再帰的に繰り返す。
サーチエンジンで検索が行われると、クローラーの処理で作られたデータベースに問い合わせ、見つかったURLの情報を表示する。
Googleなどでは、多くのユーザが探したいページを提供するために、たくさん使われている単語を重要語としたり、たくさんのページからリンクされているページを表示順上位に表示するような工夫をしている。
ページランキングを上げるためのWebページの工夫をすることを、SEO (Search Engine Optimization) という。しかし逆にページランキングを不当に上げようと特殊なテクニックのページ作りをする人もいるが、最近では不当なページ作りは逆にランキングが落とされるようになっている。
理解度確認
- URLが与えられてページが見れるまでに行われることを説明せよ。
- サーチエンジンのディレクトリ型とロボット型の違いを説明せよ。
トランザクション処理
トランザクション処理
トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。
例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。
上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)
排他処理の実装方法
排他処理を実現する方法としては、ロック(Lock)、セマフォ(Semaphore)、ミューテックス(Mutex)が使われる。
ロックの例としては、C言語では flock() 関数が有名。(後述のロッキング方式/悲観的制御を参照)
- C言語でのファイルロック(共有ロック,排他ロックの機能あり)
- 共有ロック:他のプロセスの読み込みは許可するけど、書き込みは禁止。
- 排他(占有)ロック:他のプロセスの読み込みも書き込みも禁止する。
- 使い終わったらアンロック。
セマフォの例としては、カウンタセマフォが使われる。
- 対象資源を使用中のプロセスの数を表す、カウンタを使う。
- 初期値0の状態は、だれも使っていない状態。
- 対象資源を使う時にカウントアップ、使い終わったらカウントダウンする。
ミューテックスは、セマフォの使用中/開放状態を 0,1 で管理するようなもの。
ロックはファイルに対して使うもので、セマフォやミューテックスは、プロセスやスレッド間の同期に使うことが多い。
同時実行制御
複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。
- ロッキング方式(悲観的制御)
先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。- ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
- ロックの種類
ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
- 2相ロッキングプロトコル
トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
- ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
- 時刻印方式/タイムスタンプ方式(楽観的制御)
データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。
デッドロック
複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)
このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。
グラフ理論(Wikipedia)
前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ぶ。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼び、始点(行)と終点(列)の経路がある所を1で表す。
メモリ管理・スタック領域とヒープ領域
ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のようなデータを保存するためのスタック領域と、new 命令で確保されるヒープ領域についてその使われ方などについて理解する。
C言語やJavaでのメモリ領域(静的領域とスタック領域)
C言語では、データ領域は、定数領域、静的変数領域、スタック領域、ヒープ領域 で構成される。また、変数にはスコープという変数が使える範囲がある。
定数領域は、値が変化しないデータが保存される。
静的変数領域は、プログラムが起動したときに確保され、プログラム終了と共にデータが消される。
スタック領域は、関数が呼び出される時に確保され、関数を抜ける時にデータが消される。関数の引数や関数の局所変数などは、この領域に保存される。
#include <stdio.h> int x = 123 ; // 静的大域変数 const int y = 234 ; // 静的大域変数(定数) 再代入不可 void foo() { int b = 345 ; // 動的局所変数 b++ ; printf( "%d %d\n" , x , b ) ; } void bar( int a ) { int b = 456 ; // 動的局所変数 static int c = 789 ; // 静的局所変数 x++ ; b++ ; c++ ; printf( "%d %d %d\n" , x , b , c ) ; foo() ; } int main() { int z = 890 ; // 動的局所変数 bar( z ) ; bar( z ) ; printf( "%d\n" , z ) ; return 0 ; } // 実行結果 // 124 457 790 // 124 346 // 125 457 791 // 125 346 // 890
大域変数は混乱の元
以下のようなプログラムでは、foo() を実行すると”0 1 2″ と表示され、main の中で foo() を3回呼び出しているので、”012,012,012″と表示されると勘違いするかもしれない。しかし、xが大域変数(Javaでは大域変数は無いけど)であるため、foo() の処理の中で x=3 となっているため、mainの中では、2回目のループが動かないため、”0 1 2″と表示されるだけである。
こういったように、誰もが使える変数を、どこからでも呼び出せる状態にしておくとプログラムの間違いが発生しやすい。
// C言語での大域変数の問題 int x ; void foo() { // 0 1 2 と出力 for( x = 0 ; x < 3 ; x++ ) printf( "%d\n" , x ) ; } int main() { // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される? for( x = 0 ; x < 3 ; x++ ) foo() ; return 0 ; }
// Javaでの大域変数の問題 public class Main { public static int x = 0 ; // 静的クラス変数 public static void foo() { // 0 1 2 と出力 for( x = 0 ; x < 3 ; x++ ) System.out.println( x ) ; } public static void main(String[] args) throws Exception { for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される? foo() ; } }
こういう場合は、正しく局所変数を用いて、関数内でのみ使う変数 x を宣言すれば、上記のような間違いを防ぐことができる。関数内で宣言される変数は関数に入る度にメモリを確保し、関数を抜ける時にメモリ領域が消される。
// C言語での大域変数の解決のために局所変数を使う void foo() { // 0 1 2 と出力 int x ; for( x = 0 ; x < 3 ; x++ ) printf( "%d\n" , x ) ; } int main() { // 0 1 2 を出力する処理を 3回繰り返す int x ; for( x = 0 ; x < 3 ; x++ ) foo() ; return 0 ; }
// Javaでの大域変数の解決のために局所変数を使う public class Main { public static void foo() { // 0 1 2 と出力 int x ; for( x = 0 ; x < 3 ; x++ ) System.out.println( x ) ; } public static void main(String[] args) throws Exception { int x ; for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返す foo() ; } }
一方で、関数が呼び出された回数を確認したい…という用途であれば、下記のように大域変数を使うこともあるが、これだと x を間違って使われる可能性がある。
int x = 0 ; void foo() { x++ ; printf( "%d\n" , x ) ; } int main() { foo() ; foo() ; return 0 ; }
このために、C言語では静的局所変数というのがある。関数内で static で宣言された変数は、その関数の中でしか使えないが、プログラムが起動した時に変数領域が作られ初期化され、プログラムが終了した時にデータ領域が消される。
void foo() { static int x = 0 ; x++ ; printf( "%d\n" , x ) ; } int main() { foo() ; foo() ; }
Javaでは、プログラムの中でデータが間違ってアクセスされることを防ぐために、大域変数という考え方は存在しない。その代わりにクラス内で共通に利用できる変数ということで、静的なクラス変数が用いられる。static なクラス変数は、クラスがロードされた時点でメモリに確保され、プログラム終了まで保持される。
public class MyClass { public static int count = 0; // クラス変数 public static void main(String[] args) { MyClass.count++; // インスタンスを作らずにアクセス System.out.println(MyClass.count); } }
スタック領域
スタック領域は、ここまでに述べた様に「関数を呼び出す際にメモリ領域が確保・初期化され、関数が終わるとメモリ領域は消される。
以下のような main から bar() , foo() が呼び出される処理では、
- 関数呼び出し時には、戻り番地の保存、実引数の確保が行われ、
- 関数に入った時点で局所変数の領域が確保される。
- 関数が終わると、実引数・局所変数の領域が消され、スタックから取り出された戻り番地に処理を移行する。
このような関数呼び出しでは、最後(Last)に確保した変数が最初(First)に忘れればいいというデータなので、Last In First Out の スタック構造が使われる。
ヒープ領域
リスト処理のようなプログラムでは、データを覚える領域は、関数が終わった後も使われる領域なので、局所変数のように「関数が終わったらそのデータの場所が不要になる」といったLast In First Out のようなスタックで管理することは難しい。
データを確保したメモリがどの時点まで使われるのか解らない場合、スタック構造を使うことはできない。こういったデータは、ヒープメモリ(ヒープ領域)を用いる。
C言語であれば、ヒープメモリの場所の確保には malloc() 関数が用いられ、不要となった時に free() 関数でメモリの開放が必要である。free() を忘れたプログラムが、ずっと動いた状態になると再利用されないメモリ領域が発生(メモリリーク)し、その領域が大量になると、他のプログラムに悪影響がでてくる。(最悪、仮想メモリの利用でスワッピングが多発するかもしれない)
#include <stdio.h> #include <stdlib.h> struct A { // class A { int data ; // int data ; } ; // } int main() { struct A * ptr = (struct A*)malloc( sizeof( struct A ) ) ; // ptr = new A ; ptr->data = 123 ; // ptr.data = 123 ; free( ptr ) ; // Javaでは free() は不要 return 0 ; }
共有の発生したデータの扱い
C言語では、ヒープメモリの管理するには色々と複雑なことが発生する。
例えば、以下のようなリストの和集合のプログラムをC言語とJavaで示す。
このプログラムでは、リスト a, b の和集合を c に代入している。また、不要となったリストを捨てるために list_free() という関数を作成している。ただし Java では、不要となったメモリ領域の開放は不要だが、C言語との対比のために next に null を代入する処理で代用してある。
#include <stdio.h> #include <stdlib.h> struct List { int data ; struct List* next ; } ; struct List* newListNode( int x , struct List* p ) { struct List* ans = (struct List*)malloc( sizeof( struct List ) ) ; if ( ans != NULL ) { ans->data = x ; ans->next = p ; } return ans ; } void list_print( struct List* p ) { for( ; p != NULL ; p = p->next ) printf( "%d " , p->data ) ; printf( "\n" ) ; } int find( struct List* p , int key ) { for( ; p != NULL ; p = p->next ) if ( p->data == key ) return 1 ; return 0 ; } struct List* list_union( struct List* a , struct List* b ) { struct List* ans = a ; for( ; b != NULL ; b = b->next ) if ( !find( a , b->data ) ) ans = newListNode( b->data , ans ) ; return ans ; } void list_free( struct List* p ) { if ( p != NULL ) { list_free( p->next ) ; printf( "*%d " , p->data ) ; free( p ) ; } } int main(void){ struct List* a = newListNode( 11 , newListNode( 22 , NULL ) ) ; struct List* b = newListNode( 11 , newListNode( 33 , NULL ) ) ; struct List* c = list_union( a , b ) ; list_print( a ) ; list_print( b ) ; list_print( c ) ; list_free( c ) ; list_free( b ) ; list_free( a ) ; return 0 ; // free(): double free detected in tcache 2 // Aborted (core dumped) }
import java.util.*; class ListNode { int data ; ListNode next ; ListNode( int x , ListNode p ) { this.data = x ; this.next = p ; } } public class Main { public static void list_print( ListNode p ) { for( ; p != null ; p = p.next ) System.out.print( p.data + " " ) ; System.out.println() ; } public static boolean find( ListNode p , int key ) { for( ; p != null ; p = p.next ) if ( p.data == key ) return true ; return false ; } public static ListNode list_union( ListNode a , ListNode b ) { ListNode ans = a ; for( ; b != null ; b = b.next ) if ( !find( a , b.data ) ) ans = new ListNode( b.data , ans ) ; return ans ; } public static void list_free( ListNode p ) { if ( p != null ) { list_free( p.next ) ; System.out.print( "*" + p.data + " " ) ; p.next = null ; } } public static void main(String[] args) throws Exception { ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ; ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ; ListNode c = list_union( a , b ) ; // 33,11,22 list_print( a ) ; list_print( b ) ; list_print( c ) ; list_free( c ) ; System.out.println() ; list_free( b ) ; System.out.println() ; list_free( a ) ; } }
このプログラムを実行すると、c には和集合のリストが出来上がるが、33の先のデータは a とデータの一部を共有している。
この状態で、リスト全体を消すための list_free(c); list_free(b); list_free(a); を実行すると、list_free(c) の時点で a の先のリストは解放されている。このため、list_free(a) を実行すると、解放済みのデータ領域をさらに解放する処理が行われるが、すでに存在していないデータを消す処理が実行できない。
C言語のプログラムを動かすと、プログラム実行時にエラーが発生する。しかし、Java で書かれた「ほぼ同様」のプログラムは問題なく動作する。
参照カウンタ法
上記の問題は、a の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。
参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。
- データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
- 処理の中で共有が発生すると、参照カウンタをカウントアップする。
- データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
// 参照カウンタの説明用プログラム class ListNode { int refc ; // 参照カウンタ int data ; // データ ListNode next ; // 次のポインタ ListNode( int x , ListNode p ) { this.refc = 0 ; this.data = x ; this.next = p ; } } ; public class Main { public static ListNode copy( ListNode p ) { p.refc++ ; // 共有が発生したら参照カウンタを増やす。 return p ; } // 集合和を求める処理 public static ListNode list_union( ListNode a , ListNode b ) { ListNode ans = copy( a ) ; // ~~~~~~~~~共有が発生するのでrefc++ for( ; b != null ; b = b.next ) if ( !find( ans , b.data ) ) ans = new ListNode( b.data , ans ) ; return ans ; } public static void list_del( ListNode p ) { // 再帰で全廃棄 if ( p != null && --(p.refc) <= 0 ) { // 参照カウンタを減らし // ~~~~~~~~~~ list_del( p.next ) ; // 0ならば本当に消す free( p ) ; }//~~~~~~~~~ Javaでは存在しない関数(説明用) } public static void main(String[] args) throws Exception { ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ; ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ; ListNode c = list_union( a , b ) ; // a,b,cを使った処理 // 処理が終わったのでa,b,cを捨てる list_del( c ) ; list_del( b ) ; list_del( a ) ; }
ただし、Java ではこういった処理を記述しなくても、内部で参照カウンタ法を実行しているため、このような処理を書く必要はない。
unix i-nodeで使われている参照カウンタ
unixのファイルシステムの基本的構造 i-node では、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。
以下に、unix 環境で 参照カウンタがどのように使われているのか、コマンドで説明していく。
$ echo a > a.txt $ ls -al *.txt -rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 a.txt ~~~ # ここが参照カウンタの値 $ ln a.txt b.txt # ハードリンクでコピーを作る $ ls -al *.txt -rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 a.txt -rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 b.txt ~~~ # 参照カウンタが増えているのが分かる $ rm a.txt # 元ファイルを消す $ ls -al *.txt -rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt ~~~ # 参照カウンタが減っている $ ln -s b.txt c.txt # シンボリックリンクでコピーを作る $ ls -al *.txt -rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt $ rm b.txt # 元ファイルを消す $ ls -al *.txt lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt $ cat c.txt # c.txt は存在するけどその先の実体 b.txt は存在しない cat: c.txt: そのようなファイルやディレクトリはありません
ポート番号とファイアウォールとメール
ポート番号とソケット
サーバとなるコンピュータでは、1台のコンピュータで様々なサービスを提供することから、サービスを区別する必要がある。このためにポート番号が使われる。1台毎のコンピュータに割り当てられたIPアドレスを電話番号に例えるなら、ポート番号は内線電話番号に例えることができる。
サーバと通信する場合、サービスを提供するプログラムに応じて標準的なポート番号が決められている。サーバに届いたパケットは、ポート番号に応じてサービスプログラムを起動する。以下の表によく使われるポート番号の一例をあげる。
ポート番号 | プロトコル | 概要 |
20 | ftp | ファイル転送(データ) |
21 | ftp | ファイル転送(命令) |
22 | ssh | リモート接続(暗号対策あり) |
23 | telnet | リモート接続(暗号化なし) |
25 | smtp | 電子メール送信 |
465 | smtps | 電子メール送信(暗号化) |
53 | DNS | ドメインネームサービス |
80 | http | Web |
443 | https | Web(暗号化) |
110 | pop3 | メールダウンロード |
995 | pop3s | メールダウンロード(暗号化) |
143 | imap | メール閲覧 |
993 | imaps | メール閲覧(暗号化) |
137,138,139 | netbios | Windows のファイル共有 |
通信パケットには、送信元IPアドレス、送信元ポート番号、送信先IPアドレス、送信先ポート番号の情報がある。
パソコンがサーバと通信する場合は、(1)自分のIPアドレスを送信元IPアドレス、(2)その時に使われていないポート番号をランダムに選び、送信元ポート番号とする。(3)通信相手のIPアドレスと、(4)通信先のサービスのポート番号をセットして、パケットを送付する。サーバは、サービスを要求してきたクライアントの送信先ポート番号をみて、対応するサーバのプログラムが動作する。プログラムの結果を送り返す時は、送信元と送信先のIPアドレス、ポート番号を入替えてパケットを送信する。
このような、IPアドレスとポート番号でお互いにデータを送りあうデータ通信の末端という意味でソケットと呼ぶ。サーバ側は、誰からでもデータを受け入れるということでソケットを開いて待機している。クライアントは開かれたソケットに接続して情報をやり取りする。
1024未満のポート番号(ウェルノウンポート番号)は、サービスを受けとるために用途が決められているので、通常の通信プログラムでは使われない。これ以外のポート番号は、通信の送信元のポート番号として使われ、エフェメラルポート番号と呼ばれる。
ファイアウォール
ネットワークのサービスの中には、組織外に見せたくないものも多い。また、インターネットでは、悪意のあるプログラマが通信して攻撃を加えてくるかもしれない。基本的には個々のサーバのプログラムで、送信元のプログラムのIPアドレスを見て接続を拒否することもできるが、末端のサーバで設定がいい加減だと攻撃をうけてしまうかもしれない。そこで、組織全体でネットワークを守る必要がでてくる。そこでルータなどの機能で、パケットの送信相手のポート番号や、送信元のIPアドレスをみて、パケットを廃棄する場合がある。こういう、ネットワークからの攻撃を防ぐ装置は、ファイアウォール(防火壁)と呼ばれる。
データベースサーバの保護するためにファイアウォールを設置する例を示す。Webサービスを提供するためのデータベースだけど、インターネットから接続されると情報漏洩が発生するかもしれない。そこでデータベースサーバ(mysql)に接続するための3306ポートは、ファイアウォール(ルータ)で組織外からは接続させない。
Webサーバにリモート接続(ssh/22)されるのも危険なことから、この例ではルータで http(80),https(443)以外のパケットは通さないといった許可リスト方式で設定するのが一般的。
許可リスト方式と拒否リスト方式
ファイアウォールの設定では、信頼できる人だけを接続させる許可リスト方式と、怪しい人を除外する拒否リスト方式がある。
許可リスト方式は、接続していい相手のIPアドレスや、ポート番号だけをFireWallを通過させる方式。(以前はホワイトリスト方式と呼ぶことが多かった。) これとは逆に、攻撃をしてきそうな怪しいIPアドレスや、怪しいポート番号のパケットを捨てて接続させない方式は拒否リスト方式とよぶ。(以前はブラックリスト方式と呼ぶことが多かった。) 学校のサーバは、学内への攻撃を防ぐため、ポート番号については http, https など以外の受信は許可リスト方式となっている。
メールが届くまで
電子メールは、非常に迅速にメッセージを相手に届けることができ、そのメッセージを蓄積・加工・編集・転送できる。また、音声や画像といった情報も、複雑な文字情報に置き換えることで、転送できるようになっている。
メールは、利用者のコンピュータに直接届けられるわけではなく、多くの場合はメールを蓄積するメールサーバに送られる。利用者がメールを読む場合、メールサーバから自分の端末に蓄積されたメッセージを読み込み、メッセージを確認する。このメールのやり取りにおいて、メールを送る時、あるいはメールサーバ間でメールを中継するときには、SMTP(Simple Mail Transfer Protocol) が用いられる。一方、メールサーバからメールを読み出すときには、POP(Post Office Protocol) やIMAP(Internet Message Access Protocol) と呼ばれるプロトコルが用いられる。最近では、IMAPを使ったメールの読み書きをブラウザの中で実行できる WebMail が使われることが増えている。
メールが届くまでの流れは、aさんが”foo@bar.jp“に送る場合、
- aさんは、自分が加入しているメールサーバに、SMTPでメールを送る。
- メールサーバは、メールアドレスのコンピュータ名部分”bar.jp“をDNSに問合せ、そのIPアドレスを調べ、そのコンピュータにSMTPでメールを送る。※
- “bar.jp“のメールサーバは、メールアドレスのユーザ名”foo“を取り出し、各ユーザ毎にメールを保存する。
- “foo”さんは、自分宛のメールを確認するために、POPまたはIMAPで自分のメールサーバ”bar.jp”に接続し、ユーザ名,パスワードで認証して自分宛のメールを受け取る。
※上記の手順2で、相手のメールサーバに直接送れない場合は、コンピュータ名のMXレコードをDNSに問合せを行い、そこで得られたメールサーバに中継を依頼する。
$ nslookup -query=MX fukui-nct.ac.jp. Non-authoritative answer: fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com.jp
上記手順4で自分のメールを読みだす際のプロトコルで、POPは一般的に、メールサーバから自分のメール閲覧ソフトに自分宛のメールをダウンロードして削除する。このため、様々なコンピュータでメールを読む人には不便となってきた。IMAPでは、メールを読んでも、既読の目印をつけサーバに残しておく方式であり、別のコンピュータでメールを閲覧したい時にもサーバ上のメールを読むことができる。メールをフォルダに分類して保存することもできる。最近利用される Webメール では、自分が利用しているメールサーバまでは Web の機能で接続し、Webサーバとメールサーバにて IMAP を使う。
POP, IMAP, SMTPでは、暗号化されない平文が使われることから、通信内容を暗号化して通信する POPS, IMAPS, SMTPS といったプロトコルも使用される。
メールヘッダ
メールを出すときには、宛先やタイトルや本文などの情報がついている。
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とは、勝手に送られてくる迷惑メールであり、昔であれば特定の商品などの宣伝メールが送られてきた。最近では、元々、SMTPでメールを送る際には、ユーザ認証が行われていなかったことから、ウィルス(マルウェア)を拡散させるために、マルウェアをダウンロードさせるWebサイトに誘導したり、メールの添付ファイルに悪意のプログラムを混入させて送り付けてくる。 spam拡散を目的としたウィルスに感染すると、そのパソコンの利用者のメール情報を盗んだり、spam拡散の送信者(spammer)からの指令によって、spamを送信する踏み台(ボットネット/spammerに操られるパソコンのネットワーク)となってしまう。
迷惑メールのspamだが、大文字のSPAMと記載するとランチョンミートの意味となる。
spamが迷惑行為を指すようになったのは、モンティパイソンのSPAMのギャグが由来。
そこで spam 対策として、利用者が身近なメールサーバにメールの配送を依頼する際(前に掲載した図の(1)の通信)には、 SMTP送信の前にPOP/IMAP接続しユーザ認証を行った時だけメールを送ることができるPOP before SMTP(or IMAP before SMTP)や、SMTP-AUTHといった方式でユーザ認証を行うようになってきた。
一方、メールサーバからメールサーバにメールを送る際(前に掲載した図の(2)の通信)では、接続してきたメールサーバが正当なメールサーバなのかを確認する送信ドメイン認証ために、SPF, DKIM,DMARC などの機能が用いられる。SPF(Sender Policy Framework)では、DNSに登録されている正当なメールサーバの情報との比較が行われる。DKIM(DomainKeys Identified Mail)では、送信側のメールサーバが公開鍵暗号(後の講義で説明)をつかったDKIM署名をメールに付け、受信側でDKIM署名を公開鍵を使って検証を行うことで、正答なメールかを判断する。DMARCは、SPFやDKIMで検証した結果、怪しいと判断されたメールの取扱いをどうすべきかを指定できる。
(最近の google mail は、SPF,DKIM,DMARCが設定されていないとメールを受け取らない。これらの対策以前は80%がspamという時代もあったが、近年は全メールのうち50%ほどがspamらしい。)
((( SPF,DKIM,DMARCに関するDNSの設定例 ))) $ nslookup -query=TXT tsaitoh.net tsaitoh.net text = "v=spf1 +ip4:64.33.3.150 a mx -all" ### +ip4: は、このIPアドレスはメールサーバとして「正当」だよ...の意味 $ nslookup -query=TXT postfix._domainkey.tsaitoh.net postfix._domainkey.tsaitoh.net text = "v=DKIM1; h=sha256; k=rsa; p=...公開鍵..." ### p=公開鍵 は、この公開鍵で メールについているDKIM署名が確認できたら「正当」だよ...の意味 $ nslookup -query=TXT _dmarc.tsaitoh.net _dmarc.tsaitoh.net text = "v=DMARC1; p=quarantine; rua=mailto:report-a@tsaitoh.net; ruf=mailto:report-f@tsaitoh.net" ### p=quarantine は「SPF,DKIMの認証に失敗したら迷惑フォルダに分類していいよ」の意味
理解度確認
- メールの送信から受信までの処理を、それに使われるプロトコルを交えて説明せよ。
- Forms による理解度確認
データベースの物理設計
前半はデータベースの物理設計の話を行う。後半は、レポート課題の時間とする。
データベースの物理設計
データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。
ディスク容量の見積もり
データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。
実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。
そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。
また、データベースへのデータの削除を行う場合、データが1つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。
-- PCTFREE,PCTUSED の使い方の例 -- CREATE TABLE Person ( id INTEGER NOT NULL PRIMARY KEY , name VARCHAR( 20 ) , address VARCHAR( 30 ) , ) PCTFREE 10 PCTUSED 40 ; -- PCTFREE+PCTUSED < 100 --
このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。
一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い。
例えば、ページサイズが4096バイト、ページ制御情報が32バイト、スロット制御情報が1データあたり4バイト、PCTFREEが30%、平均の1件あたりのデータ長が256バイトで、100000件を保存するとする。この場合、1ページ内でデータ用に使用できる領域は、(4096-32)✕(1-0.3) = 2844バイトとなる。この場合、1ページに保存できるデータは 2844÷(256+4) = 10.9 となり、最大で10件となる。このため、データを保存するために必要なデータ領域は 4096×(100000/10) = 40.9MB となる。単純にデータを覚えるだけであれば、本来なら 256×100000=25.6MB であるため、実際には1.6倍のデータ領域が必要であることが分かる。(教科書の説明より…)
また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。
補足:残り予定:トランザクション処理, 内部構造, テスト前レポート課題
ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、2分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか?
究極のシンプルなやり方(メモリの無駄)
最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。
import java.util.*; class PhoneName { int phone ; // (例) 27-2925 String name ; PhoneName( int ph , String nm ) { this.phone = ph ; this.name = nm ; } } public class Main { public static PhoneName[] table ; public static void entry( int ph , String nm ) { table[ ph ] = new PhoneName( ph , nm ) ; } public static String find( int ph ) { return table[ ph ].name ; } public static void main(String[] args) throws Exception { table = new PhoneName[ 1000000 ] ; // 無駄にでかい entry( 272925 , "tsaitoh" ) ; entry( 621111 , "nit-fukui") ; entry( 123456 , "forger" ) ; System.out.println( find( 621111 ) ) ; } }
しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。
ハッシュ法
先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。
import java.util.*; class PhoneName { int phone ; // 27-2925 String name ; PhoneName( int ph , String nm ) { this.phone = ph ; this.name = nm ; } } public class Main { public static PhoneName[] table ; public static void entry( int ph , String nm ) { table[ ph ] = new PhoneName( ph , nm ) ; } public static String find( int ph ) { return table[ ph ].name ; } public static void main(String[] args) throws Exception { table = new PhoneName[ 1000000 ] ; entry( 272925 , "tsaitoh" ) ; entry( 621111 , "nit-fukui") ; entry( 123456 , "forger" ) ; System.out.println( find( 621111 ) ) ; } }
ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。
ハッシュ関数に求められる特性
ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムとは言えない。このことから、ハッシュ関数には以下のような特徴が必要となる。
- 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
- 簡単な計算で求まること。
- 同じデータに対し常に、同じハッシュ値が求まること。
ここで改めて、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いのだろうか?
ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか?
オープンアドレス法
先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。
これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。
import java.util.*; class PhoneName { int phone ; // 27-2925 String name ; PhoneName( int ph , String nm ) { this.phone = ph ; this.name = nm ; } } public class Main { public static PhoneName[] table ; public static int hash_func( int ph ) { return ph % 100 ; } public static void entry( int ph , String nm ) { int idx = hash_func( ph ) ; while( table[ idx ] != null ) idx = (idx + 1) % 100 ; table[ idx ] = new PhoneName( ph , nm ) ; } public static String find( int ph ) { int idx = hash_func( ph ) ; for( ; table[ idx ] != null ; idx = (idx + 1) % 100 ) if ( table[ idx ].phone == ph ) return table[ idx ].name ; return null ; } public static void main(String[] args) throws Exception { table = new PhoneName[ 100 ] ; entry( 272925 , "tsaitoh" ) ; entry( 621111 , "nit-fukui") ; entry( 123425 , "forger" ) ; System.out.println( find( 272925 ) ) ; System.out.println( find( 123425 ) ) ; } }
注意:このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。
この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。
文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率ができるだけ一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
public static int hash_func( String nm ) { int s = 0 ; for( int i = 0 ; i < nm.length() ; i++ ) s += nm.charAt( i ) ; return s % 100 ; }
文字列順で異なる値となるように
前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。
public static int hash_func( String nm ) { int s = 0 ; for( int i = 0 ; i < nm.length() ; i++ ) s += (nm.charAt( i ) + s * 小さい素数) % 大きい素数 ; return s % 100 ; }
以下の方法は、繰り返しの度に s に小さい素数を掛けることで、数値全体に文字の影響がでるようにしている。これだけだと計算途中の s の値が最終的な100個に収めるための “% 100” で下2桁に影響がでないことから、大きい素数で余りを求めてみた。この計算方法は、疑似乱数を生み出す線形合同法の考え方を参考にした。
チェイン法
前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。
チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。
この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。
import java.util.*; class PhoneNameNode { int phone ; // 27-2925 String name ; PhoneNameNode next ; PhoneNameNode( int ph , String nm , PhoneNameNode nx ) { this.phone = ph ; this.name = nm ; this.next = nx ; } } public class Main { public final static int table_size = 100 ; public static PhoneNameNode[] table ; public static int hash_func( int ph ) { return ph % table_size ; } public static void entry( int ph , String nm ) { int idx = hash_func( ph ) ; table[ idx ] = new PhoneNameNode( ph , nm , table[ idx ] ) ; } public static String find( int ph ) { int idx = hash_func( ph ) ; for( PhoneNameNode p = table[ idx ] ; p != null ; p = p.next ) if ( p.phone == ph ) return p.name ; return null ; } public static void main(String[] args) throws Exception { table = new PhoneNameNode[ table_size ] ; for( int i = 0 ; i < table_size ; i++ ) table[ i ] = null ; entry( 521125 , "tomoko" ) ; entry( 272925 , "saitoh" ) ; entry( 621160 , "mike" ) ; System.out.println( find( 272925 ) ) ; System.out.println( find( 521125 ) ) ; } }
理解度確認
毎年、冬休み期間中の自主的な理解度確認として、CBT を用いた理解度確認を行っています。今年も実施しますので、下記のシステムにログインし情報構造論では「ソフトウェア」(50分) を受講して下さい。
- https://cbt.kosen-ac.jp/
- 認証には、MS-365 のアカウントとパスワードでログインしてください。
データベースとB木
2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。
B木の構造
2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータ d0, … , d2N-1 と、2N+1本のポインタ p0, … , p2N から構成される。pi の先には、di-1< x < di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。下図は位数2のB木の例を示す。
B木からデータの検索
データを探す場合は、ノード内のデータ di の中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O( log N ) となる。
B木へのデータの追加
B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。
ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。
データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。
B木とデータベース
このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。
データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。
データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。
((リレーショナル・データベースの例)) STUDENT[] RESULT[] ID | name | grade | course ID | subject | point -----+----------+-------+-------- -----+---------+------- 1001 | t-saitoh | 5 | EI 1001 | math | 83 1002 | sakamoto | 4 | E 1001 | english | 65 1003 | aoyama | 4 | EI 1002 | english | 90 外部キー ((SQLの例 2つの表の串刺し)) -- 60点以上の学生名,科目名,点数を出力 -- select STUDENT.name, RESULT.subject, RESULT.point --射影-- from STUDENT , RESULT --結合-- where STUDENT.ID = RESULT.ID -- 串刺し -- --選択-- and RESULT.point >= 60 ; ((上記SQLを Java で書いた場合)) STUDENT[] student = { ... } ; RESULT[] result = { ... } ; for( int st = 0 ; st < student.length ; st++ ) // 結合(from) for( int re = 0 ; re < result.length ; re++ ) if ( student[ st ].ID == result[ re ].ID // 選択(where) && result[ re ].point >= 60 ) System.out.println( student[ st ].name + " " // 射影(select) + result[ re ].subject + " " + result[ re ].point ) ;
- 学生と成績(Paiza.ioでSQL)
- Javaで書いたデータベースの串刺し
B+木
データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。
そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。下図で示すB+木では、青で示す検索用のB木の部分と、赤で示す順次処理を行うためのシーケンスセットの部分から構成される。
ドメイン名とDNS
ドメイン名とDNS
インターネットでの通信では、IPプロトコルでコンピュータを指定するが、IPアドレスは無機質で覚えるのが大変であり、コンピュータに名前をつけて利用する。この際に、コンピュータの所属などが分かるようにしたものをドメイン名と呼ぶ。
例えば、電子情報工学科のドメイン名 www.ei.fukui-nct.ac.jp は、ピリオド部分で区切られ、以下のような意味を持つ。
- .jp – 国ドメイン(.uk イギリス,.ch 中国,アメリカは無し)
- .ac – 種別ドメイン(.co.jp,.com:会社,.ne.jp,net:ネットワーク系)
- fukui-nct – 組織ドメイン
- .ei. – サブドメイン(組織内が細分化されている場合)
- www. – ホスト名※
このような省略されていない、対象となるコンピュータを指定するためのドメイン名は、FQDN(Fully Qualified Domain Name)と呼ばれる。FQDNでの名前を ホスト名※ と呼ぶことも多い。
ただしアメリカでは、国ドメインを一般的に使わない※。また最近では、世界的な企業では国ドメインが意味をなさないので、アメリカ以外でも .com や .net といった、汎用トップレベルドメイン(gTLD)が使われる。様々なサービスを展開している企業では、組織種別が意味をなさないため、toyota.jp といった種別ドメインがない.jpドメイン名も増えてきた。高専機構のドメイン名 kosen-ac.jp も、”kosen-ac” が高専機構の組織ドメイン名なので注意。”-ac”は種別ドメインではない。
以下に、主要な組織ドメイン・国ドメインをあげる。
|
※はgTLD |
DNSのしくみ
DNSは、Domain Name Service であり、コンピュータ名(ドメイン名)から、IPアドレスを調べるサービスで、ポート番号53,UDPを使っている。
インターネットに接続する際には、最も身近なDNS※の情報が与えられ、ユーザがコンピュータ名を問い合わせると、身近なDNSがコンピュータのIPアドレスを返してくれる。この際に、検索結果はキャッシュとして一定期間保存される。身近なDNSがそのコンピュータ名を知らない場合は、上位のDNSに問い合わせを行い、DNSルートサーバもコンピュータ名をキャッシュしていない場合は、管理元の組織のDNSに問い合わせが行われる。このようにすることで特定のDNSサーバに問い合わせが集中しないようになっている(負荷分散)。 DNSサーバの情報は DHCP サーバからIPアドレスなどと一緒に取得することができる。
以前の説明で DHCP(IPアドレス,サブネットマスク,ゲートウェイなどのネットワーク設定のサービス)を紹介しているが、IPアドレス以外にも、DHCPはそのネットワークで使える最寄りの DNS サーバの情報を得ることができる。

DNSと正引きと逆引き
DNSの使い方としては、一般的な使い方は、ドメイン名からIPアドレスを調べる正引きが多い。ブラウザは http://www.fukui-nct.ac.jp/ というURLが与えられたら、DNSに www.fukui-nct.ac.jp を問い合わせ、104.215.53.205 の結果が得られることで、http://104.215.53.205/ のコンピュータに接続を試みる。
これとは逆に、サーバ側では接続してきた相手のコンピュータが信頼できる相手か調べたい時がある。この時には IPアドレスからドメイン名を調べる逆引きを行う。これにより、IP アドレスをきちんと管理している組織であれば、ドメイン名が分かるのでどの組織から接続されているのか確認ができる。
DNSの情報を調べるためのコマンドは、nslookup を用いる。
DNSと様々な情報
DNS では、様々な情報が取得できる。IPアドレス以外にも、メールを送ってもらうサーバのIPアドレス(MXレコード)なども取得できる。
((( 正引きの例 ))) $ nslookup www.google.com Server: 172.31.208.1 Address: 172.31.208.1#53 Non-authoritative answer: Name: www.google.com Address: 142.250.206.228 # 調べる度に異なる値が返ってくるかも Name: www.google.com Address: 2404:6800:400a:804::2004 ((( 逆引きの例 ))) $ nslookup 142.250.206.228 228.206.250.142.in-addr.arpa name = kix06s10-in-f4.1e100.net. # 正引きと逆引きが一致していない例 Authoritative answers can be found from: ((( MX レコードを調べる例 ))) $ nslookup -query=MX fukui-nct.ac.jp # MXレコード = そのドメイン宛のメールはどのコンピュータに送ればいい? Non-authoritative answer: fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com. ((( AAAA レコードを調べる例 ))) $ nslookup -query=AAAA www.google.com # AAAAレコード = IPv6アドレスを指定した正引き Non-authoritative answer: Name: www.google.com Address: 2404:6800:400a:813::2004 ((( 正引きと逆引きの異なる例 ))) $ nslookup tsaitoh.net Name: tsaitoh.net Address: 64.33.3.150 $ nslookup 64.33.3.150 150.3.33.64.in-addr.arpa name = ttn64-33-3-150.ttn.ne.jp.
DNSとセキュリティ
DNSは、コンピュータ名とIPアドレスを対応付けるものであり、これには正引き(コンピュータ名からIPアドレスを求める)と、逆引き(IPアドレスからコンピュータ名を求める)がある。セキュリティ対策が厳しい場所では、
- 正引きを使うことで、特定の組織のドメイン名を持つコンピュータからのアクセスを許可/禁止する。(例:国ドメイン.xxからは接続拒否)
- 正引きで、コンピュータ名が登録されている所からのみ許可する。(例:組織ドメイン.fukui-nct.ac.jpからは接続許可)
- IPアドレスから逆引きして求めたコンピュータ名をさらに正引きして同じIPアドレスが求まるかを確認
といった対策を行う。
- DNSのドメイン名は、当初は最初に申請した人に割り当てられる。このため、nintendo.com といったドメイン名を、関係ない人が取得するといったトラブルがあった。(サイバースクワッティング)
- DNSを用いたクラッキングでは、ウィルスに感染させたパソコンに偽物のIPアドレスを教えることで、偽装した別コンピュータに誘導し個人情報を盗む手口がある。(DNSポイズニング/スプーフィング)
- 他にもウィルスに感染させた大量のパソコンから、同時にルートサーバに大量のDNSの問合せを送ることで、処理能力を低下させると、インターネット全体でDNS参照ができなくなる攻撃もある。(DNSルートサーバへの分散DoSアタック)
- DNSは、他のコンピュータに接続するための重要な情報だが、独裁国家などでは国にとって不都合な情報が得られるドメイン名のIPアドレスを改ざんしアクセスできないようにすることもある。このため、Google 社では 覚えやすい 8.8.8.8 という IPアドレスの DNS サーバを提供している。この 8.8.8.8 は、DNS の返答速度も速いことから、ブラウザの表示速度を高速化するために自分のPCに設定する人も多い。
- 暗号化されていない通信は、同一ネットワーク上の機器がパケット解析ソフトなどを実行すると、相手がどういうDNS参照をしているか見られてしまう。この対策として最近は DNS over HTTPS という方式も出てきている。
ドメイン名と罠
- “jcb.co” というドメイン名のリンク。クレジットカードのJCB?
“.co” はコロンビア、どうみても怪しい。(ウィルス対策ソフトが怪しいサイトとしてブロック) - 昔話 www.docomo.ne.jp にアクセスするつもりが www.docomo.co.jp とタイプミス。
アダルトサイトにつながった… - goog1e.com(lと1の違い)、аррӏе.com (ӏはキリル文字) – ホモグラフ攻撃
- メールアドレス …@gmai.com にメールを送ったら個人情報漏洩 – ドッペルゲンガードメイン
データべースの設計と正規形
テスト問題の返却および解答の説明を行い、その後、データベースの設計において、重要な正規形についての説明の導入。
正規形
データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。一般的に不整合が発生しないためには、以下の第1正規形、第2正規形、第3正規形を満たすように表を分ければよい。
第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。
- 中央省庁のデータ表記を統一:河野太郎行政・規制改革担当相のTweet
データベースと直接関係しないけど、データは原子値じゃないと困るというお話。 - 雑談 正しいデータとして扱えるドキュメントとは…
キーの説明:超キー(スーパーキー)とは、データベースで1つのデータを 選び出すために必要なデータ項目であり、複数の項目で1データを指定 できる場合もある。
候補キーとは、必要最小限の項目となっているものを指す。 1項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。
データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。
![]() |
![]() |
第1正規化 | 第2正規化 |
第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。
- 完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。
- 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。
この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。他に部分従属となっている属性は何か?
- 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。
第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。
![]() |
第3正規化 |
上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。
おまけ:BC正規形,第4,5正規形
この他にも、 さらに「非キーからキーに関数従属性がある場合にそれを取り除く」、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)を分解」して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解」することにより得られる第5正規形などがある。
トップダウン設計・ボトムアップ設計
データベースの設計にあたって、実際の設計手順の説明を行う。
トップダウン設計では、対象業務を記述し、その中から名詞となっている実体を抽出する。 さらに動詞や形容詞のように記載されている関連を抽出する。 抽出した実体・関連では、あいまいであったり冗長であったりするので、整理したうえで、 その実体・関連をER図に表す。
ボトムアップ設計では、対象業務で実際に使われている入力帳票や結果の出力などを 見ながら、第1正規形を満たすように表を作っていく作業からおこなう。
トップダウン設計やボトムアップ設計で、 ER図や第一正規形を満たすような表が出来上がったら、 その属性の中で従属性を確認しながら、第2正規形・第3正規形へと整理していく。
データベース後半課題
データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。
情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研テーマであれば、実験結果の表をデータベースで管理するとした場合の設計を行うこと。どちらでもない卒研で、卒研のテーマの中にデータベース化すべき対象が無い場合は、身の回りの帳票(例えばコンビニのレシートなど)をデータベース化することを検討すること。
レポートで記載する内容は、以下の通りとする。
- 卒業研究におけるデータベース化する対象の説明
- データベースをトップダウン設計する際の
- 実体と関連を抽出するまでの説明
- 正規化を行う経過の説明
- 上記を踏まえたトップダウン設計でのER図
- データベースをボトムアップ設計する際の
- 対象とする帳票に相当するデータの一例と説明
- レベル分けや正規化を行う経過の説明
- 上記を踏まえたボトムアップ設計でのER図
- 考察
- トップダウン設計とボトムアップ設計に違いがあれば、設計の見直しの過程の説明
- 両設計方法から分かったこと
Node-REDのインストール
卒研学生用に、古いPCに Ubuntu 24 をインストールし、Node-RED 環境を構築
Ubuntu のセットアップ後に以下の作業を行う。
nodejs のインストール
新しい nodejs 22 を入れたいので apt パッケージは使わない。
#--- nodejs 22 install $ sudo apt install curl $ curl -fsSL https://deb.nodesource.com/setup_22.x | sudo -E bash - $ sudo apt install -y nodejs
Node-REDのインストール
#--- node-red install $ sudo npm install -g npm@10.9.1 $ sudo npm install -g -unsafe-perm node-red node-red-admin
Node-REDのsystemd登録
OS起動と共に Node-RED を起動したいので、Systemd に登録
Systemd のファイルを作成
#--- node-red systemd setup $ sudo vi /etc/systemd/system/node-red.service [Unit] After=syslog.target network.target Documentation=http://nodered.org/ [Service] Environment="NODE_OPTIONS=--max-old-space-size=128" Environment="NODE_RED_OPTIONS=-v" ExecStart=/usr/bin/node-red $NODE_OPTIONS $NODE_RED_OPTIONS WorkingDirectory=/root/ User=root Group=root Nice=10 SyslogIdentifier=Node-RED StandardOutput=syslog Restart=on-failure KillSignal=SIGINT [Install] WantedBy=multi-user.target
Systemd の有効化と起動と確認
$ sudo systemctl enable node-red $ sudo systemctl start node-red $ sudo systemctl status node-red ● node-red.service Loaded: loaded (/etc/systemd/system/node-red.service; enabled; preset: enabled) Active: active (running) since Wed 2024-12-04 14:25:50 JST; 10min ago Docs: http://nodered.org/ Main PID: 23602 (node-red) Tasks: 11 (limit: 9334) Memory: 58.2M (peak: 68.4M) CPU: 2.243s CGroup: /system.slice/node-red.service └─23602 node-red 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 復元することはできません。その場合、ファイルを削除してクレデンシャルを 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 再入力しなければなりません。 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 設定ファイル内で 'credentialSecret' オプションを使って独自キーを設定 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: します。変更を次にデプロイする際、Node-REDは選択したキーを用いてクレ 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: デンシャルを再暗号化します。 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: --------------------------------------------------------------------- 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 4 Dec 14:25:51 - [warn] 暗号化されたクレデンシャルが存在しません 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 4 Dec 14:25:51 - [info] サーバは http://127.0.0.1:1880/ で実行中です 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 4 Dec 14:25:51 - [info] フローを開始します 12月 04 14:25:51 tsaitoh-lab Node-RED[23602]: 4 Dec 14:25:51 - [info] フローを開始しました
後は、ブラウザを起動して、http://127.0.0.1:1880/ を開くだけ。