一致性 hash 算法( consistent hashing )

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 所示的那样。

CentOS 6.3下Samba服务器的安装与配置

一、简介 Samba是一个能让Linux系统应用Microsoft网络通讯协议的软件,而SMB是Server Message Block的缩写,即为服务器消息块 ,SMB主要是作为Microsoft的网络通讯协议,后来Samba将SMB通信协议应用到了Linux系统上,就形成了现在的Samba软件。后来微软又把 SMB 改名为 CIFS(Common Internet File System),即公共 Internet 文件系统,并且加入了许多新的功能,这样一来,使得Samba具有了更强大的功能。 Samba最大的功能就是可以用于Linux与windows系统直接的文件共享和打印共享,Samba既可以用于windows与Linux之间的文件共享,也可以用于Linux与Linux之间的资源共享,由于NFS(网络文件系统)可以很好的完成Linux与Linux之间的数据共享,因而 Samba较多的用在了Linux与windows之间的数据共享上面。 SMB是基于客户机/服务器型的协议,因而一台Samba服务器既可以充当文件共享服务器,也可以充当一个Samba的客户端,例如,一台在Linux 下已经架设好的Samba服务器,windows客户端就可以通过SMB协议共享Samba服务器上的资源文件,同时,Samba服务器也可以访问网络中 其它windows系统或者Linux系统共享出来的文件。 Samba在windows下使用的是NetBIOS协议,如果你要使用Linux下共享出来的文件,请确认你的windows系统下是否安装了NetBIOS协议。 组成Samba运行的有两个服务,一个是SMB,另一个是NMB;SMB是Samba 的核心启动服务,主要负责建立 Linux Samba服务器与Samba客户机之间的对话, 验证用户身份并提供对文件和打印系统的访问,只有SMB服务启动,才能实现文件的共享,监听139 TCP端口;而NMB服务是负责解析用的,类似与DNS实现的功能,NMB可以把Linux系统共享的工作组名称与其IP对应起来,如果NMB服务没有启动,就只能通过IP来访问共享文件,监听137和138 UDP端口。 例如,某台Samba服务器的IP地址为10.0.0.163,对应的工作组名称为davidsamba,那么在Windows的IE浏览器输入下面两条指令都可以访问共享文件。其实这就是Windows下查看Linux Samba服务器共享文件的方法。 \\10.0.0.163\共享目录名称 \\davidsamba\共享目录名称 Samba服务器可实现如下功能:WINS和DNS服务; 网络浏览服务; Linux和Windows域之间的认证和授权; UNICODE字符集和域名映射;满足CIFS协议的UNIX共享等。 二、系统环境 系统平台:CentOS release 6.3 (Final) Samba版本:samba-3.5.10-125.el6.x86_64 Samba Server IP:10.0.0.163 防火墙已关闭/iptables: Firewall is not running. SELINUX=disabled 三、安装Samba服务 1、在可以联网的机器上使用yum工具安装,如果未联网,则挂载系统光盘进行安装。 # yum install samba […]

Google Protocol Buffer 的使用和原理

简介   什么是 Google Protocol Buffer? 假如您在网上搜索,应该会得到类似这样的文字介绍: Google Protocol Buffer( 简称 Protobuf) 是 Google 公司内部的混合语言数据标准,目前已经正在使用的有超过 48,162 种报文格式定义和超过 12,183 个 .proto 文件。他们用于 RPC 系统和持续数据存储系统。 Protocol Buffers 是一种轻便高效的结构化数据存储格式,可以用于结构化数据串行化,或者说序列化。它很适合做数据存储或 RPC 数据交换格式。可用于通讯协议、数据存储等领域的语言无关、平台无关、可扩展的序列化结构数据格式。目前提供了 C++、Java、Python 三种语言的 API。 或许您和我一样,在第一次看完这些介绍后还是不明白 Protobuf 究竟是什么,那么我想一个简单的例子应该比较有助于理解它。   一个简单的例子   安装 Google Protocol Buffer   在网站 http://code.google.com/p/protobuf/downloads/list上可以下载 Protobuf 的源代码。然后解压编译安装便可以使用它了。 安装步骤如下所示: tar -xzf protobuf-2.1.0.tar.gz cd protobuf-2.1.0 ./configure –prefix=$INSTALL_DIR make make […]