マツシタのお勉強

AWSにおける可用性を向上するパターンをまとめる

クラウドにおける可用性とは

「可用性(Availability)」とはシステムが継続して稼働できる能力の事。システムを稼働しているサーバーや、データを保存しておくデータベースが1つで設計されている場合、その1つが落ちた場合にシステムが止まってしまう。これは可用性の低い設計である。設計者はサーバーやデータセンタが落ちることを想定して、可用性の高い設計をする必要がある。

参考

カテゴリ:CDP:可用性を向上するパターン - AWS-CloudDesignPattern

Multi-Serverパターン

Multi-Serverとは、仮想サーバー(EC2)を複数台ならべELB(ロードバランサー)によって適宜不可を振り分けることである。ELBにはヘルスチェック機能が備わっているので、1つのサーバーが止まった場合は、そのサーバーには処理を振り分けずに健康なサーバーのみに処理を振り分ける。これによって1つのサバーが落ちても、システムを仮想し続けることができる。

注意点

EBLと複数のEC2を使用するので、単一よりもコストがかかる

Multi-Datacenterパターン

AWSは複数のデータセンターを保持している。Multi-Datacenterパターンは複数のデータセンターにサーバーを構築しておくことで、1つのデータセンターが障害が起きた場合でも、システムを稼働し続ける事ができる。これもMulti-Serverパターンと同様にELBが処理を振り分けてくれる。

Deep Health Checkパターン

ロードバランサーDNSはヘルスチェック機能が備わってるが、基本的にはチェック出来る範囲は直接紐付いているサーバーのみである。 Deep Health Checkは直接紐付いているサーバーだけではなく、もっと奥深くのサーバーもチェックし、そのステータスをロードバランサーDNSに返してシステム全体のヘルスチェックを行うものである。

システムはDNS→Webサーバー→Proxyサーバー(代わりにアプリケーションリクエストを送るためのサーバー。直接リクエストを送らずにProxyサーバーをはさむのでセキュリティ面で恩恵がある)→アプリケーション・サーバー→データベースといくつものサーバをはさむ事がある。その全てのサーバーに対してヘルスチェックを行う事ができる。

Floating IPパターン

使用しているサーバーが止まった場合、マシンイメージを用いて仮想サーバーを新たに高速に作り、その仮想サーバーにEIPを付け替えることでシステムを稼働し続けることができる。EIPを付け替える操作もAPIが用意されているので自動化することができる。

Routing-Based HAパターン

続く。

配列における3つの要素の和

Problem

leetcode.com

与えられた配列において、任意の3点の和がゼロとなる組合せを全て取得する問題。

Solution

この問題は以下のように解くことができる。

  1. 任意の3点をstart, middle, endと置く(start < middle < end)
  2. startを固定し、middle = start + 1, end = arr.length - 1 と置く
  3. 上記により3点が決まるので、3点の和を計算しsと置く
  4. s == sumならば、その要素達をリストに追加。この時、middle++, end--する。
  5. 更新したmiddleとendがそれぞれ前回と同じ値ならば、更にmiddle++, end--する。こうすることで重複を除く事ができる。
  6. 4, 5を(middle < end)が成り立つ間繰り返す。
  7. 以上の処理をstartを0 → arr.length - 3 まで行う。

コレによる計算量はO(N2)となる。

Source Code

AtCoder ABC D - Mixing Experiment

問題

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

解き方

全列挙を考える

全列挙する場合、i番目の薬品を購入する場合としない場合を2パターンをN回行うので、計算量はO(2N)となりNは最大40なので間に合わない。

動的計画法を使う

dp(i, x, y)を以下のように定義する。

dp(i, x, y) := {i番目までの薬を使用した時、物質aの和がx, bの和がyとなる、最小コスト}

漸化式を立てる

dp(i, x, y)は漸化式を用いて次のように表す事ができる。

dp(i, x, y) = min(dp(i - 1, x, y), dp(i - 1, x - a[i], y - b[i]) + cost[i])

後は配列のインデックスがOutOfRangeしないようにfor文を回してあげる。するとi に N - 1 を代入したdp[N - 1][x][y]は、全ての薬品を考慮した時のx, yのコストを取得することができる。あとは、与えられた比となるx, yを見ていき最小コストを出力してあげる。

ソースコード

Heaps: Find the Running Median

Problem

www.hackerrank.com

This problem is that we calculate median of array the range is from 0 to ith.

Solution

By using Two Priority Queues: minHeap and maxHeap, we can solve this problem. The roles of them are following.

  • minHeap : To store bigger half values in array.
  • maxHeap: To store smaller half values in array.

In this case, the root value of minHeap and the root value of maxHeap are medians. The points is that which heap should we add each element and we have to keep the balance of two heaps size.

Source Code

Trie Tree in Java

What is Trie Tree

Trie Tree is one of the tree structure to search element. The feature of this tree that each node dose not have element information, but also each edge has element information. Trie tree is used to search String like dictionary.

www.youtube.com

Problem

www.hackerrank.com

Source Code