kakts-log

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

babel ES6からES5へのトランスパイル

概要

babel.jsをつかって ES6のシンタックスで書かれたjavascriptファイルをES5のシンタックスにトランスパイルする方法をまとめました。
実務で使ったことなかったので勉強がてらさらっとまとめます。

babel-cliのインストー

babelをコマンドラインで利用するに当たって、babelのコマンドラインクライアントである、npm モジュールのbabel-cliをインストールする必要があります。

www.npmjs.com

開発環境のみで使うので –save-devでpackage.jsonに対してdevDependenciesにモジュールの情報を追記させます。

$ npm install --save-dev babel-cli

今回はサンプルとして今回 hapiというhttpサーバモジュールを使うのでこちらもインストールしておきます

$ npm install --save hapi

.babelrcにプラグイン設定記述

babelでトランスパイルする際に、利用するプラグインを指定する必要があります。
今回はES6(ES2015とも言う)からES5へトランスパイルするため、ES2015 presetを指定します。
babeljs.io

babelコマンドの –presetsオプションでも指定できますが、毎回打つのは面倒なので、 babelの設定を記述するファイルである .babelrcを作成し、json形式で記述します。

.babelrc

{
  "presets": ["es2015"]
}

presets項目に使用するプラグイン名を指定します。

トランスパイル元のjsファイル作成

ここで、トランスパイル元のjsファイルである src/index.jsを作成します。
hapiモジュールを使って簡単なhttpサーバを作ります。
全てES6(ES2015)のシンタックスで記述します。

import Hapi from 'hapi';

const server = new Hapi.Server();
server.connection({
  host: 'localhost',
  port: 8000
});

// Add routing
server.route({
  method: 'GET',
  path: '/hello',
  handler: function(request, reply) {
    console.log('[/hello] requested');
    reply('hello world');
  }
});

server.start();

これを importや constを使わない、ES5形式にトランスパイルさせます。

babelコマンドをつかったトランスパイル

トランスパイルした後のファイルは dist/index.jsに作成させるとします。

さっそくコマンドラインでbabelコマンドを使ってトランスパイルさせます。
babelコマンドの –out-fileオプションをつかって、トランスパイル後のファイルの出力先を指定します。

$ babel src/index.js --out-file dist/index.js

これによって、 dist/index.jsにES5形式にトランスパイルされたjsファイルができあがります。

'use strict';

var _hapi = require('hapi');

var _hapi2 = _interopRequireDefault(_hapi);

function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }

var server = new _hapi2.default.Server();
server.connection({
  host: 'localhost',
  port: 8000
});

// Add routing
server.route({
  method: 'GET',
  path: '/hello',
  handler: function handler(request, reply) {
    console.log('[/hello] requested');
    reply('hello world');
  }
});

server.start();

元のjsファイルで使っていた import, const が使われずにそれぞれ require varを使うようにトランスパイルされているのが確認できます。

babelをつかったトランスパイルの手順は以上となります。 まだ試していませんが、最新のES2017形式のファイルをES5にトランスパイルする場合は ES2017 presetを使えばできます。
babeljs.io

node.js stringからbufferへの変換

node.jsにおいて、文字列をbufferへ変換させたいときの方法をまとめます

環境
node.js 8.1.3

Bufferインスタンスをどう生成するか

node.js 8.x系におけるBufferインスタンスの作成において、 new Bufferは既にdepricatedになっている*1ため、ここではbufferインスタンスの作成はBuffer.allocを利用します。

Buffer | Node.js v8.1.3 Documentation

Buffer.alloc と Buffer.allocUnsafe

Buffer.alloc(size)の他に、インスタンス生成時にデータを初期化させないBuffer.allocUnsafe(size)があります。
Buffer.allocは、インスタンス生成時にデータをzero-filledする初期化コストがかかるため、Buffer.allocUnsafeよりパフォーマンスは劣りますが、sensitiveなデータを含まないことが保証されるので、速度を最優先させる場面以外において、基本的にBuffer.allocを使う方が良いかと思います。
https://nodejs.org/dist/latest-v8.x/docs/api/buffer.html#buffer_class_method_buffer_allocunsafe_size

文字列をbufferに変換する場合において、Buffer.allocを利用時にBufferサイズ指定する必要があります。 下記に文字列をBufferに変換するスクリプトにあるように、ここで毎回文字列のサイズを渡してBufferインスタンスを生成します。

function bufferFromString(str) {
  // Allocates a new Buffer of size bytes.
  // If fill is undefined, the Buffer will be zero filled;
  // set size of string length
  var buffer = Buffer.alloc(str.length)
  buffer.write(str)
  return buffer
}

const text1 = bufferFromString('hello');
const text2 = bufferFromString('wor');

console.log('----text1', text1);
console.log('----text2', text2);

// text1のbufferにworを書き込む
text1.write('wor');

// 先頭の3文字分 のみ更新させるため、4,5文字目は変わらない
// hello → worlo
console.log(text1.toString('utf8'));

ただ、欠点なのは毎回Buffer.allock(size)でインスタンスを生成した後、Buffer.write()でデータを書き込む必要があるため、若干冗長です。

Buffer.from

Buffer.fromの引数に文字列を渡すと、一発で文字列をBufferに変換できます。

https://nodejs.org/dist/latest-v8.x/docs/api/buffer.html#buffer_class_method_buffer_from_string_encoding

> Buffer.from("hello world")
<Buffer 68 65 6c 6c 6f 20 77 6f 72 6c 64>

まとめ

文字列からBufferへの変換方法をざっとまとめました。 Buffer.alloc Buffer.allocUnsafe Buffer.fromはそれぞれ挙動に違いがあるので、公式ドキュメントをちゃんと読んで、状況に応じて使い分けるとよいかと思います。

参考

Uncaught TypeError: Cannot read property 'split' of undefined · Issue #185 · Keyang/node-csvtojson · GitHub

Contributing to Fawn module.

Done Refactored lib scripts. by kakts · Pull Request #11 · e-oj/Fawn · GitHub

AWS LambdaからDynamo DBにデータを追加する

概要

AWS lambda functionが呼び出された際に、AWS dynamoDBのテーブルにデータを追加していく方法についてまとめます。

今回は、API Gateway と lambdaで構築した line botに対して送信されたデータを dynamoDBに追加していくところまで説明します。

IAMユーザの設定

AWSの IAM manageページから、新規にIAMユーザを作成します。
このユーザは、Dynamo DBに対する書き込み、読み込み権限そして、lambda関数からdynamoを使う権限を付与します。

「ユーザを追加ボタン」でユーザ名を入力し、「アクセスの種類」で、プログラムによるアクセスと、AWSマネジメントコンソールへのアクセスを許可します。

ユーザの作成を完了すると、 「アクセスキーID」と、「シークレットアクセスキー」が取得できます。 この2つをlambdaからdynamoDBへのアクセス時に必要なので、メモしておきます。

作成後、IAMユーザの設定画面に移り、「アクセス権限を追加」ボタンをおし、アクセス権限を追加していきます。
予めグループを作成し、そのグループにアクセス権限を追加する方法もありますが、今回はユーザに対してアクセス権限を追加します。

「アクセス許可の付与」画面で、「既存のポリシーを直接アタッチ」項目を選択し、もともとAWS側で用意されているポリシーをユーザに追加します。 DynamoDB用のアクセス権限を追加するため、「AmazonDynamoDBFullAccess」ポリシーを探し、選択します。

f:id:kakts:20170625154758p:plain

これでIAMユーザを作成し、そのユーザに対してlambdaからDynamoDBへのデータの読み書きする権限を付与できました。

DynamoDBの設定

DynamoDBにデータを追加するためのテーブルを作成します。

DynamoDBのマネジメントコンソールにアクセスし、「テーブルの作成」ボタンからテーブル作成画面に遷移します テーブルの設定はデフォルトにし、テーブル名、プライマリーキーを設定します。
プライマリーキーはDynamoDBのテーブル内のアイテム毎にユニークなIDのことです。 本稿では、テーブル名はmessage プライマリーキーは_id と設定していきます

f:id:kakts:20170625162946p:plain

これでDynamoDBのテーブルを作成することができました。

lambda関数実装

IAMユーザの作成、DynamoDBのテーブルも作成できたので、次にlambda関数で、linebotに対して送られたメッセージをDynamoDBに保存する関数を実装していきます。
前回の 「aws lambdaとapi gatewayで linebotを作成する」で作成したlambda関数をベースに、DynamoDBにデータを追加する処理を実装します。

AWSの各サービスに対するクライアントsdkは公式で用意されており、

kakts-tec.hatenablog.com

npm の aws-sdkモジュールがあるので、コレを利用します。
www.npmjs.com

DynamoDBへのアクセス時に、先程IAMユーザの作成時に生成されたAPIアクセスキーとシークレットアクセスキーを利用します。
コードに直接埋め込むのは管理上よくないので、lambdaの環境変数に指定します。

  • DYNAMO_API_ACCESS_KEY : DynamoDBアクセス用IAMユーザのアクセスキー
  • DYNAMO_USER_SECRET_ACCESS_KEY : DynamoDBアクセス用IAMユーザのシークレットアクセスキー

DynamoDB用クライアントインスタンスの作成は下記の用な感じで行います。
exports.handlerの内部で記述すると、関数が読み込まれるたびに初期化が走るため、exports.handlerの外部で初期化させます。

const https = require('https');
const AWS = require('aws-sdk');

// dynamoDBクライアントインスタンス初期化
// IAMユーザのAPIアクセスキー、シークレットアクセスキーを指定する。  
// region apiVersionも指定する。  
const dynamo = new AWS.DynamoDB({
    region: 'ap-northeast-1',
    apiVersion: '2012-08-10',
    accessKeyId: process.env.DYNAMO_API_ACCESS_KEY,
    secretAccessKey: process.env.DYNAMO_USER_SECRET_ACCESS_KEY
});

登録するデータは、linebotから来るリクエストデータにはいっている、ユーザID、メッセージタイプ(text や sticker[スタンプ]など)、ユーザが入力したテキスト を登録していきます。

メッセージが送信される毎にデータを登録していくため、ユニークキーであるidには一意なものを指定します。
ここでは、とりあえず $USERID
$DATETIME を指定します。

データの登録は、DynamoDBインスタンスのputItemメソッドを使って行います。

http://docs.aws.amazon.com/AWSJavaScriptSDK/latest/AWS/DynamoDB.html#putItem-property

上記ドキュメントに書かれているサンプルコードですが、パラメータにテーブル名、そして 追加するアイテムを指定してきます。
アイテム内の各アトリビュートは、文字列(S)や数値(N) など、それぞれ登録するデータの型をキーに指定します。 このあたりの仕様はドキュメントを参照してください。

/* This example adds a new item to the Music table. */

 var params = {
  Item: {
   "AlbumTitle": {
     S: "Somewhat Famous"
    }, 
   "Artist": {
     S: "No One You Know"
    }, 
   "SongTitle": {
     S: "Call Me Today"
    }
  }, 
  ReturnConsumedCapacity: "TOTAL", 
  TableName: "Music"
 };
 dynamodb.putItem(params, function(err, data) {
   if (err) console.log(err, err.stack); // an error occurred
   else     console.log(data);           // successful response
   /*
   data = {
    ConsumedCapacity: {
     CapacityUnits: 1, 
     TableName: "Music"
    }
   }
   */
 });

実際に書いたlambda関数は以下になります。

const https = require('https');
const AWS = require('aws-sdk');

// dynamoDBクライアントインスタンス初期化
// IAMユーザのAPIアクセスキー、シークレットアクセスキーを指定する。  
// region apiVersionも指定する。  
const dynamo = new AWS.DynamoDB({
    region: 'ap-northeast-1',
    apiVersion: '2012-08-10',
    accessKeyId: process.env.DYNAMO_API_ACCESS_KEY,
    secretAccessKey: process.env.DYNAMO_USER_SECRET_ACCESS_KEY
});

const tableName = 'message';

// linebotから送信されたメッセージデータから返信用メッセージデータを作成する
// 本稿では、来たメッセージをそのまま返す
function createResponseMessage(messageData) {
  const message = messageData.message;
  let resMessage;
  if (message.type === 'text') {
    // text
    resMessage = {
      type: message.type,
      text: message.text
    }
  } else if (message.type === 'sticker') {
    // stamp
    resMessage = {
      type: message.type,
      packageId: message.packageId,
      stickerId: message.stickerId
    };
  }

  return resMessage;
}

exports.handler = (event, context, callback) => {
    const messageData = event.events && event.events[0];
    const replyToken = messageData.replyToken;
    const message = messageData.message;
    const text = message.text;
    const source = messageData.source;
    const resMessage = createResponseMessage(messageData);
    const data = JSON.stringify({
       replyToken: replyToken,
       messages: [resMessage]
    });

    // LINE reply apiのレスポンス設定
    const Authorization = 'Bearer ' + process.env.ENTER_ACCESS_TOKEN;
    opts = {
        hostname: 'api.line.me',
        path: '/v2/bot/message/reply',
        headers: {
            "Content-type": "application/json; charset=UTF-8",
            "Authorization": Authorization
        },
        method: 'POST',
    };

    const req = https.request(opts, function(res) {
        res.on('data', function(res) {
            console.log(res.toString());
        }).on('error', function(e) {
            console.log('ERROR: ' + e.stack);
        });
    });
    req.write(data);
    req.end();

    // DynamoDBへのメッセージデータ追加
    const userId = source.userId;
    const params = {
        TableName: tableName,
        Item: {
            _id: {
                S: userId + '_' + Date.now(),
            },
            userId: {
                S: userId
            },
            messageType: {
                S: message.type
            }
        }
    };
    // スタンプでなく文字列が投稿されたとき、textアトリビュートを追加する
    if (message.type === 'text') {
        params.Item['text'] = {
            S: message.text
        };
    }

    dynamo.putItem(params, function(err, data) {
        if (err) {
            console.error("Error occured", err);
        }
        console.error(data);
    });
};

最後に、linebotに対してメッセージを送信したあと、DynamoDBコンソールでデータが追加されていることを確認します。 f:id:kakts:20170625165955p:plain

aws lambdaとapi gatewayで linebotを作成する

概要

AWSAPI Gateway、lambdaを利用し、ユーザからのメッセージが来たときにlambda関数を呼び出し、ユーザへレスポンスを返すline botを作ります。

行った作業手順を一通りまとめます。

Linebotアカウントの作成

まず、line messaging api用のbotアカウントの作成を行うため、line business centerへログインします。
business.line.me 「アカウントリスト」タブを選択し、「アカウント作成」→「Messaging APIを始める」で、アカウントを作成する事ができます。

作成後、line@MANAGERページにて作成したアカウントの設定を行っていきます。

アカウント設定開始するとBot設定画面に遷移します。 Bot設定項目の中で「Webhook送信」項目を「利用する」に設定することで、messaging apiを利用できます。
f:id:kakts:20170622224241p:plain

またline business centerへもどり、「アカウントリスト」→作成したアカウントの「LINE Developers」から、botアカウント用のapiアクセストークンを確認することができます。

f:id:kakts:20170622224604p:plain 「ISSUE」ボタンを押すことでアクセストークンを確認できます。 このアクセストークンは後ほど使います。

API Gateway で新しいAPIの作成

awsコンソールから「サービス」→「Amazon API Gateway」を選択し、新しいAPIの作成します。
「新しい API」にチェックを入れ、適当なAPI名を入力します。
f:id:kakts:20170622234300p:plain

いったんおいておき、lambda関数の作成を行います。

aws lambdaの記述

早速aws lambdaを使ってユーザからのメッセージを受け取り、messaging apiを使ってレスポンスするための関数を書いていきます。

「Lambda関数の作成」ボタンから 「設計図の選択」画面に遷移し、そこで、lambdaで使うランタイムと、関数のサンプルを選ぶことができます。
ランタイムはNode.js と pythonから選ぶことができ、本稿では Node.js 6.10を選択します。
関数のサンプルは、「Blank Function」を選択します。 f:id:kakts:20170622231032p:plain

続いて、「トリガーの設定」画面に遷移し、lambdaを実行するためのトリガーを選択します。
本稿では、lambda関数へのエンドポイントとして、 AWS API Gatewayを利用しますので、「API Gateway」を選択します。
作成時に下記の3つの入力項目を設定します。 - API名 任意の名前 - デプロイされるステージ prod - セキュリティ AWS IAM

line botに対してユーザから送られるメッセージは、下記のreply APIの仕様に基づいて送信されます。 ユーザから受け取ったリクエストから、replyToken, textを取得し、reply api を利用することでユーザに対して返信することができます。
LINE API Reference

ここでは、ユーザから来たメッセージをシンプルにそのまま返すようにします。

lambda関数は、awsのlambda関数の設定画面で入力できるため、今回はそのまま入力していきます

const https = require('https');

exports.handler = (event, context, callback) => {
    // メッセージデータ取得
    const messageData = event.events && event.events[0];

    
    const replyToken = messageData.replyToken;
    const message = messageData.message;
    const text = message.text;
    
    const data = JSON.stringify({
       replyToken: replyToken,
       messages: [{type: "text", text: text}]
    });
    
    // line messaggin apiのアクセストークンを環境変数ACCESS_TOKENに設定する 
    const Authorization = 'Bearer ' + process.env.ACCESS_TOKEN;
    opts = {
        hostname: 'api.line.me',
        path: '/v2/bot/message/reply',
        headers: {
            "Content-type": "application/json; charset=UTF-8",
            "Authorization": Authorization
        },
        method: 'POST',
    };

    const req = https.request(opts, function(res) {
        res.on('data', function(res) {
            console.log(res.toString());
        }).on('error', function(e) {
            console.log('ERROR: ' + e.stack);
        });
    });
    req.write(data);
    req.end();
};

lambda関数が毎回実行されるたびに、デフォルトでexports.handler メソッドが呼ばれます。 引数は3つあり、 event.events内に、lineユーザからのメッセージのリクエストデータが格納されます。

line reply APIのリクエスト時に、先程「LINE Developers」管理画面で取得した アクセストークンが必要で、 リクエストヘッダーの Authorization に 追加します。

コードの中に直接アクセストークンを埋め込むと、管理上面倒なため、lambdaの環境変数を利用します。
f:id:kakts:20170622232955p:plain

上記のように、キーと値を入力することで、lambda関数内部で process.env.ACCESS_TOKENとして呼び出して使うことができます。

他にもいろいろ設定する項目があり、代表的なものをあげますが それ以外の項目はデフォルトのままでよいかと思います。

関数の設定
名前:  任意

Lambda 関数ハンドラおよびロール
・ハンドラ   index.handler
・ ロール     「テンプレートから新しいロールを選択」
・ロール名   任意のロール名

詳細設定
メモリ:128MB

api gatewayとlambda関数を紐付ける

ここで、作成した API GatewayによるAPIと lambda関数を紐付けます。
lambdaの設定画面より「トリガー」タブを選択→「トリガーを追加」を選択 → 「API Gatway」を選択し、先程作成したAPIAPI名、デプロイされるステージ、セキュリティ項目を入力します。

f:id:kakts:20170622234715p:plain

「メソッドの作成」→「POST」を選択しチェックボタンを押し、下記のように作成したlambda関数の設定を入れます。
f:id:kakts:20170622235021p:plain

これで、API Gatewayによって作った apiに対して POSTでリクエストを送ると lambda関数を呼び出すといって一連の設定ができました。

line managerで作成したapiの登録を行う

最後に、 LINE Developer管理画面で、Webhook URLを設定していきます。
先程のlambdaの設定画面の「トリガー」タブに、連携したAPIのURLが表示されています。

これを LINE Developer管理画面 に登録します。
登録後、Webhook URL 項目に「verify」ボタンができるので、これを押すとapiとの疎通確認を行います。
これでsuccessが出たら設定完了です。

verify時に下記の文言がでてエラーが出た場合は、再度api gateway と lambdaの設定を見直す必要があります

A http status of the response was '502 Bad Gateway'.

verify時にlambdaのcloud watchログを見ると reply apiで下記のエラーが出ていますが、api gatewayと lambdaの設定自体が正しければ successになっているので、特に問題は無いかと思います。

{"message":"Invalid reply token"}

linebotにメッセージを送る

これで一通りの設定が完了したので、実際にbotに対してメッセージを送ってみます。
成功すると以下の通りにメッセージを返してくれるようになります。 f:id:kakts:20170623001606j:plain

うまくいかない場合は lambdaのcloudwatchのログを見て、lambda関数内でエラーが出ているか確認することと、API Gatewayの設定が正しいか再度確認することが大事です。

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

概要

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

ブルームフィルタとは

ブルームフィルタとは確率的データ構造の一種で、あるデータが集合に属するかどうかを判定する際に使われます。
特徴としては、メモリの空間消費が少なくすみ、非常に効率的にデータの存在判定ができます。
デメリットとしては、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
}