タグ

ブックマーク / kumagi.hatenablog.com (6)

  • 世紀末LSM-Treeプチフリ神話の終わり - Software Transactional Memo

    凍った木が溶け始める様子をそれっぽく描いてもらった この記事はデータベース・システム系 Advent Calendar 2023の2日目の記事である。前日は僕、明日も僕。 Log Structured Merge Tree(以下LSM-Tree)という物をご存知だろうか。データ構造としては順序付きの辞書であり結構昔に発明されており各操作の計算オーダーは赤黒木等と同じである。システム系学会を追っていると無限に亜種が提案されているので特徴を一言で言い表すのは難しいのだが、その一種であるLevelDBChromiumの中でも使われている。 https://chromium.googlesource.com/chromium/src/+/HEAD/third_party/leveldatabase/leveldb_chrome.h LSM-Treeの典型的な実装の概要とその利点・欠点を整理すると

    世紀末LSM-Treeプチフリ神話の終わり - Software Transactional Memo
    nurse
    nurse 2023/12/02
  • ストレージとコンフィグでデータベースのグリッチを探す - Software Transactional Memo

    AIに描いてもらったストレージで作ったレース会場 はじめに この記事はデータベース・システム系 Advent Calendar 2023の一日目の投稿である。今年読んだ論文(今年書かれた論文とは限らない)の中で驚きや納得があって良かったなぁと思った論文をいくつか紹介していきたいと思う。 論文の文そのものは機械翻訳なりチャットAIなりに叩き込めば誰でも内容の抽出はできるので、こちらのブログ内では何故これが良いと思ったかについて僕の主観に基づいて書いていく。僕の解釈が厳密に正しいことは一切保障しないし、気になって読んでみたら全然内容違うやんけ!と驚くところまでがセットくらいの気軽なつもりで読んで欲しい。 最初に紹介する論文は「When Database Meets New Storage Devices: Understanding and Exposing Performance Mism

    ストレージとコンフィグでデータベースのグリッチを探す - Software Transactional Memo
    nurse
    nurse 2023/12/01
  • 分散プログラミングモデルおよびデザインパターンの考察 その4 - Software Transactional Memo

    引き続き分散システムのデザインパターンの話をしていく。例によって適切な名前を見つけられなかった場合にはその場で適当に名づけているので、ここに書いてある名称が技術レベルでの正式名称だとは思わず、正式名称を見つけたらそっとコメント欄で教えてください。 Application Level Ack リクエストを受け取った際にAcknowledgment(Ack) を返却するのは重要であるというのは異論の余地はない。だが、どのレベルで返却すべきかというのはデザインスペースの一部である。 ご存知の通り、TCPはそもそもSYN → SYN-ACK →ACKの3方向ハンドシェイクを行い、それぞれの通信ペイロードにシーケンス番号を付けて送達を確認している。SO_LINGERを使えばclose時に未送信パケットが残っていればそれを送り終わるまでclose()をブロッキングする事もできる。TCPのトランスポート

    nurse
    nurse 2022/10/27
  • 6年勤めたNTTを退職しました - Software Transactional Memo

    最終退社時の自分の机 2012年に修士卒からの新卒でNTT研究所に入り、6年間お世話になりました。 研究所では同期や先輩や後輩や上司に恵まれ、存分に書籍や論文を読んで勉強して力を蓄えたり、対外的な発表の場にも恵まれ外ではできないような体験をすることができました。 ありがとうございました。 入社当時に作られたtogetterを見返すと togetter.com togetter.com まるで昨日のように感じられる。 NTT社内で僕が何をやっていたかについては言える物は軒並みアウトプットされているのでわざわざここでは触れない。 NTT研究所について NTT研究所を客観的に見た時にどうかを書いていく とにかく人に恵まれている。採用の倍率が高いのもあって潤沢な学生エントリーからよりすぐりのエリートが謎の力でポテンシャルを見極められて採用されている。同期を見てひと目ですごい奴も居れば、一見してわか

    6年勤めたNTTを退職しました - Software Transactional Memo
    nurse
    nurse 2018/11/26
  • 分散キューという名の苦しみ - Software Transactional Memo

    TL;DR 分散システムにおいてキューを導入する場合、当にキューが必要なのか再考すべき。そこが地獄の入り口だから。 システムの抽象 コンピュータの世界は、来は0と1の信号の羅列が飛び交う無機質なものである。でも人類は信号だけですべてを語らず、様々な喩えを定義してきた。それはデスクトップ・ウィンドウ・マウスカーソルといったグラフィカルな表現に留まらず、パケットやカプセル化といった用語にロック・キュー・リスト・木などのアルゴリズムやデータ構造の世界にも自然に溶け込んでいる。これらはすべて人間の理解を助けるための喩え話に過ぎず、この喩えこそが人間のより直感的な理解をもたらす一方で、発想の制約を生み出してきた。 人間が大きなシステムを作るときも何らかの喩えを用いてシステム全体を整理する。アーキテクチャの「ポンチ絵」を描いて情報共有をするのは企業に勤めていれば経験した人も多いだろう。パワーポイン

    分散キューという名の苦しみ - Software Transactional Memo
    nurse
    nurse 2018/06/18
  • HTMはメモリ管理の為に生まれてきたんだよ! ΩΩ<な、なんだってー - Software Transactional Memo

    HTMの第一人者にして、obstruction-freeやwait-freeなどの厳密な定義や、CAS命令の数学的な意義を証明し、The Art of Multiprocessor Programmingの著者で、ロックフリーでもSTMでも八面六臂の活躍をしているMaurice Herlihy先生が連名している最近の論文を流し読み。 Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev, Mark Moir: On the power of hardware transactional memory to simplify memory management. PODC 2011: 99-108 「トランザクショナルメモリのパワーでメモリ管理を簡略化する」という感じ。 GCを使わない環境下においてメモリ管理は鬼門になってて、そのせいでC++のロ

    HTMはメモリ管理の為に生まれてきたんだよ! ΩΩ<な、なんだってー - Software Transactional Memo
    nurse
    nurse 2013/06/11
  • 1