Big Table: A Distributed Structured Storage Systemを見たメモ - スティルハウスの書庫の書庫
Big Table: A Distributed Structured Storage System ＜Googleの典型的なクラスターノード構成＞ クラスターノード構成 クラスターノード Intelベースの安いPC Linux OS Scheduler slave GFS chunk server Cluster scheduling master Lock service (Chubby) GFS master これらのノードの上に、スケジューラが各種サービスを載せていく 各種タスク（アプリ？） Bigtable Server（tablet server） Bigtable Master tablet 1つのtabletは100〜200MB程度のデータを保有 1台のtablet serverで100以下のtabletを保有 復旧が高速：1台がダウンしても、その100個のtabletは他
グローバルトランザクション／分散トランザクションについて - スティルハウスの書庫の書庫
「グローバルトランザクション」という言葉の意味について、昨日の飲み会で議論になったので、まとめ。 グローバルトランザクションと分散トランザクション グローバルトランザクションは、分散トランザクションと同義です。グローバルトランザクションは複数のリソースマネージャを含むトランザクションを指します。一方、ローカルトランザクションは単一のリソースマネージャ（DB等）のみで構成されるトランザクションを指します。 http://download.oracle.com/docs/cd/B14117_01/java.101/b10979/xadistra.htm#i1066628 A distributed transaction, sometimes referred to as a global transaction, is a set of two or more related transac
あまりパッとしたDremelクローンが出てこないので俺が考えた - スティルハウスの書庫の書庫
ディスクI/Oの並列度が1000超えてないDremelクローンって… Apache DrillやCloudera ImpalaといったDremelインスパイア系のリアルタイム低遅延でカラム型なデータストア的何かがいくつか出てきて、最初はちょっと身構えた（Amazon RedshiftはRDBクラスタって感じでDremel系とは違うかも）。Dremelの立場危うし！ しかし、よくよく話を聞いてみるとどれも並列度が数十って規模らしく、ちょっとガッカリ＋安心した次第。オープンソースでDremel的なものを作るなら、俺ならこうするぜ！ってアイディアを今朝思いついたので、自分で実装する気はないけど書き残しておきたい。 ビッグデータの最大のボトルネックはディスクドライブ 先日公開されたBigQueryのホワイトペーパー、英語だし基本はDremelペーパーを読みやすくした程度の内容なのであまりまじめに読
GAEのサーバー構成とリクエストの流れ - スティルハウスの書庫の書庫
＜Google App Engine Stackの構成（引用元）＞ GAE Stackの特徴 現在の利用状況 8万以上のアプリを収容 140M PV/day 20万人以上の開発者が利用 統合環境を提供 サーバーの構築や管理が不要。デプロイが容易 ログ管理、管理コンソールや各種ツールを提供 スケーラブルなWebアプリ構築のためのベストプラクティス利用を促す環境 個々のリクエストの処理時間やリソース消費を制限 ステートレス設計と内蔵APIの利用 Datastoreによるパーティション化されたデータモデルの利用 非常に高いスケーラビリティと可用性を備えるGoogleのクラスタ環境を簡単に利用できる 自動クラスタリングによる負荷分散と高可用性を提供 アプリの負荷状況に応じてApp Serverを動的に増減 アプリ間の隔離性を維持、個々のアプリの安全性とパフォーマンスを確保 既存のGoogleテクノ
文字通り「ネットワークがコンピューター」な金融HFTでのFPGAの使われ方 - スティルハウスの書庫の書庫
ここのところ重度のFPGA中二病にかかってしまい、冬休み中もDE0ざんまいな日々。気になっていた金融のHFT（high frequency trading：大手投資銀行等がμ秒単位の超高速で株式等を売り買いしてる恐ろしい市場）におけるFPGA利用状況について、HFT Reviewにこってりしたレポート（HFT業界のベンダー各社にインタビューしたもの）が載っていたので、勢い余って面白かった部分を超訳してしまった。 元ネタはこちら： FPGA & Hardware Accelerated Trading, Part One - Who, What, Where and Why? FPGA & Hardware Accelerated Trading, Part Two - Alternative Approaches FPGA & Hardware Accelerated Trading, P
Google Megastoreのお勉強メモ #appengine - スティルハウスの書庫の書庫
BrettさんのSTMに関する記事の中でGoogle Megastoreについて言及されていて、そのリンク先がハミルトン先生の2008年7月の記事（内で紹介されていたPhil Bernsteinさんのメモ）でした。つまりどうやらMegastoreに関する公開情報でGooglerのお墨付きなものはこれしかなさそうです。そこで改めて要点を写経しつつ、App Engineレベルから見た疑問点等をまとめてみました。なお、青色部分は私の訳注および感想です。同じ記事について解説したkuenishiさんの記事もありますので、合わせてご参照ください。 ところでここでは「BigTable」表記です。BigtableのTが大文字か小文字かについてguidoは「う〜ん論文ではtだったから小文字じゃないかな〜」と言ってました。つまりGoogle社内でも統一されてません。 Google Megastore What
Migration to a Better Datastoreの要点メモ・その１ - スティルハウスの書庫の書庫
appengine blogにポストされたMigration to a Better Datastoreの要点をピックアップしてみました。間違い等ありましたらご指摘ください！ Googleは「マルチホーミング」を追求している データセンター単位でのダウンに対応する リードオンリータイプのアプリなら簡単だが、Gmail/Calendar/App Engineのようなリアルタイムに読み書きのあるアプリでは難しい 現在のApp Engineにおけるマルチホーミングの仕組み Datastoreサービスは個々のアプリについて1つのデータセンターで提供 Bigtableの（訳注：その下のGFSの？）レプリケーション機能により、データはデータセンターAからデータセンターBにバックグラウンドでレプリケーションされる （データセンター規模の障害やメンテによる）データセンターの切り替え時の動作 AのDatas
仮想化＋SSDで幸せになれました - スティルハウスの書庫の書庫
もう5年ほどVMware Workstationを使っていますが、SSDの登場で、便利さが一気に2レベルくらいアップしました。 VMのネックはディスクI/Oが遅いこと。Hyper-Vの最新版やIntegrity VMなどではネーティブ性能に近いディスクI/Oを達成しているという話も聞きましたし、VMwareの高い製品にはそうしたオプションがあるのかもしれません。しかし普通にVMware WorkstationやESXiでVMを作り、あらかじめディスク領域を10GBとか確保してやっても、VMのディスクI/Oはネーティブの2/3程度。さらに、1台のHDDを複数のVMで共有すると、劇的に遅くなります。Windows XPゲストのVMなどは、かなりもっさりです（LinuxゲストのVMは軽いのであまり気になりませんが）。しかし、それぞれのVMに個別のHDDを割り当てるのは、仮想化のメリットも半減です
BigtableによるDatastoreの実装 - スティルハウスの書庫の書庫
Bigtableにできること Bigtableは「ソート済みのExcel表」のようなデータ構造 個々のセルは過去の履歴を残せる 巨大なkey-value store。個々の行の「キー」があれば「値」を高速に取得できる キーの辞書順でソートされている スキーマレス（各行ごとにカラムの数や種類を変えられる） ＜Bigtableの構造：引用元＞ Bigtableにできること キーを指定した行単位のCRUD 行単位のACID特性が保証される 2種類のスキャン： prefix scan: キーの前方一致検索で複数行を一括取得 range scan: キーの範囲指定検索で複数行を一括取得 ソート済みなので高速に実行できる Bigtableではカラムの値に基づく検索は一切実行できない！ ＜prefix scanとrange scan：引用元＞ Datastoreのエンティティテーブル Datastore
トランザクションとエンティティグループ - スティルハウスの書庫の書庫
Datastoreのトランザクション エンティティグループ単位でACIDを保証 Bigtableは行単位のACIDしか保証しない。Datastoreではエンティティグループ単位でのACIDを保証している 楽観的排他制御（optimistic lock）を実装 エンティティグループのrootエンティティにて、トランザクションの最終コミット時間のタイムスタンプを記録 トランザクションの開始時に同タイムスタンプを確認し、コミット時にタイムスタンプを再度確認する タイムスタンプが変化していなければ、更新内容を保存して、タイムスタンプを更新する タイムスタンプが変化してれば、他のトランザクションとの競合が発生しているので、トランザクションをロールバックする RDBの悲観的排他制御（SELECT FOR UPDATE）のようにエンティティをロックしないので、スループットは高いが、競合時のリトライが必要
STMよくわかりません＞＜ - スティルハウスの書庫の書庫
@ashigeruさん謹製のsmalltable_toyのソースを読み解く基礎知識として、Beautiful CodeのSubversion解説につづき、@ashigeruさんとの会話で教えていただいたSTM(Software Transactional Memory)の論文をちろっと読んでみました（pdfをkindleに入れて、子供とガーラ湯沢で雪遊びした帰りの新幹線で読んでました）。 2/3くらい読み進んで、理解度は50%くらいだとは思うのですが、これまでの疑問点： 要するにメモリやオブジェクトを（悲観的ロックの代わりに）バージョニングで楽観排他するってことだと思うのだけとどうか？（helpingとか最適化手法はいろいろあるようだけど） 元ネタであるHardware Transactional Memoryは、つまりメモリチップのレベルでメモリ内容の書き換えをバージョン管理してtx排他
Datastoreによるクエリの実装 - スティルハウスの書庫の書庫
クエリ＝インデックス＋スキャン すべてのクエリは「インデックス＋スキャン」に変換される Bigtableはクエリをサポートしていない。GAEのアプリが実行するすべてのクエリは、インデックスとスキャンの組み合わせに変換される Datastoreのインデックスとは エンティティテーブルとは別に作成されるBigtableのテーブル クエリを記述すると自動的に作成される。明示的な作成も可能 3種類のインデックス カインドインデックス シングルプロパティインデックス コンポジットインデックス カインドインデックス 「エンティティのカインド（Kind＝クラスのこと）の名前」をキーとするインデックス あるクラスのすべてのエンティティの一覧を提供 例：Grandparentでカインドインデックスをスキャン SELECT * FROM Grandparent ＜カインドインデックス：引用元＞ シングルプロパ
BigQueryってなんぞ？ - スティルハウスの書庫の書庫
Google I/O 2010では、Google Storageと合わせて利用する新機能「BigQuery」が発表されました（これもApp Engineとは個別のプロダクトです）。ひとことで言えば「何100億件のデータも数秒〜数10秒で集計できる、大規模並列クエリサービス」です。既存のOLAPやデータウェアハウスに相当するもので、更新処理には使えません。 MapReduceとはどう違う？ 大規模なデータセットに対して多数のサーバで並列処理するという点ではMapReduceに似ていますが、処理結果がすぐに得られる点、そしてSQLっぽいクエリ言語で表現できる集計処理しか実行できない（mapperやreducerを定義してデータを任意の方法で加工したりできない）点がMRとは異なります。MRよりさらに高水準の分散処理サービスです（MR＋Hiveに近いかもしれません）。 リンク集 BigQuery
Bigtableの内部構造 - スティルハウスの書庫の書庫
Bigtableの概要 Bigtableとは 構造化データを管理するための分散化ストレージ 膨大な数の汎用サーバーをつなげてペタバイト規模のデータを扱えるよう設計されている Bigtableの歴史 およそ7人年の開発作業を経て、2005年4月からプロダクション利用を開始 2006年時点では、Googleの60以上のプロジェクトがBigtableを利用 検索, Analytics, Finance, Orkut, Earth, YouTube, Mapなど Bigtableが動くサーバーの構成 ＜Googleの典型的なクラスターノード構成：引用元＞ 個々のノードの基本構成 Intelベースの安いPC Linux OS Schedulerスレーブ Schedulerマスターの指示に従ってノード上に各種サービスをデプロイする GFSチャンクサーバー GFSのチャンク（データ）を保存する タブレッ
Paxosお勉強メモ - スティルハウスの書庫
Paxosのお勉強メモです（以下、分散システムとか無知なのですごく勘違いしてる可能性ありますので要注意） Wikipedia: Paxos algorithm Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures. Paxosは、信頼性の低い複数の処理ノードによるネットワークで「コンセンサス
App EngineやNoSQLはスケーラブルだからエラいのではない - スティルハウスの書庫の書庫
…という視点で@ashigeruさんとつぶやいたまとめ。 kazunori_279scalabilityやスループットの高さよりも、すべてのアプリをpartition-tolerantに書くよう強制して巨大インフラに細粒度で集約し、桁違いの全体最適を実現できることが重要と思う。でないと大規模サービス以外はあまり必要ない＞NoSQLとかKVSlink ashigeru@kazunori_279 エコノミックにするコツはCPU Usageを平均70%以上くらいにするとからしいですねwlink kazunori_279@ashigeru 発電所の発電機だってそんな感じの運用ですよねlink ashigeru@kazunori_279 そうだとおもいます。 #appengine 関係の社内向けメモでは、fine-grain distributed app hostingによるロードの均一化みたいな
STMよくわかりません＞＜・その２ - スティルハウスの書庫の書庫
前回にひきつづきSTMをお勉強中。WikipediaのSTMの説明を読み直していたら、以下のような記述がありました。 2005年に、Tim Harris、Simon Marlow、Simon Peyton Jones そして Maurice Herlihy によって STM が Concurrent Haskell 上に構築された。これは任意のアトミックな操作をより大きなアトミックな操作に合成することができる。この役に立つ考えはロックベースプログラミングでは不可能である。以下妄想：RDB等の文脈での楽観排他だと、2つのtx間で競合検出したらリトライするしかないけど、上記のように両者を合成できるとすれば新しいかもしれない…。どういう仕掛けだろう？ 逆にこれをRDBとかデータストア一般に適用すれば、ロックフリーなおかつリトライ不要なtx排他手法なんてのが実現できる。。？ ああそれとも副作用のな
2009-06-16
App Engine: Now Serving Java Servlet API HTTP Sessionは永続化され、どのクラスタノードからでも同じセッション内容を取得できる App Engine API jar パッチリリースのアップグレードは自動的に行われ、再デプロイの必要はない ApiProxy APIコールはApiProxyを経由して実行される 個々のリクエストの情報（ThreadLocal）を保存する APIコールをAOPのようにインターセプトして、その前後に追加処理を挿入できる ログ記録など クラスパス変更（JAR入れ替え？）だけで、APIのサービスプロバイダーを変更できる unit testに便利 Flexible Sandboxing きめ細かなサンドボックス制御で、安全性を確保しつつ、できるだけ多くの既存コードを動かせる環境を提供する app engineで使える既存ラ
Task Queueのタスクがどのように複数のJVMに負荷分散されるか試したよ #appengine - スティルハウスの書庫の書庫
ご存じのとおり、App EngineのJVM（App Server）はクラスタ化されていて負荷分散される――というのがGoogleの説明です。しかし、WebブラウザからApp Engineに届くHTTPリクエストや、Task Queueのタスクによって呼び出されるHTTPリクエストは、実際にどのような感じで複数のJVMに配られるのでしょうか？ どれくらいの量のリクエストが届いたとき、何台のノードに負荷分散される？ 負荷分散のアルゴリズムは？（単純ラウンドロビン、sticky session/session affinity、負荷状況に応じた転送など） 新しいJVMの追加や、既存のJVMの削除のタイミングは？ これらについてはGoogleから情報が公開されておらず、謎です。そこでApp Engine利用者の皆さんが実際の経験やテストを通じて情報を交換しながら想像たくましくするしかないわけです
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ahack #4 の@ashigeruさんのBigQuery解説 - スティルハウスの書庫の書庫
