Optimize getting server for key in Redis::Distributed

[fatkodima]

When looking at https://github.com/redis/redis-rb/issues/1089, and running node_for many times, I noticed that it is slow and made some investigation. I was able to make it 2x faster and use 0 memory.

Testing script

# frozen_string_literal: true

require "bundler/inline"

gemfile(true) do
  source "https://rubygems.org"

  git_source(:github) { |repo| "https://github.com/#{repo}.git" }

  gem "redis", path: "~/Desktop/oss/redis-rb"
  gem "benchmark-ips"
  gem "stackprof"
  gem "memory_profiler"
end

require "stackprof"
require "memory_profiler"
require "redis"
require "redis/distributed"

r = Redis::Distributed.new([{ url: 'redis://1.1.1.1:6379/0' }, { url: 'redis://2.2.2.2:6379/0'}])
keys = 10_000_000.times.map { SecureRandom.hex }

StackProf.start
MemoryProfiler.start
start = Process.clock_gettime(Process::CLOCK_MONOTONIC)

keys.each do |key|
  r.node_for(key)
end

delta = Process.clock_gettime(Process::CLOCK_MONOTONIC) - start
puts "Finished in #{delta.round(1)} seconds"
StackProf.stop
report = MemoryProfiler.stop
report&.pretty_print(scale_bytes: true, to_file: "tmp/memory_profiler.txt")
StackProf.results('tmp/stackprof.dump')

Timing

Before: Finished in 22.3 seconds After: Finished in 11.3 seconds

CPU profile

Before

==================================
  Mode: wall(1000)
  Samples: 22456 (0.00% miss rate)
  GC: 1155 (5.14%)
==================================
     TOTAL    (pct)     SAMPLES    (pct)     FRAME
      5133  (22.9%)        5133  (22.9%)     String#[]
      9404  (41.9%)        4984  (22.2%)     Redis::HashRing.binary_search
      4420  (19.7%)        4420  (19.7%)     Integer#<=>
     13069  (58.2%)        2931  (13.1%)     Redis::HashRing#get_node_pos
      2700  (12.0%)        2700  (12.0%)     String#to_s
       883   (3.9%)         883   (3.9%)     (marking)
       734   (3.3%)         734   (3.3%)     Zlib.crc32
       272   (1.2%)         272   (1.2%)     (sweeping)
     21274  (94.7%)         213   (0.9%)     Redis::Distributed#node_for
      6151  (27.4%)          80   (0.4%)     Redis::Distributed#key_tag
     13148  (58.6%)          79   (0.4%)     Redis::HashRing#get_node
     21301  (94.9%)          27   (0.1%)     block in <main>
      1155   (5.1%)           0   (0.0%)     (garbage collection)
     21301  (94.9%)           0   (0.0%)     <main>
     21301  (94.9%)           0   (0.0%)     <main>
     21301  (94.9%)           0   (0.0%)     Array#each

After

==================================
  Mode: wall(1000)
  Samples: 11763 (0.00% miss rate)
  GC: 0 (0.00%)
==================================
     TOTAL    (pct)     SAMPLES    (pct)     FRAME
      5517  (46.9%)        5517  (46.9%)     Redis::HashRing#binary_search
      2738  (23.3%)        2738  (23.3%)     String#to_s
      1412  (12.0%)        1412  (12.0%)     Zlib.crc32
      1171  (10.0%)        1171  (10.0%)     String#match?
      7507  (63.8%)         511   (4.3%)     Redis::HashRing#get_node
     11734  (99.8%)         179   (1.5%)     Redis::Distributed#node_for
      2180  (18.5%)         139   (1.2%)     Redis::Distributed#key_tag
      1479  (12.6%)          67   (0.6%)     Redis::HashRing#hash_for
     11763 (100.0%)          29   (0.2%)     block in <main>
     11763 (100.0%)           0   (0.0%)     <main>
     11763 (100.0%)           0   (0.0%)     <main>
     11763 (100.0%)           0   (0.0%)     Array#each

Memory profile

Before

Total allocated: 400.00 MB (10000002 objects)
Total retained:  0 B (0 objects)

allocated memory by gem
-----------------------------------
 400.00 MB  redis-rb/lib
  128.00 B  other

allocated memory by file
-----------------------------------
 400.00 MB  /Users/fatkodima/Desktop/oss/redis-rb/lib/redis/hash_ring.rb
  128.00 B  bug_report.rb

After

Total allocated: 128.00 B (2 objects)
Total retained:  0 B (0 objects)

allocated memory by gem
-----------------------------------
  128.00 B  other

I rewrote binary search algorithm using a simpler algorithm from wiki. I changed some method signatures in HashRing. Is this allowed? Looks like these methods already should be private even before this PR.