Pythonでログストレージシステムを設計する方法

ここでは、各ログが一意のIDとタイムスタンプを持つログデータを扱うことを想定します。タイムスタンプは「年:月:日:時:分:秒」という形式の文字列で、たとえば「2019:01:01:23:59:59」のように表されます。すべてのフィールドはゼロ埋めされた10進数です。

このようなログを効率的に管理するため、以下の2つの機能を持つログストレージシステムを設計します。

• void Put(int id, string timestamp): ログの一意なIDとタイムスタンプを受け取り、ストレージシステムに保存します。
• int[] Retrieve(String start, String end, String granularity): startからendまでの範囲内にあるタイムスタンプを持つログのIDを返します。granularityパラメータは比較に使用する時間の粒度を指定します。たとえば、start = "2019:01:01:23:59:59"、end = "2019:01:02:23:59:59"、granularity = "Day" の場合、「2019年1月1日から1月2日の範囲内」にあるログを検索することを意味します。

入力例と期待される出力

次のような操作を行った場合を考えてみましょう。

put(1, "2019:01:01:23:59:59");
put(2, "2019:01:01:22:59:59");
put(3, "2018:01:01:00:00:00");
retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Year");
retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Hour");

このとき出力は以下のようになります。

• 最初のretrieveでは [1, 2, 3] を返します。granularityが「Year」のため、2018年〜2019年の範囲内にあるすべてのログが対象となるからです。
• 2番目のretrieveでは [1, 2] を返します。granularityが「Hour」のため、検索範囲は「2018:01:01:01」から「2019:01:01:23」となり、ログ3(2018:01:01:00)は範囲外になるからです。

解決のアプローチ

この問題は、タイムスタンプの文字列を粒度に応じて切り詰めて比較するというシンプルな発想で解けます。手順は以下の通りです。

• イニシャライザ(__init__)を定義し、ログを格納するための空のリストを用意します。
• put() 関数を定義します。引数として id と timestamp を受け取り、logs リストの末尾に追加します。
• retrieve() 関数を定義します。引数として s(開始)、e(終了)、gra(粒度)を受け取ります。
• 粒度ごとの切り出し位置をマップで定義します:{'Year': 5, 'Month': 8, 'Day': 11, 'Hour': 14, 'Minute': 17, 'Second': 20}。これは「YYYY:MM:DD:HH:MM:SS」という文字列の中で、各粒度まで含めた場合のスライス終了位置に対応しています。
• start := s[:index]、end := e[:index] として、開始・終了時刻を指定粒度まで切り詰めます。
• すべてのログについて、timestamp[:index] が start 以上 end 以下であれば、そのログのIDを結果として返します。

実装コード

理解を深めるために、実際のPython実装を見てみましょう。

class LogSystem(object):
    def __init__(self):
        self.logs = []

    def put(self, id, timestamp):
        self.logs.append((id, timestamp))

    def retrieve(self, s, e, gra):
        index = {'Year': 5, 'Month': 8, 'Day': 11,
                 'Hour': 14, 'Minute': 17, 'Second': 20}[gra]
        start = s[:index]
        end = e[:index]
        return (tid for tid, timestamp in self.logs
                if start <= timestamp[:index] <= end)

ob = LogSystem()
ob.put(1, "2019:01:01:23:59:59")
ob.put(2, "2019:01:01:22:59:59")
ob.put(3, "2018:01:01:00:00:00")
print(list(ob.retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Year")))
print(list(ob.retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Hour")))

入力

ob.put(1, "2019:01:01:23:59:59")
ob.put(2, "2019:01:01:22:59:59")
ob.put(3, "2018:01:01:00:00:00")
ob.retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Year")
ob.retrieve("2018:01:01:01:01:01", "2019:01:01:23:00:00", "Hour")

出力

[1, 2, 3]
[1, 2]

まとめ

この実装のポイントは、ゼロ埋めされた固定長のタイムスタンプ文字列をそのまま辞書順(文字列)比較できることにあります。粒度に応じて文字列をスライスして切り詰めるだけで、「Year」「Month」「Day」「Hour」「Minute」「Second」のいずれの単位でも正しく範囲検索が行えます。put() は O(1)、retrieve() は全ログを走査するため O(n) の計算量となり、シンプルながら実用的なログストレージシステムが実現できます。