kenju's blog

About Programming and Mathematics

TICKStack, InfluxDB and InfluxData's Design Architecture & Key Concepts Notes

I am considering to put gRPC load testing metrics into InfluxDB, and visualize with Grafana. That drives me to have strong interests in the background architecture & its design key concepts of InfluxDB, and TICK Stack.

This blog post is my researching notes for InfluxDB and TICK Stacks.

TICK Stack

InfluxDB is one of a stack of TICK Stack, which is developed as a OSS product by InfluxData.

Key Concepts

The official docs describes the basic key concepts for understanding InfluxDB:

  • timestamp
    • all data have time columns
    • RFC3339 UTC
  • tag set
    • optional
    • any key-value pairs
  • retention policy
    • how long InfluxDB keeps data (DURATION)
    • how many copies of those data are stored in the cluster (REPLICATION)
  • point
    • the field set in the same series with the same timestamp

InfluxDB Line Protocol

InfluxDB Line Protocol is a line log which looks like below:

weather,location=us-midwest temperature=82 1465839830100400200
  |    -------------------- --------------  |
  |             |             |             |
  |             |             |             |
+-----------+--------+-+---------+-+---------+
|measurement|,tag_set| |field_set| |timestamp|
+-----------+--------+-+---------+-+---------+
  • whitespaces are separator of each components
  • support floats, integers, string or booleans as field values type
  • use HTTP API with curl or CLI to write to InfluxDB with Line Protocol

Run Locally

You can use docker image for local development:

docker run \
  --name=influxdb \
  -d \
  -p 8086:8086 \
  -p 8083:8083 \
  -e INFLUXDB_ADMIN_ENABLED=true \
  influxdb:1.6

And then, run below to connect to the InfluxDB container:

docker exec -it influxdb bash
influx -precision rfc3339

Open GUI like this (only with darwin):

open http://localhost:8083

Implementation

Here is the repository of influxdb:

https://github.com/influxdata/influxdb

  • written in Golang
    • can be compiled into a single binary to run on many platforms

Query (InfluxQL)

Influx Query Language specification is described at https://docs.influxdata.com/influxdb/v1.6/query_language/ .

InfluxQL is similar to SQL, but support much more time-series oriented queries & features.

InfluxQL function supports:

  • Aggregations
    • e.g. COUNT(), MEAN(), SUM()
  • Selectors
    • e.g. MAX(), MIN(), SAMPLE()
  • Transformations
    • e.g. ABS(), CEIL(), LOG(), POW(), SIN()
  • Predictors
    • HOLT_WINTERS()
  • Technical Analysis
    • e.g. EXPONENTIAL_MOVING_AVERAGE()

『エンジニアの知的生産術』を読んだ

Reading Notes

  • 知的生産とは、知識を用いて価値を生み出すことです
  • プログラミングの学びのプロセスは、以下の繰り返し
    • 具体的に情報収集する
    • 抽象化してモデルを作る
    • 実践して検証する
  • これは失敗ではありません。「この方法ではうまくいかない」という具体的情報を発見したのです。これは学びのチャンスです。

Chapter 1. 新しいことを学ぶには

  • 中学生の頃と比べると、社会人には学ぶことに対してとても強い逆風が吹いていることがわかりました。この逆風に負けずに限られた時間やお金を学びに使っていくには、強い「やる気」が必要です ... 逆風の中で弱いエンジンを回しても進めません。それを学ぶことは諦めて、よりやる気の出ることに気持ちを切り替えたほうが良い です。やる気は貴重なリソースなので、どういうテーマならやる気がでるのか、自分をよく観察して知ることが必要 です。
  • やる気は、行動と報酬のサイクルによって維持されます。行動に対してすばやく報酬を得られることが大事 です
  • 遅延評価的勉強法 ... まずはあなたが「知りたい」と思うところからやりましょう。あなたの「知りたい」という気持ちがやる気を高め、学びのサイクルを後押ししてくれます。... 特に具体的に作りたいものがあるときはチャンスです。手を動かし始めると、たくさん知りたいことが生まれます。それをどんどん解消していくことで、高いやる気を維持しながら学ぶことができます。
  • これは数学に限りません。ざっと眺めてもわからない本は、しっかり読むしか無いのです。そして、しっかり呼んでもわからないのであれば、手を動かしながら読むしか無いのです。
  • あなたが写経の必要がないと感じるのは、あなたが新しい分野にチャレンジしていないからなのです ... あなたが苦労せずに使える「新しい言語」を学んでいる時、それは大部分すでに学んだことで構成されており、あなたは新しい概念をほとんど学んでいません。効率よくたくさん学んだつもりになって、実際はあまり新しいことを学んでいないのです。

Chapter 2. やる気を出すには

  • Get Things Done のアドバイス
    • 「気になることを全部一箇所にまとめる」ただし、「気になること」であって「ToDo」ではない
    • 「まずは基地を作れ」
  • 緊急性分解理論 ... 「思慮の砲台金次第 ならぬならばやめるべし」今日やらないといけないことが今日できる以上の量になるとき
    • 質を下げられないか
    • 量を減らせないか
    • 納期を伸ばせないか
    • 方法を変えられないか
    • 代替できないか
    • お金で解決できないか
    • どうしようもないならやめるべき
  • 楽観的な勘違い ... 楽観的な勘違いに関してはあとから気づいて修正できるのです。「不確かなときは楽観的に」です。
  • Peter Drucker ... 「私の観察では、成果を上げるものは仕事からスタートしない。... 計画からもスタートしない。時間が何に取られているかを明らかにすることからスタートする。次に時間を管理すべく、時間に対する非生産的な要求を退ける。そして最後にそうして得られた自由になる時間を大きくまとめる。」

Chapter 3. 記憶を鍛えるには

  • 記憶は1種類ではない
    • 陳述記憶と非陳述記憶
  • 海馬では時間が圧縮される
  • 「適応的Boosting」と記憶の類似性
    • 「適応的Boosting」とは、能力の低い識別器(弱識別器)を集めて、もっと正解率の高い識別機を作る手法
  • 間隔反復法によって知識を長持ちさせる

Chapter 4. 効率的に読むとは

  • "The PhotoReading Whole Mind System"
  • 『フォーカス・リーディング』
  • ソースコードの読み方と書籍の読み方の関連性
  • 「読む」というタスクの設計
  • 読書は手段、目的は別

Chapter 5. 考えをまとめるには

  • 川喜田二郎『発送法』による KJ 法
    • 社会人向けにチューニングされた方法も紹介
  • 知識の整合性
    • 実験
    • より多くのものと整合していること(完全ではないが有益ではない)

Chapter 6. アイデアを思いつくには

  • イデアの3つのフェーズ
    • 耕す
    • 芽生える
    • 育てる

Chapter 7. 何を学ぶかを決めるには

  • 敬遠戦略の分類では、自分が置かれている状況を「ポジション」にたとえて、周囲の状況を分析し有利な場所を閉めようとする戦略を「ポジショニング学派」といいます
  • 知識を価値につなげていくには、その知識分野に最も詳しい人になることを目指す必要があります。この状態を「卓越」と呼びます。
  • Lynda Gratton "Work Shift" ... 「連続スペシャリスト」(special mastery)戦略
    • ある分野の専門性を獲得し、その専門性を生かして異なる分野へ参入し、そこで新しく専門性を獲得する戦略
  • 組織の境界をまたぐ知識の貿易商戦略
    • 流れが滞っている場合にその流れを円滑にすることは、しばしば経済的な価値が伴う

Run Multiple gRPC Load Testing using ghz

先日、gRPC server の負荷試験に、ghz が使えるという旨の記事を書きました。

ghz の欠点は、複数の RPC を呼び出したいときに、複数の ghz binary を動かす必要がある点です。例えば、3 RPC が同時にそれぞれの推定負荷値でアクセスしてきたときのパフォーマンスを測定したいとすると、それぞれの推定負荷値に合わせて ghz にオプションを渡して起動し、background で別プロセスとかで動かす必要があります。

柔軟に推定負荷値を変更させながら、気軽にスケールアウトもできる負荷試験を行いたかったので、Ruby で Thread を起動し ghz を動かす wrapper scripts を書きました。

設計

設計としては、

  • 負荷をかける minion (Thread)
  • 複数の minions を管理する master

に切り分けました。RPC ごとに class Minion を継承した minon を作成し、別スレッドで起動させます。Master は、全 minions の終了を待って、レポーティング結果をファイルに出力してプロセスを終了します。

負荷サーバーに Ruby のランタイムが必要な点が欠点ではあります。

Implementation

#!/usr/bin/ruby

require "fileutils"
require "optparse"

class Minion
  attr_reader :outdir, :options
  def initialize(outdir:, options:)
    @outdir = outdir
    @options = options
  end

  protected

  def run_command(options)
    command_str = build_command_str(options)
    puts "[DEBUG] executing '#{command_str}'"
    result = system(command_str)
    result
  end

  def command
    "ghz"
  end

  def host
    if options[:env] == "production"
      "***.***.***.***:5050"
    else
      "127.0.0.1:50051"
    end
  end

  def proto
    "protobuf-definitions/v1/hello.proto"
   end

  def package
    "services.v1.Hello"
   end

  def metadata
    "testdata/metadata.json"
  end

  def request_count
    10_000
  end

  # QPS(= Query Per Second)
  def rate_limit
    1_000
  end

  private 

  def build_command_str(options)
    common_opts = [
      command,
      "-proto #{proto}",
      "-n #{request_count}",
      "-q #{rate_limit}",
      "-M #{metadata}",
      "-insecure",
    ]

    [common_opts, options, host].flatten.join("\s")
  end
end

class HelloMinion < Minion
  def run
    options = [
      "-call #{package}.Hello",
      "-D testdata/hello.json",
      "-o #{File.join(outdir, 'hello.log')}",
    ]
    run_command(options)
  end
end

class Master
  def initialize(options)
    @options = options
  end

  def run
    setup
    load_test
    cleanup
  end

  private

  def outdir
    "log"
  end

  def setup
    puts "[INFO] rm #{outdir}/*.log..."
    FileUtils.rm(Dir.glob("#{outdir}/*.log"))

    puts "[INFO] mkdir #{outdir}..."
    FileUtils.mkdir_p(outdir)

    puts "[INFO] starting load testing..."
  end

  def load_test
    minions = [
      HelloMinion,
    ]
    threads = in_parallel(minions) {|minion| minion.run }
    threads.each(&:join)
  end

  def cleanup
    puts "[INFO] load test log is emmitted at log/"
  end

  def in_parallel(minions, &block)
    minions
      .map {|minion| minion.new(outdir: outdir, options: @options) }
      .map {|minion|
        Thread.new { block.call(minion) }
      }
  end
end

class CLIOptionParser
  def self.parse
    options = {}
    OptionParser.new do |opts|
      opts.banner = "Usage: run-bench-parallel [options]"

      options = {
        env: 'development',
      }

      opts.on('-e', '--env VALUE', "environment value (default: #{options[:string]})") {|v|
        options[:env] = v
      }
    end.parse!
    options
  end
end

options = CLIOptionParser.parse
Master.new(options).run

Usage

Development/Production の環境ごとにホストを分けたかったので、optparse で渡せるようにしています。

development:

$ bin/run-bench-parallel --env development

production:

$ bin/run-bench-parallel --env production

Great tool for benchmarking gRPC server - github.com/bojand/ghz

While I am searching benchmarking tool for gRPC server, I found a really great tool with clean API:

https://github.com/bojand/ghz

Here is a working example repository for simple gRPC server/client and benchmarking test, written in Golang.

https://github.com/kenju/go-grpc-server/tree/v0.0.1

Althing you have to do is create a config file for cli options, and run ghz -config ./ghz.config.json after launching gRPC server.

{
  "proto": "./services/message_service.proto",
  "call": "messagesservice.MessageService.GetMessage",
  "c": 4,
  "n": 1000,
  "D": "testdata/message_db.json",
  "M": "testdata/metadata.json",
  "x": "5s",
  "host": "0.0.0.0:1000"
}

After that, you can get a result something like this:

$ make perftest
ghz -config ./ghz.config.json

Summary:
  Count:    1000
  Total:    266.77 ms
  Slowest:  27.33 ms
  Fastest:  0.15 ms
  Average:  0.98 ms
  Requests/sec: 3748.58

Response time histogram:
  0.148 [1] |
  2.867 [967]   |∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎
  5.585 [4] |
  8.304 [4] |
  11.023 [3]    |
  13.741 [1]    |
  16.460 [0]    |
  19.179 [4]    |
  21.897 [0]    |
  24.616 [8]    |
  27.335 [8]    |

Latency distribution:
  10% in 0.25 ms
  25% in 0.29 ms
  50% in 0.35 ms
  75% in 0.47 ms
  90% in 0.83 ms
  95% in 1.44 ms
  99% in 24.47 ms
Status code distribution:
  [OK]  1000 responses

What I feel it great is:

  • cli options are simple & minimal, but sufficient
    • you can change rate limit/cpus/connections easily
  • you can change output with csv/json/html also
    • this is great if you want to build visualization tool built upon ghz

ghz is the very example of "doing one thing well".

NOTE: I am still in investigating, and not yet use it at a production environment

Reading Notes of "Designing Data-Intensive Applications" Chapter 6: Partitioning

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

「Reading Notes of "Designing Data-Intensive Applications" Chapter 5: Replication」(http://itiskj.hatenablog.com/entry/2018/09/04/050000) に引き続き、第六章の Reading Notes. 発表担当ではないけど、まとめる過程で思考を整理できるので、今回も書くことに。

Reading Notes

My Impressions

Partitioning is much more difficult problems than Replication (Chapter 5), since we have to take care about distributed computers, and not only about single hosted machine.

I have thought that hash key partitioning or simple round-robin partitioning is enough for many cases. Such simple cases will be enough for some cases, but the more complicated and sophisticated methodology is required to solve the current distributed networks' problems, especially in the era of cloud computing.

For example, simple algorithm can lead to hot spots if used without much considerations. Which keys to use for hash partitioning depends on each application's domain (timestamp, user id, UUID, etc.).

Rebalancing is also an interesting topic. Implementing rebalancing may be easy, but what makes it difficult is its cost. If rebalancing takes so much time, applications may be too slow for daily usage.

Partitioning

There are 2 types of partitioning:

  • Key range partitioning
  • Hash partitioning
type pros cons
Key range partitioning efficient range queries are possible available only when the key can be sorted / hot spots risk
Hash partitioning may distribute load more evenly cannot use range queries

Secondary indexes

There are 2 ways to implement secondary indexes:

  • Document-partitioned indexes (local indexes)
  • Term-partitioned indexes (global indexes)
type index position read write
Document-partitioned in the same partition as the primary key scatter/gather across all partitions write to only updated single partition
Term-partitioned separately, using the indexed values read can be served from a single partition several partition needs to be written

Rebalancing

  • How not to do it: hash mod N
  • The problem with the mod N approach is that if the number of nodes N changes, most of the keys will need to be moved from one node to another
  • there is a fairly simple solution: create many more partitions than there are nodes, and assign several partitions to each node

Request Routing

  • Many distributed data systems rely on a separate coordinate service such as Zoo-Keeper to keep track of this cluster metadata
  • LinkedIn's Espresso use Helix (which in turn relies on ZooKeeper), HBase, SolrCloud and Kafka also use ZooKeeper
  • Cassandra and Riak use a gossip protocol among the nodes to disseminate any changes in cluster state

Reading Notes of "Designing Data-Intensive Applications" Chapter 5: Replication

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

社内の輪読会で、DDIA を読んでいる。Chapter 5 は自分が担当だったので、そのときに社内向けに書いたまとめの一部抜粋。

グローバルチームのメンバーの輪読会に混ぜてもらっている形なのだが、なかなかレベルが高いものの、DDIA の内容が自分の興味関心にぴったりなこともあって、モチベーション高く維持できており、刺激の多い最高の学びの機会となっている。最初の回は、ネイティブ話者に混じって技術的な議論をする機会がなかなかなかったため、聞き役に徹することも多かったのだが、今回くらいから徐々に発言する場面を増やすことができて、非常に楽しく参加している。毎週月曜日に、早く参加したくてしょうがない予定があるというのも、なかなか良いものだ。

今回は、Replication が題材の回。興味があったので、References に紹介されていた、AWS Redshift, DynamoDB, Apache Kafka のリーダー戦略や Replication について書かれた論文も読んでみた。DDIA は、現役の研究者が書かれたということもあって、質の高い情報が密度高く紹介されており、難解な箇所も多々あるが、非常に読んでいて勉強になる。今年であった中でもベスト3に入る良著。

ちなみに、AWS DynamoDB について書かれた論文を読んだときのメモは、別記事 "論文『Dynamo: Amazon's Highly Available Key-value Store』を読んだ"(http://itiskj.hatenablog.com/entry/2018/09/03/213643) にもまとめてあるので、そちらも参照されたい。

List of Sections

  • Leaders and Followers
    • Synchronous Versus Asynchronous Replication
    • Setting Up New Followers
    • Handling Node Outages
    • Implementation of Replication Log
  • Problems with Replication Log
    • Reading Your Own Writes
    • Monotonic Reads
    • Consistent Prefix Reads
    • Solutions for Replication Lag
  • Multi-Leader Replication
    • Use Cases for Multi-Leader Replication
    • Handling Write Conflicts
    • Multi-Leader Replication Topologies
  • Leaderless Replication
    • Writing to the Database When a Node is Down
    • Limitations of Quorum Consistency
    • Sloppy Quorums and Hinted Handoff
    • Detecting Concurrent Writes
  • Summary

Keywords

* eventual consistency
* leader-based replication/master-slave replication
* single-leader/multi-leader/leaderless
* synchronous/asynchronous/semi-synchronous
* chaing replication (Microsoft Azure Storage)
* replicatoin logs
* WAL(Write-ahead log)
* read-after-write-consistency/read-your-write-consistency
* monotonic reads
* consistent prefix reads
* replication topology

Summary

Why replication?

  • To achive high availability/scalability
  • To allow operation even while network disconnected
  • To increase latency

How to replicate?

NOTE: each approach has both pros/cons.

  • Single-leader replication
  • Multi-leader replication
  • Leaderless replication
type pros cons
Single-leader easy to understand, no conflict resolution less robust
Multi-leader robust against faulty, network interupptions and latency spikes complex and harder to maintain
Leaderless (same with the above) complext (especially the quorum model)

When to replicate?

type pros cons
synchronous easy to gurantee consistency slow (especially if there are many folowers)
asynchronous blazingly fast harder to gurantee consistency
semi-synchronous both advantages from synchronous & asynchrnous harder to implement

How to tackle Replication Lag Problem?

Here are some consistency models:

  • Read-after-write consistency
  • Monotonic reads
  • Consistent prefix reads

My Reading Notes 🔖

Semisync replication

Briefly looked through this blog post, introduced at references [7]

http://yoshinorimatsunobu.blogspot.com/2014/04/semi-synchronous-replication-at-facebook.html

Semisync replication was originated from Google in 2007. Official MySQL supported from 5.5. Actual implementation algorithm was substantially different from Google's.

  • there are 2 types of Semisync
    • Normal Semisync
    • Loss-Less Semisync
  • Facebook use MySQL's mysqlbinlog for Semisync

Amazon Redshift replication

  • Amazon Redshift seems to support single-leader replication
    • but, the leader nodes seem to exist more than one, so maybe "multi-leader replication"?
    • "follower nodes" are called "compute nodes" instead
    • see "Deep Dive on Amazon Redshift" slide also
      • p7, 10,
      • The leader node also has responsibility for task scheduling, parser & rewriter, planner & optimizer, compiler, code generation, etc...

Amazon DynamoDB replication

Briefly looked through this thesis, introduced at references [37]

https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

Especially, 4.2 Partitioning Algorithm, 4.3 Replication and 4.8.1 Ring Membership.

  • Dynamo follows "Leaderless" design
  • Dynamo's partitioniong scheme relies on consistent hashing
  • "every node in the sytem can determine which nodes should be in this list for any particular key", because the partitioned key can be calculated via the consistent hashing algorithm (= Leaderless)

Kafka replication

I like Pub/Sub middlewares and read below slides from references [5]

  • https://www.slideshare.net/junrao/kafka-replication-apachecon2013
  • p9 for Kafka architecture. almost same with AWS Kinesis Streams
  • p13~ for Kafka replication design.
    • Kafka Replication gurantee CA of CAP theorum.
    • Kafka distribute message brokers into some partition, and each partition has replicas of topics (p17)
    • Kafka follows Single-leader replication
      • One of the replicas is leader, and all writes go to leader
      • The leader propagates writes to followers in push style (not pull or polling style, so the leaders decide when to commit messages)
  • p21~22 for Data Flow in Replication
    • the leader push messages to each followers, commit, and then return the result to consumers
    • the leaders are evenly spread among brokers

論文『Dynamo: Amazon's Highly Available Key-value Store』を読んだ

AWS DynamoDB がサービスとしてローンチする前、Amazon 社内でショッピングカート機能などに利用されていた "Dynamo" の設計について書かれた論文。DynamoDB を普段使う身として、そもそもどういう課題を解決しようとしていたのか、そのためにどういった解決策をとったのか、という設計の骨子を知ることができる。

高い可用性と信頼性を担保する DynamoDB が、実は partitioning や conflict resolution, replication といったそれぞれの分野におけるベストプラクティスを着実に積み上げた、堅実なプロダクトということがわかる。

最初にローンチされて以降、Global Index/Secondary Index や TTL, DynamoDB Streams や Point-In-Time-Recovery, Auto-Scaling に On-Demand Backup など、数々の新機能を搭載し、ますます活躍の幅を広げている DynamoDB。しかし、それがもともとは、RDBMS には複雑すぎるシンプルなビジネス要件を、ただし EC サイトであることから求められる非常に高い可用性と信頼性を、マルチリージョンで担保するために、consistent hashing や Quorum models など定番とも言えるアルゴリズムを、Java で実直に実装したところがスタートだったという。熱い話だ。

Dynamo が実装している一連の技術は、論文に何度も登場する。例えば、Gossip-based membership や Sloppy Quorum については初見だったため、この論文をきっかけに学んだ単語も多い。

特に 4. SYSTEM ARCHITECTURE で紹介されている、使用技術の一覧がわかりやすい。こちらを参照されたい。

Problem Technique Advantage
Partitioning Consistent Hashing Incremental Scalability
High Availability for writes Vector clocks with reconciliation during reads Version size is decoupled from update rates
Handling temporary failures Sloppy Quorum and hinted handoff Provides high availability and durability guarantee when some of the replicas are note available
Recovering from permanent failures Anti-entropy using Merkle trees Synchronizes divergent replicas in the background
Membership and failure detection Gossip-based membership protocol and failure detection Preserves symmetry and avoids having a centralized registry for storing membership and node liveness information

Reading Notes

p205

  • Dynamo provides a simple primary-key only interface to meet the requirements of these applications
  • Dynamo uses a synthesis of well known techniques to achieve scalability and availability
    • data is partitioned and replicated using consistent hashing
    • consistency is facilitated by object versioning
    • the consistency among replicas during updates is maintained by a quorum-like technique and a decentralized replica synchronization protocol
    • employs a gossip based distributed failure detection and membership protocol

p206

  • however, a relational database is a solution that is far from ideal. Most of these services only store and retrieve data by primary key and do not require the complex querying and management functionality offered by an RDBMS

p207

  • An important design consideration is to decide when to perform the process of resolving update conflicts ... The next design choice is who performs the process of conflict resolution

p209

  • First, Dynamo is targeted mainly at applications that need an "always writeable" data store where no updates are rejected due to failures or concurrent writes
  • Dynamo's partitioning scheme relies on consistent hashing to distribute the load across multiple storage hosts

p210

  • Dynamo replicates its data on multiple hosts
  • The list of nodes that is responsible for storing a particular key is called the preference list ... so that every node in the system can determine which nodes should be in this list for any particular key
  • Dynamo provides eventual consistency, which allows for updates to be propagated to all replicas asynchronously
  • In order to provide this kind of guarantee, Dynamo treats the result of each modification as a new and immutable version of the data
  • Dynamo uses vector clocks in order to capture causality between different versions of the same object. A vector clock is effectively a list of (node, counter) pairs

p213

  • In Dynamo, each storage node has three main software components: request coordination, membership and failure detection, and a local persistence engine. All there components are implemented in Java.

p219

  • The production use of Dynamo for the past year demonstrates that decentralized techniques can be combined to provide a single highly-available system

論文『A Note on Distributed Computing』を読んだ

https://dl.acm.org/citation.cfm?id=974938

"論文『Orleans: Distributed Virtual Actors for Programmability and Scalability』を読んで" ( http://itiskj.hatenablog.com/entry/2018/08/30/142538 ) を書いたときと同様のきっかけで、"Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems" の Chapter 4 を読んでい。、章末の文献に紹介された一連の論文の中で、面白そうだったので読んでみた文献の一つ。

分散システムを実装するにあたって必要な基本的概念や設計パターンについて書かれている。1994 年執筆なので少し古いが、内容は今のクラウドアーキテクチャが一般的になった現代でも十分通じる、基本的な考え方が書かれていると感じた。

同様の論文に対して、他にも綺麗にまとめられた感想ブログを発見した。そちらも参考にされたい。

https://medium.freecodecamp.org/a-note-on-distributed-systems-3c796f1eb0a0

Memo

p.3

  • Writing a distributed application in this model proceeds in three phases
    • The first phase is to write the application without worrying about where objects are located and how their communication is implemented
    • The second phase is to tune performance by "concretizing" object locations and communication methods
    • The final phase is to test with "real bullets" (e.g., networks being partitioned, machines going down)

p.4

  • Communications protocol development has tended to follow two paths.
    • One path has emphasized integration with the current language model.
    • The other path has emphasized solving the problems inherent in distributed computing.

p.5

  • The major differences between local and distributed computing concern the areas of latency, memory access, partial failure, and concurrency

p.6

  • A more fundamental (but still obvious) difference between local and remote computing concerns the access to memory in the two cases - specifically in the use of pointers

p.7

  • While unlikely, it is at least logically possible that the differences in latency and memory access between local computing and distributed computing could be masked.
  • Partial failure is a central reality of distributed computing. ... This is not the case in distributed computing. where one component (machine, network link) can fail while the others continue.

Bandit Algorithm における各方式の概要をまとめる

ε-greedy

Abount

全体のアーム選択数 T の内、

  • εT 回 ... 探索期間。すべてのアームを均等に選択する
  • (1 - ε)T 回 ... 活用期間。探索期間中の結果を受けて、もっとも標本平均の高かったアームをひたすら引き続ける

という方式。

Pros/Cons

  • UCB に比べて性能が悪い場合が多い
  • 実装が容易でシステムに組み込みやすい

Pseudo Code

Parameters: ε > 0
Input: 全体のアーム選択数 T
1: 全てのアーム i を εT/K 回引く
2: 一番結果の良かったアームを (1 - ε)T 回引く

UCB = Upper Confidence Bound

About

  • 報酬期待値が高そうに見えるアームを引く
  • 選択数が少ないアームについては、まだ標本平均が真の期待値に就職していないため、ある程度選択する必要がある

という2つのバランスをとりながらアームを選択する方式。

UCB スコアを各時刻ごとに計算し、そのスコアがもっとも高いアームを時刻ごとに選択する方式。UCB スコアの計算には複数種類があり、ヘフディングの不等式に基づいたものなどがある。

Pseudo Code

1: すべてのアームを1回ずつひく
2: for t = K + 1, K + 2, ..., T do
3:   各アーム i の UCB スコアを計算
4:   スコアが最大のアームを引く(スコアが最大のアームが複数ある場合は、どれでもいい)
5: end for

Probability Matching Method

Abount

確率一致法。

「それぞれのアームが期待値最大である確率」を何らかの方式で定式化し、引くアームをその確率にしたがって選ぶもの。

言い換えると、「期待値最大である確率が高そうなアームが高確率で惹かれるが、そうでないアームも低頻度ながら引かれる」というもの。

Pros/Cons

  • 定量のバッチ更新に対して頑強
    • 常に確率を元に選択するため、オフライン計算が不要で、各アームの選択数が"確率的に"分散される

参考図書

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

論文『Orleans: Distributed Virtual Actors for Programmability and Scalability』を読んで

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Orleans-MSR-TR-2014-41.pdf

"Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems" の Chapter 4 を読んでいて、章末の文献に紹介された一連の論文の中で、面白そうだったので読んでみた。

Orleans という、分散コンピューティングにおける設計モデルの一つで、Microsoft によって開発された。特徴は、Visual Actors という、いわゆる Erlang とかの Actors モデルを「仮想化」することで中小レベルを引き上げ、広く応用できるモデルとして構築した、という点だ。

https://dotnet.github.io/orleans/

.NET Frameworks (C#) で実装され、実装も GitHub で公開されている。

https://github.com/dotnet/orleans

論文内にも書かれているが、Erlang や Akka から影響やヒントを受けている。また、Microsoft Windows Azure Cloud において本番運用されている実績もある。特に、"Halo 4" というゲームタイトルが実例としてあげられている。

Memo

p.1

  • we build the Orleans programming model and runtime, which raises the level of the actor abstraction
  • It (= Orleans) is actor-based, but differs from existing actor-based platforms by treating actors as virtual entities, not as physical ones.

p.2

  • Overall, Orleans gives developers a virtual "actor space" that, analogous to virtual memory, allows them to present in memory.
  • Orleans has been used to build multiple production services currently running on the Microsoft Windows Azure cloud, including the back-end services for some popular games
  • ... that Orleans has no need for supervision trees as in Erlang and Akka

p.3

  • Currently, Orleans supports two activation modes for actor types: single activation mode (default), in which only one simultaneous activation of an actor is allowed, and stateless worker mode, in which many independent activations of an actor are created automatically by Orleans on-demand (up to a limit) to increase throughput.

p.4

  • Orleans runs on a cluster of servers in a datacenter, each running a container process that creates and hosts actor activations. A server has three key subsystems: Messaging, Hosting, and Execution.

p.5

  • Actors in Orleans do not share state and are isolated from each other. The only way that actors can communicate is by sending messages.

p.6

  • For better programmability, Orleans allows any data type and maintains object identity through the serializer. Structs, arrays, fully polymorphic and generic objects can be used.