Rustで古典的なDisk-Oriented DBMSを実装した話 - Write and Run
KOBA789 です。みなさん DBMS は好きですか。私は好きです。 最近、自作 DBMS をずっと作っていて、ようやく最低限の機能ができたので公開をしました。 (とはいえコードを書いていたのは正味2日ほど。設計と勉強に2週間かかった) github.com この記事ではこれを作った目的と、そのちょっとした詳細についてご紹介します。 目的 Disk-Oriented DBMS の学習に適している Rust で書かれた実装が欲しかった、というのが理由です。 DBMS の勉強に適している実装というのは意外と多くありません。 MySQL や PostgreSQL といった有名な実装は実用的である一方でコード量は非常に多く、また細かな最適化によって教科書的なアルゴリズムと実際のコードの差が大きくなっているため、初学者にとっては構造を把握しづらくなっています。 教科書的な実装の Disk-Orie
VisuAlgo - データ構造とアルゴリズムを可視化する
VisuAlgo.net/en visualising data structures and algorithms through animation VisuAlgo is a trilingual site. Try visiting the other versions of VisuAlgo other than the default English version, e.g., Chinese or Indonesian. Users can see the translation statistics for these three pages. We aim to make all three has near 100% translation rate. Unfortunately the translation progress with other language
OpenDataStructures.jp
オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。 以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。 目次 訳者まえがき 本書の読み方 訳者謝辞 なぜこの本を書いたのか 謝辞 第1章 イントロダクション 効率の必要性 インターフェース 数学的背景 計算モデル 正しさ、時間計算量、空間計算量 コードサンプル データ構造の一覧 ディスカッションと練習問題 第2章 配列を使ったリスト ArrayStack：配列を使った高速なスタック操作 FastArrayStack：最適化された ArrayStack ArrayQueue：配列を使ったキュ
秒間100万リクエストをさばく - Googleの共通認可基盤 Zanzibar - 発明のための再発明
はじめに Googleの提供するサービス郡が共通して利用している認可システムにはZanzibarという名前がついています。ZanzibarはGoogleDrive・Google Map・Youtubeなどの巨大なサービスにも使用されています。 そのため、利用量も凄まじく 数10億のユーザー 数兆のACL(access control list) 秒間100万リクエスト もの量をさばいています。 にも関わらず、Zanzibarはこれを10ミリ秒以内に返します(95パーセンタイル)。 この記事では、そんなZanzibarの内部構造に関する論文「Zanzibar: Google’s Consistent, Global Authorization System」の中から、主に大量のリクエストをさばくための工夫を紹介します。 ちなみに、以前Googleの社内システム用の認可システム「Beyond
「量子理論の副産物に過ぎなかった」──東芝の「量子コンピュータより速いアルゴリズム」誕生秘話
「量子理論の副産物に過ぎなかった」──東芝の「量子コンピュータより速いアルゴリズム」誕生秘話：「量子コンピュータとは何か」を問う“新たな壁”（1/5 ページ） 今、量子コンピュータの一種である「量子アニーリングマシン」で高速に解けるとされる「組合せ最適化問題」をより速く・大規模に解くべく、各社がしのぎを削っている。 米Googleと米航空宇宙局（NASA）が2015年に「従来のコンピュータより1億倍速い」と評した量子アニーラ「D-Wave」を作るカナダD-Wave Systems、量子アニーリングを模したアルゴリズムをデジタル回路上に再現する富士通と日立、光を用いて解く「コヒーレント・イジングマシン」を作るNTTの研究グループなどだ。IBMなどが作る「量子ゲート方式」の量子コンピュータを用いた組合せ最適化計算の研究も盛んだ。 各社が組合せ最適化計算に取り組むのは、これを高速に解けると交通渋
Goptunaを使ったGo言語におけるベイズ最適化の活用 | Research Blog
はじめに 形状のわからない関数(ブラックボックス関数)の最大値あるいは最小値を求める手法として、ベイズ最適化が広く利用されています。機械学習モデルのハイパーパラメーター最適化を中心に活用が進んでいますが、入力とそれに対する評価値さえ設計できればあらゆる問題に適用できます。 例えばFacebookでは、MLモデルのチューニングはもちろん、映像コーデックのエンコードパラメーター 1、AR/VRハードウェア設計、HHVM JITコンパイラのパラメーターチューニングにベイズ最適化を適用するため BoTorch や Axの開発を進めています (F8 2019の発表 Product Optimization with Adaptive Experimentation を参照)。 弊社では多くのサーバーシステムでGo言語が採用されていますが、サーバーのgoroutine数やキャッシュシステムのメモリーバ
高速ハッシュアルゴリズム – YOSBITS
この記事は特に高速なハッシュアルゴリズムをまとめた資料です。 暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。 MurmurHash 2008年に”Austin Appleby”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。MurmurHash3 は現在のバージョンで、32ビットまたは128ビットのハッシュを生成する。MurmurHash2 は古いバージョンで、32ビットまたは64ビットのハッシュを生成する。64ビットのハッシュ値生成するソースには2つの変種がある。64ビットプロセッサ用に最適化された用の MurmurHash64A と32ビットプロセッサ用に最適化された Mu
GolangのGCを追う
Go1.5とGo1.6でGoのGCのレイテンシが大きく改善された．この変更について「ちゃんと」理解するため，アルゴリズムレベルでGoのGCについて追ってみた． まずGoのGCの現状をパフォーマンス（レイテンシ）の観点からまとめる．次に具体的なアルゴリズムについて，そして最後に実際の現場でのチューニングはどうすれば良いのかについて解説する． GoのGCの今 最初にGoのGCの最近の流れ（2016年5月まで）をまとめる． Go1.4までは単純なStop The World（STW）GCが実装されていたがGo1.5からは新たなGCアルゴリズムが導入された．導入の際に設定された数値目標は大きなヒープサイズにおいてもレイテンシを10ms以下に抑えることであった．Go1.5で新たなアルゴリムが実装されGo1.6で最適化が行われた． 以下は公開されているベンチマーク．まずはGo1.5を見る． Gophe
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
分散ロックという名の過ち - Software Transactional Memo
 TL;DR; 「分散ロック」が分散システムの設計図に登場した時 だいたいその設計は間違っていて本当に必要なものはトランザクションだ 並行システムを実装する際にロックを用いるのはとても自然なことだ。 僕も普段はロックフリー系のアルゴリズムに詳しいと言われがちだが知識量でいったら実はロック系の方が多く蓄えているかも知れない。 分散システムは並行システムであることが多いので、その中にロックが登場するのはとても自然な発想である。 よく「分散」「並行」「並列」の言葉の定義がごっちゃになっているケースがあり、この記事の主題にしたいわけではないので深くは言及しないが、分散システムは環境などの要因で突如として参加者が音信不通になったり復活したりする点で並行システムと大きく異なる。 並行システムと同じノリで分散システムを設計しようとした際に陥る頻出の過ちが「分散ロック」である。そのアイデアはとても簡単で
条件変数 Step-by-Step入門 - yohhoyの日記（別館）
多くのプログラミング言語では、マルチスレッド処理向け同期プリミティブとして「ミューテックス(mutex)」と「条件変数(condition variable)」を提供しています*1 *2。ミューテックスは排他制御機構として有名ですし、その動作もロック(lock)／アンロック(unlock)と比較的理解しやすいため、不適切に利用されるケースはあまり無いと思います*3。一方、条件変数の動作仕様はしばしば誤解され、不適切な利用による並行性バグに悩まされるケースが多いようです。 本記事では、スレッドセーフなFIFO(First-In-First-Out)キューを段階的に実装していく事例を通して、条件変数の適切な使い方について説明していきます。例示コードではC++11標準ライブラリを用いますが、Pthreads(POSIX Threads)やC11標準ライブラリへは単純に読み替え可能です（→Pthr
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道
大分たってしまったけど、ようやく時間が空いたので、db tech showcase Tokyo 2016 http://enterprisezine.jp/dbonline/detail/8466 で話した内容を記録的に書いておく。あとはSILOの解説を特に自分用に論文の4章を中心に整理しておく。あとはついでに自分の思うところも記す。 ・SILO 元論文はこちら、執筆陣はMITのLiskov一派とEddie Kohler 現在のDB研究の第一線のメンバー。 http://people.csail.mit.edu/stephentu/papers/silo.pdf SILO以降、大きくDBベースのアーキテクチャの考え方は変わりました。ほとんど全ての分散系OLTPはSILOを程度の大小はあるとはいえ、意識していると言っても過言ではないでしょう。前世代ではほぼ「空想か？」ぐらいの扱いだった分散t
ripgrep is faster than {grep, ag, git grep, ucg, pt, sift} - Andrew Gallant's Blog
ripgrep is faster than {grep, ag, git grep, ucg, pt, sift} In this article I will introduce a new command line search tool, ripgrep, that combines the usability of The Silver Searcher (an ack clone) with the raw performance of GNU grep. ripgrep is fast, cross platform (with binaries available for Linux, Mac and Windows) and written in Rust. ripgrep is available on Github. We will attempt to do the
Goでスケールする実装を書く
スケールする実装を書くためのガイド スケールするために 並列度とアムダールの法則 べき等参照透過性 Lock-FreeとWait-Free アトミックアクセス ロックの局所化 並列度とアムダールの法則 時間単位の場合は繰り返し処理のトータル時間に対し、 並列処理を妨げない処理時間の割合を「並列度」という。 （コードプロファイルを使って求める場合もあるが、 比較的単純なコードでないと計算が複雑になりやすい。） p 並列度 n 並列数 性能比 1/((1-p)+p/n) p=0.9のとき４倍の性能を得るにはn=6が必要。 n=5で４倍の性能を得るにはp=0.938が必要。 n=無限大とすると、性能比は以下の式におちつく。 理論上の性能向上限界 = 1/(1-p) 並列度90%の処理をどれだけ多数コアに分散しても理論上10倍処理効率が限界。 並列度95%の処理をどれだけ多数コアに分散しても理論上
【後編】アプリはデータで成長する！プッシュ通知の開封率を上げるアルゴリズムとは | SELECK
今回のソリューション：【バンディットアルゴリズム】 日本ではまだまだ数は少ないものの、大量のデータの解析によって事業戦略を立案する「データサイエンティスト」と呼ばれる職種のニーズが高まってきている。 株式会社VASILYが運営するファッションコーディネートアプリ「iQON（アイコン）」でも、データサイエンティストの金田 卓士さんをメンバーに引き入れ、200万人を超える会員に対してデータを活用した施策を打ち始めている。 「エモーショナルなファッションという領域をデータで解明し、ユーザーの感動体験を創出したい」と語る金田さんが入社後すぐに着手したのが、プッシュ通知の開封率の改善だ。 その際に活用したのが、限られた試行回数の中で収益を最大化する「多腕バンディットアルゴリズム」。結果的に通知の開封率を5％上昇させることに成功したという。 前編では、多腕バンディットアルゴリズムをどのようにプッシュ通
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Getting to Go: The Journey of Go's Garbage Collector - The Go Programming Language
List of hash functions - Wikipedia
http://ppl.jssst.or.jp/ppl2016/slides/visual_parsing.pdf
GitHub - google/diff-match-patch: Diff Match Patch is a high-performance library in multiple languages that manipulates plain text.
