シェルスクリプトでだいたい1時間の間隔であれをやる

[前の記事](http://qiita.com/piroor/items/6300e665bc8ac314211b)の続き？です。

「1時間間隔で決まった処理を行う」という目的だと、普通に考えたらまあ`crontab`を使う場面ですよね。

だから素直にそうしときゃいいんだけど、[シス管系女子](http://system-admin-girl.com/)の[広報用アカウント](https://twitter.com/sysadgirl_mint)の運用で使ってる[シェルスクリプト製のTwitter用bot](https://github.com/piroor/tweetbot.sh "piroor/tweetbot.sh")で自発的な自動投稿をやらせるにあたって、どういうわけか「きっかり同じ時間間隔じゃなくて、確率でちょっとだけ揺らぎを持たせたい。その方が人間くさいよね。」と思ってしまって、それをやるのに一苦労しました……という話です。これは。

### 目指す状態

そもそも「きっかり同じ時間間隔じゃなくて、ちょっとだけ揺らぎをもって定期実行したい」というのは、一体どういう状態のことを指しているのか。
これをはっきりさせないことには話が始まりません。

僕が思ってる事をアスキーアートで図にすると以下のようになります。

    00:00 基準時刻
      |
    00:15
      |
    00:30
      |
    00:45
      |          ￣＼
    01:00 目標時刻   ＞だいたいこの範囲で必ず1回実行する
      |          ＿／
    01:15
      |
    01:30
      |
    01:45
      |          ￣＼
    02:00 目標時刻   ＞だいたいこの範囲で必ず1回実行する
      |          ＿／
    02:15
      |
    02:30
      |

人間の行動で言うと、こんな感じ。

 * 時計を持って「1時間に1回これをやるように」と言われて、時計を見てその時刻に近かったらそれをやる。
 * ちょっと早くても「まぁもうやっちゃってもいいか」ということでやる。
 * ちょっと遅くても「まぁこのくらいの遅れは大丈夫でしょ」ということでやる。
 * 「やらない」という選択肢は無い。「やべっ時計見落としてた！」と気がついたらその時点で慌ててそれをやる。

ちょっとばかり時間にルーズな人の取るような行動、という事ですね。

これをもうちょっと厳密に、コンピュータにも分かりやすいであろう表現に直すと、以下のように言えるでしょうか。

 * 目標時刻の前後N分の範囲の時間帯を、処理を実行する可能性がある時間帯とする。
   * それより早かったり遅かったりしたら実行しない。
 * 目標時刻に近ければ近いほど実行の確率は高く、遠ければ遠いほど実行の確率は低い。
   * 目標時刻ちょうどで最大確率、目標時刻のN分前およびN分後の時点で最低確率とし、その間は確率が線形に変化するものとする。
 * ただし、その範囲の時間帯が過ぎようとしている時にまだ1回も処理が実行されていなければ、時間帯の終わりで必ず実行する。
 * 計算は分単位で行う。（cronjobでも1分未満の指定はできないので）

実行確率をパーセンテージで算出できれば、あとは[前のエントリ](http://piro.sakura.ne.jp/latest/blosxom/webtech/2015-12-30_random.htm "Latest topics &gt; シェルスクリプトでランダムにあれをやる - outsider reflex")でやった「何パーセントの確率であれをやる」がそのまま使えます。

となると、問題は「どうやって実行の確率を計算するか」という話になります。

### 今の時刻が目標時刻から何分ずれているかを計算する

先の定義に基づいて「ある時点での実行確率」を計算しようと思った時に、時刻を時刻の形式のまま扱おうとするとややこしいというか自分にはお手上げなので、「その日の0時0分を起点として、そこから何分経過したか」を使って計算していこうと思います。

そのために、こんな関数を用意しました。

    # "03:20"のような時刻を与えると、00:00からの経過分数を出力する
    time_to_minutes() {
      local now="$1"
      local hours=$(echo "$now" | sed -r 's/^0?([0-9]+):.*$/\1/')
      local minutes=$(echo "$now" | sed -r 's/^[^:]*:0?([0-9]+)$/\1/')
      echo $(( $hours * 60 + $minutes ))
    }

これに与える現在時刻は、コマンド置換とdateコマンドを使って`$(date +%H:%M)`とします。
例えば現在時刻が07:58なら、以下のような出力が得られます。

    $ time_to_minutes $(date +%H:%M)
    478

これを「処理を実行したい時間間隔（分）」で割った余りを得ると、現在時刻が目標時刻から何分ずれているかが分かります。
60分間隔ならこうです。

    $ interval=60
    $ lag=$(( 478 % $interval ))
    $ echo $lag
    58

58分ずれている……という結果ですが、これはどっちかというと「目標時刻からマイナス方向に2分ずれている」と扱いたいところです。
なので、実際のずれが実行間隔の半分よりも大きい場合は「マイナス方向にN分のずれ」と見なすようにします。

    $ half_interval=$(( $interval / 2 ))
    $ [ $lag -gt $half_interval ] && lag=$(( $interval - $lag ))
    $ echo $lag
    2

これで「目標時刻ピッタリから何分ずれているのか」が求まったので、次はいよいよ確率の計算です。

### 今の時刻での実行確率を計算する

目標時刻ピッタリで確率100％としてしまうとそこで必ず実行されてしまうので、目標時刻ちょうどでの最大の確率を90％、許容されるずれの最大時点での最低の確率を10％とすることにします。

全体の振れ幅は10％から90％までの「80」ですので、「目標時刻ちょうどで100％、目標時刻からのずれが許容範囲の最大になった時を0％」とした割合に80をかけた結果に10を足せば、確率は10％から90％までの範囲に収まることになります。
式にすると、こうです。

    $ probability=$(( (($max_lag - $lag) / $max_lag) * 80 + 10 ))
    $ echo $probability
    10

……おや？ どうも計算結果がおかしいですね。
実は算術展開の`$((～))`は整数のみの計算なので、計算の過程で小数が出てくると小数点以下切り捨ての計算になってしまうのです。

こうならないようにするには、小数が出てこないように注意して計算するか、小数があっても大丈夫な計算方法を使う必要があります。
例えば、先に100倍してパーセンテージを求めてから後で100で割るという方法を取るなら以下のようになります。

    $ probability=$(( (($max_lag - $lag) * 100 / $max_lag) * 80 / 100 + 10 ))
    $ echo $probability
    58

小数として計算するのであれば、数値計算用のコマンドの`bc`を使います。
これは、標準入力で与えられた式の計算結果を出力するコマンドなのですが、`scale=1;`という指定で計算時の小数点以下の桁数を指定すると、小数部を考慮した計算結果を返してくれます。

    $ probability=$(echo "scale=1; (($max_lag - $lag) / $max_lag) * 80 + 10" | bc)
    $ echo $probability
    58.0

ただし、`if [ ... ]`での条件分岐では今度は整数しか扱えないので、出力される計算結果の小数部は取り除いておく必要があります。
これはsedで行えます。

    $ probability=$(echo "scale=1; (($max_lag - $lag) / $max_lag) * 80 + 10" | bc | sed -r -e 's/\.[0-9]+$//')
    $ echo $probability
    58

ということで、ここまでをまとめて「算出した実行確率を出力する関数」にしてみましょう。

    interval=60
    half_interval=$(( $interval / 2 ))
    max_lag=5
    
    calculate_probability() {
      local target_minutes=$1
    
      local lag=$(($target_minutes % $interval))
      [ $lag -gt $half_interval ] && lag=$(($interval - $lag))
    
      local probability=$(( (($max_lag - $lag) * 100 / $max_lag) * 80 / 100 + 10 ))
      # 最小の実行確率より小さい時＝実行する可能性がある範囲の
      # 時間帯の外の時は、確率0％とする
      if [ $probability -lt 10 ]
      then
        echo 0
      else
        echo $probability
      fi
    }

### 同じ時間帯では重複実行しない

単にこの確率に基づいて実行するかどうかを決めるだけだと、00:55から01:05までの範囲で「実行時刻が揺らぐ」のではなく「その範囲で、確率次第で何度も実行される」という結果になります。
そうしないためには、同じ時間帯の中での再実行を防ぐ必要があります。

そのためには、最後に処理を実行した時刻を保持しておいて、現在時刻が最終実行時刻から一定の範囲内にある時は問答無用で処理をスキップする、ということになります。
とりあえず、最終実行時刻（として、00:00からの経過時間）を保存するようにしてみます。

    current_minutes=$(time_to_minutes $(date +%H:%M))
    probability=$(calculate_probability $current_minutes)
    if [ $(($RANDOM % 100)) -lt $probability ]
    then
      # ここで定時処理を実行
      echo $current > /path/to/last_done
    fi

ここで保存した値を次の実行の可否の判断時に使うのですが、「最後の実行からN分間は絶対に実行しない」という条件を加えても良ければ、以下のようにできます。

    current_minutes=$(time_to_minutes $(date +%H:%M))
    
    forbidden_minutes=10
    last_done=$(cat /path/to/last_done)
    if [ "$last_done" != '' ]
    then
      delta=$(($current_minutes - $last_done))
      [ $delta -le $forbidden_minutes ] && exit 0
    fi
    
    ...

現在時刻から最後の実行時刻を引いた結果の「最終実行時刻からの経過時間」を求めて、それが指定の範囲内であれば何もしないで終了するということです。
比較の演算子が`-lt`（`＜`）ではなく`-le`（`≦`）である点に注意して下さい。
`-lt`で比較してしまうと、00:55に実行してから10分後の01:05ちょうどの時点で「10分未満の範囲で実行されていないので、再実行してよい」と判断されてしまいます。

ただ、これだけだと日付をまたいだ時に判定が期待通りに行われません。
最後の実行時刻が例えば前日23時ちょうどだったとすると、`last_done`は23*60=1380ですが、現在時刻が00:04だったとすると4-1380=-1376になってしまって、負の数は「何分間は再実行しない」という指定＝正の数よりも必ず小さいので、永遠に再実行されないことになってしまいます。

なので、現在時刻から最終実行時刻を引いた結果が負の場合は、「最終実行時から0時までの経過時間」と「0時から現在までに経過した時間」の和を「最終実行時刻からの経過時間」として使う必要があります。

    current_minutes=$(time_to_minutes $(date +%H:%M))
    
    forbidden_minutes=10
    last_done=$(cat /path/to/last_done)
    if [ "$last_done" != '' ]
    then
      delta=$(($current_minutes - $last_done))
      if [ $delta -lt 0 ]
      then
        one_day_in_minutes=$(( 24 * 60 ))
        delta=$(( $one_day_in_minutes - $last_done + $current_minutes ))
      fi
      [ $delta -le $forbidden_minutes ] && exit 0
    fi
    
    ...


### その時間帯で投稿が無い時は時間帯の最後のタイミングで必ず実行する

ここまで来たらあともう一息。
最後は「その時間帯で必ず1回は実行する」という要件です。

とはいえ、これはそんなに難しく考えなくても大丈夫。
前項の段階で「指定の範囲内の時間での再実行はしない」という判定が既に行われているので、その判定の後であれば、「実行するべき時間帯の最後の瞬間で、その時間帯の中ですでに実行済みである」という場面はあり得ない事になります。
なので、単純に「今この瞬間は、実行しても良い時間帯の範囲の最後の瞬間かどうか？」を判断して、そうであれば確率100％で実行するということにすればいいです。

    current_minutes=$(time_to_minutes $(date +%H:%M))
    
    forbidden_minutes=10
    last_done=$(cat /path/to/last_done)
    if [ "$last_done" != '' ]
    then
      delta=$(($current_minutes - $last_done))
      if [ $delta -lt 0 ]
      then
        one_day_in_minutes=$(( 24 * 60 ))
        delta=$(( $one_day_in_minutes - $last_done + $current_minutes ))
      fi
      [ $delta -le $forbidden_minutes ] && exit 0
    fi
    
    # 目標時刻からのずれを計算
    lag=$(($current_minutes % $interval))
    if [ $lag -eq $max_lag ]
    then
      # ずれが、許容されるずれの最大値と等しければ、今がまさに
      # その時間帯の最後の瞬間である。
      probability=100
    else
      probability=$(calculate_probability $current_minutes)
    fi
    
    ...

### まとめ

ここまでのコード片を全てまとめた物が、以下になります。

    time_to_minutes() {
      local now="$1"
      local hours=$(echo "$now" | sed -r 's/^0?([0-9]+):.*$/\1/')
      local minutes=$(echo "$now" | sed -r 's/^[^:]*:0?([0-9]+)$/\1/')
      echo $(( $hours * 60 + $minutes ))
    }
    
    interval=60
    half_interval=$(( $interval / 2 ))
    max_lag=5
    
    calculate_probability() {
      local target_minutes=$1
    
      local lag=$(($target_minutes % $interval))
      [ $lag -gt $half_interval ] && lag=$(($interval - $lag))
    
      local probability=$(( (($max_lag - $lag) * 100 / $max_lag) * 80 / 100 + 10 ))
      if [ $probability -lt 10 ]
      then
        echo 0
      else
        echo $probability
      fi
    }
    
    current_minutes=$(time_to_minutes $(date +%H:%M))
    
    forbidden_minutes=10
    last_done=$(cat /path/to/last_done)
    if [ "$last_done" != '' ]
    then
      delta=$(($current_minutes - $last_done))
      if [ $delta -lt 0 ]
      then
        one_day_in_minutes=$(( 24 * 60 ))
        delta=$(( $one_day_in_minutes - $last_done + $current_minutes ))
      fi
      [ $delta -le $forbidden_minutes ] && exit 0
    fi
    
    lag=$(($current_minutes % $interval))
    if [ $lag -eq $max_lag ]
    then
      probability=100
    else
      probability=$(calculate_probability $current_minutes)
    fi
    
    if [ $(($RANDOM % 100)) -lt $probability ]
    then
      # ここで定時処理を実行
      echo $current > /path/to/last_done
    fi

人間くさい振る舞いをする何かを作る時の参考にしてみて下さい。

### 追記：もっと単純なやり方

コメントで、以下のようにcronjobを設定すれば良いのでは？とのご指摘がありました。

    55 * * * * sleep $(( $RANDOM \% 10 ))m; (実行したい処理)

実行の可能性がある時間帯の最初の瞬間に`sleep`を呼び、何秒間待つかは0～10分の間でランダムに決定する。その後、やりたい処理を実行する。という方法です。

「指定の時間間隔ちょうどの実行確率を最も高くしたい」「その時間帯の最初の瞬間から最後の瞬間までの間に運用を開始した時も、すぐに動作させたい」といったいくつかの要件を除外すれば、この方法が最もシンプルですね。
というか最初この指摘を見た時には「完全に置き換え可能じゃん！」とすら思ってしまいました。
（よくよく見返して、要件のいくつかがカバーされていない事にようやく気づくレベル）

無駄に複雑な要件を全て満たそうとすると手間がかかるけれども、要件の8割9割ほどを満たせれば良いという割り切りができれば手間を大きく減らせる場合がある、「そもそも本当にその要件は必要なの？」というレベルからの再考次第で実現手法を大きく簡素化できるという、いい例だと思いました。
そのあたりの絞り込みが足りないままこの記事を世に出してしまって、お恥ずかしい限りです……。

### 2017年10月5日追記：より正しい解決

[コメント欄で、原理の説明やシェルスクリプトの場合の実装例も含む素晴らしいフォローアップを頂きました](https://qiita.com/piroor/items/8682faddd4b0c7d397a1#comment-8644926a4dc57fb5c746)。ぜひそちらも併せてご覧下さいませ。


（この記事の内容は[自サイトのエントリ](http://piro.sakura.ne.jp/latest/blosxom/webtech/2016-01-03_nocronjob.htm)の転載です）