Bigtable: A Distributed Storage System for Structured Data を読んだ

Bigtable: A Distributed Storage System for Structured Data を読んだ時のメモ。

どんなもの？

• ペタバイト級のデータ、何千台ものサーバまでスケールする大規模分散ストレージ
• Google Analyics, Google Earth, Web indexing等に使われている

先行研究とくらべて何がすごい？

• 低コストで高いパフォーマンスと可用性、スケーラビリティを達成した
• Googleの既存のsystemを組み合わせて作られている
  • GFS, Chubby, MapReduce etc

技術や手法の肝は？

• Data Model

  • sparse, distributed, persistent multidimentsional sorted map
  • (row:string, column:string, time:int64) → string
    • row,column,timestampでindexingされている
  • row keyは任意の文字列
    • transaction consistencyの単位がrow
    • 辞書順にrow keyでソートされている
    • 最大64KBで一般的には10~100byte
  • column family
    • column keyをグループ化したもの
    • diskやmemoryへの割り当ての単位
  • timestampでindex化された複数バージョンのデータをもつ
    • read時には最新のデータから読まれる
    • client側で何世代保持しておくかを設定できる
  • filesystemはGFS
  • Chubbyでmaster serverやtabletサーバの管理、スキーマ情報の格納等を行う

• 構成

  • master server
    • tablet serverとやり取りする
      • Chubbyに登録されたtablet serverのデータをもとにTabletの割当をおこなう
  • tablet server
    • tabletのread/writeのハンドル、tabletの分割
    • clientとのやりとりはmaster serverを介さずにtablet serverが行う
  • tablet
    • tableを分割した単位(1つあたり100~200MB)
      • 一定範囲のrow keyのデータを含む
    • memtableとSSTableから成る
      • memtable
        • tablet serverのメモリ上にある
        • 直近でcommitされたデータをもつ
      • SSTable
        • GFSに保存されている
        • BigTableのデータを保存している
        • memtableが消えてもSSTableから再構築できる

どうやって有効と検証した？

• performance
  • tablet serverの台数を変えてread/writeのパフォーマンスを測定した
    • 1000bytesのread毎に64KBのブロックを転送した
  • random read
    • 一番遅い
    • read毎に、64KB SSTable blockを転送すると1200 read/secで75MB/sのデータをGFSから読み込むことになりネットワーク帯域がサチった
  • random write
    • random readよりもパフォーマンスが良い
      • 1つのcommit logに書き込みを行って、GFSに対してgroup commitを行っているから
  • sequential read
    • random readよりもパフォーマンスが良い
    • GFSからfetchしてくる64KB SSTable blockがblock cacheに含まれていて、64個のread requestとして使われるから

議論はある？

• tablet serverが少ない時に負荷が偏ってしまい、パフォーマンスがあまり出ない
• rebalance中はtabletの移動数が減少してしまう
• secondary indexのサポート
• multiple master replicaのcross-data-centerでのレプリケーション

次に読むべき論文は？

• The Google File System
• The Chubby lock service for loosely- coupled distributed systems.

Dynamo - Cloud Computing & Big Data Group Discussion を読んだ

Dynamo: Amazon’s Highly Available Key-value Store を読んだのでメモ

メモのフォーマットは下記を参考にした。

先端技術とメディア表現1 #FTMA15 from Yoichi Ochiai

どんなもの？

• Dynamoは可用性とスケーラビリティのあるkey-value storage
  • primary keyアクセスでかつ1Mより小さいデータを扱うものをターゲットにしている
  • always writable
  • responseの99.9percentileが300ms以内(500req/sec)

先行研究とくらべて何がすごい？

• 既存の技術の組み合わせで可用性とスケーラビリティのあるプロダクトを実装し本番で利用していること

技術や手法の肝は？

• consistent-hashingでパーティションとレプリケーションを行っている
• gossipベースのfailure detection/membership protocol
• weak-consistency(eventual consistency)によってパフォーマンス/スケーラビリティの向上
• objectはversioningされてconsistencyを担保している
• sloppy quoramとhinted hand offにより、nodeやネットワークの障害時でも可用性を担保
• anti-entropyによりレプリカの同期を行う

どうやって有効と検証した？

• 2006年12月のある日の12時間分のレスポンスタイムで検証
  • 99.9%は200ms以下でレスポンスが返ってきていた

議論はある？

• eventual consistencyを用いているので、導入する際には対象のアプリケーションがweak consistencyでも大丈夫か検討する
• nodeが増えれば増えるほど(数千nodeくらい)routing tableが大きくなって、routingのコストがかかってしまう

次に読むべき論文は？

Bigtable: A Distributed Storage System for Structured Data

統計検定2級に合格しました

概要

統計検定2級 (CBT方式試験) に合格しました。 79/100点でボーダーが60点でした。 Machine Learning | Coursera を受けた後に「統計学について何も知らないので勉強してみよう」と思ったのがきっかけです。 統計検定の勉強自体は2ヶ月ほどで、平日30分~1時間、土日2時間ほど勉強してました。

前提

文系(数ⅡBまで)で、微分積分は公式を見ると思い出せる程度でした。 微分積分をするのは10年ぶりです。

勉強法

最初の1ヶ月

マンガでわかる統計学

マンガでわかる統計学 回帰分析編

まず1週間ほどで「マンガでわかる統計学」シリーズを読みました。 確かに分かりやすかったのですが、その分内容が薄いので、このシリーズは読まずに、後述する「よくわかる心理統計」を読めば良かったと思います。

Rによるやさしい統計学

次に2週間ほどで「Rによるやさしい統計学」を読みつつ、Rで検定していました。 Rで様々な検定を行っていくのですが、統計検定では自分で計算をする必要があるので、この本も読む必要はなかったと思います。 ただ実務ではRを使うことが多いと思うので、読むならば各検定の計算方法がわかった後が良かったです。

よくわかる心理統計 (やわらかアカデミズム・わかるシリーズ)

続いて「よくわかる心理統計」を読みました。 初学者にも分かりやすい良書です。 統計用語の説明がされていたり、各検定の例題と検定の仕方が詳しく書かれていたので、この本で理解が深まりました。 統計検定2級の内容をほぼ網羅している(回帰やベイズ等は含まれていない)ので、これから勉強を始める方はまずこの本を1ヶ月かけて何度も繰り返すと良いと思います。

二ヶ月目

引き続き「よくわかる心理統計」をこの月の1週目まで読んでいました。

日本統計学会公式認定 統計検定 2級 公式問題集[2014〜2016年]

一通り勉強が終わったので、週末に過去問を解いてみました。 最初は散々な結果だったのですが、「自分がどの部分が出来ていないのか」が理解できたので、次週からベイズや確率の勉強を始めました。

完全独習 ベイズ統計学入門

ベイズについては「よくわかる心理統計」に書かれていないので、この本で勉強しました。 極力「ベイズの公式」を使わずに理解させようという方針の本で、数式アレルギーがある方でもスッと理解できると思います。 この本を読んでからベイズの問題は得点源になりました。

スバラシク実力がつくと評判の統計学キャンパス・ゼミ―大学の数学がこんなに分かる!単位なんて楽に取れる!

確率変数の問題が苦手だったので、この本の確率変数の部分だけを読んで勉強しました。 微分積分の計算方法を思い出したり、確率密度関数から期待値や分散を出す計算を練習しました。

ここで、二ヶ月目の2週間が終わりました。

日本統計学会公式認定 統計検定 2級 公式問題集[2014〜2016年]

日本統計学会公式認定 統計検定 2級 公式問題集[2012〜2014年]

残りの期間はひたすら過去問を解いていました。 各年度3回くらい解いて、わからないところはその都度「よくわかる心理統計」等で復習をしていました。

統計学入門 (基礎統計学?)

「統計学入門」も買ったのですが、内容が難しかったので使いませんでした。 「よくわかる心理統計」を何度も読み返していました。

まとめ

「文系卒で微積をするのは10年ぶり」でも、2ヶ月あれば統計検定2級合格できました。 もし2ヶ月前の自分にアドバイスするなら、下記の流れで勉強しろと言うと思います。

1. 初日に2014年くらいの過去問を解く
2. 「よくわかる心理統計」を2週間で読む
3. 再度別の過去問を解いて、自分に足りない部分を把握する
4. ベイズと確率の勉強をする
5. 過去問を解きながら、「よくわかる心理統計」で復習する

「もっと初期に過去問を解く」「色んな参考書に目移りせずによくわかる心理統計だけやり込む」をすれば、もう少し短期間で合格出来たと思います。

「機械学習の勉強のための基礎固めに！」と思っている方は、是非統計検定を受けてみてください！

SRM 647 Div2 250 PeacefulLine

問題文

TopCoder Statistics - Problem Statement

書いた

class PeacefulLine:
    def makeLine(self, x):
        counter = collections.Counter(x)
        count_arr = []

        for word, cnt in counter.most_common():
            count_arr.append(cnt)

        is_continue = True
        while is_continue:
            count_arr = sorted(count_arr)
            count_arr = map(lambda n:n-count_arr[0], count_arr)
            count_arr = filter(lambda n:n!=0, count_arr)

            if len(count_arr) <= 1:
                is_continue = False
        res = "impossible"
        if len(count_arr) <= 0 or count_arr[0] <= 1:
            res = "possible"

        return res

他の参加者のコード見た

class PeacefulLine:
    def makeLine(self, x):
        p = {}
        l = len(x)
        if (l%2==0):
            l=l/2
        else:
            l=(l//2)+1
        for i in x:
            p[i] = p.get(i,0)+1
        a = 0
        for i in p.keys():
            a = max(a,p[i])
        if(a>l):
            return "impossible"
        else:
            return  "possible"

その他

一番多い数の組が半分以上あればimpossibleだった。 数値の数を数える時に dict.get(i,0)+1 は使えそう

SRM 642 Div2 250 ForgetfulAddition

問題文

https://apps.topcoder.com/wiki/display/tc/SRM+642

書いた

class ForgetfulAddition:
    def minNumber(self, expression):
        num = str(expression)
        res = 0
        for i in xrange(1, len(num)):
            sum_num = int(num[:i]) + int(num[i:])
            if res == 0:
                res = sum_num
            res = min(res, sum_num)
        return res

他の参加者のコードみた

class ForgetfulAddition:
    def minNumber(self, expression):
        ans = 99999999
        for i in xrange(1, len(expression)):
            ans = min(ans, int(expression[i:]) + int(expression[:i]))
        return ans

感想

問題文の設定上99999999以上にはならないので、最初に設定しておけばif分無くていける。 ムダなstr変換無くす。

SRM 639 Div2 250 ElectronicPetEasy

問題文

https://apps.topcoder.com/wiki/display/tc/SRM+639

書いた

class ElectronicPetEasy:
    def isDifficult(self, st1, p1, t1, st2, p2, t2):

        first = []
        for i in xrange(t1):
            first.append(st1+(p1*i))

        second = []
        for i in xrange(t2):
            second.append(st2+(p2*i))

        res = "Easy"
        for i in first:
            if i in second:
                res = "Difficult"
                break
        return res

他の参加者のコードみた

class ElectronicPetEasy:
    def isDifficult(self, st1, p1, t1, st2, p2, t2):
        feed1 = set(range(st1, st1+p1*t1,p1))
        feed2 = set(range(st2, st2+p2*t2,p2))
        if feed1 & feed2 == set([]):
            return "Easy"
        return "Difficult"

感想

rangeでstart, stop, stepを指定すると等差数列を作れる。 set形だと&で共通する要素があるか比較できるので便利。

SRM 638 Div2 250 NamingConvention

問題文

https://community.topcoder.com/stat?c=problem_statement&pm=13521

書いた

class NamingConvention:
    def toCamelCase(self, variableName):
        while variableName.count('_') > 0:
            replace_char_index = variableName.index('_')
            variableName = variableName[:replace_char_index] + variableName[replace_char_index+1].upper() + variableName[replace_char_index+2:]
        return variableName

他の参加者のコードみたあと

result = ""
        variableName = list(variableName)
        for i, c in enumerate(variableName):
            if c == '_':
                variableName[i+1] = variableName[i+1].upper()
            else:
                result += c
        return result

感想

_ のindexを取得して、_を削除し、その後の文字を大文字にするということを考えたが、愚直に文字列をforで回したほうがシンプルだった。 pythonのstrは、Immutableなので直接書き換えることができない。 一旦Mutableなlistにしてから書き換える。