サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
TGS2024
qiita.com/kumagi
この記事はpyspaアドベントカレンダー2021の三日目です。前日の記事はykubotaさんです。 はじめに 「自分には才能がある!」と信じてこの業界に踏み込んだものの右も左も怪物だらけで形見が狭い思いをしているのは僕だけではない。 憧れるのは異世界転生のような俺TUEEEE展開であり「何ってクイックソートをしただけだが?」とか言ってたら地位と名声が向こうから転がり込んできて欲しい。 しかし世の中そんなに甘くなく、標準ライブラリを使って威張れるのは学生ぐらいのものである。 学生?そうだ!学生の頃から精進しまくっていたら今ごろすごいソフトウェアエンジニアになれていたはずなんだ!という後悔を抱えて生きている社会人が世の中にはいっぱいいる。 そんな立場から若者を見ていると「大学に入ってプログラミングを始めました」という大学生を見かけるたびにアドバイスをしたくなる衝動に駆られるが、毎度同じような事
次のような実行スケジュールを考える。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では、この
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)という方法でキャッシュを管理する事が常套手段である。 それは「一番最近からみて使われた頻度が一番少ないページを解放して、そのメモリ領域を新たなディスクページの為に使いまわす」という戦略である。 具体的な実装方法としては双方向線形リストを使う。 新たにページをメモリに複製した際、双方向線形リスト
コミットまでロックを獲得せずに実行する方式の並行制御方式。 まず、更新のたびにバージョン番号が増加する複数のデータを読む際、読んだデータのバージョン番号とデータのペアで手元で保持しておけば、再度読んだ時にバージョン番号の変動を確認すれば値が書き換わっていないかを検出できる。 この図の中の緑色の領域の中で値が変わっていない事をバージョン番号から保証できる。 これは対象となるデータがいくつに増えても同様である。 こうすれば複数の値を論理的に一瞬で読めた事になる。これを一般にスナップショット読み出しと言う。 これに2PLを組み合わせる事で、トランザクション中で読み書きする値に一切ロックをかけずにコミット時のバージョン比較で代用できることになる。 Optimistic Concurrency Control(OCC)はこの考え方を拡張したもので、トランザクション実行中は 値を読み出す時はバージョン
最近はCIといえばConcourseとかが流行っていますがJenkinsもpipelineがデフォルトで入るようになって昔とは変わってきました。 昔は「GUIついてるだけのcron」とか「結局Jenkins内のshellスクリプトが秘伝のタレになる」とか言われていました。 今はJenkinsfileというスクリプト(GroovyによるDSL)をプロジェクトのルートに置いておけばそこに対する手順の更新もgit等のvcsからバージョン管理できます。 更にはJenkinsfileの中で適切な記述をすることで操作を並列化できるのでビルド時間の短縮もできます。 そしてビルドの様子が(プラグインを設定すれば)いい感じに可視化されるので使っていて楽しいです。 簡単な使い方に関してはこのスライドとかこのスライドとかを見てもらうとして、この記事では実際に使い込んでみて僕がハマった内容と対策を共有します。 p
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
これまで多くのトランザクションの要素技術を説明してきた。 Googleの公開している論文Spanner: Google's Globally-Distributed Database は公開当初、要求される専門技術の多さからよくわからないと言っている人が多かったが、これまでに説明した要素技術をベースにすると理解しやすい。 Spannerとは 複数のデータセンターに跨ってデータベースの内容を複製し続ける事で高い可用性を実現するという構想は数多くあった。 しかしそれらの分散データベースは実用的な速度を実現しようとすると、データモデルがただのRDBより単純化して使いにくかったりトランザクションをサポートしなかったりと、アプリケーションの一貫性を実現するのが難しい。 現にGoogleの社内でもBigtableなどを用いたアプリケーションは複数あるものの、それぞれでそのデータモデルの上で無理やりトラ
ARIESとは、WALでページ更新しつつNo-forceかつStealな特性を持ち、Fuzzyなチェックポイントを獲得するという、Disk-Orientedな伝統的データベースでのベストプラクティスを集めた技法である。IBMのFellowであるDr. C.Mohanらによる"ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging"という論文が原著のようだ。 IBMのDB2やMircosoftのSQL Serverにて採用されている、とWikipediaには書いてあるが現状の製品の中では様々な改造が加えられて原型を留めてないかも知れない。現にSQL Serverのアーキテクチャはhekatonなどのインメモリ
近年のデータベースはよく「最新のインメモリ技術を採用して高速化」などという宣伝が出回っている。 参考: 既存の概念を覆す!Oracle Database In-Memoryのテクノロジー Vol.1 参考: SQL Server 2016の概要とIn-Memory OLTP の改善点(前編) 従来のデータベースだって世の中のほぼすべてのソフトウェアも最終的には(キャッシュ)メモリの中で計算処理をしているわけで、何をもってして「インメモリ技術」と呼ぶのか誤解を招いているケースが身の回りで多発していた。 ディスクDBの時代 昔、例えばOracleV2が発売した1979年では、NECからPC-8001が発売され、市販されるコンピュータのメモリは64KBとか48KBほどだった。エンタープライズ製品であればMB級のものもあるだろうとは思うがお値段も相当のものだった。 会社の業務を回すにあたって、全デ
昨日様々なトランザクション分離レベルに付いて書いた。 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
トランザクションのACID特性とはいうものの、これまではIsolationに関わる話しかしてこなかった。 しかしDurability(記録したデータが永続化される)という特性はDBを使う上で魅力的であり欠かすことができないものである。 Strict Two Phase Lock 2PLというプロトコルは「ロックを使うときは成長相と縮退相の2フェーズで扱え」というルールだったが、このプロトコルに愚直に従うだけではDurabilityを達成することはできない。 そこで「縮退相より前にコミット(データの永続化)を行え」という追加ルールを加える事でDurabilityを達成できる。 この追加ルールが加わった2PLをStrict Two Phase Lock(S2PL)と言う。 この説明ではピンと来ないと思うので図で説明すると こんな感じに、縮退相が終わった後でディスクに永続化する場合、もちろんT1
2PLでもS2PLでもロックを獲得・開放する順序の話を規定しているだけで、そのままカジュアルに走らせると悲惨な問題に直面する。デッドロックである。 Tx1: Write(x) Write(y) Tx2: Write(y) Write(x) という2つのトランザクションは、2PLに沿ってロックを記述すると Tx1: Lock(x) Write(x) Lock(y) Write(y) Unlock(x) Unlock(y) Tx2: Lock(y) Write(y) Lock(x) Write(x) Unlock(y) Unlock(x) このようにLockがそれぞれ書き込みの前に追加される。 この二つのトランザクションが並行して走ると、無事にどちらも完走する場合もあるが、停止して動かなくなることもある。 Tx1: Lock(x) Write(x) Lock(y) Tx2: Lock(y) W
実行スケジュールを動的に作成したい Conflict Serializability(CSR)が担保される実行スケジュールはトランザクションの実装上好ましい性質を持っている。 そのCSRを動的に生成する方法の1つがTwo Phase Lock(2相ロックまたは2PL)である。 厳密にはCSRより更に狭い範囲のスケジュールしか許容しないが、詳細はリカバリなどの議論を含むため後日にする。 Two Phase Lockとは、成長相と縮退相の2相からなるロックプロトコルである。 ロックプロトコルとは、複数のロックを獲得・解放する際の取り決め(プロトコル)を規定する物であり、特定のロック実装には依存しない。 Two Phase Lockの規定するプロトコルは以下である。 成長相のあとに縮退相が来なくてはならない。 縮退相のあとに成長相が来る事は許可されていない。 成長相と縮退相はそれぞれ1つずつしか
本来はこの話はトランザクション技術アドベントカレンダー初日に書くべきだったかも知れない。 トランザクションとは「1つ以上の連続した操作の単位」であり、ACID特性を満たすとよく言われている。(というか先日も何度も何度も無意識にACIDという言葉を使っていた) ACIDとは ACID(えいしっど、もしくはあしっどと読む人も居るしどっちでもいいと思う)はWikipediaにも説明があるが、そこの説明は僕にはイマイチだと感じたので僕の言葉で今一度説明する。 Atomicity Consistency Isolation Durabilityの4つがトランザクションの満たすべき性質であると提唱されており、その4つの頭文字を取ってACIDと呼ぶ。それぞれの性質の内容に付いて書くと Atomicityとは トランザクションが残す結果が、すべてのトランザクション内操作が成功したか、もしくはすべて無かった
データベースの歴史は古い。 データベースの黎明期ではメモリの価格は今とは桁違いで、1バイトあたり1円を切るかとかそういうレベルの世界だった。1バイトが1円ということは1MBのメモリが100万円以上するという事である。 また、単純にメモリのサイズも小さく、ハイエンドのメモリフレームでRAMを8MB積んでいるとかそんな世界であった。ちょっと大きな事をやろうとすると8MBを溢れる事は当然想定しなくてはならない。 HDDのランダムIOは非常に遅い。なので1バイト単位でデータを書き換えるよりはメモリで可能な限り書き換えをバッファして、ある程度の大きさでまとめて書き込みを行う事で高速化できる。 PostgreSQLではデータベースの内容をページという(デフォルトでは)8KByteの大きさに切り分けて管理している。 1ページの中にテーブルの中の数行分のデータを入れる事でRDBMSはリレーションを保存して
グループコミットによってトランザクションのスループットを大幅に引き上げる技法について昨日の記事で書いたが、この技法ではロック期間は結局ディスクのヘッドシークの長さになる。 むしろロガーとのコミュニケーションコストやログ待ちの時間を考えると個々のロック保持期間は微妙に長くなってさえいる。 また、各スレッドはロガーによって永続化されるまでトランザクションの完了を待たなくてはならないので、1回のログ操作に詰め込めるトランザクション数はスレッドの数が上限になる。 つまりスループットを上げる為にはより多くのスレッドを並列して動かす必要がある。 更には、ロガーのバッファにトランザクションログを送付する際にも、ロックが衝突する可能性もある。複数のワーカーが同時にロガーにログを送付しようとするとそこもボトルネックになりうる。 そこで提案されているのがAetherである。読みはおそらく「エーテル」で、ファイ
市販されているハードディスクは大半が7200rpmである。 これは毎分7200回転、つまり毎秒120回転する事を意味しており、ハードディスクのヘッドを目的の場所に合わせるランダムアクセスに1/120秒ほど掛かる見込みがあるとも言える。実際HDDのカタログスペックを見てもヘッドシークは10ms程度掛かると見て間違いない。 ざっくり言うと普通のハードディスクは1秒に120箇所以上に書き込む事はできない。(探せば15000rpmのハードディスクもあるけれど倍速くなるわけでもなさそう) ログを書くという事 毎秒120箇所を書き換えれないのに1つのトランザクションが120箇所を更新する内容をすべてそのままディスク上のデータに反映させていたら毎秒1トランザクションしか走らない。それではパフォーマンスが致命的に落ちるので、データベースは可能な限りHDDのヘッドシークを減らす方向に進化してきた。それがログ
Serializablitiyとは? 1. Final State Serializabilityについてポエムトランザクション Serializableとは何か 複数のトランザクションの実行スケジュールが渡された時、その挙動について論じる際の基準の1つがSerializabilityである。と、単純に一言で片付けば良いのだけれど実際にはこの中にも複数の階層と紆余曲折がある。それらについて追っていく。 Final State Equivalency さて、Writeする値はそのトランザクションがそれまでにReadしてきた値から算出された値なので、Write操作は「そこまでのReadを引数に取る多引数関数」と見なす事ができる。説明上、トランザクションの数字と関数に付ける識別子を揃えて表記する。例えばTx1が実行する操作を多引数関数で表す時はF1を用いる。そしてReadは「その前に行われたWr
イントロダクション これは@kumagiが一人でトランザクション技術に関する話をまとめていくアドベントカレンダーである。 トランザクション技術は多岐にわたり、複雑に絡み合い、DBの中で巨大な密結合コンポーネントを生み出している。そのためその中身を語るアドベントカレンダーも完全に順序付けて章立てしていくのは難しい。そのため様々な側面から一日に読めそうな文量の記事毎にまとめてアドベントカレンダーとするので、25日も話題が持つのかはさておき必ずしも記事の区切りは技術としての区切りの良さとは関係がない。 しかも初めの数日はトランザクションが実現する並行制御の理論的側面についての整理を淡々と述べるので退屈になること請け合いだけれど、可能な限り図解しながら説明を尽くすのでわからない所は容赦なくはてブやTwitterなどで書いて貰えたら適宜加筆修正をするつもり。 アドベントカレンダーを書くにあたって参考
こんな感じでdockerグループにユーザを追加することで、dockerコマンドをsudoなしで使えるようにできる。 しかしそれでは動かないという症状に見舞われる事がある。 $ docker ps Cannot connect to the Docker daemon. Is the docker daemon running on this host? $ sudo !! ←こう打つ事で直前のコマンドをsudo付きで再実行できる。 Cannot connect to the Docker daemon. Is the docker daemon running on this host?
背景 リアルタイムにmarkdownをプレビューできてGoogle Docsのようにリアルタイムに共同作業できるHackMDが便利なので特定多数しかアクセス出来ない環境に作りたくなった。 Basic認証を掛ければ当面は大丈夫そうだがHackMDにはどうやらその機能がない。 しかし外からアクセスできてサブドメイン無制限なSSL証明書のある環境を持ってないので、SSL設定済みのnginxの下にlocationを掘ってプロキシさせて走らせる事にした。 めんどくさがらずにサブドメイン用の証明書作って解決してもいいのだろうけれど今回は勉強も兼ねている。 HackMDそのものはDocker-Composeがあるので、Dockerが既に入っている環境なら $ git clone git@github.com:hackmdio/docker-hackmd $ pip install docker-comp
次のページ
このページを最初にブックマークしてみませんか?
『@kumagiのマイページ - Qiita』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く