ホーム » スタッフ » 斉藤徹 (ページ 2)

斉藤徹」カテゴリーアーカイブ

2024年3月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

検索・リンク

NoSQLと Google Firestore

データベースシステムとして、最近は NoSQL (Not Only SQL) が注目されている。この中で、広く使われている物として、Google Firestore などが有名である。教科書以外の最近のデータベースの動向ということで、最後に NoSQL の説明を行う。

リレーショナルデータベースシステムの問題

リレーショナルデータベースのシステムでは、大量の問い合わせに対応する場合、データのマスターとなるプライマリサーバに、そのデータの複製を持つ複数のセカンダリサーバを接続させる方式がとられる。しかしながら、この方式ではセカンダリサーバへのデータ更新を速やかにプライマリサーバに反映させる、さらにその結果が他のセカンダリサーバに反映させる必要があることから、大量のデータに大量の問い合わせがあるようなシステムでは、これらのデータ同期の性能が求められる。しかも、プライマリサーバが故障した場合の復旧なども考えると、こういったプライマリ・セカンダリ・サーバ構成での運用・管理は大変である。

NoSQLの利点

NoSQLのデータベースでは、すべてのデータを複数のサーバ(別のデバイス,ネットワーク)に冗長化したうえで分散して保存する。この際に、どのサーバがプライマリサーバといった概念はない。もし1つのサーバが故障したとしても、分散して保存されたデータから元のデータを自動的に修復できるような構造となっている。

データの分散保存であれば、ハードディスクの RAID システムなども関連知識となるであろう。

  • RAID0 – ストライピング(データを別デバイスに分散保存し、並行読み出しで高速化)
  • RAID1 – ミラーリング(データを複数デバイスに同じものを書き込んで、データ故障耐性を実現)
  • RAID5 – データを複数デバイスに分散保存する際に、データ誤り訂正のデータも分散保存し、高速化と故障耐性を実現
  • RAID6 – データ誤り補正のデータを複数もたせて、分散保存

リレーショナルデータベースで大量のユーザからアクセスされる場合、データが安全に取り扱うことができたり、システムに障害が発生した時の対応や、システムのスケーラビリティ(利用状況に応じて処理するプロセッサなどを増やしたり減らしたりする機能)が重要となる。NoSQLのシステムでは、中心となるプライマリサーバを作るのではなく、データを複数のシステムに分散して保存し、障害が発生しても、分散したデータから自動的にデータを修復できるような構成とする。

NoSQLのシステムでは、データ格納形式から、キーバリューストア型、カラムストア型、ドキュメントデータベース、グラフデータベースに分類される。最も代表的なものは、保存するデータ(Value)に対し検索するためのキー(Key)だけの基本的なデータ検索だけを提供する キーバリューストア(Key-Value store)である。こういった構成ではSQLとは違い、複数のテーブルをまたがった検索などができない(サブコレクションなどを使えば代用可能)。

Google の Firestore

NoSQLのデータベースを構築したのは、Google が先駆けであった。現在、このGoogle の NoSQL のシステムは、Firestore として利用されている。(データベースはFireBase)

Firestore は、ドキュメントモデルデータベースの一種であり、すべてのデータはドキュメントとコレクションに保存される。ドキュメントは、データベースでのレコードに相当するが、属性名とそれに対応したデータの JSON オブジェクトである。コレクションは、キーにより対応するドキュメントを取り出せるデータ群である。ドキュメントの中に、サブコレクションを保存することもできる。

参照カウンタの問題とガベージコレクタ

前回の授業では、共有のあるデータ構造では、データの解放などで問題が発生することを示し、その解決法として参照カウンタ法などを紹介した。今日は、参照カウンタ法の問題を示した上で、ガベージコレクタなどの説明を行う。

共有のあるデータの取扱の問題

前回の講義を再掲となるが、リスト構造で集合計算おこなう場合の和集合を求める処理を考える。

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 の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、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にならないので、取扱いが苦手。

ガベージコレクタ

では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか?
最も簡単な方法は、「処理が終わっても使い終わったメモリを返却しない」方法である。ただし、このままでは、メモリを使い切ってしまう。

そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、

  1. すべてのメモリ空間に、「不要」の目印をつける。(mark処理)
  2. 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
  3. その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)


この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。

最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような関数に入った時点で生成され関数終了ですぐに不要となる領域は、参照カウンタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。

大量のメモリ空間で、メモリが枯渇したタイミングでガベージコレクタを実行すると、長い待ち時間となることから、ユーザインタフェースの待ち時間に、ガベージコレクタを少しづつ動かすなどの方式もとることもある。

ガベージコレクタが利用できる場合、メモリ管理を気にする必要はなくなってくる。しかし、初心者が何も気にせずプログラムを書くと、使われないままのメモリがガベージコレクタの起動まで放置され、場合によっては想定外のタイミングでのメモリ不足による処理速度低下の原因となる場合もある。手慣れたプログラマーであれば、素早くメモリを返却するために、使われなくなった変数には積極的に null を代入するなどのテクニックを使う。

プログラム言語とメモリ管理機能

一般的に、C言語というとポインタの概念を理解できないと使えなかったり、メモリ管理をきちんとできなければ危険な言語という点で初心者向きではないと言われている。

C言語は、元々 BCPLB言語を改良してできたプログラム言語であった。これに、オブジェクト指向の機能を加えた C++ が作られた。C++ という言語の名前は、B言語→C言語と発展したので、D言語(現在はまさにD言語は存在するけど)と名付けようという意見もあったが、C++ を開発したビャーネ・ストロヴストルップは、ガベージコレクタのようなメモリ管理機能が無いことから、D言語を名乗るには不十分ということで、C言語を発展させたものという意味でC++と名付けている。

こういった中で、C++をベースとしたガベージコレクタなどを実装した言語としては、Java が挙げられる。オブジェクト指向をベースとしたマルチスレッドやガベージコレクタに加え、仮想マシンによる実行で様々なOS(やブラウザ)で動かすことができる。

最近注目されている言語の1つとして、C言語の苦手であった「メモリ安全性」や実行効率を考えて開発されたものに Rust が挙げられる。メモリ管理や効率などの性能から、最近では Linux の開発言語に Rust を部分的に導入されている。


C言語でデータが保存される領域は大きく以下の3つに分類される。

  1. 静的データ領域(大域変数領域)
  2. スタック領域(局所変数)
  3. ヒープ領域(malloc(),free()で管理される領域)

2,3は、処理の途中で領域が作られ不要になったら消える領域であり動的メモリ領域という。

局所変数とスタック

局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。

関数の中で関数が呼び出されると、スタックに戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。

baz()の中で、「*((&c)+8) = 123 ;」を実行したら、bar()のxを書き換えられるかも…(実際の関数呼び出し時に保存される情報はもう少し複雑:コールスタック/Wikipedia)

こういった変数の並び順を悪用し、情報の読み書きを防ぐために、局所変数の保存場所の順序を入れ替えたり、メモリのアドレス空間配置のランダム化などが行われたりする。

 

リモート接続と暗号化

リモート接続

サーバなどの管理をしていると、インターネットの先にあるコンピュータを操作したい場合が多い。こういった場合には、リモート接続機能を用いる。

リモート接続による相手側のコンピュータを操作する場合、相手側のコンピュータには リモート接続 用のサーバプログラムを起動しておく。こういったリモート接続を利用するのは、”unix” の利用者が多いが、”unix” では、サーバ のプログラムは、一般的にデーモン(daemon/守護神)と呼ばれる。[daemonとdemonの違い]

telnet と rlogin

telnet は、最も基本的なリモート接続の方法であり、TCP の 23 番ポートを使う。telnetのサーバ(telnetd – telnet daemon)は、送られてくるタイプされた文字を unix の shell (キーボードでの命令を実行するプログラム) に渡し、shell の実行結果の文字を接続元に送り返す。

telnet のクライアントの基本的動作は、タイプされた文字を送って、受信した文字データを表示するだけなので、通信の動作の確認にもよく使われる。

例えば、Webサーバは、80番ポートに”GET /ページの場所”を送ると、HTMLデータが受信できる。この手順を telnet で行う場合は、以下の様に行う。

rlogin は、TCP の 513 番ポートを使うリモート接続用のソフトで、サーバで rlogind を起動しておく。unix で rlogin クライアントを使うと、リモート側で命令を実行したりファイルをコピーすることができる

こういったリモート接続ができると、ネットワークの向こう側のコンピュータを自由に操作できる一方で、login のパスワードが破られるとコンピュータを悪用されたり情報を盗まれる可能性がある。
特に、telnet , rlogin では、通信の内容が暗号化されないため、パケット盗聴(後述)されると、サーバを悪用されてしまう。このため 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 では、サーバのディスプレイ画面の情報をクライアントに送り、クライアントの操作(キーボード入力やマウス操作)がサーバに送られ、サーバのコンピュータを自由に操作ができる。

VPN

VPN(Virtual Private Network)とは、物理的に離れた場所にある拠点間を暗号化通信をつかって、仮想的に同じネットワーク内で繋がっているような安全なデータ通信を作るもの。「仮想プライベート・ネットワーク」と呼ばれ、ルータにVPN機能が内蔵されていたり、パソコンではVPNに接続するためのソフトウェアが内蔵されている。VPNで利用されるプロトコルには、SSH/TLS(SSL)/IPsec/PPTP/L2TP/L2F/MPLSなどの種類がある。

[Wikipediaより引用]

バックドア

ssh, リモートデスクトップ, VPN といったリモート接続は、遠隔地のコンピュータを自由に操作できることから、様々なコンピュータを管理している場合、広く使われている。しかしながら、クラッキングなどの悪用の危険があるため、sshサーバ、リモートデスクトップサーバなどのソフトは、通常利用者は起動しないこと

クラッキングなどを行う場合、ウィルスを使ってリモート接続のためのソフトを動かされると、相手のコンピュータを自由に使える。このような、本来の使い方ではない侵入経路は、バックドアなどと呼ばれる。

クラウド・コンピュータ

インターネットのサービスを構築する時には、自分のコンピュータをインターネットからアクセスさせる(オンプレミス)のではなく、企業などがリモート接続機能を使って、貸し出し用に提供されているコンピュータを利用する場合も多い。こういうコンピュータを利用してサービスを提供する場合、利用者にしてみればどこにあるかよくわからないコンピュータ資源を使うことから、クラウド・コンピューティングと呼ばれる。有名なクラウド サービスとしては、Amazon AWS, Microsoft Azure, Google Cloud がある。

[Wikipediaより引用]

クラウドコンピュータを借りる場合、以下のような形態がある。

  • SaaS (Software as a Service) : リモートサーバ上でアプリケーションを事業者側が用意してあるものを借りる
  • PaaS (Platform as a Service) : 事業者側が準備した Web サーバなどを借りて、サービス提供者がソフトウェアなどを準備してサービスを提供する
  • IaaS (Infrastucture as a Service) : 事業者側がコンピュータやネットワークなどの提供する環境(インフラ)を借りて、その上に利用者が OS, Webサーバ(ミドルウェア), アプリケーションを準備してサービスを提供する
形態 コンピュータ,
ネットワーク
OS
(Linux,Windows…)
ミドルウェア
(Web,DB…)
アプリケーション ユーザ
SaaS クラウド事業者が提供
PaaS クラウド事業者が提供 サービス提供者が準備
IaaS クラウド事業者が提供 サービス提供者が準備

暗号化

Ethernet では1本の通信線を共有したり、WiFiのような無線通信では、通信データの盗聴が簡単にできてしまう。クラッカーは、通信データの中から”login, password” といった文字を検索し、その近辺の文字を探すことでパスワードを盗み出す。

このようなことを防ぐために通信データの暗号化は重要な方法である。

暗号化アルゴリズム

暗号化の最も原始的な方法が、置換式 と呼ばれる方法で、特定の文字を別な文字に変更する。rot13は、A→N,B→Oに置き換える暗号。コナン・ドイル原作のシャーロック・ホームズに出てくる踊る人形などもこれに相当する。これらの方法では、アルファベットの文字の出現頻度から元の文を想像することで解読されてしまう。

エニグマ(Enigma)は、第2次世界大戦でナチス・ドイツが用いたロータ式暗号機であり、置換式の解読方法が不可能であった。しかし、イギリスのアラン・チューリングが電気式の解読器(ボンブ)を開発することで暗号解読が可能となった。この解読器が現在のコンピュータの原型となっている。

チューリングによる暗号解読は、映画「イミテーションゲーム」を参照。

最近では、様々な暗号化アルゴリズムが開発されており、古くは “DES, AES“といったアルゴリズムが使われていたが、コンピュータの性能の向上と共に、解読に必要な時間が短くなったことから、RSA といった新しい暗号化方式が考えられ、さらに暗号化の鍵を長くすることで解読に要する時間を長くするようになっている。
(暗号化アルゴリズムについては、次週の講義でもう少し詳しく解説する。)

パスワード解読方法

ログインなどで使われるパスワードは、どのように破られるのだろうか?

  • ブルートフォース攻撃:単純に全ての文字を試す方式。文字の組み合わせ問題なので、パスワード文字列長をNとした場合、数字だけ(10N)とか英字だけ(26N)といった組み合わせでは、短時間に解読されてしまう。数字,大文字,小文字,記号などを交えたパスワードが理想。
  • 英単語辞書を用いた辞書攻撃:パスワードが長い場合、文字列の全ての組み合わせを試すには長い時間が必要となる。しかし、パスワードはユーザが記憶して使うことから覚えやすい単語が使われる。このため英単語辞書の文字を組み合わせることで、解読時間を短くできる場合がある。
  • 漏えいパスワードによる辞書攻撃:サーバへのリモート接続などができてしまった場合、パスワード情報が盗まれる場合がある。この時、別なサイトに同じパスワードを使っていると、その漏えいしたパスワードで別のサイトも接続ができてしまう。これらのことから、同じパスワードを使いまわすことは避けるべきである。
  • ソーシャル攻撃:パスワードには、簡単に覚えられるように自宅の電話番号、誕生日、家族の名前といったものを使う人が多い。このため、SNS で相手に友達登録をしてもうことで、こういった情報を手に入れ、パスワードを破る方法。最近の有名人の個人情報漏洩はこの手の攻撃が多い。

    ソーシャル攻撃は、”元クラッカー” ケビン・ミトニックが有名

攻撃が難しい暗号化へ

先に述べたような、login に使うパスワードなどは、ブルートフォース攻撃をうけると解読は時間の問題となる。これらの対策として毎回違う鍵(パスワード)を使えばいい。

    • 暗号表:置換式で読み取られるのを防ぐために、置換する文字の表を沢山作っておき、別の方法でその度毎に置換表を変更する
  • ワンタイムパスワード:使い捨てのパスワードをあらかじめ沢山作っておき、接続の度に次のパスワードを用いる方式。あるいは、時間から特殊な計算方法で生成されるパスワード。時間と共に変化するのでその度毎に違うパスワードとなる。毎回違うパスワードを入力するため、パスワード表を常に持ち歩いたり、入力が面倒なので数字だけを使うことが多く、この方法だけでは使いにくい。(次週に多要素認証などの解説も行う)

理解度確認

  • ファイアウォールの仕組みを説明せよ。
  • つぎの利用形態は、PaaS, SaaS, IaaS のどれにあたるか?
    • Microsoft が準備した Teams を使って、授業アンケートを取る。
    • 福井高専は、Microsoft Azure 環境の上に、Linux, Webサーバ, PHP, MySQL, WordPress をインストールして HP を運営。

トヨタの豊田章男…

トヨタの一族なのにトヨタの捨て駒社長…。なかなか面白い話や。

B木とB+木とハッシュ法

データベースでは、キーなどの値を高速に探し出すために、単純なデータが並んだだけのテーブルとは別に、検索専用のデータ構造を別に持たせることが多い。これらの検索用のデータは、インデックスファイルと呼ばれる。また、データベースのテーブルのデータも、高速に検索する機能とすべてのデータを順次取り扱うための機能が求められる。これらの機能を実現するための仕組みを以下に説明する。

B木

データベースのデータを扱う場合には、B木を用いることが多い。(4年の情報構造論で説明済み)

複数のデータを格納するノードは、位数Nであれば、2✕N個のデータと、その間のデータを持つノードへの2N+1個のポインタで構成される。

ノードにデータを加える場合(あるいは削除する場合)は、頻繁にノードのポインタの付け替えが発生しないように、データがN個を下回った時や、2N個を超える場合に以下のような処理を行う。ノード内のデータ数が2Nを超える場合は、均等に木構造が成長するように、中央値を上のノードに移動し、ノードを2分割する。

データを削除することでN個を下回る場合は、隣接するノードからデータを移動する。(上図の緑部分のように上位ノードの値を交えながら移動する)

このような処理を行うことで、極力不均一に成長した木構造が発生しないようにB木は管理されている。

B+木とシーケンスセット

再帰的な木構造のB木では、特定のデータを探す場合には、O(log N)で検索が可能である。

しかしながら、直積のようなすべてのデータを対象とする処理を行う場合、単純なB木では再帰呼出しをしながらの処理を必要とすることから、複雑な処理が発生する。そこで、データ列を横方向にアクセスするための単純リストであるシーケンスセットをB木と並行して管理するデータ構造B+木である。

データを検索する場合は、B木構造部を用い、全データ処理は、シーケンスセットを用いる。

ハッシュ法

ハッシュ表は、データの一部をとりだしてハッシュ値を求め、そのハッシュ値を番地とする場所にデータを保存する方法である。しかし、データの一部を取り出すため、異なるデータに対して同じハッシュ値となる場合がある。これをハッシュ衝突とよぶ。この際のデータの保存の方法から、2つの方式がある。

  1. オープンアドレス法
    ハッシュ表がすでに埋まっていたら、別の保存場所を探す方式。
  2. チェイン法
    同じハッシュ値となるデータをリスト構造で保存する方法。

チェイン法と共有のあるデータの問題

前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか?

ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか?

オープンアドレス法

先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。

これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。

// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 )
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故?
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ;
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 ) {
      if ( table[ idx ].phone == phone )
         return table[ idx ].name ;
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故?
   return NULL ; // 見つからなかった
}

注意:このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。

この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。

チェイン法

前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。

この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。

#define SIZE 100
int hash_func( int ph ) {
   return ph % SIZE ;
}
struct PhoneNameList {
   int phone ;
   char name[ 20 ] ;
   struct PhoneNameList* next ;
} ;
struct PhoneNameList* hash[ SIZE ] ; // NULLで初期化

struct PhoneNameList* cons( int ph ,
                            char* nm ,
                            struct PhoneNameList* nx ) {
   struct PhoneNameList* ans ;
   ans = (struct PhoneNameList*)malloc(
                      sizeof( struct PhoneNameList ) ) ;
   if ( ans != NULL ) {
      ans->phone = ph ;
      strcpy( ans->name , nm ) ;
      ans->next = nx ;
   }
   return ans ;
}

void entry( int phone , char* name ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , name , hash[ idx ] ) ;
}
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   struct PhoneNameList* p ;
   for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
      if ( p->phone == phone )
         return p->name ;
   }
   return NULL ;
}

これまでの授業の中では、データを効率よく扱うためのデータ構造について議論をしてきた。これまでのプログラムの中では、データ構造のために動的メモリ(特にヒープメモリ)を多用してきた。ヒープメモリでは、malloc() 関数により指定サイズのメモリ空間を借りて、処理が終わったら free() 関数によって返却をしてきた。この返却を忘れたままプログラムを連続して動かそうとすると、返却されなかったメモリが使われない状態(メモリリーク)となり、メモリ領域不足から他のプログラムの動作に悪影響を及ぼす。

メモリリークを防ぐためには、malloc() で借りたら、free() で返すを実践すればいいのだが、複雑なデータ構造になってくると、こういった処理が困難となる。そこで、ヒープメモリの問題点について以下に説明する。

共有のあるデータの取扱の問題

リスト構造で集合計算の和集合を求める処理を考える。

// 集合和を求める処理
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, 2, 3, 4 }
                                     //          ~~~~~~~ ここは b
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( a ) ;
   list_del( b ) ;
   list_del( c ) ; // list_del(b)ですでに消えている
}                  // このためメモリー参照エラー発生

このようなプログラムでは、c=join(a,b) ; が終わると下の図のようなデータ構造となる。しかし処理が終わってリスト廃棄list_del(a), list_del(b), listdel(c)を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。

実体をコピーする方法

こういった共有の問題の一つの解決法としては、共有が発生しないように実体を別にコピーする方法もある。しかし、この方法はメモリがムダになる場合もあるし、List内のデータを修正した時に、実体をコピーした部分でも修正が反映されてほしい場合に問題となる。

// 実体をコピーする(簡潔に書きたいので再帰を使う)
struct List* copy( struct List* p ) {
   if ( p != NULL )
      return cons( p->data , copy( p->next ) ) ;
   else
      return NULL ;
}

// 共有が無い集合和を求める処理
struct List* join( struct List* a , struct List* b )
{
   struct List* ans = copy( b ) ;
   //                 ~~~~~~~~~実体をコピー
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
        ans = cons( a->data , ans ) ;
   return ans ;
}

参照カウンタ法

上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

struct List* cons( int x , struct List* p ) {
   struct List* n = (struct List*)malloc( sizeof( struct List* ) ) ;
   if ( n != NULL ) {
      n->refc = 1 ; // 初期状態は参照カウンタ=1
      n->data = x ;
      n->next = p ;
   }
   return n ;
}

struct List* copy( struct List* p ) {
   p->refc++ ;  // 共有が発生したら参照カウンタを増やす。
   return p ;
}
// 集合和を求める処理
struct List* join( struct List* a , struct List* b )
{
   struct List* ans = copy( b ) ;
   //                 ~~~~~~~~~共有が発生するのでrefc++
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p != NULL
        && --(p->refc) <= 0 ) {    // 参照カウンタを減らし
      //   ~~~~~~~~~~~
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

int 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 ) ;

   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( a ) ;  // aの要素は全部refc=1なので普通に消えていく
   list_del( b ) ;  // bは、joinの中のcopy時にrefc=2なので、
                    // この段階では、refc=2 から refc=1 になるだけ
   list_del( c ) ;  // ここで全部消える。
}

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: そのようなファイルやディレクトリはありません

トランザクション処理

トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

排他処理の実装方法

排他処理を実現する方法としては、ロック(Lock)、セマフォ(Semaphore)、ミューテックス(Mutex)が使われる。

ロックの例としては、C言語では flock() 関数が有名。(後述のロッキング方式/悲観的制御を参照)

  • C言語でのファイルロック(共有ロック,排他ロックの機能あり)
  • 共有ロック:他のプロセスの読み込みは許可するけど、書き込みは禁止。
  • 排他(占有)ロック:他のプロセスの読み込みも書き込みも禁止する。
  • 使い終わったらアンロック。

セマフォの例としては、カウンタセマフォが使われる。

  • 対象資源を使用中のプロセスの数を表す、カウンタを使う。
  • 初期値0の状態は、だれも使っていない状態。
  • 対象資源を使う時にカウントアップ、使い終わったらカウントダウンする。

ミューテックスは、セマフォの使用中/開放状態を 0,1 で管理するようなもの。

ロックはファイルに対して使うもので、セマフォやミューテックスは、プロセスやスレッド間の同期に使うことが多い。

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

  1. ロッキング方式(悲観的制御)
    先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。

    • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
    • ロックの種類
      ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
      この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
    • 2相ロッキングプロトコル
      トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
  2. 時刻印方式/タイムスタンプ方式(楽観的制御)
    データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。

グラフ理論(Wikipedia)

前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ぶ。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼び、始点(行)と終点(列)の経路がある所を1で表す。

ふくいソフトウェアコンペ大賞!

2023年12月23日に開催された、ふくいソフトウェアコンペティション2023にて、4EI 藤野間くん, 中西くん, 山腰くんによる「チャリレコ- 1人1人の未来を守る次世代システム-」が、ふくいソフトウェアコンペの最優秀賞を受賞しました。

2023年最後の授業は休校かぁ…

自宅の外の雪の状態としては大した雪じゃないけど、休校になっちゃったなぁ…

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以外にも使う。

最近のブラウザは、スキーマ欄の”https://”やコンピュータ名の先頭の”www.”を省略することができる。また http は暗号通信を使わず危険であることから、警告メッセージが表示されたり、可能であれば https の通信に切り替えを試みられる。

http (Hyper Text Transfer Protocol) の流れ

httpのサーバ(Webサーバ)とブラウザでは、以下のような手順で処理が行われる。例えば http://www.ei.fukui-nct.ac.jp/~t-saitoh/index.html のページが表示されるまでを考えると、

  1. ブラウザのURL欄に、目的サイトのURLを入力。
  2. 基本的には、スキーマ欄に記載されたプロトコル(http)名から、ポート番号と通信方法(http)を決める。一般的な http 通信では、ポート番号には 80 を使う。
  3. コンピュータ名部分(www.ei.fukui-nct.ac.jp)を DNS に問合せして、得られたIPアドレスのコンピュータに接続。
  4. httpの最も簡単な GET メソッドでは、Webサーバに、サーバ内のファイル位置(/~t-saitoh/index.html)を伝えると、Webサーバは応答ヘッダ情報応答本文の指定された場所のファイルの内容を返送する。(下図参照)
  5. 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ページを検索してくれるシステムは、サーチエンジンと呼ばれる。

ディレクトリ型

最初に現れた検索システムは、ページ作者が自分のページのURLと内容となるキーワードをサーチエンジンに登録しておき、内容のカテゴリー別に、ページの紹介文章が表示されるディレクトリ型であった。(初期のYahoo)

しかし、登録するキーワード以外の文字で探そうとすると、情報を見つけることができない。

ロボット型

これらの問題を解決すべく登場したのが、Google のようなロボット型サーチエンジンである。
ロボット型の検索システムでは、クローラーとかロボット(あるいはボット)とか呼ばれるプログラムを使い、Webページの内容をダウンロードし、そこに記載された文字を使ってURLのデータベースを作成する。

  1. 与えられた URL の先のページをダウンロードする。
  2. ページ内の文字を単語に切り分けして、それぞれの単語とURLを関連付けてデータベースに保存
  3. ページ内にリンクが含まれていたら、そのURLで、この作業を再帰的に繰り返す。

サーチエンジンで検索が行われると、クローラーの処理で作られたデータベースに問い合わせ、見つかったURLの情報を表示する。

Googleなどでは、多くのユーザが探したいページを提供するために、たくさん使われている単語を重要語としたり、たくさんのページからリンクされているページを表示順上位に表示するような工夫をしている。

ページランキングを上げるためのWebページの工夫をすることを、SEO (Search Engine Optimization) という。しかし逆にページランキングを不当に上げようと特殊なテクニックのページ作りをする人もいるが、最近では不当なページ作りは逆にランキングが落とされるようになっている。

理解度確認

  • URLが与えられてページが見れるまでに行われることを説明せよ。
  • サーチエンジンのディレクトリ型とロボット型の違いを説明せよ。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー