Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
DBMS自作によるトランザクション処理の学習
Search
Yutaro Oguri
March 26, 2024
Programming
1
270
DBMS自作によるトランザクション処理の学習
Yutaro Oguri
March 26, 2024
Tweet
Share
More Decks by Yutaro Oguri
See All by Yutaro Oguri
gokartの分散並列化ライブラリkannonの紹介 @【Sansan×エムスリー】gokartで爆速開発!MLOps勉強会
yutarooguri
0
3.9k
MLパイプラインをk8sで並列分散化するOSS "kannon"の開発
yutarooguri
1
460
デバッガを自作してみよう (M3 tech talk)
yutarooguri
1
500
Other Decks in Programming
See All in Programming
イベントストーミング図からコードへの変換手順 / Procedure for Converting Event Storming Diagrams to Code
nrslib
2
1.1k
#QiitaBash MCPのセキュリティ
ryosukedtomita
1
1.5k
DMMを支える決済基盤の技術的負債にどう立ち向かうか / Addressing Technical Debt in Payment Infrastructure
yoshiyoshifujii
3
410
The Modern View Layer Rails Deserves: A Vision For 2025 And Beyond @ RailsConf 2025, Philadelphia, PA
marcoroth
2
730
Model Pollution
hschwentner
1
160
「App Intent」よくわからんけどすごい!
rinngo0302
1
100
GPUを計算資源として使おう!
primenumber
1
250
オンコール⼊⾨〜ページャーが鳴る前に、あなたが備えられること〜 / Before The Pager Rings
yktakaha4
2
990
チームのテスト力を総合的に鍛えて品質、スピード、レジリエンスを共立させる/Testing approach that improves quality, speed, and resilience
goyoki
5
1.1k
テスターからテストエンジニアへ ~新米テストエンジニアが歩んだ9ヶ月振り返り~
non0113
2
220
The Niche of CDK Grant オブジェクトって何者?/the-niche-of-cdk-what-isgrant-object
hassaku63
1
610
はじめてのWeb API体験 ー 飲食店検索アプリを作ろうー
akinko_0915
0
140
Featured
See All Featured
Mobile First: as difficult as doing things right
swwweet
223
9.7k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.6k
BBQ
matthewcrist
89
9.7k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
282
13k
Why Our Code Smells
bkeepers
PRO
337
57k
Facilitating Awesome Meetings
lara
54
6.5k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
108
19k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Writing Fast Ruby
sferik
628
62k
How to Think Like a Performance Engineer
csswizardry
25
1.7k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
830
Transcript
DBMSࣗ࡞ʹΑΔ τϥϯβΫγϣϯॲཧͷֶश খ܀༔ଠ 1
自己紹介 • 小栗 悠太郎 (Yutaro Oguri) • 東京大学 工学部 電子情報工学科
B4 • GitHub: maronuu • 研究: Approximate Nearest Neighbor Search (ベクトル検索) • 興味: 検索, DBMS, データ基盤, k8s, … 2
概要 • ラボユース: 2023/10〜活動開始 • ”Database Design and Implementation”という本を ベースにDBMSについて学びながらC++で自作
• トランザクション処理に注目 • 展望: ベクトル検索拡張機能の追加 3
DBMSの全体像 • File Manager ◦ ファイルI/O • Log Manager ◦
Logの書き込み • Buffer Manager ◦ Buffer pool (on RAM) • Recovery Manager ◦ Logを元に復元 • Concurrency Manager ◦ 並行制御 4
DBMSの全体像 • File Manager ◦ ファイルI/O • Log Manager ◦
Logの書き込み • Buffer Manager ◦ Buffer pool (on RAM) • Recovery Manager ◦ Logを元に復元 • Concurrency Manager ◦ 並行制御 5 実装したい部分
トランザクション • 1つ以上の処理をまとめた操作の単位 • 例: 2人のユーザが同一データに対して write / readをする場合 •
インタフェース ◦ Read(x), Write(x, val) ◦ Abort(), Commit() • 適切に Lock を取るなどして対処 • lockをとる対象 ◦ Block, value, file, … 6 Image is from https://qiita.com/kumagi/items/5262ff4551ba19943b70
自作DBMSにおけるLockプロトコル • Lockをとる対象: block ◦ tx.pin(block) • 2PLプロトコル ◦ Readする直前に、対象Blockに対してshared
lock (read lock) をとる ◦ Writeする直前に、対象Blockに対してexclusive lock (write lock) をとる ◦ Commit / Rollback後に全てのlockを解放する 7
現状 • File Manager ◦ ファイルI/O • Log Manager ◦
Logの書き込み • Buffer Manager ◦ Buffer pool (on RAM) • Recovery Manager ◦ Logを元に復元 • Concurrency Manager ◦ 並行制御 8 クエリ言語を介する File / Log / Buffer までは実装済み
今後の展望: ベクトル検索拡張機能 • ベクトル検索とは? ◦ ベクトルの集合から最もクエリベクトルに近いベクトルを探す ◦ 深層学習モデルによる埋め込みベクトルの活用 • 例)
sqlite-vss ◦ SQLiteでベクトル検索を可能にする拡張機能 ◦ SELECT papers.*, vss_papers.distance FROM vss_papers JOIN papers ON vss_papers.rowid = papers.id WHERE vss_search(vss_papers.summary_embedding, vss_search_params(?, 10)) 9
今後の展望: ベクトル検索拡張機能 必要となる変更 • ベクトル形式の レコードのサポート • 並行制御をどうする? ◦ ベクトル検索では
Readが圧倒的 ◦ とりあえずなし? 10