これは株式会社TimeTree Advent Calendar 2024の12日目の記事です。
昨日は同じBackendエンジニアの Zorfmorf による From image to schedule: TimeTree and AI でした。
記事で紹介していた画像からの予定作成は、自分もよく使うお気に入りの機能の一つです。AIの進化に合わせてアーキテクチャとパフォーマンスを改善してくれる Zorfmorf に大感謝です。
TimeTreeでBackendのAPI開発を行っている ta1kt0me です。
TimeTree では現在サービスのスケールを支えるためにデータベースを Cloud Spanner に移行しています。
その際にビット反転シーケンスの値を再反転する Ruby の実装を行う必要があったので紹介します。
なお、この記事でのビット反転は bit flipping ではなく bit reversal になります。
また、 Cloud Spanner の Google SQL のBIT_REVERSE関数のうち、第二引数を TRUE としたビット反転シーケンスと同じアルゴリズムを Ruby で実装するというものになります。
BIT_REVERSE関数のビット反転
- 固定長64ビットの整数
- 最上位ビットは符号を表す
- 残りの63ビットを反転
参考にいくつか例を挙げます。
先頭は符号ビットは
- 0以上ならば0
- 0よりも小さいならば1
となります。残りの63ビットを反転します。
# 1 をビット反転すると 4611686018427387904
0|000000000000000000000000000000000000000000000000000000000000001
↓
0|100000000000000000000000000000000000000000000000000000000000000
# -2 をビット反転すると -4611686018427387905
1|111111111111111111111111111111111111111111111111111111111111110
↓
1|011111111111111111111111111111111111111111111111111111111111111
# 6148914691236517205 をビット反転すると 6148914691236517205
0|101010101010101010101010101010101010101010101010101010101010101
↓
0|101010101010101010101010101010101010101010101010101010101010101
# -6148914691236517205 をビット反転すると -1537228672809129302
1|010101010101010101010101010101010101010101010101010101010101011
↓
1|110101010101010101010101010101010101010101010101010101010101010
目がシパシパしますね。
BIT_REVERSE関数の検証結果
# 1 -> 4611686018427387904
$ gcloud spanner databases execute-sql db_name --instance instance_name --sql='SELECT BIT_REVERSE(1, TRUE);'
(Unspecified)
4611686018427387904
# -2 -> -4611686018427387905
$ gcloud spanner databases execute-sql db_name --instance instance_name --sql='SELECT BIT_REVERSE(-2, TRUE);'
(Unspecified)
-4611686018427387905
Java の実装
Java のコードはシンプルなので参考として紹介します。
Long.reverse メソッドを使います。
long input = 1L;
(Long.reverse(input) >>> 1) | (input & 0x8000000000000000L);
64ビットの符号付き整数型のビット反転を行なった後、元々最上位ビットだったビットを右シフト（符号なし）によって取り除きます。そして変換前の符号ビットと論理和を得ます。
Ruby の実装
Rubyの整数は固定長ではないため、固定長を前提とした計算が複雑になります。
input = 1
reversed_63bit = [input].pack("q>").unpack1("B64").reverse.to_i(2) >> 1
return reversed_63bit if input >= 0
[reversed_63bit | 0X8000_0000_0000_0000].pack("q>").unpack1("q>")
バイナリで扱い固定長64ビットとして表現します。
ただし、ビットを反転するようなメソッドはないため文字列として処理します。
負数の場合だけ符号ビットの論理和を計算します。
最終的な出力は符号つき固定長64ビットとして表現するためpack/unpack1で変換します。
Ruby の別実装
動作やパフォーマンス検証の過程でいくつかの実装を試してみました。
文字列の変換を使わない場合
前項で利用していたビット文字列の反転を使わない実装です。
def reverse(input)
value = [input].pack("q>").unpack1("q>")
reversed_63bit = reverse_bit(value) >> 1
return reversed_63bit if input >= 0
[(reversed_63bit | 0x8000_0000_0000_0000)].pack("q>").unpack1("q>")
end
def reverse_bit(value)
tmp = ((value >> 1) & 0x5555_5555_5555_5555) | ((value & 0x5555_5555_5555_5555) << 1)
tmp = ((tmp >> 2) & 0x3333_3333_3333_3333) | ((tmp & 0x3333_3333_3333_3333) << 2)
tmp = ((tmp >> 4) & 0x0F0F_0F0F_0F0F_0F0F) | ((tmp & 0x0F0F_0F0F_0F0F_0F0F) << 4)
[tmp].pack("Q>").reverse.unpack1("Q>")
end
処理が複雑になったのでメソッドを分けています。
大きな差分としては reverse_bit メソッドの内容です。
[tmp].pack("Q>").reverse ではバイトを反転するため、その前にバイト単位のビットを反転します。
バイト反転では符号なし64ビット整数として扱い、全体の変換前後では符号あり64ビット整数として変換します。
この実装は前項の実装よりもパフォーマンスが劣っていました。
パフォーマンス比較
#! /usr/bin/env ruby
# frozen_string_literal: true
require "bundler/inline"
gemfile true do
source "https://rubygems.org"
gem "benchmark-ips"
gem "debug"
end
class Simple
attr_reader :input
def initialize(input)
@input = input
end
def reverse
reversed_63bit = [input].pack("q>").unpack1("B64").reverse.to_i(2) >> 1
return reversed_63bit if input >= 0
[reversed_63bit | 0X8000_0000_0000_0000].pack("q>").unpack1("q>")
end
end
class NoBitStringReverse
attr_reader :input
def initialize(input)
@input = input
end
def reverse
value = [input].pack("q>").unpack1("q>")
reversed_63bit = reverse_bit(value) >> 1
return reversed_63bit if input >= 0
[(reversed_63bit | 0x8000_0000_0000_0000)].pack("q>").unpack1("q>")
end
def reverse_bit(value)
tmp = ((value >> 1) & 0x5555_5555_5555_5555) | ((value & 0x5555_5555_5555_5555) << 1)
tmp = ((tmp >> 2) & 0x3333_3333_3333_3333) | ((tmp & 0x3333_3333_3333_3333) << 2)
tmp = ((tmp >> 4) & 0x0F0F_0F0F_0F0F_0F0F) | ((tmp & 0x0F0F_0F0F_0F0F_0F0F) << 4)
[tmp].pack("Q>").reverse.unpack1("Q>")
end
end
Fetching gem metadata from https://rubygems.org/...........
Resolving dependencies...
============
Positive
============
ruby 3.3.6 (2024-11-05 revision 75015d4c1f) [arm64-darwin23]
Warming up --------------------------------------
Simple 239.373k i/100ms
NoBitStringReverse 175.471k i/100ms
Calculating -------------------------------------
Simple 2.331M (± 3.6%) i/s (428.97 ns/i) - 11.729M in 5.038266s
NoBitStringReverse 1.716M (± 3.9%) i/s (582.80 ns/i) - 8.598M in 5.019572s
Comparison:
Simple: 2331166.6 i/s
NoBitStringReverse: 1715848.2 i/s - 1.36x slower
============
Negative
============
ruby 3.3.6 (2024-11-05 revision 75015d4c1f) [arm64-darwin23]
Warming up --------------------------------------
Simple 155.243k i/100ms
NoBitStringReverse 82.289k i/100ms
Calculating -------------------------------------
Simple 1.548M (± 3.0%) i/s (646.05 ns/i) - 7.762M in 5.019763s
NoBitStringReverse 833.046k (± 2.5%) i/s (1.20 μs/i) - 4.197M in 5.041290s
Comparison:
Simple: 1547879.3 i/s
NoBitStringReverse: 833045.7 i/s - 1.86x slower
正負で変換方法を変える
パフォーマンスのため、0以上の処理を別の実装で置き換えてみます。
if input >= 0
input.to_s(2).rjust(63, "0").reverse.to_i(2)
else
# 負数の実装は元のまま
reversed_63bit = [input].pack("q>").unpack1("B64").reverse.to_i(2) >> 1
[reversed_63bit | 0X8000_0000_0000_0000].pack("q>").unpack1("q>")
end
ビット文字列に変換した後、反転するのに不足した分を 0 で埋める実装です。
正の数の場合だけですが、やりたいことが一番わかりやすいかもしれません。
パフォーマンス比較
#! /usr/bin/env ruby
# frozen_string_literal: true
require "bundler/inline"
gemfile true do
source "https://rubygems.org"
gem "benchmark-ips"
gem "debug"
end
class Simple
attr_reader :input
def initialize(input)
@input = input
end
def reverse
reversed_63bit = [input].pack("q>").unpack1("B64").reverse.to_i(2) >> 1
return reversed_63bit if input >= 0
[reversed_63bit | 0X8000_0000_0000_0000].pack("q>").unpack1("q>")
end
end
class Improved
attr_reader :input
def initialize(input)
@input = input
end
def reverse
if input >= 0
input.to_s(2).rjust(63, "0").reverse.to_i(2)
else
reversed_63bit = [input].pack("q>").unpack1("B64").reverse.to_i(2) >> 1
[reversed_63bit | 0X8000_0000_0000_0000].pack("q>").unpack1("q>")
end
end
end
puts "\n\n============"
puts " Positive"
puts "============"
Benchmark.ips do |benchmark|
benchmark.config time: 5, warmup: 2
benchmark.report("Simple") { Simple.new(1).reverse }
benchmark.report("Improved") { Improved.new(1).reverse }
benchmark.compare!
end
puts "\n\n============"
puts " Negative"
puts "============"
Benchmark.ips do |benchmark|
benchmark.config time: 5, warmup: 2
benchmark.report("Simple") { Simple.new(-2).reverse }
benchmark.report("Improved") { Improved.new(-2).reverse }
benchmark.compare!
end
Fetching gem metadata from https://rubygems.org/...........
Resolving dependencies...
============
Positive
============
ruby 3.3.6 (2024-11-05 revision 75015d4c1f) [arm64-darwin23]
Warming up --------------------------------------
Simple 239.159k i/100ms
Improved 307.056k i/100ms
Calculating -------------------------------------
Simple 2.377M (± 1.7%) i/s (420.61 ns/i) - 11.958M in 5.031109s
Improved 3.024M (± 2.9%) i/s (330.73 ns/i) - 15.353M in 5.082289s
Comparison:
Improved: 3023589.4 i/s
Simple: 2377485.7 i/s - 1.27x slower
============
Negative
============
ruby 3.3.6 (2024-11-05 revision 75015d4c1f) [arm64-darwin23]
Warming up --------------------------------------
Simple 158.268k i/100ms
Improved 159.856k i/100ms
Calculating -------------------------------------
Simple 1.571M (± 1.7%) i/s (636.66 ns/i) - 7.913M in 5.039639s
Improved 1.543M (± 4.4%) i/s (648.19 ns/i) - 7.833M in 5.088238s
Comparison:
Simple: 1570693.2 i/s
Improved: 1542750.6 i/s - same-ish: difference falls within error
Spanner Emulator の実装
Cloud Spanner の BIT_REVERSE関数の実装の実態は正確にはわかりませんが、 Emulator は公開されているのでその実装を少し追っています。
ビットの反転を行い、最上位の符号ビットと下位63ビットの論理和を算出しています。
ビットを反転している zetasql_base::Bits::ReverseBits64 はこちらになります。 CPUのアーキテクチャによって処理する内容は変わっています。 defined(_LP64) の処理を参考にして 文字列の変換を使わない場合を実装しました。
ARMの64ビット命令セットの場合は専用のアセンブリ命令があってシンプルですね。
余談（背景）
実装についてはあらかた書いたので、ここからは余談です。
そもそもこの実装が必要になった背景を紹介します。
サービスの成長に伴い、現在、私たちはデータベースを Aurora for MySQL から Cloud Spanner への意向作業に取り組んでいます。移行の具体的な背景や意思決定に関しては、 Google Cloud Next Tokyo ’24で、SREチームのマネージャーと一緒に話したので、もし興味のある方はご覧ください（私の出番は後半ちょっとですが）
TimeTreeのBackend APIはRuby on Railsを使っています。PKにも基本的に Auto Increment を利用しています（他にもSnowflake IDをカスタマイズして利用しているケースもあります）。
しかし、Cloud Spannerを利用するにあたりPKのホットスポットの問題を抱えることになりました。
回避策として、ビット反転シーケンスというものを利用します。
サービスではすでに生成済みのIDがあります。移行時は生成済みIDもビット反転して保存します。
しかし、アプリケーションの仕様上、生成済みIDのビット反転前の値を利用したいケースあります。
そのため、DB上のビット反転された値をRuby上で再反転して元の値に変換する必要が生じました。
終わりに
変換処理に負数の計算に2の補数を使ってみたりもしましたが、固定長の変換はpackを使う方が意図が伝わりやすくなると考えています。とはいえ、わかりやすさは人やチームによって基準が異なるので難しい。
紹介した実装よりも、読みやすい、あるいは効率の良い表現があるかもしれませんが、固定長を前提にした操作に関してはRubyではやや複雑になるという発見がありました。
TimeTreeのエンジニアによる記事です。メンバーのインタビューはこちらで発信中！ note.com/timetree_inc/m/m4735531db852
Discussion