Rubyから(ry → はやい

qiita.com

mattn.kaoriya.net

primenumber.hatenadiary.jp

2年以上放置していたけど、なんかフィボナッチ数の計算を高速化するのが流行ってると聞いて(違

フィボナッチ数が64bitで表現できる場合に限ると、以下がO(1)でほぼ最速だと思う。

FIB = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738].freeze

def fib(n)
  FIB[n]
end

puts fib(40)

解説もベンチマークも要らない...よね？

YARN-467/YARN-527でハマッタ件

CDH4.1.2のYarnクラスタで、${yarn.nodemanager.local-dirs}/filecache/以下にディレクトリがいっぱい(3万以上)できてしまってタスクが起動しなくなるという現象に見舞われました。
# 他のnodeでリカバリしてjob自体は成功していましたが。。。

どうやらDistoributed Cacheを利用していると、どんどんディレクトリが作成されていく一方で、自動でcreanupはしてくれない模様。
jiraにも上がっていますが、取りあえず古いディレクトリを削除するようcronを仕込んで対応完了としました。

(参考)
https://issues.apache.org/jira/browse/YARN-467
https://issues.apache.org/jira/browse/YARN-527

CapacitySchedulerでのリソース管理

前のエントリでは各ノードのメモリ管理について書いたので、次にクラスタ全体のリソース管理として
CapacitySchedulerについてのメモです。
なお、CDH4.1.2で試した結果ですので、最新のバージョンとは(ry

CapacitySchedulerについて

クラスタ上では同時に様々なmapreduceを実行するのが普通だと思います。
CapacitySchedulerを利用すると、各jobごとに重要度に応じて、柔軟なリソース割り当てを行うことができます。

詳細は以下を確認してください。
http://archive.cloudera.com/cdh4/cdh/4/hadoop/hadoop-yarn/hadoop-yarn-site/CapacityScheduler.html


以下、微妙に気になったトコをメモしていきます。

rootのcapacity設定は必須

自明なのでなくてもいい気がしますが、無いと怒られます。

<property>
  <name>yarn.scheduler.capacity.root.capacity</name>
  <value>100</value>
</property>

defaultのcapacity設定は必須

defaultはjob設定でマッチするqueueがない場合に割り当てられるqueueです。
無いとやっぱり怒られます

<property>
  <name>yarn.scheduler.capacity.root.queues</name>
  <value>default</value>
</property>
<property>
  <name>yarn.scheduler.capacity.root.default.capacity</name>
  <value>100</value>
</property>

各キューのcapacityとmaximum-capacityとuser-limit-factorの関係

分かりにくかったのですが、、、

  • クラスタがアイドル状態の場合
    • そのjobは"capacity*user-limit-factor +α"分までリソースを利用できる。
    • ただしqueue全体でmaximum-capacityを超えることはできない。
  • クラスタがビジー状態の場合
    • "capacity+α"分までリソースを利用できる
    • 上記の"+α"分は弾力性設定で、capacityを少し超えるまではコンテナを起動できる。
    • そのためuser-limit-factorが1でも"Over Capacity"状態になりうる。

minimum-user-limit-percentの影響はよくわかりませんでした(汗

例

アドホックなHiveクエリ等の野良MapReduceはdefaultで、定期的なバッチ等はmanagedで実行することを想定しています。

<property>
  <name>yarn.scheduler.capacity.root.capacity</name>
  <value>100</value>
</property>
<property>
  <name>yarn.scheduler.capacity.root.queues</name>
  <value>default,managed</value>
</property>

<property>
  <name>yarn.scheduler.capacity.root.default.capacity</name>
  <value>40</value>
</property>
<property>
  <name>yarn.scheduler.capacity.root.default.user-limit-factor</name>
  <value>1.5</value>
</property>
<property>
  <name>yarn.scheduler.capacity.root.default.maximum-capacity</name>
  <value>70</value>
</property>

<property>
  <name>yarn.scheduler.capacity.root.managed.capacity</name>
  <value>60</value>
</property>
<property>
  <name>yarn.scheduler.capacity.root.managed.user-limit-factor</name>
  <value>2</value>
</property>

この場合ですが、

  • アイドル状態のときは
    • defaultに投入されたジョブは60%(= 40% * 1.5)までリソースを使用可
    • defaultに複数ジョブが投入された場合、合計で最大70%までリソースを使用可
    • managedに投入されたjobは100%のリソースを利用可
  • 非アイドル状態のときは
    • defaultに投入されたジョブは40%までリソースを使用可
    • managedに投入されたジョブは60%までリソースを使用可
  • defaultが70%リソースを使用しているときにmanagedにジョブが突っ込まれたら
    • managedはとりあえず30%のリソースでジョブが実行できる。
    • defaultに投入されたジョブのコンテナが終了すると、managed側が空いたリソースでコンテナを起動できる。

まとめ

以下のような考え方で各queueの設定を決めていけばいいと思います。

  • capacityはクラスタがビジーのときにどれくらいの割合でリソースを割り振りたいかで決定する。
  • maximum-capacityは、他queueのために最低限どれくらいリソースを残しておきたいかで決定する。
  • user-limit-factorは、アイドル状態で効く設定なので気持ち多めでいいんじゃないかと。

なおqueueはツリー的に細分化して設定していくこともできます。
上の例では面倒なので、defaultとそれ以外みたいなカンジにしてしまってますが。

Hadoop yarnの各ノードのメモリ管理

yarnはmr1と色々と変わっているのですが、まず各ノードにおけるメモリの設定についてまとめます。
なお、CDH4.1.2で試した結果ですので、最新のバージョンとは挙動が異なる可能性があります。
# まとめるのをサボっていた結果既にCDH4.2がリリースされています(汗

メモリ管理の基本

yarnではapplication master(以下AM)やmapper, reducerを総称して「コンテナ」と呼び、「各コンテナが利用すると想定する物理メモリ量」をmapred-site.xmlの以下の項目で設定します。

  • yarn.app.mapreduce.am.resource.mb => AMが使用するとするメモリ
  • mapreduce.map.memory.mb => mapperが使用するとするメモリ
  • mapreduce.reduce.memory.mb => reducerが使用するとするメモリ

ResourceManager(以下RS)は上記設定を元に、各ノードでyarn-site.xmlのyarn.nodemanager.resource.memory-mbで指定した物理メモリ量の超えないようにコンテナを起動していきます。

例えば次のような設定をした場合、

  • yarn.nodemanager.resource.memory-mb = 8192
  • yarn.app.mapreduce.am.resource.mb = 2048
  • mapreduce.map.memory.mb = 1024
  • mapreduce.reduce.memory.mb = 2048

そのノードでのコンテナの起動パターンには以下のようなモノが考えられます。

  • mapperだけ8個
  • reducerだけ4個
  • AM1個 + reducer2個 + mapper2個
  • 他アレコレ。

どのようなパターンでコンテナが起動しても最終的にyarn.nodemanager.resource.memory-mbだけしかメモリを使わないと考えることができるので、全体としてのメモリ使用量の見積もりは簡単になります。

注意点その1

上記のように各ノードごとの最大同時起動コンテナ数が決定されるので、CPUのコア数等、メモリ以外のリソースも考慮して、各設定項目はバランス良く設定をすべきです。

駄目な例として、yarn.nodemanager.resource.memory-mbを多めにとって、各コンテナの想定量が少ないままだと、特定ノードでコンテナ起動が集中して、パフォーマンスも出ないし、全然分散処理できないという結果につながります。

注意点その2

mapreduce.map.memory.mbなどは「想定する物理メモリ量」と記述したとおり、あくまで「想定量」です。
実際に使用されるメモリが想定量を超えてはいけません。
超えた場合そのコンテナはNodeManager(以下NM)にkillされます。
そのため、メモリ使用想定量を変更する場合は、以下のmapred-site.xmlのjava optsの設定も同時に修正すべきです。

  • yarn.app.mapreduce.am.command-opts => AMのjava opts
  • mapreduce.map.java.opts => mapperのjava opts
  • mapreduce.reduce.java.opts => reducerのjava opts

また想定量は増やさずにheapの設定だけ増やしてしまうのも、同様に問題があるのでやめるべきです。

注意点その3

NMはコンテナで使用している物理メモリだけでなく、仮想メモリも監視しています。仮想メモリの使用想定量は物理メモリの想定量にyarn.nodenamager.vmem-pmem-ratioを乗じたものになります。

NMにコンテナがkillされた場合、物理メモリではなく仮想メモリが想定量を超えてしまっているのが直接のトリガになっているケースもあると思います。
その場合はyarn.nodenamager.vmem-pmem-ratioを修正すればいいのですが、そもそものheapの設定を失敗している可能性もあるので、まず先にheapの設定を確認することをオススメします。

注意点その4

大量のreducerを起動するjobを起動してしまうと、AMとreducerで全リソースを使い切ってしまいmapperが起動できず、reducerは起動できないmapperが終わるのを待つというデッドロックが発生するケースがあるようです。

十分なノード数があればそんなに心配しなくても大丈夫だと思いますが、冗談みたいな数のreducerを起動するjobは、一応注意した方がよいでしょう。