【Rails】URLをインデックス可能な形でデータベースに保存する方法

はじめに

URLをデータベースにユニークに保存したくなる時があると思います。
URLは仕様としては長さの上限はありません。
クエリパラメーターやフラグメントを含めた長いURLは、string型では保存できずtext型で保存する必要があります。しかし、text型はご存知の通りMySQLやPostgreSQLでは、インデックスを貼れません。
インデックスが貼れなければ、UNIQUEインデックスも貼れないので、重複データが挿入される可能性があります。
また、すでに保存されたURLを検索するのにも不利です。

そこで、railsを使って、URLをstring型で、モデルとして保存する方法を考えました。

ハッシュを利用するけど・・・

長い文字列を保存するための方法として、ハッシュ関数を利用します。
ご存知の通り、ハッシュ関数を利用すればどんなに長い文字列も短い文字列に一意に変換できます。
ハッシュ関数で計算したハッシュをキーにしてインデックスします。

しかし、ハッシュ関数は衝突する可能性が非常に小さいですがあります。その同じハッシュになってしまった場合のハンドリングを考える必要があります。
wikipedia - ハッシュテーブル にあるように、衝突時のキーの対処法としては、「開番地法」と「連鎖法」の２種類があります。

開番地法

「開番地法」ではハッシュが衝突した時に新しい別のハッシュを計算し直す為、UNIQUEインデックスを保持することができます。
しかし、検索をする際に返り値を検証しながら複数回検索する必要があります。
また、保存したデータの削除は想定されていません。削除する場合は、ハッシュが衝突しているデータのハッシュをすべて再計算する必要があります。

連鎖法

「連鎖法」は、同じハッシュを使う為、UNIQUEインデックスが貼れません。その為、重複データが入る可能性があります。
しかし、1回DB検索するだけで候補を絞り込みができる為、検索は有利です。
データの削除も他のデータを気にせずに削除することができます。

方針

そこで、今回は、「連鎖法」と「楽観的ロック」を使うことで擬似的に「開番地法」を実現するハイブリット型の設計を行うことにしました。
これによって、開番地法のメリットである、重複データの挿入を防ぐことを実現しながら、連鎖法のメリットである、検索を容易にして、かつ削除も即座に行えるようになりました。

URLをユニークに保存するため、URLの正規化とパースにAddressableを使いました。

ハッシュ関数は、比較的高速で32文字に変換してくれるMD5を採用しました。MD5はセキュリティの安全度はもはや高くはありませんが、ハッシュキーがバレたところで痛くもかゆくもないので大丈夫です。

環境

• Rails: 5.0.1
• Ruby: 2.4.0
• Addressable: 2.4.0

docker-composeで環境を構築しています。githubのサンプルはこちら
サンプルを立ち上げるには、以下を実行してください。

git clone https://github.com/kawasin73/sample_rails_url.git
cd sample_rails_url
script/bootstrap

また、テストの実行は以下の通りです。

docker-compose up -d spring
docker-compose exec spring bin/rspec spec/

実装

マイグレーション

class CreateUrls < ActiveRecord::Migration[5.0]
  def change
    create_table :urls do |t|
      t.string :scheme, null: false
      t.string :host, null: false
      t.integer :port, null: false, default: 0
      t.text :path, null: false
      t.text :query, null: true
      t.text :fragment, null: true
      t.string :path_component_hash, null: false, limit: 32
      t.integer :hash_number, null: false, default: 0

      t.index [:host, :scheme, :port, :path_component_hash, :hash_number], unique: true, name: 'url_unique_index'
    end
  end
end

Url モデル

app/models/url.rb

# == Schema Information
#
# Table name: urls
#
#  id                  :integer          not null, primary key
#  scheme              :string           not null
#  host                :string           not null
#  port                :integer          default("0"), not null
#  path                :text             not null
#  query               :text
#  fragment            :text
#  path_component_hash :string(32)       not null
#  hash_number         :integer          default("0"), not null
#
# Indexes
#
#  url_unique_index  (host,scheme,port,path_component_hash,hash_number) UNIQUE
#

class Url < ApplicationRecord
  validates :scheme, presence: true
  validates :host, presence: true, length: { maximum: 256 }
  validates :port, presence: true
  validates :path, presence: true
  validates :path_component_hash, presence: true, length: { is: 32 }
  validates :hash_number, presence: true

  validates :scheme, inclusion: { in: %w(http https) }
  validates :path, format: { with: /\A\/.*/ }

  # need no uniqueness validation
  # validates_uniqueness_of :hash_number, scope: [:scheme, :host, :port, :path_component_hash]

  validate :force_immutable

  def to_s
    # "#{scheme}://#{host}#{port > 0 ? ":#{port}" : ''}#{path_component}"
    Addressable::URI.new(scheme: scheme, host: host, port: port, path: path, query: query, fragment: fragment).to_s
  end

  def self.parse(url_string)
    uri = Addressable::URI.parse(url_string.to_s)
    return nil if uri.nil?
    uri.normalize!
    url = Url.new(scheme: uri.scheme.to_s.downcase, host: uri.host.to_s.downcase, port: uri.port || 0, path: uri.path, query: uri.query, fragment: uri.fragment) do |url|
      url.set_hash
    end
    url.find_or_create
  rescue Addressable::URI::InvalidURIError
    nil
  end

  def find_or_create(max_retry: 3)
    try_to_save
  rescue ActiveRecord::RecordInvalid
    nil
  rescue ActiveRecord::RecordNotUnique
    if max_retry > 0
      max_retry -= 1
      retry
    else
      raise
    end
  end

  def set_hash
    self.path_component_hash = Digest::MD5.hexdigest(path_component)
  end

  def path_component
    if @path_component.nil?
      @path_component = path
      @path_component += "?#{query}" if query.present?
      @path_component += "##{fragment}" if fragment.present?
      @path_component
    else
      @path_component
    end
  end

  private

  def try_to_save
    urls = Url.where(scheme: scheme, host: host, port: port, path_component_hash: path_component_hash).to_a
    if urls.empty?
      self.save!
      self
    else
      found_urls = urls.select { |url| url.path_component == self.path_component }
      if found_urls.empty?
        begin
          self.hash_number = urls.map(&:hash_number).max + 1
          self.save!
          self
        rescue ActiveRecord::RecordNotUnique
          self.hash_number = 0
          raise
        end
      elsif found_urls.count == 1
        found_urls.first
      else
        raise "not_unique_urls! url: #{self.to_s}, ids: #{found_urls.map(&:id)}"
      end
    end
  end

  # URL: http://swaac.tamouse.org/rails/2015/08/13/rails-immutable-records-and-attributes/
  def force_immutable
    if self.changed? && self.persisted?
      errors.add(:base, :immutable)
      # Optional: restore the original record
      self.reload
    end
  end
end

解説

カラムは、scheme, host, port, path, query, fragment, path_component_hash, hash_numberです。
仕様として、

• hostは、256文字まで
• schemeは、httpかhttpsのみ
• path, query, fragment は文字数上限なし

です。hostも文字数上限なしにしても良かったのですが、めんどくさかったのでこれでいきます。

ハッシュは、pathとqueryとfragmentを合わせたものをpath_componentと定義し、path_componentをハッシュにしたものを利用しました。
URLの文字列すべてをハッシュにしてもいいのですが、schemeとhostとportをUNIQUE複合インデックスに入れることで、ハッシュのスコープを作り、ハッシュの衝突を起こりにくくしています。

「楽観的ロック」のバージョン管理として、hash_numberを用います。
検索の際に path_component を使うことで、「連鎖法」の検索の高速さを実現します。
path_componentとhash_numberを合わせてUNIQUEインデックスに追加することで、「開番地法」のようにUNIQUEなデータの挿入を実現します。

Validation

validates_uniqueness_of

Railsには、validates_uniqueness_ofがありますが、これはモデルの保存前にデータベースアクセスを発生させてしまうため利用しません。その代わり、Urlモデルの作成は必ずUrl.parseを用いて、try_to_saveの中でそのURLがユニークであることを保証しています。

force_immutable

Urlモデルは一度保存されたら変更することを想定していません。そのため、モデルの中身が変更された状態で保存しないようにバリデーションをかけます。

Url.parse

URLの検索も保存もこのUrl.parseを通して行います。
この中では、文字列のURLを正規化し、ハッシュを計算して検索に備えます。

Url#find_or_create

複数のプロセスでアプリケーションを実行していた場合、アプリケーションコードだけでは防ぎきれず、重複してデータの挿入が行われることがあります。
その時は、DBのUNIQUEインデックスによって挿入がキャンセルされActiveRecord::RecordNotUniqueエラーが送出されます。
その際は検索をretryすることで同じタイミングで挿入されたデータを取得することができます。
しかし、max_retryの3回以上もretryを繰り返すのは何かがおかしいのでエラーを送出します。

schemeの値などがおかしかった場合は、バリデーションに引っかかり、ActiveRecord::RecordInvalidが送出されます。その時は、nilを返してURLが不正であることを呼び出し元に教えます。

Url#try_to_save

ここが大本命です。まず、ハッシュが同じUrlの一覧を取得し、to_aで配列に代入します。
そもそも、ハッシュの衝突はほとんど起こらないので、アプリケーション側のメモリに全部載せてしまっても大丈夫です。

ハッシュが同じUrlがない場合

url.empty?の時です。この時は、そのURLは保存されていないので、保存して自身を返します。

ハッシュが同じUrlがあり、path_componentが同じUrlがない場合

found_urls.empty? の時です。この時は、そのURLは保存されていないが、ハッシュが衝突しているのでhash_numberを違うものにして保存します。
hash_numberを常に「他のUrlのhash_numberの最大のもの + 1」とすることで、hash_numberは「楽観的ロック」のバージョンとして機能します。
hash_numberを変更して保存し、自身を返します。

保存に失敗した場合は、retryに備えるため、hash_numberをdefaultの0に戻します。

ハッシュが同じUrlがあり、path_componentが同じUrlが1つある場合

found_urls.count == 1 の時です。この時は、found_urlsがそのURLに対応したUrlであるため、found_urlを返します。

ハッシュが同じUrlがあり、path_componentが同じUrlが2つ以上ある場合

重複したUrlが２つ以上保存されていることになり、想定外のエラーです。
ここでは、StandardErrorを送出していますが、エラー監視サービスにエラーを通知して、found_urls.firstを返してもいいと思います。

重複挿入しそうな時

実は、ここまで厳密に実装しましたが、悲観的ロックではなく、楽観的ロックであるため、Urlが重複して保存される場合があります。

1. URL1 が保存される。（ハッシュをHash1とする）
2. ハッシュがHash1となるURL2を保存しようとして、Url#try_to_saveの１行目を実行。[URL1]が保持される。
3. 別のプロセスでURL1が削除される
4. さらに別のプロセスでURL2を保存する。その時、Hash1のUrlはないため、hash_number = 0として保存される。
5. 最初にURL2を保存しようしたプロセスで保存を実行。この時は[URL1]が保存されているため、URL1.hash_number + 1である、1がhash_numberとして保存される。
6. 結果、URL2が2つ保存される。

これを防ぐためには、Url#try_to_saveの

begin
  self.hash_number = urls.map(&:hash_number).max + 1
  self.save!
  self
rescue ActiveRecord::RecordNotUnique
  self.hash_number = 0
  raise
end

をactiverecord-importgemを使って

begin
  self.hash_number = urls.map(&:hash_number).max + 1
  self.class.import!([self, *urls], on_duplicate_key_update: [:hash_number])
  self
rescue ActiveRecord::RecordNotUnique
  self.hash_number = 0
  raise
end

とすれば、知らぬ間にhash_numberの最大値が変わっていてもその変更に気づけます。

最後に

「重複挿入しそうな時」は書いてる時に思いつきました。ごめんなさい。
多分大丈夫だとは思うのですが、重複挿入してしまう場合を思いついた時はコメントをお願いします・・・。