2010年7月20日火曜日

本の紹介

お久しぶりです。

今日は本の紹介をします。

大規模サービス技術入門という本を最近読みました。
この本は、はてなのインターンシップで学生向けに行っている講義+演習を本にしたものです。学生向けというだけあって、システムの設計・運用上の概要(の例)がわかりやすく説明されています。
決して深い所まで議論している本ではありませんが、サーバ設計の考え方からAPの実装まで説明されていて、「システム」について学ぶ上で良い本だと思います。


システムの中で、APサーバやDBサーバを多重化・冗長化することではどういった効果が見込めるのか?
システムの負荷を分析して、サーバのスケールアップ/スケールアウトを考える上でのポイントは?どんな時にメモリ増設が有効で、どんな時にサーバ多重化が有効か?
何億ものドキュメントから全文検索をする際の実装上のポイントは?(どういったポリシーで実装すればユーザ満足度につながるか?)そのためのアルゴリズムは?
などなど。



講義で学んだ知識が、システム開発・運用の現場でどう役に立つのか(自分の知識が実際のシステムの中のどの部分と結びつくのか)を知るための良い読み物だと思います。

以下もくじ。

  • 第1回 大規模Webサービスの開発オリエンテーション―全体像を把握する
    • Lesson 0 本書の源 ―本書で説明すること,しないこと
    • Lesson 1 大規模なサービスと小規模なサービス
    • Lesson 2 成長し続けるサービスと,大規模化の壁
    • Lesson 3 サービス開発の現場
  • 第2回 大規模データ処理入門 ―メモリとディスク,Webアプリケーションと負荷
    • Lesson 4 はてなブックマークのデータ規模 ―データが大きいと処理に時間がかかる
    • Lesson 5 大規模データ処理の難所 ―メモリとディスク
    • Lesson 6 スケーリングの要所
    • Lesson 7 大規模データを扱うための基礎知識
  • 第3回 OSのキャッシュと分散 ―大きなデータを効率良く扱うしくみ
    • Lesson 8 OSのキャッシュ機構
    • Lesson 9 I/O負荷の軽減策
    • Lesson 10 局所性を活かす分散
  • 第4回 DBのスケールアウト戦略 ―分散を考慮したMySQLの運用
    • Lesson 11 インデックスを正しく運用する ―分散を考慮したMySQL運用の大前提
    • Lesson 12 MySQLの分散 ―スケーリング前提のシステム設計
    • Lesson 13 MySQLのスケールアウトとパーティショニング
  • 第5回 大規模データ処理[実践]入門 ―アプリケーション開発の勘所
    • Lesson 14 用途特化型インデクシング ―大規模データを捌く
    • Lesson 15 理論と実践の両側から取り組む
  • 第6回 [課題]圧縮プログラミング ―データサイズ,I/O高速化との関係を意識する
    • Lesson 16 [課題]整数データをコンパクトに持つ
    • Lesson 17 VB Codeと速度感覚
    • Lesson 18 課題の詳細と回答例
  • 第7回 アルゴリズムの実用化 ―身近な例で見る理論・研究の実践投入
    • Lesson 19 アルゴリズムと評価
    • Lesson 20 はてなダイアリーのキーワードリンク
    • Lesson 21 はてなブックマークの記事カテゴライズ
  • 第8回 [課題]はてなキーワードリンクの実装 ―応用への道筋を知る
    • Lesson 22 [課題]はてなキーワードリンクを作る
    • Lesson 23 回答例と考え方
  • 第9回 全文検索技術に挑戦 ―大規模データ処理のノウハウ満載
    • Lesson 24 全文検索技術の応用範囲
    • Lesson 25 検索システムのアーキテクチャ
    • Lesson 26 検索エンジンの内部構造
  • 第10回 [課題]全文検索エンジンの作成 ―基本部分,作り込み,速度と精度の追求
    • Lesson 27 [課題]はてなブックマーク全文検索を作る
    • Lesson 28 回答例と考え方
  • 第11回 大規模データ処理を支えるサーバ/インフラ入門 ―Webサービスのバックエンド
    • Lesson 29 エンタープライズ vs. Webサービス
    • Lesson 30 クラウドvs.自前インフラ
  • 第12回 スケーラビリティの確保に必要な考え方 ―規模の増大とシステムの拡張
    • Lesson 31 レイヤとスケーラビリティ
    • Lesson 32 負荷の把握,チューニング
  • 第13回 冗長性の確保,システムの安定化 ―ほぼ100%の稼動率を実現するしくみ
    • Lesson 33 冗長性の確保
    • Lesson 34 システムの安定化
    • Lesson 35 システムの安定化対策
  • 第14回 効率向上作戦 ―ハードウェアのリソースの使用率を上げる
    • Lesson 36 仮想化技術
    • Lesson 37 ハードウェアと効率向上 ―低コストを実現する要素技術
  • 第15回 Webサービスとネットワーク ―ネットワークで見えてくるサービスの成長
    • Lesson 38 ネットワークの分岐点
    • Lesson 39 さらなる上限へ
  • 特別編 いまどきのWebサービス構築に求められる実践技術 ―大規模サービスに対応するために
    • Special Lesson 1 ジョブキューシステム ―TheSchwartz、 Gearman
    • Special Lesson 2 ストレージの選択 ―RDBMSかkey-valueストアか
    • Special Lesson 3 キャッシュシステム ―Squid,Varnish
    • Special Lesson 4 計算クラスタ ―Hadoop

Nexus One販売終了

Nexus Oneが手に入らなくなるっぽい。
http://japan.cnet.com/news/service/story/0,3800104747,20417034,00.htm
もう2台ほど買っておこうかな。

SunSPOTとか面白いものはどんどん手に入らなくなってきてしまう。

2010年7月14日水曜日

App Inventor for Android

App Inventor for Androidなんてものが、どんどん出てきたら、もうコーディングなんてする必要ないかな。
確かに簡単なものだったらできそう。
XMLで書けるauのケータイカスタムキットなんてものあったけど、まったく流行ってなさそうだし、やっぱコーディングできないとね。

2010年6月18日金曜日

忘れがちなC++での関数ポインタ

クラス内部で状態によって呼ぶ出す関数を変えるときには関数ポインタを使うと便利ですが、C++では書き方が若干面倒なので、その記録。
#include <cstdlib>
#include <iostream>

class FPSample {
public:

    void function_switch(int sw) {
        switch (sw) {
            case 1: m_pFunctionSample = &FPSample::function1;
                break;
            case 2: m_pFunctionSample = &FPSample::function2;
                break;
            default:
                std::cout << "default" << std::endl;
        }
    }

    bool function(int x) {
        return (this->*m_pFunctionSample)(x);
        // return (*mFunctionSample)(x); // Error
    }
private:
    typedef bool (FPSample::*FUNCTION_SAMPLE)(int);
    FUNCTION_SAMPLE m_pFunctionSample;

    bool function1(int x) {
        std::cout << "function1 : " << x << std::endl;
        return true;
    }

    bool function2(int x) {
        std::cout << "function2 : " << x << std::endl;
        return false;
    }
};

int main(int argc, char** argv) {
    FPSample mFPSample;
    int sw;
    int x;

    x = 10;
    
    sw = 1;
    mFPSample.function_switch(sw);
    mFPSample.function(x);

    sw = 2;
    mFPSample.function_switch(sw);
    mFPSample.function(x);

    return 0;
}

2010年6月14日月曜日

たまには使えるアプリ

Wifiの受信レベルを測定し、それをグラフにするアプリです。



















package jp.ac.uu.is.degas.android.wifi;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import android.app.Activity;
import android.content.BroadcastReceiver;
import android.content.Context;
import android.content.Intent;
import android.content.IntentFilter;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.graphics.Paint.FontMetrics;
import android.net.wifi.ScanResult;
import android.net.wifi.WifiManager;
import android.os.Bundle;
import android.view.Menu;
import android.view.MenuItem;
import android.view.SurfaceHolder;
import android.view.SurfaceView;

public class WifiViewActicvity extends Activity {

    private static final int MENU_START = 0;
    private static final int MENU_PAUSE = 1;
    private static final int MENU_QUIT = 2;
    private MySurfaceView mySurfaceView;
    private WifiManager mWifiManager;
    private boolean run;
    private static final float MIN_LEVEL = -120;
    private static final float MAX_LEVEL = 0;
    private static final int TIME_BUFFDER_SIZE = 50;
    private HashMap apMap;
    private long cnt;

    private int[] lineColor = { Color.BLUE, Color.CYAN, Color.GREEN,
            Color.MAGENTA, Color.RED, Color.YELLOW, Color.WHITE };
    private int indexOfColor;

    /** Called when the activity is first created. */
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        mySurfaceView = new MySurfaceView(getApplication(), 0,
                TIME_BUFFDER_SIZE, MIN_LEVEL, MAX_LEVEL, TIME_BUFFDER_SIZE,
                (int) ((MAX_LEVEL - MIN_LEVEL) / 10));
        setContentView(mySurfaceView);
        apMap = new HashMap();
        run = false;
        cnt = 0;
        indexOfColor = 0;
    }

    private void startScan() {
        run = true;
        mWifiManager = (WifiManager) getSystemService(WIFI_SERVICE);
        registerReceiver(mBroadcastReceiver, new IntentFilter(
                WifiManager.SCAN_RESULTS_AVAILABLE_ACTION));
        mWifiManager.startScan();
    }

    private void pauseScan() {
        run = false;
    }

    private final BroadcastReceiver mBroadcastReceiver = new BroadcastReceiver() {
        @Override
        public void onReceive(Context context, Intent intent) {
            List scanResults = mWifiManager.getScanResults();
            for (ScanResult result : scanResults) {
                String bssid = result.BSSID;
                int level = result.level;
                AccessPoint ap = apMap.get(bssid);
                if (ap == null) {
                    ap = new AccessPoint(TIME_BUFFDER_SIZE + 1);
                    ap.setColor(lineColor[indexOfColor]);
                    indexOfColor++;
                    indexOfColor %= lineColor.length;
                }
                ap.setLevel(cnt, Float.valueOf(level));
                ap.setUpdate(true);
                apMap.put(bssid, ap);
            }
            for (Map.Entry e : apMap.entrySet()) {
                AccessPoint ap = e.getValue();
                if (!ap.isUpdate()) {
                    ap.setLevel(cnt, null);
                }
                ap.setUpdate(false);
                apMap.put(e.getKey(), ap);
            }
            if (run) {
                mySurfaceView.setData(cnt, apMap);
                cnt++;
                startScan();
            }
        }
    };

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        menu.add(0, MENU_START, 0, "START").setIcon(
                android.R.drawable.ic_media_play);
        menu.add(0, MENU_PAUSE, 0, "PAUSE").setIcon(
                android.R.drawable.ic_media_pause);
        menu.add(0, MENU_QUIT, 0, "QUIT").setIcon(
                android.R.drawable.ic_menu_close_clear_cancel);
        return super.onCreateOptionsMenu(menu);
    }

    @Override
    public boolean onOptionsItemSelected(MenuItem item) {
        switch (item.getItemId()) {
        case MENU_START:

            startScan();
            break;
        case MENU_PAUSE:
            pauseScan();
            break;
        case MENU_QUIT:
            finish();
            break;
        }
        return super.onContextItemSelected(item);
    }
}

class AccessPoint {
    private Float[] data;
    private boolean update;
    private int color;

    AccessPoint(int size) {
        data = new Float[size];
    }

    void setLevel(long cnt, Float level) {
        data[(int) (cnt % data.length)] = level;
    }

    void setUpdate(boolean update) {
        this.update = update;
    }

    boolean isUpdate() {
        return update;
    }

    void setColor(int color) {
        this.color = color;
    }

    int getColor() {
        return color;
    }

    Float[] getData() {
        return data;
    }
}

class MySurfaceView extends SurfaceView implements SurfaceHolder.Callback,
        Runnable {
    private SurfaceHolder mSurfaceHolder;
    private Thread thread;
    private Canvas canvas;
    private MyGraph myGraph;
    private float minX, maxX, minY, maxY;
    private int numDivX, numDivY;
    private long cnt;
    private HashMap apMap = new HashMap();

    MySurfaceView(Context context, float minX, float maxX, float minY,
            float maxY, int numDivX, int numDivY) {
        super(context);
        mSurfaceHolder = getHolder();
        mSurfaceHolder.addCallback(this);
        myGraph = new MyGraph();
        this.minX = minX;
        this.maxX = maxX;
        this.minY = minY;
        this.maxY = maxY;
        this.numDivX = numDivX;
        this.numDivY = numDivY;
    }

    public void surfaceChanged(SurfaceHolder holder, int format, int width,
            int height) {
    }

    public void surfaceCreated(SurfaceHolder holder) {
        thread = new Thread(this);
        thread.start();
    }

    public void surfaceDestroyed(SurfaceHolder holder) {
        thread = null;
    }

    public void run() {

        while (thread != null) {
            canvas = mSurfaceHolder.lockCanvas();
            myGraph.drawRule(canvas);

            String[] bssidName = new String[apMap.size()];
            int[] bssidColor = new int[apMap.size()];
            int num = 0;
            for (Map.Entry e : apMap.entrySet()) {
                AccessPoint ap = e.getValue();
                Float[] originalData = ap.getData();
                int size = originalData.length;
                Float[] data = new Float[2 * size];
                for (int i = 0; i < size; i++) {
                    data[2 * i] = Float.valueOf(i);
                    data[2 * i + 1] = (cnt < size) ? originalData[i]
                            : originalData[(int) ((i + cnt + 1) % size)];
                }
                myGraph.drawLines(canvas, data, ap.getColor());
                bssidName[num] = e.getKey();
                bssidColor[num] = ap.getColor();
                num++;
            }
            if (apMap.size() > 0) {
                myGraph.drawLegend(canvas, bssidName, bssidColor);
            }
            mSurfaceHolder.unlockCanvasAndPost(canvas);
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
            }
        }
    }

    @Override
    protected void onSizeChanged(int width, int heigh, int old_w, int old_h) {
        int size = (width < heigh) ? width : heigh;
        myGraph.setDarwArea(size, size, minX, maxX, minY, maxY, numDivX,
                numDivY, false, true);
    }

    void setData(long cnt, HashMap apMap) {
        this.cnt = cnt;
        this.apMap = apMap;
    }
}

class MyGraph {
    private static final float TOP_MARGIN_RATIO = 0.05f; // 描画エリアサイズに対する上マージンの比
    private static final float BOTTOM_MARGIN_RATIO = 0.05f; // 描画エリアサイズに対する下マージンの比
    private static final float LEFT_MARGIN_RATIO = 0.05f; // 描画エリアサイズに対する左マージンの比
    private static final float RIGHT_MARGIN_RATIO = 0.05f; // 描画エリアサイズに対する右マージンの比
    private boolean labelFlagX; // X軸ラベル表示フラグ
    private boolean labelFlagY; // Y軸ラベル表示フラグ
    private Paint paintLabel = new Paint();
    private float bodyW; // ラベルを含むグラフエリア
    private float bodyH; // ラベルを含むグラフエリア
    private float graphW; // ラベルを含まないグラフエリア
    private float graphH; // ラベルを含まないグラフエリア
    private float graphOriginX; // ラベルを含まないグラフエリアの原点
    private float graphOriginY; // ラベルを含まないグラフエリアの原点
    private float minX, maxX, minY, maxY;
    private int numDivX, numDivY;

    private float legendOriginX; // 凡例原点
    private float legendOriginY; // 凡例原点
    private Paint legendLabel = new Paint();

    void setDarwArea(float drawW, float drawH, float xMin, float xMax,
            float yMin, float yMax, int xDivNum, int yDivNum,
            boolean labelXFlag, boolean labelYFlag) {
        this.minX = xMin;
        this.maxX = xMax;
        this.minY = yMin;
        this.maxY = yMax;
        this.numDivX = xDivNum;
        this.numDivY = yDivNum;
        this.labelFlagX = labelXFlag;
        this.labelFlagY = labelYFlag;
        // ラベルを含むグラフエリア
        bodyW = (1 - LEFT_MARGIN_RATIO - RIGHT_MARGIN_RATIO) * drawW;
        bodyH = (1 - TOP_MARGIN_RATIO - BOTTOM_MARGIN_RATIO) * drawH;
        // ラベルを含まないグラフエリア
        FontMetrics fontMetrics = paintLabel.getFontMetrics();
        graphH = bodyH;
        if (labelXFlag) {
            graphH += (fontMetrics.top + fontMetrics.bottom);
        }
        graphW = bodyW;
        if (labelYFlag) {
            float maxTextWidth = 0;
            for (int i = 0; i < yDivNum + 1; i++) {
                String text = String
                        .valueOf(yMin + i * (yMax - yMin) / yDivNum);
                float baseX = paintLabel.measureText(text); // テキスト幅
                maxTextWidth = (baseX > maxTextWidth) ? baseX : maxTextWidth;
            }
            graphW -= maxTextWidth;
        }
        // ラベルを含まないグラフエリアの原点
        graphOriginX = LEFT_MARGIN_RATIO * drawW + (bodyW - graphW);
        graphOriginY = TOP_MARGIN_RATIO * drawH;
        // 凡例原点
        legendOriginX = graphOriginX + 0.05f * graphW;
        legendOriginY = graphOriginY + 0.05f * graphH;
    }

    /* グラフの罫線、軸描画 */
    void drawRule(Canvas canvas) {
        // 背景色
        canvas.drawColor(Color.WHITE);
        // 罫線
        Paint paintRule = new Paint();
        paintRule.setStyle(Paint.Style.FILL);
        paintRule.setColor(Color.BLACK);
        for (int i = 0; i < numDivX + 1; i++) {
            canvas.drawLine(graphOriginX + i * (graphW / numDivX),
                    graphOriginY, graphOriginX + i * (graphW / numDivX),
                    graphOriginY + graphH, paintRule);
        }
        for (int i = 0; i < numDivY + 1; i++) {
            canvas.drawLine(graphOriginX,
                    graphOriginY + i * (graphH / numDivY), graphOriginX
                            + graphW, graphOriginY + i * (graphH / numDivY),
                    paintRule);
        }
        // 軸ラベル
        paintLabel.setColor(Color.GRAY);
        FontMetrics fontMetrics = paintLabel.getFontMetrics();
        if (labelFlagX) {
            for (int i = 0; i < numDivX + 1; i++) {
                String text = String
                        .valueOf(minX + i * (maxX - minX) / numDivX);
                float baseX = paintRule.measureText(text) / 2; // テキスト幅の半分
                float baseY = -fontMetrics.top; // baselineからtopまでの高さ
                canvas.drawText(text, graphOriginX + i * (graphW / numDivX)
                        - baseX, graphOriginY + graphH + baseY, paintLabel);
            }
        }
        if (labelFlagY) {
            for (int i = 0; i < numDivY + 1; i++) {
                String text = String
                        .valueOf(minY + i * (maxY - minY) / numDivY);
                float baseX = paintLabel.measureText(text); // テキスト幅
                float baseY = -fontMetrics.top / 2; // baselineからtopまでの高さの半分
                canvas.drawText(text, graphOriginX - baseX, graphOriginY
                        + graphH - i * (graphH / numDivY) + baseY, paintLabel);
            }
        }
    }

    void drawLines(Canvas canvas, Float[] data, int color) {
        // 境界チェック
        for (int i = 0; i < data.length / 2; i++) {
            if (data[2 * i] != null && data[2 * i + 1] != null) {
                data[2 * i] = (data[2 * i] < minX) ? minX : data[2 * i];
                data[2 * i] = (data[2 * i] > maxX) ? maxX : data[2 * i];
                data[2 * i + 1] = (data[2 * i + 1] < minY) ? minY
                        : data[2 * i + 1];
                data[2 * i + 1] = (data[2 * i + 1] > maxY) ? maxY
                        : data[2 * i + 1];
            }
        }
        float[] pts = new float[4 * (data.length / 2 - 1)];
        // 描画座標へ変換
        float pxlParUnitX = graphW / (maxX - minX); // X軸の単位辺りの画素値数
        float pxlParUnitY = graphH / (maxY - minY); // Y軸の単位辺りの画素値数
        for (int i = 0; i < data.length / 2 - 1; i++) {
            if (data[2 * i] != null && data[2 * i + 1] != null
                    && data[2 * i + 2] != null && data[2 * i + 3] != null) {
                float x1 = data[2 * i];
                float y1 = data[2 * i + 1];
                float x2 = data[2 * i + 2];
                float y2 = data[2 * i + 3];
                pts[4 * i] = (x1 - minX) * pxlParUnitX + graphOriginX;
                pts[4 * i + 1] = graphH - (y1 - minY) * pxlParUnitY
                        + graphOriginY;
                pts[4 * i + 2] = (x2 - minX) * pxlParUnitX + graphOriginX;
                pts[4 * i + 3] = graphH - (y2 - minY) * pxlParUnitY
                        + graphOriginY;
            }
        }
        Paint paint = new Paint();
        paint.setColor(color); // 線の色
        paint.setStrokeWidth(2); // 線の太さ
        canvas.drawLines(pts, paint);
    }

    void drawLegend(Canvas canvas, String[] name, int[] color) {
        Paint paint = new Paint();
        float lineLength = 0.05f * graphW;
        FontMetrics fontMetrics = legendLabel.getFontMetrics();
        float width;
        float textW = 0;
        for (int i = 0; i < name.length; i++) {
            width = legendLabel.measureText(name[i]);
            textW = (width > textW) ? width : textW;
        }
        float textH = -fontMetrics.top + fontMetrics.bottom;

        float legendH = name.length * textH + fontMetrics.bottom;
        float legendW = textW + lineLength;

        paint.setColor(Color.WHITE);
        paint.setStyle(Paint.Style.FILL);
        canvas.drawRect(legendOriginX, legendOriginY, legendOriginX + legendW,
                legendOriginY + legendH, paint);

        paint.setColor(Color.BLACK);
        paint.setStyle(Paint.Style.STROKE);
        canvas.drawRect(legendOriginX, legendOriginY, legendOriginX + legendW,
                legendOriginY + legendH, paint);
        float x, y;
        x = legendOriginX;
        y = legendOriginY + textH;
        for (int i = 0; i < name.length; i++) {
            paint.setColor(color[i]);
            paint.setStrokeWidth(2);
            canvas.drawLine(x, y + fontMetrics.top / 2, x + lineLength, y
                    + fontMetrics.top / 2, paint);
            paint.setColor(Color.BLACK);
            canvas.drawText(name[i], x + lineLength, y, legendLabel);
            y += textH;
        }
    }
}