アルゴリズム+データ構造勉強会(1)の解答例とレビュー

今週の勉強会の解答例および、その修正です。

解答例

<?php
   $abc=array(46,2,5,39,38,6,24,1,283,3,7,8,-4,4,0,99,100,9,29,9);
   $arr_cnt = count($abc) - 1;
//   print("$arr_cnt\n");
   print("ソート前:");
   for($i=0;$i<20;$i++){
      if($i == $arr_cnt){
         print("$abc[$i]\n");
      }else{
         print("$abc[$i] ");
      }
   }
   sort($abc);
   print("ソート後:");
   for($i=0;$i<20;$i++){
      if($i == $arr_cnt){
         print("$abc[$i]\n");
      }else{
         print("$abc[$i] ");
      }
   }
?>

新人なので「コーディング規約はどうした」というのは置いておくとしまして。動作はするにしても、いくつか直したほうがよさそうです。

PHPの閉じタグは省略する

PHPの閉じタグ「?>」は省略したほうが不具合混入の可能性がなく、安全です。詳しくはググるなど

join()の利用

配列を出力するときに「スペース区切り、ただし末尾で改行」を実現しようと、頑張っています。

   $arr_cnt = count($abc) - 1;
//   print("$arr_cnt\n");
   print("ソート前:");
   for($i=0;$i<20;$i++){
      if($i == $arr_cnt){
         print("$abc[$i]\n");
      }else{
         print("$abc[$i] ");
      }
   }

これで悪いことはないのですが、せっかくPHPを使っているので関数を使って楽をしてみましょう。

   print("ソート前:");
  echo join(' ', $abc);
  echo "\n";

join()は「配列要素を文字列により連結する」関数です。「連結する」というと難しい感じがしますが、言い換えると「区切り文字を使ってくっつける」ということです。これで「スペース区切り」を実現します。
要素が1つの時はどうなる? という疑問がありそうですが、その場合はその要素1つが文字列として返ります。区切り文字は使われません。
区切り文字なので末尾には何もつきませんので、「行末で改行」は単に改行出力になります。

join()を使っての区切り文字実現はよくある定型句なので、覚えておくと便利です。

試行錯誤のコメントは消す

他の人にはむしろ読むときの邪魔になるので、試行錯誤の過程は消しておきましょう。

修正後

結果、こうなります。

<?php
   $abc=array(46,2,5,39,38,6,24,1,283,3,7,8,-4,4,0,99,100,9,29,9);

   print("ソート前:");
   echo join(' ', $abc);
   echo "\n";

   sort($abc); 

   print("ソート後:");
   echo join(' ', $abc);
   echo "\n";

だいぶすっきりしました。

アルゴリズム+データ構造勉強会(1)

社内勉強会として、初級者向けにアルゴリズム+データ構造の勉強会を始めました。全15回、毎週月曜開催なので大学の半期授業ぐらいの長丁場です。

せっかくなので資料を公開します。

PHPで書かれたアルゴリズム本って見つからないんですよね。需要ないんでしょうか。

linuxファイル操作:特定の行から末尾までを取得する方法

○行目からのテキストを取得したい、などの操作が時々ありますが、headとtailを駆使すれば……大変なので、tailのオプション使います。-nオプションは取得行数指定ですが、tailの-nは「tail -n +1234」のように+を付けると1234行目から残り全部が出力されます。

続きを読む

apacheのログローテートには再起動を伴う

今日の一幕。

Aさん「今日の4:30頃のport80停止は何か作業を行った結果でしょうか」
Bさん「時間的にはログローテートのタイミングですね」
Aさん「そうなんですね。でもなぜ今日に限ってアラートが上がったのでしょうか」
Bさん「centosのログローテート(正確には日次cron)は4:30開始です。ログローテートの仕組みはファイル名を変えての『apache再起動』です。監視に引っかかるぐらいの時間がapache再起動にかかればこうなりますが……」
Aさん「起動しているので問題ないですかね……時間がかかった理由は気になりますが……」
Bさん「あるいはネットワーク遮断が起きればこういう出方をするかもしれないです」

centos標準のhttpdはlogrotateという仕組みを使ってログローテートを行います。これはcronで毎日起動しますが、これは4:30に起動され、httpdの場合は再起動を伴います(※若干のウソがあります)。
そのため、httpdの設定を変えて再起動しないなど手抜きすると翌日に動いていないなんてことになるので、意外と注意が必要な事項です。

Bさん「まったく別のサーバにも同じ内容のアラートがあったorz」
Bさん「監視側の誤検知のようです」

オーノー。そんなこともあります。

サーバの負荷を調べるコマンド集その2:ディスクI/O、ネットワークI/Oの確認

サーバの負荷を確認する、サーバの負荷を調べるコマンド集その1の続きです。

ディスクI/Oの確認:sar、dstat

ディスクI/Oがどうであるか、一番手っ取り早いのがsarです。

$ sar
 Linux 2.6.32-220.7.1.el6.x86_64 (feanor.localdomain)     2012年07月07日     _x86_64_    (2 CPU)

 00時00分01秒       CPU     %user     %nice   %system   %iowait    %steal     %idle
 00時10分01秒       all     12.29      0.00      4.91      0.14      0.00     82.66
 00時20分01秒       all      6.21      0.00      4.16      0.04      0.00     89.59

「%iowait」の数値が他と比べて大きければ、ディスクI/Oに引きずられている可能性が高いです。時系列に並ぶので、どの時刻から上がっているか、定期バッチ処理が契機の時などはわかりやすいです。

契機がなく定常的に負荷が高い場合、現在どのプロセスが高いかを確認します。「dstat -al –top-bio」です。

$ dstat -al --top-bio
----total-cpu-usage---- -dsk/total- -net/total- ---paging-- ---system-- ---load-avg--- ----most-expensive----
usr sys idl wai hiq siq| read  writ| recv  send|  in   out | int   csw | 1m   5m  15m |  block i/o process   
 29   4  50  16   0   2| 914k 1994k|   0     0 | 210B   84B| 104  9732 |1.19 1.28 1.32|init [3]    173k 2032k
 13   4  49  33   0   3|1504k  164k|1068k 2282k|   0     0 |8212    13k|1.19 1.28 1.32|nfsd        324k    0
 13   3  76   5   0   2|1852k  100k|1669k 4248k|   0     0 |7286    11k|1.10 1.26 1.31|nfsd        304k    0
 29   8  44  14   1   5|1928k   84k|1444k 4733k|   0     0 |  13k   20k|1.10 1.26 1.31|nfsd        316k    0
 28   6  45  18   0   5| 272k  148k|1643k 3038k|   0     0 |  12k   19k|1.10 1.26 1.31|nfsd        104k    0

コマンドがない場合は、centosの場合はepel導入後「yum install dstat」で幸せになれます。
vmstatのように、1秒ごとに1行ずつ表示されていきます。最初の1・2行は表示がなんだかおかしいのですが、3行目あたりから見ると安定します。
見るべきは一番右の「block i/o process」で、これに出てくるプロセスがそのタイミングで一番I/O負荷をかけているプロセスです。これでいうとnfsdをなんとかしてやろう、ということになります。

ネットワークI/Oの確認:dstat

ネットワークI/Oの負荷が問題になる場合はzabbix等の監視ソフトが導入されている場合が多いのでコマンドで頑張るシーンはあまりないとは思いますが、dstatの「net/total」の欄がネットワークの通信量になります。これが回線契約の上限値にはりつきっぱなしになっているなどあれば、ネットワークの見直しが必要になります。

ネットワークを使っているプロセスが特定できずに困ったという経験がないためプロセスを特定するちょうど良いコマンドは知らないのですが、ネットワークだけを使うというのはルータでもない限りあまり考えられないので、topなどでCPUなりを使っているプロセスを特定するとだいたい特定できます。

さいごに

緊急対応の場合はアプリケーションの特性であるなどを知っておかないと迅速な対応はできないので上記コマンドだけでは難しいものがありますが、普段からずっと重いなどの場合はこれらのコマンドでおおよそ原因プロセスを特定できています。プロセスを特定できれば「どこから手を付ければいいかわからない」ということにならず、「これこれを改善すれば効果が期待できる」と言い切りやすい状態になると思います。

サーバの負荷を調べるコマンド集その1:CPUの確認

1つのサーバに複数のサービス(WebとDBとか)が乗っていると、負荷が高いときにどれが原因なのか、原因のように見せかけて別の何かに引っ張られているだけなのか、よくわからなくなる場合があります。そんなときに手がかりになるコマンドをご紹介します。

「負荷が高い」とは

サーバにとって「負荷が高い」とは、サーバ資源の枯渇をさします。具体的には

  • CPUを使い切っている
  • ディスクI/Oを使い切っている
  • ネットワークI/Oを使い切っている
  • (メモリを使い切っている)

がwebサービスでの主要因です。他にもありますが、これで9割がた抑えられます。

メモリをカッコ書きにしたのは、メモリを使い切るとスワップが激しく稼働しだしてディスクI/Oを使い切ってしまうというのが負荷の原因なので、分類としては最終的にディスクI/Oに入ってしまうからです。しかし負荷のよくある原因の1つなので真っ先に監視対象になります。

CPUの確認:uptime、w、top、sar

uptimeはロードアベレージの確認に使います。

$ uptime
 15:45:16 up 632 days, 17:09,  1 user,  load average: 1.32, 0.68, 0.56

注目すべきは「1.23」の部分で、この部分がCPUスレッド数より大きいようであれば、処理をさばき切れていません。小さければ処理待ちは発生していないので、アプリケーションチューニングをがんばります。

CPUスレッド数がわからない場合は「cat /proc/cpuinfo」でprocessorの数を確認しましょう。

$ cat /proc/cpuinfo | grep processor | wc
      2       6      28

この場合は2個です。

wもロードアベレージの確認ですが、1文字で入力できるのでuptimeより6倍楽です。

$ w
 15:49:34 up  1:10,  2 users,  load average: 0.08, 0.06, 0.01
USER     TTY      FROM              LOGIN@   IDLE   JCPU   PCPU WHAT
takekosh tty1     :0               02:26    4:24m  9.75s  0.02s pam: gdm-password
takekosh pts/0    :0.0             02:26   13:16m  0.11s  0.11s bash

topはどのプロセスがCPUを使っているかを確認するのに使います。

top - 15:51:37 up  1:12,  4 users,  load average: 0.06, 0.05, 0.00
 Tasks: 183 total,   2 running, 181 sleeping,   0 stopped,   0 zombie
 Cpu(s):  0.3%us,  0.3%sy,  0.0%ni, 98.5%id,  0.6%wa,  0.0%hi,  0.2%si,  0.0%st
 Mem:   2054880k total,   640624k used,  1414256k free,    20484k buffers
 Swap:  4128760k total,        0k used,  4128760k free,   299380k cached

 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
 3312 takekosh  20   0 15020 1252  920 R  0.7  0.1   0:00.04 top
 2116 root      20   0  130m  29m 7436 S  0.3  1.5   0:10.13 Xorg
 2477 root      20   0 40328  612  364 S  0.3  0.0   0:02.11 udisks-daemon
 2899 takekosh  20   0  310m  15m  10m S  0.3  0.8   0:05.88 gnome-terminal

「%CPU」の部分が大きいプロセスがCPUを使っています。重くなっている処理ですが、このプロセスが原因ではない場合もあります。

sarは10分ごとのサーバ状況を表示します。

$ sar
 Linux 2.6.32-220.7.1.el6.x86_64 (feanor.localdomain)     2012年07月07日     _x86_64_    (2 CPU)

 00時00分01秒       CPU     %user     %nice   %system   %iowait    %steal     %idle
 00時10分01秒       all     12.29      0.00      4.91      0.14      0.00     82.66
 00時20分01秒       all      6.21      0.00      4.16      0.04      0.00     89.59

コマンドがない場合は「yum install sysstat」で幸せになれます。

このうち「%user」が高ければ「CPUを使い切っている」になります。その時はさっきのtopで見たプロセスを調整することになります。「%iowait」が高い場合はCPUは「他に引きずられて高くなっている」になります。その場合はディスクI/Oを疑ってみます。

時系列での表示なので、負荷の上がった時間帯に走り始める処理(たとえばバックアップとか)を知っていると、それを疑うと近道です。近道ですが、あくまでも推測になので、ときどき遠回りになります。

長くなったので一旦切ります。次はディスクI/Oの確認です。

続き:サーバの負荷を調べるコマンド集その2

yumでインストールできるyamlライブラリ:php-symfony-YAML

フレームワーク外でも簡単にyamlを使いたく、かといってphpバンドルのyamlライブラリを使うのもいまいちな気がしたので、yumでインストールするyamlライブラリを使いました。やや古いライブラリのようですが、今回は機能より気楽さです。以下、使い方です。

続きを読む

新しいさくらのVPS(v3)でファイルシステムの比較をしてみる

新しくなったさくらのVPS(v3)が欠品を起こすほどに人気で、すごいですね。さくらは安定なので私もよく使います。

CentOSが6になってからext4が標準で入るファイルシステムになりましたが、インストール時にxfsも選択できます。それぞれの特性は仕様から考えることはできますが、仮想環境下ではホストマシンの設定次第でストレージ性能が変わったりするので試してみました。

試験概要:10万個のファイルを作り、「ls」と「ls -l」の速度を確認する

比較対象:ext3、ext4、xfs

結果はext3、ext4はほぼ同じ、xfsがやや優位という感じですが、0.1秒ほどしか変わっていません。もうちょっと差が出ると思ったのですが、やはりやってみないとわからないですね。xfsは故障時の復旧でext4に劣るので、どちらを選択するかは載せるアプリケーション次第になります。

以下は試験内容です。


パーティションはインストール時にそれぞれ切りました。LVM配下になっています。
マウントオプションもインストール時のままとしました。

/dev/mapper/vg_wwwxxxxxx-LogVol04 /opt/ext3               ext3    defaults        1 2
/dev/mapper/vg_wwwxxxxxx-LogVol02 /opt/ext4               ext4    defaults        1 2
/dev/mapper/vg_wwwxxxxxx-LogVol03 /opt/xfs                xfs     defaults        1 2

10万個のファイルを作るスクリプトは次のものになります。0バイトのファイルを作ってもなんなので、1バイト以上入れてみました。

<?php

for ($i = 1; $i <= 100000; $i++) {
`echo $i > $i`;
}

それぞれのパーティションにtestディレクトリを作り、その下で作成しました。ファイル作成時のスピードは次のようになりました。

◆ext3
real    3m17.071s
user    0m52.997s
sys     2m19.586s

◆ext4
real    3m16.484s
user    0m53.057s
sys     2m18.849s

◆xfs
real    3m22.518s
user    0m53.080s
sys     2m25.700s

さて、「ls」と「ls -l」の実行ですが、ネットワーク転送に影響されてはいけないので「time ls > /dev/null」「time ls -l > /dev/null」で実行します。5回実行してrealが1番速いもの、遅いものを無視してのこり3つで平均を取りました。

◆ext3
# time ls > /dev/null
real    0m0.211s
user    0m0.134s
sys     0m0.075s

# time ls -l > /dev/null
real    0m1.269s
user    0m0.481s
sys     0m0.789s

◆ext4
# time ls > /dev/null 
real    0m0.210s
user    0m0.136s
sys     0m0.074s

# time ls -l > /dev/null 
real    0m1.282s
user    0m0.457s
sys     0m0.790s

◆xfs
# time ls > /dev/null 
real    0m0.090s
user    0m0.068s
sys     0m0.021s

# time ls -l > /dev/null 
real    0m1.147s
user    0m0.429s
sys     0m0.717s

OpenswanでSingle DESを使う方法

最近IPSecを設定する機会がありました。OpenswanはデフォルトではSingle DESをサポートしてないのですが、相手方がSingle DES前提でした。歴史ある機器だとデフォルトがSingle DESなのですね。
暗号化強度としては低いのですが、それ前提でよかったのでそのまま進めました。が、意外とSingle DESの設定の仕方が記事として見つからなかったのでここに記録します。環境は

  • openswan 2.6.37(現在の最新)
  • CentOS 5.5

です。

結論を書くと、コンパイルオプションを設定するファイル「Makefile.inc」を2か所書き換えます。

# should we include all manner of known to be broken/weak?
# use this only if you are building some kind of a testing
# device. Normal use does not need any of this.
USE_WEAKSTUFF?=true

# Build algorithms that don't even encrypt (also must set WEAKSTUFF)
# unless you are doing negative testing, turning this on is foolish.
USE_NOCRYPTO?=true

「USE_WEAKSTUFF」と「USE_NOCRYPTO」の2つをtrueにします。これで「ike=des-md5;modp768」など、des(single DES)の設定が可能になります。

このとき、WEAKSTUFFだけをtrueにしてUSE_NOCRYPTOはfalseのままdesを使うと、エラーメッセージではなくsegmentation faultになります。NOCRYPTO(暗号なし)の設定なのでfalseのままで良いと勘違いして、ずいぶん苦しめられました。Single DESなんか使うな、という記述がドキュメントに散見されたので、openswan開発者にとってSingle DESはもはや暗号とは呼べないんでしょうね。