kakts-log

programming について調べたことを整理していきます

確率的データ構造・ブルームフィルタについてのまとめ

概要

特定のデータが、ある集合やリストに含まれるかどうかを判定するために、線形探索や二分探索など、いくつかのサーチアルゴリズムがありますが、
本稿ではメモリの使用効率、探索の際の計算量が優れているブルームフィルタを用いたアルゴリズムについてまとめます。

ブルームフィルタとは

ブルームフィルタとは確率的データ構造の一種で、あるデータが集合に属するかどうかを判定する際に使われます。
特徴としては、メモリの空間消費が少なくすみ、非常に効率的にデータの存在判定ができます。
デメリットとしては、false-positive(偽陽性)によるデータの誤判定の可能性があり、集合に存在しないデータを存在すると誤判定してしまう場合があります。このような誤判定が許されないような状況においては、ブルームフィルタは使えません。 逆に、false-negative(偽陰性)による誤判定はないため、データは実際にあるのに存在しないと判定することはありません。

ブルームフィルタ - Wikipedia

ブルームフィルタのデータ構造について

ハッシュベースサーチは集合Cのすべての要素をリンクトリストもしくはオープンアドレスハッシュテーブルHに格納する どちらのケースにおいても、多くの要素がハッシュテーブルに格納され、要素の格納に係る時間は、要素数が増えるに従い増えていく。 実際、この振る舞いは他のサーチアルゴリズムにも共通したもので、要素の探索にかかる比較時間とのトレードオフとなる。

ブルームフィルターはビット配列Bを提供し、集合CからBに追加することと、特定の要素EがBに存在するかどうかの判定は定数時間で行うことができ、驚くことに、これは既にBに格納されたデータ数とは独立しています。
しかし、ブルームフィルターにおいては、要素がBに存在するか判定する際に、 false-positiveである場合があります。 つまり、実際には存在しないのに、存在すると判定してしまう場合があります(日本語で言うと偽陽性

False-positiveになる簡単な例

例 下記のテーブルは、u,v,w,zの4つのデータに対して、ハッシュ関数3つそれぞれで得られたハッシュ値をまとめています。

ハッシュ値1 ハッシュ値2 ハッシュ値3
u 1 3 8
v 2 4 8
w 1 2 6
z 1 2 3

u, v, wの3つのデータを集合Cに追加したときのビット配列は 下記の通りになるとします。

配列のインデックス 0 1 2 3 4 5 6 7 8 9
ビット 0 1 1 1 1 0 0 0 1 0

このとき、このビット配列をもとに、u, v, w, zのそれぞれが集合Cに存在するかを判定します。

各データに対して計算された 3つのハッシュ値をビット配列のインデックスとみなし、ビット配列の各インデックスの値をチェックします。
データuについて見てみると、インデックスは 1, 3, 8となります。 ビット配列の 1, 3, 8番目の値をみると、それぞれ1となるので、データuが集合Cに存在すると判定されます。 これは、実際にデータuは集合Cに追加されているので、正しい振るまいです。データv, wにおいても同様に存在すると判定されます。

ここで、実際に集合Cに追加されていないデータzについて見てみます。 3つのインデックスは 1, 2, 3となりますが、それぞれビット配列の要素を調べてみると、どれも1となり、データzは集合Cに存在していないに、存在すると判定されます。 これがfalse-positiveの一例です。
言うまでもなく、ブルームフィルタの実装において、このfalse-positiveの割合が低ければ低いほど、ブルームフィルタの精度が高くなります。
この精度向上のためには、ハッシュ値を均等に出力するハッシュ関数をどう実装するか、さらにはビット配列の長さをどうするかも重要になります。

pythonですが簡単な実装は以下の通りになります。

Best, Average Worst: O(k)

create(m)
    return bit array of m bits
end

add (bits, value)
    # Kビットある場合、ビット毎にの桁を計算するためK個分のハッシュ関数がある
    foreach hashFunction hf
        ## << left シフトオペレータをつかって2^(hf)を効率的に計算できる
        setbit = 1 << hf(value)
        bits |= setbit
end

search(bits, value)
    foreach hashFunction hf
        checkbit = 1 << hf(value)
        # もしチェックビットが0だったら求める値は存在しない
        if checkbit | bits = 0 then
            return false

         # false-positiveすべてのビットがセットされているが求める値は追加されていない
    return true
end

ブルームフィルタの入出力

ブルームフィルタはデータをハッシュベースサーチのように処理する。 アルゴリズムはmビットのすべてが0になっているビット配列Mからスタートする。 データが追加される時、k個のハッシュ関数が、Mの配列内のビットの位置を計算する。

ブルームフィルタのコンテキスト

ブルームフィルタは、メモリの使用量が少なくすみ、非常に効率的ですが、利用可能な条件があり、 それは先程説明したfalse-positiveに関して許容されるときです。

有効的な活用法としては、探索コストの高いデータ探索(diskドライブへのアクセスが行われる場合)などに、前段として ブルームフィルタを導入し、false-positiveなケースはあるが、事前にデータ存在判定を行う事が挙げられます。

solution

ブルームフィルタは mビットのデータが必要です。 下記の実装は

class bloomFilter:
    def __init__(self, size = 1000, hashFunctions=None):
        """
        指定したサイズのビット数をもつブルームフィルタを作成する。
        同時にハッシュ関数も作成する
        """

        self.bits = 0
        self.size = size

        if hashFunctions is None:
            self.k = 1
            self.hashFunctions = [lambda e, size : hash (e) % size]
        else:
            self.k = len(hashFunctions)
            self.hashFunctions = hashFunctions

    def add(self, value):
        """
        ブルームフィルタにデータを追加する
        """
        for hf in self.hashFunctions:
            self.bits |= 1 << hf(value, self.size)

    def __contains__(self, value):

        """
        valueがブルームフィルタに存在するか判定する。
        ブルームフィルタの性質上 false-positiveな状態が発生しうる
        この場合、実際にデータは存在しないのにtrueを返してしまう。
        しかし false-negativeは起こり得ない
        """
        for hf in self.hashFunctions:
            if self.bits & 1 << hf(value, self.size) == 0:
                return False

            return True

この実装は、k個のハッシュ関数が存在していることを前提としており、各ハッシュ関数

データが追加されるときは毎回、k個のビットが、ハッシュ関数によって計算されたビット位置に対してセットされます。

分析

ブルームフィルタに必要なメモリ容量は mビットで固定されている。
このメモリ容量は、追加されるデータ量に応じて増加することはありません。

さらに、このアルゴリズムはデータの探索と追加毎にk回操作しか行わないため、O(k)時間で1回の操作が完了します。 kは数値なので、定数時間で処理ができるためかなり速いです。

各データに対して、偏りなく効率的にビット値を計算するアルゴリズムを設計するのは非常に難しいことで、ビット配列のサイズは定数だが、false-positiveが発生するレートを極力下げる必要があります。

さらに重要な特徴としては、ブルームフィルタはデータを削除することは仕組み上できないです。
例をあげると、もし1つのデータを消す場合 k個のハッシュ関数によって(1, 3, 5 ,8, 9)というハッシュ値を持っていた場合、他のデータで(1, 3, 5 ,8, 9)のハッシュ値のうちどれか1つでも持っているデータに関する情報もブルームフィルタから消えてしまうため、判定できなくなるためです。

まとめ

ブルームフィルタのデータ構造、探索ロジックについて簡単ですがざっくりとまとめました。
ブルームフィルタを利用する上で考慮すべき、false-positiveの発生確率については、また別記事でまとめたいと思います。

docker-composeでmongoDBのレプリカセット構築

概要

mongoDBのレプリカセットを構築する際に、docker-composeをつかって、複数のコンテナを立ち上げる方法をまとめます。

docker-composeを使うことで、複数のコンテナの設定の記述と、コンテナ起動、停止が楽にできるため、ローカル環境などで軽くmongoDBのレプリカセットを構築したいときは非常に便利です。

今回は下記構成で1セットのレプリカセットを作ります。 f:id:kakts:20170621001525p:plain

mongod primary secondary合わせて計3コンテナ用意し、それぞれに ホスト環境の30001, 30002, 30003ポートを割り当てます。
primayノードが死んだときに、次のprimaryノードを決定するために必要なarbiterノードを1コンテナ作り、30004ポートを割り当てます。

環境

今回のレプリカセット構築における環境は以下のとおりです。

macOS sierra 10.12.5
docker: 17.03.1-ce
docker-compose 1.11.2
mongoDB 3.4.5

docker-compose.ymlを記述する

さっそく、4つ分のコンテナの設定をdocker-compose.ymlに記述していきます。
ここでは、使用するmongoのdockerイメージはmongo公式のリポジトリのものを使います。
https://hub.docker.com/_/mongo/

docker-compose.yml

version: "3"
services:
  mongod001:
    container_name: mongors001
    image: mongo:3.4.5
    command: mongod --replSet rs1 --noprealloc --smallfiles
    ports:
      - "30001:27017"
  mongod002:
    container_name: mongors002
    image: mongo:3.4.5
    command: mongod --replSet rs1 --noprealloc --smallfiles
    ports:
      - "30002:27017"
  mongod003:
    container_name: mongors003
    image: mongo:3.4.5
    command: mongod --replSet rs1 --noprealloc --smallfiles
    ports:
      - "30003:27017"
  mongoa001:
    container_name: mongoa001
    image: mongo:3.4.5
    command: mongod --replSet rs1 --noprealloc --smallfiles
    ports:
      - "30004:27017"

こんな感じでservices配下に レプリカセット用のmongodノード3台、arbiterノード1台分の記述をしていきます。
imageは mongo:3.4.5と書くことで、前述した公式mongoリポジトリの3.4.5タグのイメージを取ってきます。

mongoのコンテナを立ち上げると、デフォルトでコンテナ内の27017ポートを利用する*1ため、各ノード毎に “{ホストのポート番号}:27017” と記述してホストのポートと各コンテナ内のポートを紐付けます。

各コンテナのcommandで、実際にコンテナ内で起動するコマンドを記述します。
本稿では、レプリカセットの名前をrs1とします。

docker-composeでコンテナを立ち上げる

docker-composeでコンテナを立ち上げる準備ができたので、実際に立ち上げてみます。

docker-compose upコマンドで、実行しているディレクトリにあるdocker-compose.ymlファイルを読み込み、コンテナを立ち上げていきます。

今回はバックグラウンドで立ち上げるため、docker-compose up の-dオプションを付けます

# バックグラウンドでコンテナ立ち上げ
$ docker-compose up -d
Starting mongors002
Starting mongoa001
Starting mongors001
Starting mongors003

立ち上げ自体はコレだけです。 念のため、正常に立ち上がったか、docker-compose psコマンドで確認してみます。

$ docker-compose ps
   Name                 Command               State            Ports           
------------------------------------------------------------------------------
mongoa001    docker-entrypoint.sh mongo ...   Up      0.0.0.0:30004->27017/tcp 
mongors001   docker-entrypoint.sh mongo ...   Up      0.0.0.0:30001->27017/tcp 
mongors002   docker-entrypoint.sh mongo ...   Up      0.0.0.0:30002->27017/tcp 
mongors003   docker-entrypoint.sh mongo ...   Up      0.0.0.0:30003->27017/tcp 

指定したとおり、4つのコンテナが正常に上がっているのを確認できました。
ここでStateがUpになっていない場合は、docker-compose logsでエラーを確認して対処します。

各コンテナに紐付けられているポートも30001〜30004まで紐付けられているので、続いてはレプリカセットの設定を進めていきます。

mongoのレプリカセットを初期化する。

早速、起動したmongoコンテナに接続してmongoのレプリカセットの設定を行っていきます。
mongors001 という名前のコンテナに接続するため、 ホストのmongoコマンドを叩いて30001ポートに接続します。

# ホスト(mac)で実行
$ mongo --port 30001


# レプリカセット初期化
> rs.initiate

# ステータス確認
> rs.status()
{
    "set" : "rs1",
    "date" : ISODate("2017-06-20T15:04:39.227Z"),
    "myState" : 1,
    "term" : NumberLong(17),
    "heartbeatIntervalMillis" : NumberLong(2000),
    "optimes" : {
        "lastCommittedOpTime" : {
            "ts" : Timestamp(1497971077, 1),
            "t" : NumberLong(17)
        },
        "appliedOpTime" : {
            "ts" : Timestamp(1497971077, 1),
            "t" : NumberLong(17)
        },
        "durableOpTime" : {
            "ts" : Timestamp(1497971077, 1),
            "t" : NumberLong(17)
        }
    },
    "members" : [
        {
            "_id" : 0,
            "name" : "mongors001:27017",
            "health" : 1,
            "state" : 1,
            "stateStr" : "PRIMARY",
            "uptime" : 24,
            "optime" : {
                "ts" : Timestamp(1497971077, 1),
                "t" : NumberLong(17)
            },
            "optimeDate" : ISODate("2017-06-20T15:04:37Z"),
            "infoMessage" : "could not find member to sync from",
            "electionTime" : Timestamp(1497971056, 1),
            "electionDate" : ISODate("2017-06-20T15:04:16Z"),
            "configVersion" : 7,
            "self" : true
        }
    ],
    "ok" : 1
}

レプリカセットメンバー追加
> rs.add("mongors002:27017")
> rs.add("mongors003:27017")

arbiterメンバ追加
> rs.addArb("mongoa001:27017")

これでレプリカセットの初期化と、secondaryノード、arbiterノードの追加ができました。 細かいところは省きますが、 最後にrs.status()を確認すると下記のようにmembersに各ノードが追加されているのを確認できます。

> rs.status()
{
    "set" : "rs1",
    "date" : ISODate("2017-06-20T15:07:46.407Z"),
    "myState" : 1,
    "term" : NumberLong(17),
    "heartbeatIntervalMillis" : NumberLong(2000),
    "optimes" : {
        "lastCommittedOpTime" : {
            "ts" : Timestamp(1497971258, 1),
            "t" : NumberLong(17)
        },
        "appliedOpTime" : {
            "ts" : Timestamp(1497971258, 1),
            "t" : NumberLong(17)
        },
        "durableOpTime" : {
            "ts" : Timestamp(1497971258, 1),
            "t" : NumberLong(17)
        }
    },
    "members" : [
        {
            "_id" : 0,
            "name" : "mongors001:27017",
            "health" : 1,
            "state" : 1,
            "stateStr" : "PRIMARY",
            "uptime" : 211,
            "optime" : {
                "ts" : Timestamp(1497971258, 1),
                "t" : NumberLong(17)
            },
            "optimeDate" : ISODate("2017-06-20T15:07:38Z"),
            "electionTime" : Timestamp(1497971056, 1),
            "electionDate" : ISODate("2017-06-20T15:04:16Z"),
            "configVersion" : 11,
            "self" : true
        },
        {
            "_id" : 1,
            "name" : "mongors002:27017",
            "health" : 1,
            "state" : 2,
            "stateStr" : "SECONDARY",
            "uptime" : 114,
            "optime" : {
                "ts" : Timestamp(1497971258, 1),
                "t" : NumberLong(17)
            },
            "optimeDurable" : {
                "ts" : Timestamp(1497971258, 1),
                "t" : NumberLong(17)
            },
            "optimeDate" : ISODate("2017-06-20T15:07:38Z"),
            "optimeDurableDate" : ISODate("2017-06-20T15:07:38Z"),
            "lastHeartbeat" : ISODate("2017-06-20T15:07:44.551Z"),
            "lastHeartbeatRecv" : ISODate("2017-06-20T15:07:43.562Z"),
            "pingMs" : NumberLong(0),
            "configVersion" : 11
        },
        {
            "_id" : 2,
            "name" : "30002:27017",
            "health" : 0,
            "state" : 8,
            "stateStr" : "(not reachable/healthy)",
            "uptime" : 0,
            "optime" : {
                "ts" : Timestamp(0, 0),
                "t" : NumberLong(-1)
            },
            "optimeDurable" : {
                "ts" : Timestamp(0, 0),
                "t" : NumberLong(-1)
            },
            "optimeDate" : ISODate("1970-01-01T00:00:00Z"),
            "optimeDurableDate" : ISODate("1970-01-01T00:00:00Z"),
            "lastHeartbeat" : ISODate("2017-06-20T15:07:44.553Z"),
            "lastHeartbeatRecv" : ISODate("1970-01-01T00:00:00Z"),
            "pingMs" : NumberLong(0),
            "lastHeartbeatMessage" : "Invalid argument",
            "configVersion" : -1
        },
        {
            "_id" : 3,
            "name" : "mongors003:27017",
            "health" : 1,
            "state" : 2,
            "stateStr" : "SECONDARY",
            "uptime" : 74,
            "optime" : {
                "ts" : Timestamp(1497971258, 1),
                "t" : NumberLong(17)
            },
            "optimeDurable" : {
                "ts" : Timestamp(1497971258, 1),
                "t" : NumberLong(17)
            },
            "optimeDate" : ISODate("2017-06-20T15:07:38Z"),
            "optimeDurableDate" : ISODate("2017-06-20T15:07:38Z"),
            "lastHeartbeat" : ISODate("2017-06-20T15:07:44.551Z"),
            "lastHeartbeatRecv" : ISODate("2017-06-20T15:07:43.568Z"),
            "pingMs" : NumberLong(0),
            "configVersion" : 11
        },
        {
            "_id" : 4,
            "name" : "mongoa001:27017",
            "health" : 1,
            "state" : 7,
            "stateStr" : "ARBITER",
            "uptime" : 7,
            "lastHeartbeat" : ISODate("2017-06-20T15:07:44.550Z"),
            "lastHeartbeatRecv" : ISODate("2017-06-20T15:07:43.720Z"),
            "pingMs" : NumberLong(1),
            "configVersion" : 11
        }
    ],
    "ok" : 1
}

v8 ver6.0まとめ

v8 ver6.0がリリースされました。
ざっくりと新機能や改善点を整理します。
v8project.blogspot.jp

Main features

SharedArrayBuffer

ver6.0から、SharedArrayBufferがのサポートが開始されました。

developer.mozilla.org

SharedArrayBufferは、javascriptワーカーと、ワーカー間の同期制御時にメモリを共有するローレベルメカニズムです。

Object rest/spread properties

ES.nextの仕様において、現在stage3 である Object rest/spread propertiesが採用されました。

変数宣言時に、Object内の特定のプロパティを指定でき、さらに …restと記述すれば、指定されていない残りのプロパティをまとめて取得できます。

// Rest properties for object destructuring assignment:
const person = {
  firstName: 'Sebastian',
  lastName: 'Markbåge',
  country: 'USA',
  state: 'CA',
};
const { firstName, lastName, ...rest } = person;
console.log(firstName); // Sebastian
console.log(lastName); // Markbåge

// firstName, lastName以外のプロパティをまとめて取得できる
console.log(rest); // { country: 'USA', state: 'CA' }

// Spread properties for object literals:
// オブジェクトリテラルを用いて変数を宣言する際にも同様に記述して使うことができる
const personCopy = { firstName, lastName, ...rest };
console.log(personCopy);
// { firstName: 'Sebastian', lastName: 'Markbåge', country: 'USA', state: 'CA' }

ES6 Performance

v8 ver6.0において、ES2015の機能のパフォーマンス改善もされています。 javascriptのパフォーマンスベンチマークツールである Ares-6において、10%の改善がみられたようです。

http://browserbench.org/ARES-6/

v8 API

v8 APIに関してもいくつかの変更が加えられています。
変更点詳細は下記ページにまとまっています。
docs.google.com

npm5から導入された package-lock.jsonについて

先日npm5がリリースされました。同時期にリリースされたNode.js v8.0.0にもバンドルされており、
複数ある新機能のうち、package-lock.jsonについて気になったので本家のドキュメントの内容を読んでまとめました。

docs.npmjs.com

package-lock.jsonについて

package-lock.json はnode_modules配下やpackage.jsonに変更があった際に自動で作成・変更されるファイルです。
具体的には、 npm install npm update npm uninstallなど、パッケージに変更が加えられるタイミングで作成・変更されます。

このファイルはpackage.jsonなどのように、リポジトリのソースの一部として組み込まれるように設計され、様々な目的のために利用されます。

package-lock.jsonを導入する目的は以下のとおりです。

  • リポジトリの依存関係を表現する単一の方法を提供する。
    チームメンバーそれぞれの環境での開発時や、CIによるデプロイ時など、環境に限らず同じ依存関係をもってサブモジュールをインストールできることを保障します。

  • 対象のサブモジュールに対して、過去のバージョンに容易に戻れるような手段を提供する。

  • 可読性のあるソースコードにより、モジュール改装の変更の可視化を容易にする。

  • npmパッケージのインストールプロセスの最適化
    すでにインストール済みのパッケージのメタデータ解析をスキップする事により、インストールプロセスの最適化を実現します。
    yarnと比べるとまだまだ遅いですが、npm4と比べるとかなり速度が改善しています。
    docs.google.com

package-lock.jsonの重要な点は、ファイルが公開できることと、もしトップレベルモジュールにpackage-lock.jsonファイルがある場合、下位モジュールでのpackage-lock.jsonは無視されるということです。
npm4で存在していた、npm-shrinkwrap.jsonとフォーマットを共有しているため、本質的には中身は同じものですが、package-lock.jsonはファイルを公開できることが異なります。
しかしpackage-lock.jsonを公開することは、CIツールを使ったデプロイを行うか、本番環境への公開プロセスを使用しない限り、おすすめできません。

もしpackage-lock.jsonとnpm-shrinkwrap.jsonがパッケージのルートディレクトリに両方存在していた場合、
package-lock.jsonは完全に無視されます。

参考

npm5の他の機能も解説されており、勉強になります。
yosuke-furukawa.hatenablog.com

npm-shrinkwrap.jsonとpackage-lock.jsonとの違いについて stackoverflow.com

docker run時にホスト上のランダムなポートにコンテナを割り当てる

docker run時にコンテナ内の特定のポートに、host上のランダムなポートをbindさせる方法をまとめます。

簡単なwebサーバの実装とDockerコンテナ用のDockerfileの記述

今回、下記のような構成で簡単なwebサーバを作るとする。

$ tree
.
├── Dockerfile            # webサーバ用コンテナのDockerfile
└── app
    └── identidock.py  # Flask webサーバの実装

今回は本筋でないので説明しませんが、pythonのwebフレームワークであるFlaskを使って、localhost の/に対してhttpリクエストしたときに Hello Worldを返す簡単なサーバを作ります。
./app/identidock.py に下記のように実装します。

from flask import Flask
app = Flask(__name__)

@app.route('/')
def hello_world():
    return 'Hello World\n'

if __name__ == '__main__':
    app.run(debug = True, host = '0.0.0.0')

続いて肝心なDockerfileの説明をします。
uwsgiというユーザ・グループを作成した上で、 コンテナ内の9090番ポートにwebサーバ、9191番にサーバパフォーマンス統計用のサーバを立ち上げる設定を記述します

FROM python:3.4


# uswgiというグループ・ユーザを作成
RUN groupadd -r uwsgi && useradd -r -g uwsgi uwsgi

# Flask uWSGI pip install
RUN pip install Flask==0.10.1 uWSGI==2.0.8

# コマンド実行時の作業ディレクトリ指定
WORKDIR /app

# ./appをコンテナ内にあるファイルシステムの/appにコピーする
COPY app /app

# 解放するポートを明示的に指定
EXPOSE 9090 9191
# これ以降のすべての行の実行ユーザをuwsgiに設定する
USER uwsgi

# uWSGIを実行する新たなコマンドを生成する
# uWSGIに対して、9090ポートで待ち受けるhttpサーバを起動させる。 /app/identidock.pyからappというアプリを実行させる
# 9191でstatsサーバも起動する
CMD ["uwsgi", "--http", "0.0.0.0:9090", "--wsgi-file", "/app/identidock.py", "--callable", "app", "--stats", "0.0.0.0:9191"]

これで、ひとまずwebサーバ用のDockerコンテナの準備ができたので、buildしていきます。

webappという名前でDockerコンテナのbuildを行います。

$ docker build -t webapp .

Dockerコンテナを指定したホスト上のポートにbindさせる

まずは、Dockerコンテナ内の 9090, 9191番ポートをホスト上の指定したポートにbindさせます。
方法としては、docker runコマンド実行時に、オプションで設定させるだけです。

コンテナ内の9090,9191を下記のポートにbindさせることとします。

  • 9090番ポート → host上の9090番ポート 9090:9090
  • 9191番ポート → host上の9191番ポート 9191:9191
    上記のように、 ${host上のポート}:${コンテナ内のポート}という形式で、docker run時に -pオプションで追加してあげればbindすることができます。
    同時に、コンテナ名を webapp-testとします
$ docker run -d -p 9090:9090 -p 9191:9191 --name webapp-test

docker runが完了したら、実際にポートがbind されているか、 docker portで確認します。

# docker port確認
$ docker port webapp-test
9191/tcp -> 0.0.0.0:9191
9090/tcp -> 0.0.0.0:9090

#  疎通確認
$ curl localhost:9090 
Hello World

これで、指定したホスト上のポートにDockerコンテナをbindさせることができました。

Dockerコンテナにホスト上のポートをランダムにbindさせる。

今度は、Dockerコンテナの9090, 9191に対して、ホスト上の大きな番号のポートを自動的に割り当てます。
この方法は非常に簡単で、 docker run 時に -P を引数として使うことで、実現できます。

docker run –helpでは、-Pオプションは以下のように説明されています。

-P, --publish-all    Publish all exposed ports to random ports

やることはこれだけです。

# ホスト上のランダムなポートにコンテナを割り当てる
$ docker run -d -P --name webapp-test webapp

# ポート確認
$ docker port webapp-test
9090/tcp -> 0.0.0.0:32769
9191/tcp -> 0.0.0.0:32768

Dockerコンテナへのランダムなポートbindの利点

このランダムなポートbindの利点としては、ある1台のホスト上に複数のコンテナを実行する際に、使われていないポートを自分で管理して明示的にしていするよりも、ポートのbindを全部Docker側に任せる事ができるので、管理が楽になります。

docker exitedなコンテナをまとめて削除する

dockerでの開発中に、docker runしてエラーが発生し、exitedになっているコンテナが残った状態になる場合があります。

$ docker ps -a
CONTAINER ID        IMAGE                    COMMAND                  CREATED             STATUS                     PORTS                    NAMES
0efc271c4b9e        testapp               "python identidock.py"   6 seconds ago       Exited (1) 4 seconds ago                            gifted_nobel
cf94c6f94ae3        testapp               "bin/bash"               10 seconds ago      Created                                             stoic_murdock
65ebe4051e20        testapp               "bin/bash"               5 minutes ago       Created                    0.0.0.0:5000->5000/tcp   infallible_ritchie

コンテナ名やIDを指定して下記のように1つずつコンテナを削除するのもできます

$ docker rm ${CONTAINER_NAME}
$ docker rm ${CONTAINER_ID}

これでは複数exitedになっている場合大変なので、docker rmの引数に、exitedなコンテナのIDをまとめて渡すようにします。

exitedなコンテナのIDのみ取得する

まず、docker ps -aを実行したときに表示されるコンテナの一覧から、 statusがexitedなもののコンテナIDのみ出力させるようにします。 –filterで条件を指定することでコレが可能になります。

status exitedなコンテナのIDのみ表示させる
$ docker ps -a --filter 'status=exited' -q
0efc271c4b9e
cf94c6f94ae3
65ebe4051e20

これをdocker psの引数として渡すことで、exitedなコンテナをまとめて削除できます。

# exitedなコンテナをまとめて削除する
$ docker rm $(docker ps -a --filter 'status=exited' -q)

Hash-Based サーチアルゴリズム まとめ

今回、多くの要素を持ち、必ずしもソートされていないコレクションに対して特定の値を探す際に効果的なHash-Basedサーチアルゴリズムについてまとめます。
日本語ではハッシュ法による探索アルゴリズムと呼ばれることもあります。

Hash-Basedサーチアルゴリズム

一般的によく知られたアプローチの一つは、hash関数をつかって、検索対象のコレクションの要素内の特徴を使ってハッシュテーブルのインデックスに変換することです。
ハッシュ法によるサーチは、シーケンシャルサーチやバイナリサーチよりも、average-caseでのパフォーマンスがより良いものとなっています。

Hash-Basedサーチにおいて、n個の要素を持つ集合Cは最初にHと呼ばれるハッシュテーブルと、配列構造を持つb個のビンにロードされる。
この前処理はO(n)のパフォーマンスを持つが、 しかし後の検索においてパフォーマンスが向上する。 ハッシュ関数のコンセプトはこのパフォーマンス向上を可能にする。

ハッシュ関数は各要素Ciを整数値hiに変換する決定関数です。
まず、hiを 0<= hi < bと仮定する。 要素をハッシュテーブルに読み込む時、 Ciは H[hi]のビンに格納される。 すべての要素が格納された後、アイテムtを探索する場合は H[hash(t)]のビンの中から要素を探索する

ハッシュ関数は、もし要素CiとCjが同値の場合 hash(Ci) == hash(Cj)となることを保証します。
これは、集合Cの中の要素のうち、ハッシュ値が同じ場合がありうることを意味します。
これはハッシュ衝突として知られ、ハッシュテーブルはこの状況に対応する方法が要求されます。

最もよく知られた解決策として、各ハッシュインデックスにlinked listを保持し、すべてのハッシュ衝突したデータをハッシュテーブルに格納する手法があります。
各ハッシュインデックスが保持するlinked listは線形的にサーチされる必要がありますが、各linked listの要素数は非常に少ないため、探索時間は短くすみます。

下記の疑似コードはハッシュインデックスが衝突した際の linked-listの振る舞いを書いている

  • Uを取りうるハッシュ値の集合とする。 各要素e は Cに属していて、 ハッシュ値 h は Uに属する
  • ハッシュテーブルHはb個のビンを持っている。各ビンは集合Cの中からn個の要素を持つ。
  • ハッシュ関数hashは、集合Cのすべての要素eに対して 0<= h <bとなるハッシュ値hを出力する
Best, Average O(1)
Worst O(n)

// ハッシュテーブルをロードする
loadTable (size, C)
    H = new array of given size
    foreach e in C do
        h = hash(e)
            if H[h] is empty then
            H[h] = new Linked List
            add e to H[h]
    return A
end

// サーチ
search (H, t)
    h = hash(t)
    list = H[h]
    if list is empty then
        return false
    if list contains t then
        return true
    return false
end

Hash-Basedサーチの2つの問題

Hash-Basedサーチを実装するにあたって、主要な問題は2つあります。
- ハッシュ関数のデザイン
- ハッシュ値衝突のハンドリング

綿密に設計されていないハッシュ関数は、ハッシュキーをハッシュテーブルに分配するロジックが良くないため、ハッシュテーブルへの値の格納において、偏りがでてしまいます。
そして、特定のビンに多くの値が格納されるので、ハッシュ衝突が起きる割合が多くなります。
これはhash-basedサーチにおけるパフォーマンスの低下を招きます

input/output

イナリサーチと異なり、Hash-Based searchにおいては、サーチ対象のコレクションCは必ずしもソートされる必要がない。 もしCがソートされていた場合、Cの各要素をハッシュテーブルHに格納するハッシュ関数は、H内部で元のソート情報を保持することがないので意味がない

Hash-Based-Searchにおける入力は、既に作成済みのハッシュテーブルHと、サーチ対象の要素tです。 アルゴリズムは、要素tが、ハッシュ関数を適用した出力値 h = hash(t)として、H[h]のビンに含まれている場合trueを返す。

もし213,557個の英単語の配列があるとして、ある単語を探す場合 バイナリサーチの場合は最大で18回(log(213557) = 17.70)の探索が必要です。 Hash-Based Searchの場合比較回数は、コレクションのサイズというよりも、ハッシュテーブルの各ビンが保持するlinked-listの長さに依存します。

ハッシュ関数について

hash関数を定義するに当たって、ゴールは多くの異なる値を正の数に変換し、各要素を必ずしもユニークにする必要はない ハッシュ化は何十年にも渡って研究されてきているが、その多くの手法はサーチ以外の目的に対しても使うことができる。

例えば、特別なハッシュ関数は暗号化に使われたりする。 サーチにおいては、ハッシュ関数はハッシュテーブルへの値のばらつきが均一であることと、計算時間が短いものが良いです。 → ハッシュ関数の実装については後日まとめます。。。