KotlinでMultiSetを雑に実装する
AtCoderの問題を解いているときにMultiSetがあると助かる場面があったためざっくり実装。
import java.util.TreeMap import java.util.TreeSet class SortedMultiSet<T>( comparator: Comparator<T>? = null, val map: TreeMap<T, Int> = TreeMap<T, Int>(comparator) ) :MutableSet<T> by map.keys{ override fun add(element: T): Boolean { map[element] = (map[element]?: 0) + 1 return true } override fun remove(element: T): Boolean { val x = map[element] if(x == null){ return false } if(x == 1){ map.remove(element) } else { map[element] = x - 1 } return true } }
- できること
- 同じ値を複数追加
- できないこと
- 同じ値を含む全要素ループ←同じ値は1回しかループされない
各種Mapへの要素追加、ランダムアクセス、イテレーションの実行速度
Kotlinで使用できるMapは主に
- HashMap (hashMapOf)
- LinkedHashMap (mutableMapOf)
- TreeMap (sortedMapOf)
の3つ。
結論から書くと、
- 要素の追加はHashMapが最も速い。次にLinkedHashMap。TreeMapは遅い。
- ランダムアクセスはHashMapとLinkedHashMapがほぼ同じ。TreeMapは遅い。
- イテレーションはLinkedHashMapが圧倒的に速い。
LinkedHashMapはキーの挿入順を保持しているのでイテレーションが高速に行える。
それぞれを使い分けるなら、
- ランダムアクセスのみ行う→HashMap
- イテレーションを行う→LinkedHashMap
- キーがソートされていると嬉しい→TreeMap
といった感じだろうか。
計測
で各処理を行い、100回計測した平均を取る。
要素の追加(更新)
for(i in (1..N).map{Random.nextInt(N)}){ map[i] = 1 }
HashMap | 5.35 msec |
LinkedHashMap | 7.39 msec |
TreeMap | 34.63 msec |
ランダムアクセス
事前に要素の追加と同じく要領でMapを埋めておく。
val keys = map.keys.shuffled() for(i in keys){ map[i]!! }
HashMap | 4.45 msec |
LinkedHashMap | 4.86 msec |
TreeMap | 30.54 msec |
イテレーション
事前に要素の追加と同じく要領でMapを埋めておく。
for((k, v) in map){ k + v }
HashMap | 3.97 msec |
LinkedHashMap | 0.93 msec |
TreeMap | 6.91 msec |
コード全体
import kotlin.system.* import kotlin.random.Random val N = 100_000 val M = 100 val randomArray = Array(M){IntArray(N){Random.nextInt(N)}} val randomPair = Array(M){randomArray[it].map{it to 1}} fun main(){ val maps = listOf(hashMapOf<Int, Int>(), linkedMapOf<Int, Int>(), sortedMapOf<Int, Int>()) println("********Test set********") maps.forEach(::testSet) println("\n********Test get********") maps.forEach(::testGet) println("\n*****Test Iteration*****") maps.forEach(::testIteration) } fun testSet(map: MutableMap<Int, Int>){ var t = 0.0 repeat(M){ m -> map.clear() t += measure(1){ for(i in randomArray[m]){ map[i] = 1 } } } map.clear() printResult(map, t / M) } fun testGet(map: MutableMap<Int, Int>){ var t = 0.0 repeat(M){ i -> map.clear() map.putAll(randomPair[i]) val keys = map.keys.shuffled() t += measure(1){ for(i in keys){ map[i]!! } } } map.clear() printResult(map, t / M) } fun testIteration(map: MutableMap<Int, Int>){ var t = 0.0 repeat(M){ i -> map.clear() map.putAll(randomPair[i]) t += measure(1){ for((k, v) in map){ k + v } } } map.clear() printResult(map, t / M) } fun measure(n: Int, block: (Int) -> Unit) = (1..n).map{ System.gc() measureTimeMillis{ block(it) } }.average() fun printResult(k: Any, t: Double){ println("${k::class.simpleName}: \t$t msec") }
KotlinでCollectionをソートするときのメモ
Mutableなやつ
sort()
sort()を使うとコレクション自身がソートされるので何も返ってこない点に注意。
val list = mutableListOf(5, 1, 3, 2, 4) list.sort() println(list) // [1, 2, 3, 4, 5]
SortedSetを使う
val set = sortedSetOf(5, 1, 3, 2, 4) println(set) // [1, 2, 3, 4, 5]
Immutableなやつ
sorted()を使う
ソートされたコレクションが返ってくる。
val array = listOf(5, 1, 3, 2, 4).sorted() println(array) // [1, 2, 3, 4, 5]
Pair<Int, Int>をソートする
sortedWith, compareByを使う
MutableなコレクションならsortWithでもOK。
val pairs = Array(10){ Random.nextInt(10) to Random.nextInt(10) }.sortedWith(compareBy({it.first}, {it.second})) println(pairs.joinToString("\n")) /* (0, 1) (1, 4) (1, 8) (2, 1) (5, 7) (5, 8) (7, 6) (8, 4) (9, 1) (9, 7) */
compareByは引数にセレクタを複数渡せる。 compareBy - Kotlin Programming Language
セレクタ1つで済むときはsortBy、sortedBy
val pairs = Array(10){ Random.nextInt(10) to Random.nextInt(10) }.sortedBy{it.second} println(pairs.joinToString("\n")) /* (9, 2) (9, 2) (7, 4) (3, 5) (2, 5) (7, 6) (4, 7) (9, 8) (6, 9) (0, 9) */
1コア512MBのVPSでMastodonする
この記事はMastodon Advent Calendar 2017 - Adventar / Mastodon Advent Calendar 2017 - Qiita day 10の記事です。
どうもこんにちは。crakaCです。 タイトルの通り、512MB丼というお一人様インスタンスを建ててのんびりマストドンしています。 1コア512MBという限られた資源の中で、出来るだけ快適にMastodonをするためにしてきたことを書いていこうと思います。
下準備
ドメイン取得、VPSを借りる、sshの設定などなどありますが、この辺は他の人達に任せようと思います。
マストドンを建てる
ProductionGuideに沿ってコマンドを実行していくと立ち上がります。
assets:precompile
を実行する時にメモリを2GBくらい消費するので、スワップ領域を確保しておきましょう。さくらのVPSでは4GBスワップに充てられているので時間はかかりますが通ります。
お一人様設定
誰一人ユーザーがいない状態で、.env.productionファイル内のSINGLE_USER_MODE=true
を有効にして起動すると登録画面が出てこなさそう(未確認)なので、最初はコメントアウトした状態で起動した気がします。
Mastodon起動後、ブラウザから自分のアカウントを登録します。お一人様インスタンスとして使っていくので、メール設定はすっ飛ばしてやっていきました。
# 手動でユーザー認証 RAILS_ENV=production bundle exec rails mastodon:confirm_email USER_EMAIL=hoge@pi.yo # 管理者に設定 RAILS_ENV=production bundle exec rails mastodon:make_admin USERNAME=hogehoge
ログインできることを確認したら、SINGLE_USER_MODE=true
を有効にしてmastodon-webを再起動します。
これでひとまずお一人様インスタンスの完成です。
Mastodonをチューニング
このサーバー上で一番のボトルネックになるのはメモリです。512MBで動かしていると常時スワップが発生してしまいます。どうにかしてメモリ消費を抑えるためにしてきたことを書いていきます。
PgBouncerの導入
PgBouncer Guideに沿って、PgBouncerを導入します。
postgresqlのプロセス数を減らすことが出来るため、メモリが少ない環境でマストドンを快適に動かすためにはとても良いです。
各種serviceファイルのチューニング
Tuning Mastodonを参考に、mastodon-*.service設定していきます。
mastodon-web.service
Environment="WEB_CONCURRENCY=1" Environment="MAX_THREADS=5"
を追加します。 TuningMastodonによると、
For a single-user instance, 1 process with 5 threads should be more than enough.
とのことなので、一人鯖ならこれで十二分ぽいですね。
WEB_CONCURRENCYについては、 pumaの公式サンプルには
Typically this is set to the number of available cores
と書いてあるので、基本的にはコア数と同じ値にすると良いでしょう。
1コアの場合ですが、30-40% performance difference between single and clustered mode with one worker · Issue #1387 · puma/pumaというIssueが気になったので、私はWEB_CONCURRENCY=1のときはsingle modeでpumaが動作するようにconfig/puma.rbを変更しています。
diff --git a/config/puma.rb b/config/puma.rb index 0397b892..8c46fc07 100644 --- a/config/puma.rb +++ b/config/puma.rb @@ -8,12 +8,14 @@ else end environment ENV.fetch('RAILS_ENV') { 'development' } -workers ENV.fetch('WEB_CONCURRENCY') { 2 } -preload_app! - -on_worker_boot do - ActiveRecord::Base.establish_connection if defined?(ActiveRecord) +worker_num = ENV.fetch('WEB_CONCURRENCY') { 2 }.to_i +if worker_num > 1 then + workers worker_num + preload_app! + on_worker_boot do + ActiveRecord::Base.establish_connection if defined?(ActiveRecord) + end end plugin :tmp_restart
メモリ消費は少し減りました(ちゃんと測ってない)。worker数が1のclustered modeで起動していると、たまにworkerプロセスが正しく死なずに複数に増えていることがありました。single modeで起動するようにしておくとそういう現象は起きない(はず)なので安心です。
mastodon-streaming.service
ProductionGuideでは、streamingを起動する時に下記のように指定されています。
ExecStart=/usr/bin/npm run start
htop
でプロセスツリーを眺めてみるとなんか深かったので、下記のように変更しました。
ExecStart=/usr/bin/node streaming/index.js
メモリの使用量にどれだけ効果があるかはわかりません…。(ちゃんと測ろう) また、pumaと同様にクラスタ数が1のときはthrongを使わずにworkerを1つだけ起動しています。
diff --git a/streaming/index.js b/streaming/index.js index 83903b89..d7a6617f 100644 --- a/streaming/index.js +++ b/streaming/index.js @@ -480,9 +480,13 @@ const startWorker = (workerId) => { process.on('error', onError); }; -throng({ - workers: numWorkers, - lifetime: Infinity, - start: startWorker, - master: startMaster, -}); +if (numWorkers > 1) { + throng({ + workers: numWorkers, + lifetime: Infinity, + start: startWorker, + master: startMaster, + }); +} else { + startWorker(0); +}
mastodon-sidekiq.service
sidekiqのスレッド数はsidekiqのドキュメントによるとデフォルトで25なのですが、Gargron氏曰く「多すぎ!」ということでMastodonではデフォルト値が5になっています。
ですが、スレッド数が5つだとレスポンスが遅いインスタンスがあると詰まってしまうことがしばしばあります。
pgbouncerを導入したことで、sidekiqのスレッド数が増えてもPostgreSQLのコネクションを使いまわせるようになったため、アグレッシブに増やすことが可能になります。
Environment="DB_POOL=20" ExecStart=/home/mastodon/.rbenv/shims/bundle exec sidekiq -c 20 -q default,1 -q push,1 -q pull,1
DB_POOLの値と、sidekiqのスレッド数は同じにしておきます。sidekiqのスレッド数よりもDB_POOLの値が小さいと、ActiveRecord::ConnectionTimeoutError
が出て再試行ジョブが溜まってしまうことがあります。
-cオプションでスレッド数を指定します。 sidekiqのドキュメントには、50以上はやめといたほうがいいよと書いてあるので程々に増やしましょう。スレッドを増やすほどsidekiqのメモリ消費は激しくなります。何事もバランスが大事ですね。
-qオプションでキューを作ります。このとき、,
に続けてキューの優先度を設定できます。
何も設定していないと、手前のキューが空にならない限り後ろのキューでジョブが実行されないため、程よく指定していきます。(参考: Advanced Options#queues)
とはいえ、現状私がトゥートしても数秒で待機状態のジョブがなくなるため、あんまり意味はなさそうです。
また、pawoo.netではキューのプロセスを分けて起動してるようです(実際に運用してみてわかった、大規模Mastodonインスタンスを運用するコツ)。
mastodon-sidekiq-default.service, mastodon-sidekiq-push.serviceのようにして複数serviceを作成することでプロセスを分けることができます。 CPU、メモリに余裕があれば複数プロセスでsidekiqを動かしてみたいですが、1コア512MBサーバーでは厳しいです。
↓pgbouncerなし/ありで、sidekiqのスレッド数を増やすとどういう差がでるかという図です。 don.crakac.com don.crakac.com
pgbouncerがないと、sidekiqのDB_POOLで指定した数だけpostgresqlのコネクション(=プロセス)が作成されますが、pgbouncerありだと僅かな数のコネクションだけで回してくれます。
カーネルパラメータの調整
sidekiqとpumaがもりもりスワップを使っていくのを抑えるために、vm.swappiness=10
にしてみました。
DBサーバーにおすすめの設定みたいです。
そもそも実メモリが足りていないため、スワップ抑制効果はありませんでした。 ですが、気持ちassets:precompileが速くなった気がします。(未計測)
vm.swappinessについてはLinuxのswappinessは本当にスワップしにくさを設定できるのかという記事にとてもよくまとまっています。
GCパラメータの調整
RubyではGC(Garbage Collection)の挙動を環境変数で調整することが出来ます。起動時に必要なメモリをドバっと割り当て、そこから先は出来るだけ新しくメモリを増やさず、出来るだけ速やかにメモリを解放するように設定します。
module GC (Ruby 2.4.0)を参考に、mastodon-web.service, mastodon-sidekiq.serviceに以下の環境変数を追加しました。
Environment="RUBY_GC_HEAP_INIT_SLOTS=500000" Environment="RUBY_GC_HEAP_GROWTH_FACTOR=1.2" Environment="RUBY_GC_HEAP_GROWTH_MAX_SLOTS=1000000" Environment="RUBY_GC_HEAP_FREE_SLOTS_MIN_RATIO=0.1" Environment="RUBY_GC_HEAP_FREE_SLOTS_MAX_RATIO=0.3" Environment="RUBY_GC_HEAP_OLDOBJECT_LIMIT_FACTOR=1.2" Environment="RUBY_GC_OLDMALLOC_LIMIT_MAX=67108864"
なんとなくスワップの増え方が緩やかになりましたが、時間が経つとやっぱりもりもりスワップしていきます。
paperclipの調整
posix-spawn
Mastodonで画像の処理を担っているpaperclipですが、Optimizing Paperclip Gem for Testing and Productionによると、posix-spawnを追加するといい感じになるようです。
ローカル環境で、Gemfileにgem 'posix-spawn'
追記してbundle install
を実行して、Gemfile.lockを更新します。
出来上がったGemfile, Gemfile.lockを本番環境に反映します。
快適になったような、なっていないような、そんな感じです。
ImageMagickの最適化
paperclipの内部ではImageMagickが呼び出されています。identity
、convert
はどちらもImageMagickを実行しています。
apt-get install imagemagick
でインストールされるものは、quantum-depthが16になっています。
1ピクセルのRGB各色をそれぞれ16bitで扱えるのですが、普通の画像はだいたい各色8bitなので無駄です。
インストールされているImageMagickのquantum-depthは、convert -version
を実行することで確認できます。
$ convert -version Version: ImageMagick 6.8.9-9 Q16 x86_64 2017-07-31 http://www.imagemagick.org
Q16
が、quantum-depthが16であることを表しています。
apt-getでQ8のものをインストールできないのでソースコードからビルドします。 手順は、ImageMagickを弱小鯖用にビルド&インストールするにまとめてあります。
リサイズ時に-define jpeg:sizeを指定する
大きいJPEG画像を小さくリサイズする時、-define jpeg:sizeを指定することによってメモリの消費を抑えることが出来ます。
diff --git a/app/models/media_attachment.rb b/app/models/media_attachment.rb index abc5ab85..eef9d473 100644 --- a/app/models/media_attachment.rb +++ b/app/models/media_attachment.rb @@ -120,6 +120,8 @@ class MediaAttachment < ApplicationRecord [:gif_transcoder] elsif VIDEO_MIME_TYPES.include? f.file_content_type [:video_transcoder] + elsif f.file_content_type == 'image/jpeg' + [:jpeg_processor] else [:thumbnail] end diff --git a/lib/paperclip/jpeg_processor.rb b/lib/paperclip/jpeg_processor.rb new file mode 100644 index 00000000..bc66f379 --- /dev/null +++ b/lib/paperclip/jpeg_processor.rb @@ -0,0 +1,8 @@ +module Paperclip + class JpegProcessor < Paperclip::Thumbnail + def initialize(file, options = {}, attachment = nil) + super + @source_file_options = "-define jpeg:size=#{@target_geometry.width.to_i}x#{@target_geometry.height.to_i}" if @current_geometry.width.to_i > @target_geometry.width.to_i && @current_geometry.height.to_i > @target_geometry.height.to_i + end + end +end
上記2つの調整を行うことで、極端な例ですが、6000x4000のJPEGを変換する際のメモリ消費量を約230.9MBから約19MBに減らすことが出来ました。
GIFを変換するときのメモリ消費をなんとかする
巨大なjpegのリサイズは上記の変更で省メモリに抑えられましたが、メモリがぴょんぴょん跳ねるタイミングがありました。 メモリが跳ねているタイミングのsyslogを見てみると、どうやらGIFの変換が原因ということがわかりました。
手元のMacだと全然メモリ消費しないのになんでだ???と3日くらい頭を抱えていました(
ImageMagickでgifをconvertする時のメモリ消費を何とかしたい)が、ImageMagick/MagickCore/quantize.cのCacheShift = 3
に固定して、ImageMagickを再度ビルドすることでGIF変換時のメモリ消費が落ち着きました。
CacheShift = 3
はmacOS/iOS用の値なのですが、macOS上でちゃんと動いてるしサーバー上でもとりあえず動いたし大丈夫やろってことで本番投入しています。
これにより、GIFの変換に必要なメモリが128MBくらいから8MBくらいになりました。1/16です。すごいですね。
まとめ
512MBで動かすために色々やって、効果があったなあと実感できたものは以下です。
- ImageMagickを頑張る
- メモリ消費がとても減りました
- pgbouncerを導入してsidekiqのスレッド数を増やす
- メモリ消費量を抑えつつジョブがさばける速度が上がるので最高
- pumaをsingle modeで動かす
- 若干メモリ消費が減ります
- GCパラメータ
- Swapが増えにくくなったような気はしますが、まだ調整の余地はありそう
感想
最後に
私が最初にMastodonを知ったのは4月の半ばでした。ぬるかるさんが建てた自宅鯖爆破祭りに参加していた記憶があります。 その後、新生mstdn.jpにアカウントを作ってしばらく経ってから、friends.nicoに移りました。
LTLの空気が一番馴染むのがfriends.nicoでした。23時のテレホタイム、23時55分の2355、日付が変わる際のあけおめラッシュなど、一体感や心地よさを最も強く感じたのがfriends.nicoでした。
friends.nicoのマスコットであるをニコるくんをぐるぐる回すスクリプト書いたりして楽しんでいました
テレホ、あけおめを一番最初に投稿するために、ブラウザとは別に時計を表示して、投稿が完了するまでのラグを考慮しつつ「テレホ」「あけおめ」を投稿していたりなどしました。
そして、9月14日にお一人様インスタンスを立ち上げました。動機としてはfriends.nico上だとLTLへのレスポンスが多めになりがちなので、他鯖の人にフォローされてもコンテキストが伝わらなそうで若干申し訳ないなーということと、個人鯖を建てている人をそこそこ見かけるようになったし自分も試しにやってみるかな―という感じです。
ドキュメントに沿って立ち上げて、ブラウザ越しにアクセスして、実際に動いているのを見て、何とも言えない達成感を味わうと同時に、 自分が立ち上げたインスタンスが他のインスタンスの人達とつながっていくことがとても嬉しかったことを覚えています。
また、色んなインスタンスの鯖缶の皆さんたちをフォローしてみると、どういう改良/改造をしているのかという情報が流れてきてとても勉強になりました。
その後、自分の誕生日(今日)までMastodonに人残ってるかなぁ…続いてるかなぁ…という風に思っていましたが、Mastodonをテーマにしたアドベントカレンダーがたくさん立ち上がり、自分の誕生日にマストドンのアドベントカレンダーを公開することになるとは思いもしませんでした。
Mastodonのコミッタ、コントリビュータのみなさん。各鯖の管理人のみなさん。マストドンを使っている皆さん。ありがとうございます。
誕生日おめでとう、俺。
今後は適当にmaster追従しつつ、4月中に始めていたAndroid向けMastodonクライアントアプリづくりに専念したいなあと思うところです。 以上です。
お一人様インスタンスを建てたドン
さくらのVPS 1コア512MBプランで今のところ動いていますが、いつ死ぬかはわかりません。
メモリは常にswap使っててかなりヤバそうな雰囲気だけど、CPUはかなり遊んでいるのでなんかいい方法ないかなーと思う次第です。
tigで新規ファイルが表示が出来なくなったので、設定を追加したら直った
tigとは?
ターミナル上で使えるgitクライアント。gitのコマンドをガシガシ打っていくよりタイプ数も減るし見やすいので便利。
最近なぜか新しいファイルを表示してくれなくなったのでチョット不便だった。
環境
やったこと
/usr/local/etc/tigrc に以下の行を追加
set status-show-untracked-files = yes
無事表示されるようになった。めでたしめでたし。
DateUtilsでいい感じに時刻表示
Mastodonクライアントを作っていて、API叩いて降ってくる時刻の形式が "2017-07-17T12:24:30.721Z"
となっているのでこれを上手いこと表示する。
val format = "yyyy-MM-dd'T'HH:mm:ss.SSS"; val sdf = SimpleDateFormat(format, Locale.getDefault()) val time = sdf.parse(source).time + TimeZone.getDefault().rawOffset return DateUtils.getRelativeTimeSpanString(time, System.currentTimeMillis(), DateUtils.SECOND_IN_MILLIS)
こういう感じにするとちょうどいい感じになる