Rails
Database
DB設計

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

More than 1 year has passed since last update.


はじめに

URLをデータベースにユニークに保存したくなる時があると思います。

URLは仕様としては長さの上限はありません。

クエリパラメーターやフラグメントを含めた長いURLは、string型では保存できずtext型で保存する必要があります。しかし、text型はご存知の通りMySQLやPostgreSQLでは、インデックスを貼れません。

インデックスが貼れなければ、UNIQUEインデックスも貼れないので、重複データが挿入される可能性があります。

また、すでに保存されたURLを検索するのにも不利です。

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


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

長い文字列を保存するための方法として、ハッシュ関数を利用します。

ご存知の通り、ハッシュ関数を利用すればどんなに長い文字列も短い文字列に一意に変換できます。

ハッシュ関数で計算したハッシュをキーにしてインデックスします。

しかし、ハッシュ関数は衝突する可能性が非常に小さいですがあります。その同じハッシュになってしまった場合のハンドリングを考える必要があります。

wikipedia - ハッシュテーブル にあるように、衝突時のキーの対処法としては、「開番地法」と「連鎖法」の2種類があります。


開番地法

「開番地法」ではハッシュが衝突した時に新しい別のハッシュを計算し直す為、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は、httphttpsのみ


  • path, query, fragment は文字数上限なし

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

ハッシュは、pathqueryfragmentを合わせたものをpath_componentと定義し、path_componentをハッシュにしたものを利用しました。

URLの文字列すべてをハッシュにしてもいいのですが、schemehostportをUNIQUE複合インデックスに入れることで、ハッシュのスコープを作り、ハッシュの衝突を起こりにくくしています。

「楽観的ロック」のバージョン管理として、hash_numberを用います。

検索の際に path_component を使うことで、「連鎖法」の検索の高速さを実現します。

path_componenthash_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が2つ以上保存されていることになり、想定外のエラーです。

ここでは、StandardErrorを送出していますが、エラー監視サービスにエラーを通知して、found_urls.firstを返してもいいと思います。


重複挿入しそうな時

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


  1. URL1 が保存される。(ハッシュをHash1とする)

  2. ハッシュがHash1となるURL2を保存しようとして、Url#try_to_saveの1行目を実行。[URL1]が保持される。

  3. 別のプロセスでURL1が削除される

  4. さらに別のプロセスでURL2を保存する。その時、Hash1のUrlはないため、hash_number = 0として保存される。

  5. 最初にURL2を保存しようしたプロセスで保存を実行。この時は[URL1]が保存されているため、URL1.hash_number + 1である、1hash_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の最大値が変わっていてもその変更に気づけます。


最後に

「重複挿入しそうな時」は書いてる時に思いつきました。ごめんなさい。

多分大丈夫だとは思うのですが、重複挿入してしまう場合を思いついた時はコメントをお願いします・・・。