Native extension to perform the binary search within the hashring

Posted on In ,
  • 可以看到为了提高查询性能，采用C去实现，如果安装了RubyInline,会启动C扩展实现的同名方法，加速binary_search查询性能
  • 也可以发现，从客户端分配键到哪个redis节点是通过比较节点的crc32与key的crc32的大小的方式，进行分配的
    class << self
  # gem install RubyInline to use this code
  # Native extension to perform the binary search within the hashring.
  # There's a pure ruby version below so this is purely optional
  # for performance.  In testing 20k gets and sets, the native
  # binary search shaved about 12% off the runtime (9sec -> 8sec).
  begin
    require 'inline'
    inline do |builder|
      builder.c <<-EOM
      int binary_search(VALUE ary, unsigned int r) {
          int upper = RARRAY_LEN(ary) - 1;
          int lower = 0;
          int idx = 0;

          while (lower <= upper) {
              idx = (lower + upper) / 2;

              VALUE continuumValue = RARRAY_PTR(ary)[idx];
              unsigned int l = NUM2UINT(continuumValue);
              if (l == r) {
                  return idx;
              }
              else if (l > r) {
                  upper = idx - 1;
              }
              else {
                  lower = idx + 1;
              }
          }
          if (upper < 0) {
            upper = RARRAY_LEN(ary) - 1;
          }
          return upper;
      }
      EOM
    end
  rescue Exception
    # Find the closest index in HashRing with value <= the given value
    def binary_search(ary, value, &block)
      .....
    end

  end
end