We Are GRIPHONE / サーバー

ある日時より前のログデータの削除を二分探索を使って効率的にやってみた

MoriKensukePosted by

この記事はGRIPHONE Advent Calendar 2019 19日目の記事です。

こんにちは。グリフォンでサーバーサイドエンジニアをしている森と申します。
今回は古くなったログデータの削除を二分探索を使って効率化した話をしたいと思います。

はじめに

ゲーム運用ではカスタマーサポートや不具合の調査、統計用にログを取っておくケースが多いと思います。
私はゲーム運営のプロジェクトに所属しているのですが、そこでも色々なログを保存しています。

一部のログはMySQLのテーブルにレコードを保存していっているのですが、放っておくとログは溜まっていくばかりなので、「ある日時より前のログは削除したい」という要望が出ました。

ログテーブルのカラムにはログの生成時間が入っているので、削除自体は難しいことはないのですが、ログテーブルは件数が多く、数億件以上レコードが入っているものも複数あるため、1件1件レコードを見ながらある日時より前かどうかを判定しながらログを削除していくと非常に時間がかかってしまいます。
そこで、二分探索を使って効率的にデータを削除してみることにしました。

ログを格納するテーブルについて

今回削除するテーブルは以下のような構成になっています。

CREATE TABLE IF NOT EXISTS `example_log` (
  `id`                   BIGINT      UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'ID',
  ...
  ...
  `create_time`          DATETIME    NOT NULL                         COMMENT 'ログ作成日時',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='ログテーブルの例';

create_timeカラムにはログの生成時刻が入っており、idはAUTO_INCREMENTで数字の連番がふられていきます。

このテーブルはレコードA, Bがある時、「A.id <= B.id であるならば、A.create_time <= B.create_timeである」という性質を持っています。なので、idが大きい方が新しく生成されたログということになります。
この性質はログをテーブルにinsertする時の時間をそのままcreate_timeにいれておけば自然に満たすと思います。
idには主キーインデックスが貼ってあるので、create_timeの古い順にソートをすることは低コストで行えます。
なので、あとは「create_timeがある時刻より小さい中で、一番大きいレコードのid」を見つければそれ以下のidのレコードは全て削除することができることがわかります。

ロジック

簡単なのは、以下のようにクエリで求める方法です。

SELECT id FROM example_log WHERE create_time <= (ある日時) ORDER BY id DESC LIMIT 1;

しかし、create_timeにインデックスが貼られていないため、単純に「create_time <= （ある日時）」という条件だと全件探索になり時間がかかります。

さて、あなただったらこのテーブルに対し、どのようにしてこのようなレコードを見つけますか？

例えば、以下のようなアルゴリズムが考えられます。

  1. idの古い順に1件ずつ見ていく
  2. create_timeが一定より古かったら次のidのレコードをみる
  3. create_timeが一定より新しかったら処理を終了

idが古い方に目的のレコードがあればすぐ終わりますが、idが新しい方に目的のレコードがある場合は結局ほぼ全件調べることになってしまいます。
このようなソートされたデータ列に対しては効率よく目的のデータの一を見つけるアルゴリズムがあります。それが二分探索です。

二分探索はソートされたデータ列に対し、その中央のデータを調べて検索範囲をどんどん半分にしていく探索アルゴリズムです。とても有名なアルゴリズムなのでご存知の方も多いかと思います。一部の言語ではライブラリに二分探索を行う関数が用意されてたりします。
二分探索については以下のサイトで詳しく説明されていますので興味ある方はご覧ください。

二分探索の魅力はなんといっても探索回数の少なさです。
N件のレコードがある場合、全件探索だとN件のレコードを調べる必要がありますが、二分探索だと \(log_{2} N\) 件のレコードを調べるだけで済みます。
例えば、10億件のレコードがある場合は全件探索だと10億レコード調べる必要があるのに対し、二分探索だとわずか30レコード調べるだけで目的のレコードを見つけることができます。

example_logをidでソートすると、create_timeについてもソートされた列を得ることができます。これは「A.id <= B.id であるならば、A.create_time <= B.create_timeである」という性質のためです。
よって、二分探索を行うことによって、「create_timeがある時刻より小さい中で、一番大きいレコードのid」を求めることができます。

サンプルコード

以下はPHPで書いた二分探索のコードです。getTargetIdRange関数にexample_logテーブルのレコードの最小のidと最大のidを渡すと、二分探索で削除して良い範囲のidの配列を返します。nullの場合は削除できるidがありません。

<?php

    /**
     * 削除対象のidの範囲を取得
     * ループを回す計算量はO(log($maxId - $minId))
     *
     * @param int $minId テーブル内のレコードの最小のid
     * @param int $maxId テーブル内のレコードの最大のid
     *
     * @return int[]|null
     */
    protected function getTargetIdRange(int $minId, int $maxId)
    {
        // getThresholdCreateTimeはそれ以前は削除していいログの日時を返す関数
        $thresholdCreateTime = $this->getThresholdCreateTime();

        // 消してよいレコードの中で最大のidを探索する
        $high = $maxId;
        $low = $minId;

        while ($low < $high) {
            $middle = (int)ceil(($high + $low) / 2);

            // canDeleteTargetRecordは$middleのidのレコードのcreate_timeが$thresholdCreateTime以下ならtrue, そうでなければfalseを返す関数
            if ($this->canDeleteTargetRecord($middle, $thresholdCreateTime)) {
                $low = $middle;
            } else {
                $high = $middle - 1;
            }
        }

        $middle = (int)ceil(($high + $low) / 2);

        if ($middle == $low) {
            // 削除できるレコードが1件もない場合の例外処理
            if (!$this->canDeleteTargetRecord($middle, $thresholdCreateTime)) {
                return null;
            }
        }

        return [$minId, $middle];
    }

終わりに

今回は二分探索を用いた高速なデータ検索を紹介しましたがいかがでしたでしょうか。
アルゴリズムやデータ構造を使うことで驚くほど高速化ができますので、遅い処理に困った時はみなさんも色々使ってみてください！

このエントリーをはてなブックマークに追加