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


## はじめに

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

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

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

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

しかし、ハッシュ関数は衝突する可能性が非常に小さいですがあります。その同じハッシュになってしまった場合のハンドリングを考える必要があります。
[wikipedia - ハッシュテーブル](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB) にあるように、衝突時のキーの対処法としては、「開番地法」と「連鎖法」の２種類があります。

### 開番地法

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

### 連鎖法

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

## 方針

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

URLをユニークに保存するため、URLの正規化とパースに[Addressable](https://github.com/sporkmonger/addressable)を使いました。

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

## 環境

- Rails: 5.0.1
- Ruby: 2.4.0
- Addressable: 2.4.0

docker-composeで環境を構築しています。[githubのサンプルはこちら](https://github.com/kawasin73/sample_rails_url)
サンプルを立ち上げるには、以下を実行してください。

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

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

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

## 実装

### マイグレーション

```ruby
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 モデル

```ruby: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`の

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

を`activerecord-import`gemを使って

```ruby
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の最大値が変わっていてもその変更に気づけます。

## 最後に

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