データ指向アプリケーションデザインを読んでLSM-treeインデックスに基づくKVSを作る - 油そば
この記事はMicroAd Advent Calendar 2019の4日目の記事です。 qiita.com はじめに どういうKVSを作るか 手始めにログベースのKVS 書き込み, 読み取り, 削除 ログフォーマットの決定 実装 LSM-treeインデックスを持つKVSを実装する 書き込み MemTableからSSTableの生成 SSTableの反映 SSTableのマージとコンパクション バッファを使ったマージ&コンパクション ステップ1. SSTable毎にキーを読み出す ステップ2. バッファ内の最小のキーの最新の値を読み出す 再起動時の復元 アクターで組み立てる 書き込みのケース 読み取りのケース コード はじめに データ指向アプリケーションデザインは今年買って読んだ技術書の中で最も読み応えがあった本でした。 www.oreilly.co.jp 単に周回で読むだけでも学びが多い本
論文メモ: Mison: A Fast JSON Parser for Data Analytics | κeenのHappy Hacκing Blog
L. Yinan, N. R. Katsipoulakis, B. Chandramouli, J. Goldstein, D. Kossmann. “Mison: A Fast JSON Parser for Data Analytics,” Proceedings of the VLDB Endowment, Volume 10 Issue 10, June 2017, p1118-1129. を読んだメモ。 本当にただのメモなので内容を知りたければ論文を読むように。 Apache Spark や Apache Drill などいわゆるビッグデータを処理するソフトウェアでJSONをパースするのに無視できないコストが掛かる。 特に、JSONにクエリを投げるのに一旦パースしてからクエリを処理するのにはかなり無駄が多い。Parquetなどのフォーマットもあるが、MisonはJSONのまま処理
Cache-Oblivious データ構造入門 @DSIRNLP#5 - iwiwiの日記
「データ構造と情報検索と言語処理勉強会」にお邪魔して，「Cache-Oblivious データ構造入門」という発表をさせてもらいました． 新年会 + データ構造と情報検索と言語処理勉強会 #DSIRNLP 5 - 参加者は何か発表してネ スペシャル - PARTAKE Cache-Oblivious データ構造入門 @DSIRNLP#5 from Takuya Akiba 実はこういうインターネットから集う感じのいわゆる勉強会に参加するのは初めてでした．発表も初めてなので結構緊張していて大変だったのですが，参加者の皆さんがとても優しくて助かりました．懇親会 (新年会) もとても楽しかったです．主催の overlast さん，会場を提供してくださっていたスマートニュースさん，どうもありがとうございました． 発表の内容は以下のような感じです． DB の索引としての B 木の利点の復習 Cach
RocksDBをさまざまな言語（C++, Rust, Kotlin, Python）で利用する - にほんごのれんしゅう
RocksDBをさまざまな言語（C++, Rust, Kotlin, Python）で利用する InstagramのCassandraのバックエンドをJVMベースのものから、RocksDBに切り替えたというニュースが少し話題になりました。 CassandraのJVMは定期的にガーベジコレクタが走って、よろしくないようです。 P99というテストケースではデフォルトのJVMからRocksDBに張り替えたところ10倍近くのパフォーマンスが得られたとのことです。 データ分析でもメモリ収まりきらないけど、Sparkのような分散システムを本格に用意する必要がない場合、NVMe上にLevelDB, RocksDBなどのKVSを用意して加工することがあります。 ローカルで動作させるには最強の速度だし、文句のつけようもない感じです。 LSMというデータ構造で動いており、比較対象としてよく現れるb-treeよ
SQLアンチパターン - ナイーブツリー
社内勉強会資料 追記: 2013-10-31 ついったで指摘( https://twitter.com/akuraru/status/395822183777202176 )を受けたので入れ子集合のノード追加の説明の所を修正しました。
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「階層型データベース」調べても基本概念以外ほとんど情報が出てこないです。製品名、解説サイト、使用している企業/システム、経験談等具体的な情報を教えてもらえませんか？ - Quora
Log Structured Merge Tree
計算量と僕とWeb開発 / computational complexity and I and Web
LLVMで遊ぶ（整数圧縮とか、x86向けの自動ベクトル化とか）
B TreeとML - 修行の場
ソーシャルゲームのためのデータベース設計