月度归档:2014年03月

一致性哈希(consistent hash)

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛;

1 基本场景

比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;

hash(object)%N

一切都运行正常,再考虑如下的两种情况;

1 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;

2 由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;

1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;

再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。

有什么方法可以改变这个状况呢,这就是 consistent hashing…

2 hash 算法和单调性

Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

3 consistent hashing 算法的原理

consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。

下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

3.1 环形hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

 点击查看原图

图 1 环形 hash 空间

3.2 把对象映射到hash 空间

接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

 点击查看原图

图 2 4 个对象的 key 值分布

3.3 把cache 映射到hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的hash 算法。

假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

 点击查看原图

图 3 cache 和对象的 key 值分布

说到这里,顺便提一下 cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为hash 输入。

3.4 把对象映射到cache

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2和 object3 对应到 cache C ; object4 对应到 cache B ;

3.5 考察cache 的变动

前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时,cache 会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。

3.5.1 移除 cache

考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。

 点击查看原图

图 4 Cache B 被移除后的 cache 映射

3.5.2 添加 cache

再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 和object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

 

因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。

点击查看原图

图 5 添加 cache D 后的映射关系

4 虚拟节点

考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

平衡性

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2 、 object3 和 object4 ;分布是很不均衡的。

为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

仍以仅部署 cache A 和 cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 。

点击查看原图

图 6 引入“虚拟节点”后的映射关系

此时,对象到“虚拟节点”的映射关系为:

objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ;

因此对象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。

引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache时的映射关系如图 7 所示。

点击查看原图

图 7 查询对象所在 cache

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为202.168.14.241 。

引入“虚拟节点”前,计算 cache A 的 hash 值:

Hash(“202.168.14.241”);

引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值:

Hash(“202.168.14.241#1”);  // cache A1

Hash(“202.168.14.241#2”);  // cache A2

 

PHP 

在PHP使用pecl::memcache  的时候,客户端也已经实现了 consistent 算法。需要修改如下参数。

memcache.hash_strategy=consistent
memcache.hash_function=crc32

WebSocket

首先认识HTML5的websocket:

在HTML5规范中,我最喜欢的Web技术就是正迅速变得流行的WebSocket API。WebSocket提供了一个受欢迎的技术,以替代我们过去几年一直在用的Ajax技术。这个新的API提供了一个方法,从客户端使用简单的语法有效地推动消息到服务器。让我们看一看HTML5的WebSocket API:它可用于客户端、服务器端。而且有一个优秀的第三方API,名为Socket.IO。

什么是WebSocket API?

WebSocket API是下一代客户端-服务器的异步通信方法。该通信取代了单个的TCP套接字,使用ws或wss协议,可用于任意的客户端和服务器程序。WebSocket目前由W3C进行标准化。WebSocket已经受到Firefox 4、Chrome 4、Opera 10.70以及Safari 5等浏览器的支持。



WebSocket API最伟大之处在于服务器和客户端可以在给定的时间范围内的任意时刻,相互推送信息。WebSocket并不限于以Ajax(或XHR)方式通信,因为Ajax技术需要客户端发起请求,而WebSocket服务器和客户端可以彼此相互推送信息;XHR受到域的限制,而WebSocket允许跨域通信。


Ajax技术很聪明的一点是没有设计要使用的方式。WebSocket为指定目标创建,用于双向推送消息。

关于web实时通信技术的发展(poll,ajax,comet等)以及websocket的介绍具体请参见:

使用 HTML5 WebSocket 构建实时 Web 应用 http://www.linuxidc.com/Linux/2012-02/54014.htm

链接的文章介绍了websocket的旧版协议草案,并用.net实现了该草案。

在2011年7月份,websocket发布了最新版的协议草案,草案的最新版本是草案10,草案的链接地址为:http://tools.ietf.org/html/draft-ietf-hybi-thewebsocketprotocol-10,新的草案增加了安全性和可扩展性。

新草案客户端与服务器端的握手协议:

客户端发起websocket请求

[javascript]
  1. socket = new MozWebSocket("ws://localhost:12345/websocket/server.php")  

这里用的是firefox浏览器,所以用MozWebSocket(),其他浏览器像chrome,需要用WebSocket()

请求头信息格式:

[plain]
  1. GET /chat HTTP/1.1  
  2. Host: localhost:12345  
  3. Upgrade: websocket  
  4. Connection: Upgrade  
  5. Sec-WebSocket-Key: kHuChwCCkr9PZDPWo+nMXg==  
  6. Sec-WebSocket-Origin: http://localhost  
  7. Sec-WebSocket-Protocol: websocket  
  8. Sec-WebSocket-Version: 8  

服务器端取得请求信息,主要是Sec-WebSocket-Key的值,取得该值之后,连接上字符串258EAFA5-E914-47DA-95CA-C5AB0DC85B11,然后计算其sha1散列值,生成一个20位的字符串,再对该字符串进行base64编码,最后得到的值,按照下列响应信息格式返回给客户端

[plain]
  1. HTTP/1.1 101 Switching Protocols  
  2. Upgrade: websocket  
  3. Connection: Upgrade  
  4. Sec-WebSocket-Accept: 0VXXdxNQxqV7u7vtIhrxqdYUgRA=  
  5. Sec-WebSocket-Protocol: websocket  

客户端接收到服务器的响应信息,连接建立。

新草案的数据传输格式请参考下文:

    2、数据传输的格式:

以下是一个格式标准图:

点击查看原图

FIN:1位,用来表明这是一个消息的最后的消息片断,当然第一个消息片断也可能是最后的一个消息片断;

RSV1, RSV2, RSV3: 分别都是1位,如果双方之间没有约定自定义协议,那么这几位的值都必须为0,否则必须断掉WebSocket连接;

Opcode:4位操作码,定义有效负载数据,如果收到了一个未知的操作码,连接也必须断掉,以下是定义的操作码:
      *  %x0 表示连续消息片断
      *  %x1 表示文本消息片断
      *  %x2 表未二进制消息片断
      *  %x3-7 为将来的非控制消息片断保留的操作码
      *  %x8 表示连接关闭
      *  %x9 表示心跳检查的ping
      *  %xA 表示心跳检查的pong
      *  %xB-F 为将来的控制消息片断的保留操作码

Mask:1位,定义传输的数据是否有加掩码,如果设置为1,掩码键必须放在masking-key区域,客户端发送给服务端的所有消息,此位的值都是1;

Payload length: 传输数据的长度,以字节的形式表示:7位、7+16位、或者7+64位。如果这个值以字节表示是0-125这个范围,那这个值就表示传输数据的长度;如果这个值是126,则随后的两个字节表示的是一个16进制无符号数,用来表示传输数据的长度;如果这个值是127,则随后的是8个字节表示的一个64位无符合数,这个数用来表示传输数据的长度。多字节长度的数量是以网络字节的顺序表示。负载数据的长度为扩展数据及应用数据之和,扩展数据的长度可能为0,因而此时负载数据的长度就为应用数据的长度。

Masking-key:0或4个字节,客户端发送给服务端的数据,都是通过内嵌的一个32位值作为掩码的;掩码键只有在掩码位设置为1的时候存在。
Payload data:  (x+y)位,负载数据为扩展数据及应用数据长度之和。
Extension data:x位,如果客户端与服务端之间没有特殊约定,那么扩展数据的长度始终为0,任何的扩展都必须指定扩展数据的长度,或者长度的计算方式,以及在握手时如何确定正确的握手方式。如果存在扩展数据,则扩展数据就会包括在负载数据的长度之内。
Application data:y位,任意的应用数据,放在扩展数据之后,应用数据的长度=负载数据的长度-扩展数据的长度。

    数据帧协议是按照扩展的巴科斯范式(ANBF:Augmented Backus-Naur Form RFC5234)组成的:       

[plain]
ws-frame                = frame-fin   
                          frame-rsv1   
                          frame-rsv2   
                          frame-rsv3   
                          frame-opcode   
                          frame-masked   
                          frame-payload-length   
                          [ frame-masking-key ]   
                          frame-payload-data   
 
 frame-fin               = %x0 ; 表示这不是当前消息的最后一帧,后面还有消息   
                        / %x1 ; 表示这是当前消息的最后一帧   
 
frame-rsv1              = %x0   
                          ; 1 bit, 如果没有扩展约定,该值必须为0    
 
 
frame-rsv2              = %x0   
                          ; 1 bit, 如果没有扩展约定,该值必须为0   
 
frame-rsv3              = %x0   
                          ; 1 bit, 如果没有扩展约定,该值必须为0   
 
frame-opcode            = %x0 ; 表示这是一个连续帧消息   
                        / %x1 ; 表示文本消息   
                        / %x2 ; 表示二进制消息   
                        / %x3-7 ; 保留   
                        / %x8 ; 表示客户端发起的关闭   
                        / %x9 ; ping(用于心跳)   
                        / %xA ; pong(用于心跳)   
                        / %xB-F ; 保留    
   
frame-masked            = %x0 ; 数据帧没有加掩码,后面没有掩码key   
                        / %x1 ; 数据帧加了掩码,后面有掩码key   
 
 
frame-payload-length    = %x00-7D   
                        / %x7E frame-payload-length-16   
                        / %x7F frame-payload-length-63   
   ; 表示数据帧的长度   

 
 
frame-payload-length-16 = %x0000-FFFF   
   ; 表示数据帧的长度   
   
frame-payload-length-63 = %x0000000000000000-7FFFFFFFFFFFFFFF   
   ; 表示数据帧的长度   
   
frame-masking-key       = 4( %0x00-FF ) ; 掩码key,只有当掩码位为1时出现   
   
frame-payload-data      = (frame-masked-extension-data   
                           frame-masked-application-data)   ; 当掩码位为1时,这里的数据为带掩码的数据,扩展数据及应用数据都带掩码   
                        / (frame-unmasked-extension-data   
                           frame-unmasked-application-data) ; 当掩码位为0时,这里的数据为不带掩码的数据,扩展数据及应用数据都不带掩码   
   
frame-masked-extension-data     = *( %x00-FF ) ; 目前保留,以后定义   
   
frame-masked-application-data   = *( %x00-FF )   
   
frame-unmasked-extension-data   = *( %x00-FF ) ; 目前保留,以后定义   
   
frame-unmasked-application-data = *( %x00-FF ) 

基本数据类型

C#数据类型
.NET框架数据类型
说 明
bool
System.Boolean
逻辑值,true或者false,默认值为false
byte
System.Byte
无符号的字节,所存储的值的范围是0~255,默认值为0
sbyte
System.SByte
带符号的字节,所存储的值的范围是-128~127,默认值为0
char
System.Char
无符号的16位Unicode字符,默认值为’/0’
decimal
System.Decimal
不遵守四舍五入规则的十进制数,通常用于财务方面的计算,默认值为0.0m
double
System.Double
双精度的浮点类型,默认值为0.0d
float
System.Single
单精度的浮点类型,默认值为0.0f
int
System.Int32
带符号的32位整型,默认值为0
uint
System.UInt32
无符号的32位整型,默认值为0
long
System.Int64
带符号的64位整型,默认值为0
ulong
System.UInt64
无符号的64位整型,默认值为0
object
System.Object
指向类实例的引用,默认值为null
short
System.Int16
带符号的16位整型,默认值为0
ushort
System.UInt16
无符号的16位整型,默认值为0
string
System.String
指向字符串对象的引用,默认值为null

 

C语言中 float、double、long double精度、数值范围

IEEE754浮点数的表示方法。C语言里对float类型数据的表示范围为-3.4*10^38~+3.4*10^38。double为-1.7*10^-308~1.7*10^308,long double为-1.2*10^-4932~1.2*10^4932.

类型

比特(位)数

有效数字

数值范围

float

32

6~7

-3.4*10^38~+3.4*10^38

double

64

15~16

-1.7*10^-308~1.7*10^308

long
double

128

18~19

-1.2*10^-4932~1.2*10^4932

decimal

128

28~29

±1.0*10^28 ~ ±7.9*10^28

 

基础类型描述:

byte: 八位整数 -128——127,可用来节省内存的使用。
short: 16位整数 -32768——32,767,也比较省内存。
int: 32位整数 -2,147,483,648——2,147,483,647,一般来说整数都够用了
long: 64位整数 -9,223,372,036,854,775,808—— 9,223,372,036,854,775,807,一般不需要用
float: 32位浮点,如果浮点需要节省内存用这个。
Double: 64位浮点,一般非整数浮点可用这个。

 

究竟如何计算该范围,分析如下:

对于单精度浮点数(float)来说,符号位一位,指数位8位,尾数23位。指数能够表示的指数范围为-128~127。尾数为23位。

float和double的精度是由尾数的位数来决定的。浮点数在内存中是按科学计数法来存储的,其整数部分始终是一个
隐含着的“1”,由于它是不变的,故不能对精度造成影响。float:2^23 =
8388608,一共七位,这意味着最多能有7位有效数字,但绝对能保证的为6位,也即float的精度为6~7位有效数字;double:2^52 =
4503599627370496,一共16位,同理,double的精度为15~16位。

 

其中负指数决定了浮点数所能表达的绝对值最小的非零数;而正指数决定了浮点数所能表达的绝对值最大的数,也即决定了浮点数的取值范围。float的范围为-2^128 ~
+2^128,也即-3.40E+38 ~
+3.40E+38;double的范围为-2^1024 ~
+2^1024,也即-1.79E+308
~+1.79E+308。

 

以float为例,如下表:

符号

尾数

指数

1

23

8

数符(+-)

小数部分(决定精度)

-127~128 指数(决定范围)

 

例如:

+1.1111111111111111111111*2^127(小数点后面23个1,由于尾数的范围1~2,其最高位总为1,故只需存取小数部分,所以小数为是23位1),约等于2*2^127=3.4*10^38。为3.4*10^38负数亦然。

Double的计算与此类似,double的符号位为63位,指数为62~52位,共11位。表示的范围为-1024~1023。尾数为51~0。表示的
范围为+1.1111111111111111..11111*2^1023(小数点后面52个1)为1.7*10^308。负数亦然。

 

mysql & java:

类型名称 显示长度 数据库类型 JAVA类型 JDBC类型索引(int)
VARCHAR L+N VARCHAR java.lang.String 12
CHAR N CHAR java.lang.String 1
BLOB L+N BLOB java.lang.byte[] -4
TEXT 65535 VARCHAR java.lang.String -1
INTEGER 4 INTEGER UNSIGNED java.lang.Long 4
TINYINT 3 TINYINT UNSIGNED java.lang.Integer -6
SMALLINT 5 SMALLINT UNSIGNED java.lang.Integer 5
MEDIUMINT 8 MEDIUMINT UNSIGNED java.lang.Integer 4
BIT 1 BIT java.lang.Boolean -7
BIGINT 20 BIGINT UNSIGNED java.math.BigInteger -5
FLOAT 4+8 FLOAT java.lang.Float 7
DOUBLE 22 DOUBLE java.lang.Double 8
DECIMAL 11 DECIMAL java.math.BigDecimal 3
BOOLEAN 1 同TINYINT
ID 11 PK (INTEGER UNSIGNED) java.lang.Long 4
DATE 10 DATE java.sql.Date 91
TIME 8 TIME java.sql.Time 92
DATETIME 19 DATETIME java.sql.Timestamp 93
TIMESTAMP 19 TIMESTAMP java.sql.Timestamp 93
YEAR 4 YEAR java.sql.Date 91