Computer Science キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム TinyLFUの論文を読んだので概要と、それを支えるアルゴリズムを紹介します。 Overview TinyLFU はアクセス頻度を近似し、軽量でハイパフォーマンスに設計されたキャッシュアルゴリズムです。最近、Database Internals を読んでいて TinyLFU を知ったのですが、Database Internals では TinyLFU の詳細が書かれていなかったので、TinyLFUが提案されている論文を読んでみました。その内容をザックリ解説してみようと思います。 論文はこちらです。 TinyLFU: A Highly Efficient Cache Admission Policy いきなりTinyLFUの紹介を始めると混乱するので、ベースとなる技術やアルゴリズム
October 1, 2007 This article was contributed by Ulrich Drepper [Editor's note: This is the second installment in Ulrich Drepper's "What every programmer should know about memory" document. Those who have not read the first part will likely want to start there. This is good stuff, and we once again thank Ulrich for allowing us to publish it. One quick request: in a document of this length there are
1. はじめに Rapidash というGo用のキャッシュライブラリを公開しました。 以前 https://qiita.com/goccy/items/a54af6db3b8623e90c38 で紹介した Octillery 同様、弊社の負荷対策用ライブラリになります。 キャッシュというとコンテキストによって用途は様々ですが、 Rapidash はアプリケーションサーバの応答性能を向上させるために、主にデータベースの負荷分散を目的として開発したライブラリになります。 主な機能は以下のようなものです。 検索しか行わないテーブルのデータをアプリケーションサーバ起動時にデータベースからすべて吸い上げ、インデックスの定義に従ってメモリ上に B＋Tree 構造で展開する。検索時は範囲検索もできる 読み書きを行うテーブルのレコードを memcached や Redis といったキャッシュサーバに格納し
なかなかよいおもちゃを見つけたので、紹介します。 fly.io fly.io は CDN Edge Worker で JavaScript に特化した PaaS です。既存のサービスで近いものだと CloudFlare Workers もしくは Lambda@Edge でしょうか。 アカウント登録をして、次のようなコマンドを叩くとエッジで動くアプリケーションを作成することができます。 npm install -g @fly/fly fly login # mkdir my-flyio; cd my-flyio fly new 最小コードはこんな感じ。CloudFlare Workers と同じような ServiceWorker 風と、Google Cloud Function 風の 2 つのパターンでワーカーを定義できます。 // index.js addEventListener('fe
HTML5 Conference 11/25
株式会社メルカリ プリンシパルエンジニア 久保 達彦氏 個人同士の取引を対象としたフリマアプリ「メルカリ」 は、国内だけでなく米国や英国でもサービスを展開し、全世界で1億ダウンロードを突破しました。メルカリ上で売買される商品金額は月間で100億円以上に、メルカリ上で出品される商品数は毎日100万品以上にまで大きくなっています。 メルカリのコンテンツは画像の占める割合が高く、データ通信の大部分が画像です。日々の出品に伴い画像ファイルも大量に増え続けます。画像配信には従来からCDNを利用していましたが、配信データ量の大幅な増加に伴い、CDNのキャッシュヒット率の低下が顕著になってきました。そこで、CDNとオリジンサーバの間に中間的なキャッシュサーバを導入することにしました。「別途キャッシュサーバを導入するにはそれなりに太い回線が必要な規模でしたので、その能力を持った事業者さん数社を検討しました
CDN_Study という勉強にいってきた。 https://http2study.connpass.com/event/81469/ そこで、Akamaiの方が、「個人の意見だけど、アプリケーション側がもっと基礎設計でステートレスでキャッシュフレンドリーな設計になってないといけないよね」という旨の発言をしていて、最近そのことにアプリケーションエンジニアとして同じようなことを考えていたので、書き出してみる。 SPAとかSSRとかフロントの不毛な話は出さないようにしてるが、主にサーバレス環境を意識している。 前提 世の中のアプリケーション内のモジュールは、Statefull or Stateless に分類でき、それをツリー状に表現できれば差分検知できる、という React の仮想 DOM 的な世界観が自分にある 以下の話は、基本的には Fastly のサロゲートペアーとそのためのミドルウェ
CDN Study (Akamai/Fastly) - connpass 久しぶりにすごい人混みに身をおいたわ・・。 どんな勉強会だったか CDNにもいろんな歴史がある あの頃のCDNといまのCDNでは、世界観も役割も変わってきてる 気がする ので、中の人に聞いてみよう！ という主旨の会。 from Akamai 資料は見つけたら CDNの過去と現在 1995年の時点で、中央集権的なWebは破綻するといわれていた 中央集権型ゆえに インターネットの混雑が問題になるだろう from Tim Berners-Lee インターネットは網の目 ただ実際は地震でケーブルが切れて不安定になったり 去年のGoogleの経路のアレとかも 爆発的なトラフィックによる負荷 スターウォーズの新作トレーラーとか インドのプレミアリーグとか CDNってそもそも インターネットの不安定さを避けるためにどうすれば ユー
@egapoolです。今回初めてISUCON7に参加させていただきました。（チーム名：元pyns） 当日やったこととこかはこちらにまとめています。 ISUCON7に参加して予選突破しませんでした。 – そろそろちゃんとやります 今回のお題の一つ目の壁は、いかに画像ファイル（アバターアイコン）をキャッシュさせてサーバーからデータを返さないようにするかでした。 8時間の大部分をこの対応に費やしましたが解決は出来ませんでした。 原因はきっちり304を返すための基礎知識が足りていなかったことです。 ですのでこれを機に勉強しなおしてみました。 304 (Not Modified) 大前提ですが、304ステータスコードは キャッシュの有効無効の確認付きリクエストに対して、有効である場合に返すステータスコード です。 この場合サーバーはリソースデータ(ペイロード)を送信しません。 すなわち，サーバは、［
Microservices on Fastly
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
This post is part of a series of 31 Rails 4 articles being released each day in December 2012. In production, an initial boot of your Rails application will load the schema of all your models into a schema cache. For those developers who have a large amount of models in their application, Rails 4 has introduced a schema cache dump to speed up the initial application boot time. To make a dump of yo
本日コーポレートサイトでお知らせした通り、Web版のメルカリにおいて一部のお客さまの個人情報が他者から閲覧できる状態になっていたことが判明しました。原因はすでに判明して修正が完了しております。また、個人情報を閲覧された可能性のあるお客さまには、メルカリ事務局より、メルカリ内の個別メッセージにてご連絡させていただきました。 お客さまの大切な個人情報をお預かりしているにも関わらず、このような事態に至り、深くお詫びを申し上げます。 本エントリでは技術的観点から詳細をお伝えさせていただきます。 2017年6月27日 CDNのキャッシュの動作について、CDNプロバイダと仕様について確認し検証を行いました。その結果一部記述に実際と異なる箇所があり、加筆修正いたしました。 概要 メルカリWeb版のコンテンツキャッシュをしているCDNのプロバイダ切り替えを行いました。 その際本来キャッシュされるべきでない
groupcache は Go で書かれた分散キャッシュライブラリで、複数プロセスでキャッシュを共有するプログラムが簡単に書けます。多くの用途で memcached を置き換えることを目指していて、Google のプロダクション環境で使われているようです。 個人的に groupcache の魅力は、 キャッシュを複数のピアに分散する (sharding) キャッシュに無いデータを同時に大量にリクエストしても、キャッシュ生成処理は1度だけ実行され、他のリクエストには生成されたキャッシュを返す（厳密では無いが、だいたいの場合1度きり） 頻繁にリクエストされるデータがリモートにあった場合、ローカルにもキャッシュする 一方、注意しないといけない点はキャッシュのアップデートには対応していないことです。groupcache には expire や明示的な破棄は存在しません。あるキーに対する値は 常に
はじめに CentOS 6上でepelからyumでインストールできるApache Traffic Server v5.3.0を試してみました (*1)。Ansibleのプレーブックを https://github.com/hnakamur/trafficserver-ansible-playbook に置いています。記事執筆時点のバージョンは https://github.com/hnakamur/trafficserver-ansible-playbook/tree/8efa6790d29bd8e62e488ceb7486a435e327d795 です。 *1: 当初epelからyumでtrafficserverをインストールしていたのですが、Cache Inspectorが複数のURLを分割する処理にバグ（後述します）があったため、 修正版をCopr上のhnakamur/apache-
この記事はセカイエ Advent Calendar 2015とVarnish Cache Advent Calendar 2015の2日目の記事になります。 かなり前の話(8月)になるのですがリノコという定額リフォームサービスのサイトがTV東京のワールドビジネスサテライト(以下WBS)に取り上げられました。 ありがたいことにたっぷり取り上げていただきました。その際に少しだけVarnishを使って負荷対策をお手伝いしたのでその時のことを書きます。 （なおここでとった対策は緊急ということで外しています。） TV放映される上で負荷対策として検討したこと スケールアップ・アウト トップページ及びそこから回遊されるページの静的化 Varnish導入 動き的には1を検討してみてその結果たりなさそうという判断を行い2,3を並列で行った感じです。 スケールアウト リノコではクラウドを利用しているわけで当然
Overview of Redis key eviction policies (LRU, LFU, etc.) Redis is commonly used as a cache to speed up read accesses to a slower server or database. Since cache entries are copies of persistently-stored data, it is usually safe to evict them when the cache runs out of memory (they can be cached again in the future if necessary). Redis lets you specify an eviction policy to evict keys automatically
問題 アプリケーション内でhttpsによる外部APIを叩いているサーバのメモリ使用量が増加し続ける件について調べた。 該当のサーバでは、以下のようにメモリの使用率が徐々に上昇していく。 また、アプリケーションのプロセス自体がメモリを消費しているわけではない状態。 原因 調査すると、このバグ仕様を踏んでいるのではないかと思われるページを見つけた。 https://bugzilla.redhat.com/show_bug.cgi?id=1044666 内容としては、curlを実行した際に /etc/pki/nssdb/以下の存在しないファイル(毎回違うパス)に対してaccessシステムコールが大量にコールされ、 negative dentry cacheが溜まっていき、メモリ使用量が圧迫されるというもの。 実際、この状況が起きているサーバを調べるとメモリ使用率のうち多くを占めているのはnega
ActiveRecordで1:Nの関係を扱うとき、ある親レコードに対して子レコードが幾つ存在するかという情報を、都度計算するのではなくキャッシュしておきたいケースは多いと思います。代表的な実装方法として、ActiveRecordのcounter cacheの機能を利用し、親レコード内にキャッシュを保存しておくという方法があります。 今回は、この情報を親レコード内ではなく揮発性のキャッシュに保存させるために、volatile_counter_cacheというGemをつくりました。memcachedやredisなどのKVSにキャッシュを保存することを想定しています。 方針 以下のような方針に基づいたキャッシュ戦略を想定しています。 RDB上には正規化された一次データだけ保存する 非正規化された二次データはRedis等のKVSに保存する 二次データは揮発しても良いようにする 概観 端的に言うと、
https://www.youtube.com/watch?v=rP9EKvWt0zo 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約1時間前 TwitterのYao Yuが、大規模サービスのキャッシュにおいてRedisを活用する取組みについて紹介しています。 1) Redisを採用している理由 キャッシュだけで、ストレージとしては利用していない。 主なところでは、Twitterのタイムラインで利用している。ホーム画面であれ、ユーザ画面であれ、タイムラインはTweetのインデックスなので、key/valueストア型のRedisを利用するケースとして最適。 以前はmemcachedを使っていたが、問題になったのは、タイムラインでおきるread/writeは、（ユーザが閲覧している範囲に追加反映するということなの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
