サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
猫
qiita.com/kumagi
これまで多くのトランザクションの要素技術を説明してきた。 Googleの公開している論文Spanner: Google's Globally-Distributed Database は公開当初、要求される専門技術の多さからよくわからないと言っている人が多かったが、これまでに説明した要素技術をベースにすると理解しやすい。 Spannerとは 複数のデータセンターに跨ってデータベースの内容を複製し続ける事で高い可用性を実現するという構想は数多くあった。 しかしそれらの分散データベースは実用的な速度を実現しようとすると、データモデルがただのRDBより単純化して使いにくかったりトランザクションをサポートしなかったりと、アプリケーションの一貫性を実現するのが難しい。 現にGoogleの社内でもBigtableなどを用いたアプリケーションは複数あるものの、それぞれでそのデータモデルの上で無理やりトラ
昨日様々なトランザクション分離レベルに付いて書いた。 AnomalyとはSerializableでない実行を引き起こす異常状態パターンのことを言う。 弱い分離レベルほどAnomalyが起きやすい。 これから図を交えながらAnomalyについて説明する。 図中の「W(x)」は「xに何らかの値を書き込む」、「R(x)」は「xの値を読む」をそれぞれ意味する。 分かりやすいようにReadは青、Writeは赤色で統一する。 また、Anomalyの被害に遭うのは常にT1に統一する。 Cはコミットを意味する。 Dirty Read Anomaly 未コミットな値を読んでしまうAnomalyの事。Readがロック関係なしに値を読んでしまう場合などに起きる。 T1が書き換えられる最中のxの値を読んでしまっている。もしT2が途中でアボートしたらT1はどこにも存在しない値を読んだ事になってしまう。 READ U
この記事はpyspaアドベントカレンダー2021の三日目です。前日の記事はykubotaさんです。 はじめに 「自分には才能がある!」と信じてこの業界に踏み込んだものの右も左も怪物だらけで形見が狭い思いをしているのは僕だけではない。 憧れるのは異世界転生のような俺TUEEEE展開であり「何ってクイックソートをしただけだが?」とか言ってたら地位と名声が向こうから転がり込んできて欲しい。 しかし世の中そんなに甘くなく、標準ライブラリを使って威張れるのは学生ぐらいのものである。 学生?そうだ!学生の頃から精進しまくっていたら今ごろすごいソフトウェアエンジニアになれていたはずなんだ!という後悔を抱えて生きている社会人が世の中にはいっぱいいる。 そんな立場から若者を見ていると「大学に入ってプログラミングを始めました」という大学生を見かけるたびにアドバイスをしたくなる衝動に駆られるが、毎度同じような事
Register as a new user and use Qiita more conveniently You get articles that match your needsYou can efficiently read back useful informationWhat you can do with signing up
Multiversion Serialization Graph(MVSG)の導入 マルチバージョンの環境でのトランザクションの順序を整理する為に、Multiversion Serialization Graphという考え方を導入する。 グラフとは頂点と辺からなる構造で、各頂点は各トランザクションの各ステップである。 辺を引くルールは簡単で あるトランザクションAが書いた(=新バージョンを生成した)値を別のトランザクションBが読む場合、A→Bの関係を取る あるトランザクションAが書いた(=新バージョンを生成した)後で別のトランザクションBが書く(=新バージョンを生成する)場合、A→Bの関係を取る という2つのルールでトランザクションステップの間に辺を引く。文章で書くとわかりにくいので図で書いて説明すると例えば以下のようなマルチバージョンスケジュールがある。 この中で、上に書いたルールの通り
Reads-From関係の導入 トランザクション内で値を書き込む場合、その書き込み操作はMultiversionの実行時には必ず「新たなバージョンを作る」という操作で代用する(無限にバージョンを増やしていくとメモリが足りないという問題はあるがそれは後日の議論で解決する)。 「トランザクションaがxに書き込む」場合、その値をバージョンaを付けてxaと表現することにする。トランザクション1が書いた値ならx1と表現するしトランザクション2が書いた値ならx2と表現する。そうしてバージョンを付けた値を扱うスケジュール図をマルチバージョンスケジュール図と以後では呼ぶ。 マルチバージョンスケジュール図から「それぞれのReadが読んだバージョンはどのバージョンか」を集合の形で抽出し、それをReads-From関係と呼ぶ。なお初期状態はTx0という特殊なトランザクションがすべて書き込んだ物として扱う。 ↑の
次のような実行スケジュールを考える。T1がxを読んだらコミット前にT2がやってきてxの値を書き換えてしまった。 このトランザクションの挙動は S2PLであればT1がxを読んだ時点でロックされるのでT2はロックが取れず停止する OCCであれば、T1がコミットしようとしてValidateする段階でAbortする というように、通常であれば走りえない。しかし、このT1の実行はT2がコミットした後であってもコミットできてもT1→T2の順に動作が完了したという形にSerializeできるので、本当はAbortする必要がない。つまりこの実行はSerializableだがCSRの外にある実行スケジュールという事になる。 1983年のTODSのPhilip A. BernsteinらによるMultiversion concurrency control-theory and algorithmsでは、この
DB上のページは「Atomicな複数更新」かつ「コミット時に全ページをForce」かつ「No-Steal」という、設計上の非常に遅い選択肢を選ばない限り、プロセス・OS・電源の障害からの復旧は基本的に一貫性が無い状態がスタート時点になる前提が必要である。 一貫性のないDBのページを復旧するためにログを残しており、一貫性のないページとログからDBの一貫性を取り戻す作業をリカバリと呼ぶ。 どのようなリカバリが必要とされるかはDB側のページ一貫性設計に大きく依存する。 基本的な戦略としては、DBのACID特性を維持するために「すべてのトランザクションをALL or Nothingに倒す」「ユーザに完了を報告した可能性のあるトランザクションはすべてALL側へ倒す」というのが前提となる。(CやIに関してはログを生成した時点で解決していると言える) 前述したようにStealのあるDBでは未コミットなペ
直交するStealとForceの軸 ディスクの一部を適宜メモリに写し取って編集するページモデルのデータベースの設計上の選択肢として、StealとForceの2軸がある。 トランザクション側の都合で任意のページをメモリから追い出せるシステムの場合、それを「Steal」と呼ぶ。(任意といっても流石にWALのルールに違反はできないが) それはつまり、トランザクションが認知しないタイミングでも任意のページが他のトランザクションの手によってメモリから追い出される事を意味するので、書き換わった(ダーティな)ページが未コミットのまま永続化される可能性がある。なのでリカバリ時にそのための配慮(Undo操作)が必要となり複雑度が増す。トランザクションからすると自分が触っているページが「盗まれる」のでStealと呼ぶのだろうと思う。 Stealを許さないシステムの場合(No-Stealと呼ぶ)トランザクション
前回のまとめ VSRを定義したけれどまだ実用性が足りない。 Conflict Equivalence スケジュールに対して以下の条件で集合confを定義する 2つのトランザクション中の操作が同一の値に触れ、少なくともどちらかがWriteである場合に競合と呼ぶ スケジュールの中で競合している操作a,bについて操作a→操作bの順に触った場合にそれをa→bの競合関係と呼び、{a, b}と表記する すべての競合に対してそれを行いすべての競合関係の集合をconfとする 2つのスケジュールについてそれぞれのconfが一致する場合にConflict Equivalent(以下競合等価)と呼ぶ。 文章で読んでもピンとこないので、とあるスケジュール図Aを例に描いてみると例えばこのようになる。 並行して実行されたTx1, Tx2の2つのトランザクションについて、同一の値に対して読み書きした操作のペア(競合関係
コード生成とかしてる時に _ で要素を繋いだ snake_case から、大文字小文字の組み合わせで単語の繋ぎ目を表現する CamelCase へ変換する必要に駆られる事があります。 Rails使ってればActiveRecordがなんとかしてくれるのですが、RailsばかりがRubyではありません。 書けば済む話ですが、ググってもそのものズバリのスニペットが見当たらなかったのでおいておきます。 class String def to_camel() self.split("_").map{|w| w[0] = w[0].upcase; w}.join end end
初めに パーサを書いてSQLなりC言語なりから文脈を抽出したいことが良くあります。 伝統的な方法としてはflexなりyaccなりのツールを組み合わせてアレコレするんですが、yacc以外の方法として treetop というライブラリが提案されています。 BNFとはちょっと違うPEGという文法規則を入力することでパーサを生成してくれるツールです。 BNFが | 記号で「AもしくはB」を記述したのに対し、PEGは / 記号で「Aを試してダメだった場合に限りBを試す」を表現するので、文法解釈時に候補の絞り込みが高速なことが利点らしいですが詳しい証明は知りません。 インストール $ tt Treetop Parsing Expression Grammar (PEG) Comand Line Compiler Usage: tt [options] grammar_file[.treetop|.tt
posted articles:トランザクション:34%ポエム:32%Python:13%C++:8%Ruby:6%
TL;DR; Amazon AuroraはIn-Memory DBでもなくDisk-Oriented DBでもなく、In-KVS DBとでも呼ぶべき新地平に立っている。 その斬新さたるやマスターのメインメモリはキャッシュでありながらWrite-BackでもなくWrite-Throughでもないという驚天動地。 ついでに従来のチェックポイント処理も不要になったのでスループットも向上した。 詳細が気になる人はこの記事をチェキ! Amazon AuroraはAWSの中で利用可能なマネージド(=運用をAWSが面倒見てくれる)なデータベースサービス。 ユーザーからはただのMySQL、もしくはPostgreSQLとして扱う事ができるのでそれらに依存する既存のアプリケーション資産をそのまま利用する事ができて、落ちたら再起動したりセキュリティパッチをダウンタイムなしで(!?)適用したりなどなどセールストー
TL;DR; Eventual Consistencyとか言いながらどうせもっとまともな一貫性実装してることはよくあるんだからみんな適切な名前を使おうぜ。 なぜこの記事を書くのか NoSQLの文脈においてスケーラビリティとのトレードオフでEventual Consistencyという用語は結構な頻度で出てくる。 ACIDに対抗してBASE(Basicaly Avalilable, Soft state, Eventual consistency)なんて言葉が出てきたり、CAP定理の中のAとPだと言ってみたり、分散システムのスケーラビリティを高めるために人類は一貫性を諦めることに余念がない。 その一方で、諦められた一貫性に関しては雑な分類論で語られる事が多く実はもっと適切な言葉があるのに「Eventual Consistencyです」なんて言われる事が良くある。そこで、この記事では過去に並行
Paxosとは何か 分散システムの金字塔とも呼ばれ、Leslie Lamport大先生の輝かしい成果の一つとして知られる分散合意アルゴリズムPaxos。 既存の解説 実はすでに存在するPaxosの解説は充分に質が高い Wikipediaの項目にも結構長々と書かれていて、これを読んで理解できた人はもう僕の記事を読む必要はない。 同様にPFIの久保田さんによる解説スライドもあり、これも良く書けているし、これを読んで理解できた人もこれ以上記事を読む必要はない。 minghai氏によるブログ記事のこれとか特にこっちなんかはかなり納得感があり、これらを読んで理解できた人も(中略) tyonekura氏によるスライドも良くかけていて(中略) この記事はこれらの説明に目を通してもなお理解できなかった人、もしくはこれらの説明をこれから読もうと思っている人に向けて書き、Paxosアルゴリズムの詳細な説明自体
データベース内のデータはページ単位でHDD内に配置され、ページ単位でメモリにバッファ及びキャッシュとして複製される。 HDD内のデータにアクセスする際は一旦メモリにページごと複製してからアクセスするわけだが、メモリ内におけるページの量は一般にHDDに置けるページ量より小さい(そうでない前提での話題はまた後日)。 LRU どのページをメモリに写し、どのページをHDDに置くかというのは、基本的にディスクアクセスの量を最小化する方向に最適化をする。 その際にはLeast Recently Used(LRU)という方法でキャッシュを管理する事が常套手段である。 それは「一番最近からみて使われた頻度が一番少ないページを解放して、そのメモリ領域を新たなディスクページの為に使いまわす」という戦略である。 具体的な実装方法としては双方向線形リストを使う。 新たにページをメモリに複製した際、双方向線形リスト
中身が空っぽだったら待つだけのベーシックな並行キュー。 conditionを正しく使う為に毎回conditionの使い方ググるのが面倒くさいのでここに置いておく。 #ifndef BLOCKING_QUEUE_HPP_ #define BLOCKING_QUEUE_HPP_ #include <boost/thread.hpp> #include <queue> template <typename T> class blocking_queue { public: blocking_queue() {} void enqueue(const T& item) { { boost::mutex::scoped_lock lk(lk_); const bool was_empty = queue_.empty(); queue_.push(item); if (was_empty) { em
gitの仕様が変わったためか、ぐぐって出てくる情報だとたまに古いのか新しいのか分からないのでgit 1.7.2.5で動いた情報を共有。 新しくコミットしたものの、あるファイルだけ特定の古いコミットの物で上書きしたくなるときがあります。 動かなかったやり方
コミットまでロックを獲得せずに実行する方式の並行制御方式。 まず、更新のたびにバージョン番号が増加する複数のデータを読む際、読んだデータのバージョン番号とデータのペアで手元で保持しておけば、再度読んだ時にバージョン番号の変動を確認すれば値が書き換わっていないかを検出できる。 この図の中の緑色の領域の中で値が変わっていない事をバージョン番号から保証できる。 これは対象となるデータがいくつに増えても同様である。 こうすれば複数の値を論理的に一瞬で読めた事になる。これを一般にスナップショット読み出しと言う。 これに2PLを組み合わせる事で、トランザクション中で読み書きする値に一切ロックをかけずにコミット時のバージョン比較で代用できることになる。 Optimistic Concurrency Control(OCC)はこの考え方を拡張したもので、トランザクション実行中は 値を読み出す時はバージョン
最近はCIといえばConcourseとかが流行っていますがJenkinsもpipelineがデフォルトで入るようになって昔とは変わってきました。 昔は「GUIついてるだけのcron」とか「結局Jenkins内のshellスクリプトが秘伝のタレになる」とか言われていました。 今はJenkinsfileというスクリプト(GroovyによるDSL)をプロジェクトのルートに置いておけばそこに対する手順の更新もgit等のvcsからバージョン管理できます。 更にはJenkinsfileの中で適切な記述をすることで操作を並列化できるのでビルド時間の短縮もできます。 そしてビルドの様子が(プラグインを設定すれば)いい感じに可視化されるので使っていて楽しいです。 簡単な使い方に関してはこのスライドとかこのスライドとかを見てもらうとして、この記事では実際に使い込んでみて僕がハマった内容と対策を共有します。 p
TL;DR; std::vectorのinsert()やerase()はイテレータを返すし、連続してそのvectorに操作する場合そのイテレータを戻り値で受け取らないのはバグの温床になりがちなので気をつけましょう。 初めに std::vectorは適切に使えば配列のサイズやらリサイズやらを意識の外に追いやれるので大変便利です。 vector.insert(iter, value) を使うと、iterが指す場所に新たにvalueを挿入し、その後ろの値をいい感じにずらしてくれます。 vector.erase(iter) を使うと iterが指している場所の値を消去し、配列のその後ろの値をずらして隙間を埋めてくれます。 どっちも手動で実装すると下らないミスをしがちなのでvectorのメソッドを頼りましょう。 insertもeraseも、操作をした瞬間に使用したiteratorが指す場所は不定にな
ACIDの中でIsolationは特に蔑ろにされがち、と昨日の記事に書いたが具体的にどのように蔑ろにされるかについて詳しく説明する。 ANSI規格 米国国家規格協会、いわゆるANSIではトランザクションの分離レベルが4つ定められている。 READ UNCOMMITTED: 未コミットの値を読む事がある(Dirty Read Anomaly) READ COMMITTED: コミット済みの値しか読まないが、1つのトランザクションの中で複数回同じ値を読みにいった時に外のトランザクションによって更新された最新の値を読んでしまって一致しない事がある(Non-Repeatable Read Anomaly)。また、読んだ値に後から書き込む際に他のトランザクションによって更新された値であっても更にその上から上書きしてしまい過去の更新が消失する(Lost Update Anomaly)。また、2つの値を
CheckIO というプログラミングサイトで2年以上前にPythonで書いたコードが久々に見返したらリファクタリングの提案がされてて少し感動したので解説を兼ねて共有する。 問題の回答とそこから伸びているスレッドは問題を解いた人にしか見えないらしいのでここにコピーする。以下の引用は全てこの問題やスレッドが出典である。 問題 0と1の二次元配列で迷路を渡すので、その迷路の (1, 1) の座標から初めて(10, 10) まで辿り着く経路を N,S, E, Wからなる文字列で返却せよ。 0は床、1は壁を表す。Nは上、Sは下、Eは右、Wは左を表す。およそこの図が全てである。経路は複数ありうるが最終的にゴールにたどり着ける経路を1つ返却すればよい。 僕の(いまいちな)回答 とにかくタイピングしたくなかったので回答を短く収めた。 def checkio(data): result = [] dirs
In-Memory DBのアーキテクチャは数多く提案されてきたが、特にパフォーマンスに直結するトランザクション周りでのボトルネック改善は需要の高い研究領域である。 これから紹介するStephen TuらのSOSP'13は大きなメモリと多くのCPUコアを活用してより高い性能を発揮するために考案された新しいトランザクションアルゴリズム:Siloを提案している。 In-Memory DBの問題点 昨日書いたように、In-Memory DBではページ単位でのバッファプールの管理やWALやUndoログが不要となり、トランザクション内でページを書き換えるたびにLog Sequence Numberを生成する必要はなくなった。 コミット時にリカバリに足る分のRedoログが記録できればよいのだが、そのRedo処理を行うためにはログをどの順序で実行すべきかを決定する指標が必要となる。逆に言えば、どの順序でロ
前回のまとめ FSRという基準を導入したが実用性がイマイチなので別の基準を考える。 View Equivalency さて、最後の状態が一致するかどうかでスケジュールの等価性をテストすると不都合が起きてしまうので、それにさらに制約を加えて行く。2つのスケジュール図の最後の状態の一致のみを見てはダメなので、2つのスケジュール図のトランザクションのすべてのステップでのエルブランセマンティクスが一致した場合に満たされるのがView Equivalency(ビュー等価)である。 もちろん最後の状態も「すべてのステップ」のうちの1つなのでView Equivalencyを満たす場合Final State Equivalencyも確実に満たす。また、トランザクションを直列に逐次実行したスケジュールとView Equivalencyが満たされる場合、そのトランザクションは View Serializab
次のページ
このページを最初にブックマークしてみませんか?
『@kumagiのマイページ - Qiita』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く