###

alias hbin me

[译] How the Hash Works in Ruby

原文:https://launchschool.com/blog/how-the-hash-works-in-ruby

这篇文章将会简短的介绍 Hash 这种数据结构,它是如何实现的,以及 MRI Ruby Hash 的演变历史。

什么是 Hash?

Hash 是一种键-值(key-value)存储结构,它也被称作字典(译者注:Python 就是 dict)或者关系型数组(Associative array)。得益于这种键-值的存储结构,它可以进行高效的插入和查找操作,而且时间复杂度仅是 O(1)。这种特性使得 Hash 成为程序员最有用的编程工具之一,所以绝大多数的编程语言都把它纳入到核心库。

在 Ruby 中,你可以用字面量的方式声明一个 Hash,如:

1
2
h = { color: 'black', font: 'Monaco' }
h = { :color => 'black', :font => 'Monaco' }

或者,用传统的 new 方法:

1
2
3
h = Hash.new
h[:color] = 'black'
h[:font] = 'Monaco'

Hash 是如何存储数据的?它为什么高效?

为了理解这个问题,让我们先回顾下基本的线性存储结构 - 数组(Array)。如果我们知道其中某个元素的下标,那我们就可以快速的随机访问它所存储的元素。

1
2
a = [1, 2, 4, 5]
puts a[2] #> 4

如果 Hash 中存储的键是整数值,并且这个值也比较小,比如它在 1-20 或者 1-100 这个范围内,那我们可以简单的用数组来存,把键作为数组的下标。

举个例子,我们需要存储这样一组数据:

  • 一个教室有 20 个学生,我们要存这个教室里所有学生的名字
  • 每个学生的 ID 都在 1 - 20 之间
  • 任意两个学生的 ID 都不相同

我们就可以简单的用数组来存,假设数据如下:

Key Value
1 Belle
2 Ariel
3 Peter Pan
4 Mickey Mouse

那数组就可以表示为:

1
students = ['Belle', 'Ariel', 'Peter Pan', 'Mickey Mouse']

但是,如果学生的 ID 是 4 位数呢?那我们只能用一个长度为 10000 的数组来存,这样才能通过 ID 来访问学生的名字。(很显然,这浪费了很多空间),为了解决这个问题,我们可以用 4 位数 ID 的后两位来表示其在数组中的位置(比如,我们有个学生 ID 是 4221,它的后两位是 21)。但是假设现在,我们有另外一个学生,它的 ID 是 3221,它的后两位也是 21,那我们只能把这两个数放到数组的同一个下标内,这就会造成数据冲突。如:

Key Hash(key) = last 2 digits Value
4221, 3221 21 Belle, Sofia
1357 57 Ariel
4612 12 Peter Pan
1514 14 Mickey Mouse
1
2
3
4
5
students = Array.new(100)
students[21] = ['Belle', 'Sofia']
students[57] = 'Ariel'
students[12] = 'Peter Pan'
students[14] = 'Mickey Mouse'

而且,如果 ID 是 10 位数呢?或者 ID 是字符串呢?这就种方式就变得不高效或者不适用了。所以,太简单的哈希策略会导致很多问题。

那 Ruby 的哈希策略是什么呢?

好了,我们现在已经明白哈希策略的目的就是为了把某个键转化为有限范围内的一个整数。为了缩小这个范围,一个通常的策略就是取模运算。取模运算策略,就是把键去除以存储表的大小,得到的余数就是这个键在存储表中的位置。因此,在上面这个例子中,如果存储表的大小为 20,取模之后他们的位置分别是1, 17, 12, 14,运算如下:

  • 4221 % 20 = 1
  • 1357 % 20 = 17
  • 4612 % 20 = 12
  • 1514 % 20 = 14

但是,在真实的编程过程中,键并不总会是整数,他们也可能是字符串,对象,或者其他数据类型。这个时候,我们可以用单向的哈希函数(digest)对键求值,然后再用取模运算得出其存储位置。这种哈希函数是一种数学函数,它可以接收任意长度的字符串,然后返回一个固定长度的整数值。这也正是 Hash 这种数据结构的名字由来。Ruby 使用了一种叫做 MurMur 的哈希函数,求得的值再用质数 M 取模,M 的取值根据存储结构大小来判断。

1
murmur_hash(key) % M

这段代码可以在 Ruby 的源代码里找到 st.c file

有的时候,两个不同的键哈希后会得到同样的值,所以他们的值会被存放到表中的相同位置(译者注:也叫做桶),这种情况被称作哈希冲突(hash collision)。

Ruby 是如何处理哈希冲突的?

哈希函数面临的一个问题是如何让值更加分散。如果大多数键哈希取模后都落到同一个桶里,那我们再要找某个 key 时,只能先找到这个桶,然后遍历整个桶里的数据,最终才找到匹配的数据。这种方式就违背了我们设计 Hash 这种数据结构的初衷,也不能在 O(1) 的时间复杂度里随机访问了。由于需要遍历,此时的时间复杂度已近降为 O(n) 了。

研究发现,如果上面的除数 M 是一个质数的话,其结果会更加均匀分布。但是,即使选择了最合适的除数,当数据量增加时,冲突仍然不可避免。Ruby 会根据当前数据的密度(density)调整除数 M 的值。这里的密度指存储表中某一个桶里数据的个数。在上面的例子中,其密度为 2,因为第一个桶里有两个值。

Ruby 默认设置允许的最大密度为 5

1
#define ST_DEFAULT_MAX_DENSITY 5

当密度达到 5 的时候, Ruby 就会调整除数 M,重新计算所有的记录的哈希值,调整其位置。Data Stuctures using C 说:“求除数 M 的算法是:生成最为接近 2 的幂数的质数”。源码 st.c 中第 158 行计算了新 Hash 大小。

1
2
3
4
5
6
7
8
new_size(st_index_t size)
{
    st_index_t i;
    for (i=3; i<31; i++) {
       if ((st_index_t)(1<<i) > size) return 1<<i;
    }
    return -1;
}

JRuby 的实现可能会更容易理解一些,它直接预生成了这些质数数组。如下数组,它有 11,19 等等等等

1
private static final int MRI_PRIMES[] = { 8 + 3, 16 + 3, 32 + 5, 64 + 3, 128 + 3, 256 + 27, ....};

当 Hash 的大小持续增长,达到一定值的时候,重新哈希(rehashing)可能会导致性能问题(Spike performance)。Pat Shaughnessy 在它的 <Ruby under a Microscope> 这本书中详细分析了这一情况,并且用图形化的方式向你展示了重新哈希导致的性能问题(译者注:Figure 7-8)。

Ruby 的 Hash 在每一个进程里都不一样

一个有意思的事是,Hash 在 Ruby 各个进程都是唯一的。Ruby 会给 Murmur hash 算法一个随机的 seed,在不同的进程中相同的,即使 key 相同,哈希值也不一样。

Ruby 2.0 以后会把长度小于等于 6 的 Hash 打包(packed)

另一个有意思的事是,当 Hash 数据非常少的时候(长度小于或等于 6),Ruby 会把这些元素打包起来只存到同一个桶中,而不是根据 Key 去哈希取模然后分布到不同的桶中。也就是说,它就又变回了简单的数组。这个特性是最近添加的,这个 pull request 的作者在留言处写到:

调研表明,一个典型的 Rails 应用会分配大量的小的 Hash,其中最多 40% 的 Hash 大小不超过一个。

Ruby 的 Hash 键是有序的

从 Ruby 1.9.3 开始,Hash 的键会按照其插入顺序排序。在 Ruby-forum 上有人问,为什么要让键有序,以及这会不会对性能造成影响。Ruby 的创始人 Matz 也在那里回复了,

Q: 有人能解释下,为什么要加入这个特性吗?

Matz: 在某些情况下非常有用,尤其是关键字参数。

Q: 这不会拖慢在 Hash 上的方法调用吗?

Matz: 不会的,对 Hash 操作并不会碰到其顺序的信息,除了遍历的时候。内存占用也只是增加一点点。

(译者注:这里略过两段关于 Ruby 2.0 引入的新特性介绍)…

结语

数据结构是相通的。无论是 Java,Python,还是 Ruby 他们的 Hash 的本质都是一样的。也希望,通过这边文章,能帮助大家从更深的角度去理解它,而不是仅仅把自己当做一个 API 的使用者,然后写出运行效率更高的代码,甚至能积极参与进来,帮助社区一起打造下一个 Ruby 版本。

译完

[References]

A ruby implementation of the KMP algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
require 'test/unit'

class TestKmp < Test::Unit::TestCase
  def kmp_search(string, substring)
    # Create a fail_table, which stands for if comparision fail at `pos` of substing,
    # where will be the beginning for the next round comparision.
    fail_table = [-1, 0]
    pos = 2
    cnd = 0
    while pos < substring.length
      if substring[pos - 1] == substring[cnd]
        fail_table[pos] = cnd + 1
        pos += 1
        cnd += 1
      else
        fail_table[pos] = 0
        pos += 1
        cnd = 0
      end
    end

    s = i = 0
    while s + i < string.length
      if string[s + i] == substring[i]
        i += 1
        return s if i == substring.length
      else
        s = s + i - fail_table[i]    # without fail_table, we will move `s` to right by 1 step
        i = fail_table[i] if i > 0   # without fail_table, we will compare substring from the beginning, aka, i = 0
      end
    end
  end

  def test_kmp_search
    assert_equal 15, kmp_search('ABC ABCDAB ABCDABCDABDE', 'ABCDABD')
    assert_equal nil, kmp_search('ABC ABCDAB ABCDABCDABDE', 'ABCDEF')
  end
end

[References]

HTTP Caching

前天 Hulu onsite 面试,第二轮被问到关于缓存的问题,之后才想起来 HTTP Caching 没有答上 orz

《Web 性能权威指南》关于性能优化实践里说:

最好最快的请求是没有请求。

而 HTTP Caching 做的就是这个事情,用好 HTTP Caching,可以减少客户端不必要的请求,也可以减少部分请求中服务器所需要返回的数据大小,节约带宽。 现代浏览器基本上都能很好的支持这一标准,它会自动检查其资源缓存,执行必要的验证,然后在满足限制条件的情况下返回资源的本地副本。

HTTP/1.1 定义了一组 Header:Cache-Control, Expires, ETag, If-Match, If-Match-Since, If-None-Match, Last-Modified, If-Modified-Since, etc..

[References]

Sharing Sessions Across Subdomain

The part you want to watch out for here is that if you set :domain => :all like is recommend in some places, it simply won’t work unless you’re using localhost. :all defaults to a TLD length of 1, which means if you’re testing with Pow (myapp.dev) it won’t work either because that is a TLD of length 2

1
App.config.session_store ... , :domain => :all, :tld_length => 2

http://excid3.com/blog/sharing-a-devise-user-session-across-subdomains-with-rails-3/ http://stackoverflow.com/questions/10402777/share-session-cookies-between-subdomains-in-rails/15009883#15009883)

asdf

rbenv, pyenv, nvm, exenv … 这么多版本管理工具,而且每一个都有对应 oh-my-zsh plugin,都加上后连 zsh 都慢了下来,导致每次新开 Tab 都要等两三秒。

无意中发现这个 asdf,号称可扩展的版本管理工具,可以支持 Ruby, Node.js, Elixir 等多种语言和工具。

目前支持的语言:

  • Elixir
  • Erlang
  • Go
  • LFE
  • Lua
  • OpenResty
  • MongoDB
  • Node.js
  • PHP
  • Postgres
  • Python
  • Redis
  • Riak
  • Ruby
  • Rust
  • Terraform

还有 Postgres! Redis!! MongoDB!!! 简直多到没朋友!!!

花了一点时间装上试用,删除多余的 oh-my-zsh 的插件,打开终端 Tab 又快到飞起,小霸王游戏机珍藏版84合1的感觉!值!!!

Connection Pooling

池化技术是减少计算机某些昂贵开销的一种有效手段。 网络请求就是典型的一种情况。将 Keepalive 的连接池化,可以有效提高性能。

Faraday 是一个 Ruby HTTP 请求的通用接口。它将各种常用 HTTP client 包的接口抽象出来,只要替换 Adapter 就可以实现不同库无缝切换。

关于各种 HTTP client adapters 的对比测试,这篇博文非常详尽:http://reevoo.github.io/blog/2014/09/12/http-shooting-party/ 结果如下图:

结果对比悬殊,最快的 Curb 和 Excon 相差有 12 倍之巨!Patron 和 Excon 也相差 6.8 倍!

这放在有大量请求的时候,性能影响非常大,比如:Elasticsearch

The official (non-Java) clients written and supported by Elasticsearch all use HTTP under the hood to communicate with Elasticsearch.

如上所说 Elasticsearch 官方所有非 Java 的包都是通过 HTTP 的方式链接的。 所以选用一个更快的,可以保持连接(Keep-Alive) 的 HTTP clint 非常重要。感谢 Elasticsearch-ruby 作者,已经默默为我们做了这部分工作,如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Auto-detect the best adapter (HTTP "driver") available, based on libraries
# loaded by the user, preferring those with persistent connections
# ("keep-alive") by default
#
# @return [Symbol]
#
# @api private
#
def __auto_detect_adapter
  case
  when defined?(::Patron)
    :patron
  when defined?(::Typhoeus)
    :typhoeus
  when defined?(::HTTPClient)
    :httpclient
  when defined?(::Net::HTTP::Persistent)
    :net_http_persistent
  else
    ::Faraday.default_adapter
  end
end

所以,我们需要做的只是:gem install patron boom!

但是这还不够!因为除了 Keep-Alive 还有一个更重要的池化(Pooling)! 从 Faraday 的 Patron Adapater 源码

1
2
3
4
5
6
7
8
# https://github.com/lostisland/faraday/blob/master/lib/faraday/adapter/patron.rb#L73-L78

def create_session
  session = ::Patron::Session.new
  session.insecure = true
  @block.call(session) if @block
  session
end

可以看到,这里只是简单新建一个链接,所以我们可以把这个连接池化(Pooling)。这里我们可以使用 connection_pooling 包, 所以一个简单的实现可以是:

1
2
3
4
5
6
7
8
# NOT TESTED, be caution to use it in production!

def create_session
  session = ConnectionPool::Wrapper.new(size: 5, timeout: 3) { ::Patron::Session.new }
  session.insecure = true
  @block.call(session) if @block
  session
end

当然,用 ConnectionPool::Wrapper 的方式相比 with 方式要慢一些,更好的的方式应该把 call 方法里对 session 的调用都用 with 包裹起来,参见 connection_pooling 的文档。

用 Ngrok 搭建自用内网穿透服务

最近做微信开发,怎么用开发机调试回调就成了麻烦事。一开始试用了 localtunnel 可是这货隔几分钟就会访问不了,需要重启,但是这样又来回来的改回调地址,实在太麻烦了。于是放弃。

正好在 Ruby-China 上搜到一篇环境搭建的文章,里面介绍了另一利器 ngrok

安装过程很简单,照着 https://gist.github.com/lyoshenka/002b7fbd801d0fd21f2f 做就可以了,不过这里有三点需要注意!!!

1) 编译 Mac Client

编译客户端 ngrok 时需要注意,Mac 用户编译需要加上:GOOS 和 GOARCH 两个参数,如:

1
2
GOOS="linux" GOARCH="amd64" make release-server    # For Linux Server
sudo GOOS="darwin" GOARCH="amd64" make release-client   # For Mac Client, 这里提示要 sudo 权限

如果你需要其它操作系统的客户端,可以参见完整的 GOOS/GOARCH 列表:https://golang.org/doc/install/source#environment

2) 80 接口

由于微信公众号接口只支持80接口,所以在启动 Server 的时候得用 80 端口,也就是:

1
sudo bin/ngrokd -tlsKey=device.key -tlsCrt=device.crt -domain="$NGROK_DOMAIN" -httpAddr=":80" -httpsAddr=“:443"

3)子域名

如果你像我一样,喜欢用 my.xxxx.com or you.xxxx.com 子域名作为回调的话,那么编译和启动 Server 的时候 export NGROK_DOMAIN=xxxx.com

我的完整命令:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
############# 登陆服务器

# 编译 Ngrok 服务端和客户端
export NGROK_DOMAIN="xxxx.com"
git clone https://github.com/inconshreveable/ngrok.git
cd ngrok

openssl genrsa -out rootCA.key 2048
openssl req -x509 -new -nodes -key rootCA.key -subj "/CN=$NGROK_DOMAIN" -days 5000 -out rootCA.pem
openssl genrsa -out device.key 2048
openssl req -new -key device.key -subj "/CN=$NGROK_DOMAIN" -out device.csr
openssl x509 -req -in device.csr -CA rootCA.pem -CAkey rootCA.key -CAcreateserial -out device.crt -days 5000

cp rootCA.pem assets/client/tls/ngrokroot.crt

GOOS="linux" GOARCH="amd64" make release-server    # For Linux Server
sudo GOOS="darwin" GOARCH="amd64" make release-client   # For Mac Client, 这里提示要 sudo 权限

# 启动服务端
sudo bin/ngrokd -tlsKey=device.key -tlsCrt=device.crt -domain="$NGROK_DOMAIN" -httpAddr=":80" -httpsAddr=":443"

############# 下载 Client 到本地,在本地执行下面的命令:

# 生成客户端配置文件:
export NGROK_DOMAIN="xxxx.com"
echo -e "server_addr: $NGROK_DOMAIN:4443\ntrust_host_root_certs: false" > ngrok-config

# 启动客户端
./ngrok -config=ngrok-config -subdomain=my 3000

然后,我就可以使用 http://my.xxxx.com 访问我本地了。

Done.

Prevent Nginx From Processing Requests with Undefined Server Name

It makes me confused for a while, so I decide to write it down.

The first server block in the nginx config is the default for all requests that hit the server for which there is no specific server block.

A proper Nginx configs have a specific server block for defaults

1
2
3
4
5
6
7
8
9
10
11
12
http {
    [...]

    server {
        listen 80 default_server;
        server_name _;
        return 444; # HTTP response that simply close the connection and return nothing
    }

    include /etc/nginx/conf.d/*.conf;
    include /etc/nginx/sites-enabled/*;
}

NULL vs Empty String

在设计表的时候,一般字段默认值都会是 NULL,但是,我们在使用的时候,会碰到这个问题:用户提交一个表单值后,原本默认值是 NULL 的字段被赋上了空字符串!

NULL 还是 Empty ?

首先来看看这两种值的含义:

  • NULL -> 没有值
  • 空字符串 -> 有值,但值为 “”

比如,邮箱字段:用空字符串就是有问题的,因为,空字符串本身就是一个不合法的邮箱地址!所以,如果你的场景中 NULL 和 空字符串的定义不一样,那就得考虑如何处理上面遇到的情况了。

数据库怎么定义?

  1. 如果一个字段是 NOT NULL,那么我的就可以认定这是一个必填项,那确保给他一个默认值。
  2. 如果一个字段是 ALLOW NULL,那么不要给他赋一个空的字符串。

代码中怎么处理?

对于允许为 NULL 的字段,我们应该将 form 表单提交上来的空字符串换成 NULL 值:

1
2
3
attributes.each do |column, value|
  self[column].present? || self[column] = nil
end

已经有一些 Gem 可以处理这个问题,比如 attribute_normalizer 只需要在 Model 中声明:normalize_attributes :email 它会默认执行 strip 和 blank 两个标准化方法。