公司去年上了F5,好用是好用，但是费用太高昂了，所以最近一直在研究软负载均衡这一块儿，恰巧今年年初谷歌开源了seesaw，让自己可以绕过很多弯路。特此总结下之前了解的负载均衡策略。 －Sunface在分布式系统中，负载均衡是非常重要的环节，通过负载均衡将请求派发到网络中的一个或多个节点上进行处理。通常来说，负载均衡分为硬件负载均衡及软件负载均衡。硬件负载均衡，顾名思义，在服务器节点之间安装专门的硬件进行负载均衡的工作，F5便为其中的佼佼者。软件负载均衡则是通过在服务器上安装的特定的负载均衡软件或是自带负载均衡模块完成对请求的分配派发。一般而言，有以下几种常见的负载均衡策略：一.轮询。作为非常经典的负载均衡策略，早期该策略应用地非常广泛。其原理很简单，给每个请求标记一个序号，然后将请求依次派发到服务器节点中，适用于集群中各个节点提供服务能力等同且无状态的场景。其缺点也非常明显，该策略将节点视为等同，与实际中复杂的环境不符。加权轮询为轮询的一个改进策略，每个节点会有权重属性，但是因为权重的设置难以做到随实际情况变化，仍有一定的不足。二.随机。与轮询相似，只是不需要对每个请求进行编号，每次随机取一个。同样地，该策略也将后端的每个节点是为等同的。另外同样也有改进的加权随机的算法，不再赘述。三.最小响应时间。通过记录每次请求所需的时间，得出平均的响应时间，然后根据响应时间选择最小的响应时间。 ...继续阅读 (30)

  B~树               1.前言：动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树 (Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然对查找效率是有所提高的；还有一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，也就是这篇文章所要阐述的主题B~tre ...继续阅读 (13)

问题重现：小Y最近在甜品店工作,其工作是切蛋糕。现在有n个顾客来购买蛋糕，并且每个顾客有一个到达的时间，以及需要买的蛋糕的长度ai。由于小Y每次只能服务一个顾客，【问题严谨性补充：而顾客如果进店没有服务员立刻为他服务，他将离开】所以对于相冲突的顾客没有办法提供服务。问小Y最多能为多少位顾客提供服务。小Y能够决定是否卖蛋糕给某个顾客。如果答应顾客要买长度为ai的切糕，那么小Y还要将蛋糕切成单位长度给顾客。如果对ai的蛋糕切成x和ai-x，所花的时间代价为x*(ai-x)。例如，当一个用户在1时刻，需要长度为4的蛋糕，此时小Y可以将其先切成2分长度为2的，花费为4，再将两段长度为2的分别切成1,1的，花费分别为1和1，则总花费时间为4+1+1 = 6， 则小Y为该用户服务时间为6.已知第i位顾客进店时间，以及购买蛋糕大小。分析:涉及问题一：大小为n的蛋糕需要多长时间切成单位长度？f(x)=x*(n-x) 绘制函数草图可以得到：x=1时得到最小值，也就是说每次1单位1单位的切用数学归纳法证明上述的解得到的最终和解也是最小的n=2时 f(x)显然得到的最小解n=3时 f(x)显然得到的最小解n=4时 f(x)显然得到的最小解...假设n=i-1时也能得到最小解n=i时切成x 和(i-x)显然x必然是前面已经推出的n的一个解，i-x也是前面推出的一个解，而f(x)的最优解和f(i-x)就是每 ...继续阅读 (50)

struct(结构体)也是一种聚合的数据类型，struct可以包含多个任意类型的值，这些值被称为struct的字段。用来演示struct的一个经典案例就是雇员信息，每条雇员信息包含：员工编号，姓名，住址，出生日期，工作岗位，薪资，直属领导等。每个雇员的所有信息都可以存在一个struct中，该struct可以作为变量，或者作为函数的参数、返回值，或者被存到数组、切片中，等等。下面声明了一个Employee类型的结构体，还声明了一个Employee类型的变量dilbert：typeEmployeestruct{ IDintNamestringAddressstringDoB time.Time PositionstringSalaryintManagerIDint}vardilbert Employeedilbert的struct字段可以通过点操作符来访问，例如dilbert.Name和dilbert.Dob。同时dilbert的字段是变量，因此可以直接对成员赋值：dilbert.Salary -=5000// demoted, for writing too few lines of code也可以对成员进行取址，然后通过指针访问：position := &dilbert.Position *position ="Senior "+ *positi ...继续阅读 (38)

哈希表是一种非常好用、适用面很广的数据结构，是key-value对的无序集合。它的key是唯一的，通过key可以在常数复杂度时间内进行查询、更新或删除，无论哈希表有多大。Go语言的map类型就是对哈希表的引用，表示为map[key]value。map中所有的key都是相同的类型，所有的value也是相同的类型，不过key和value可以是不同的类型。key代表的数据类型必须支持==和!=运算符，这样map才能检测指定的key是否已经存在。虽然浮点数支持相等运算符，但是正如我们在第二章提到的，浮点数是不精确的，因此用它做key，不是个好想法，甚至最坏的情况可能发生用NaN来进行比较。value的数据类型是没有限制的。使用内置函数make创建map：ages :=make(map[string]int)// mapping from strings to ints也可以使用类似slice语法来创建map：ages :=map[string]int{"alice":31,"charlie":34, }这相当于：ages :=make(map[string]int) ages["alice"] =31ages["charlie"] =34还可以通过map[string]int{}来创建空map。Map中的元素可以通过key来访问：ages["alice"] =32fmt.Println(a ...继续阅读 (68)

Slice是长度可变的元素序列(数组不可变)，每个元素都有相同的类型。slice类型写作[]T，其中T代表slice中的元素类型；slice和数组写法很像，只是没有指定长度。数组和slice之间的联系非常紧密。slice是非常轻量的数据结构，它是引用类型，指向底层的一个数组，该数组被称之为slice的底层数组，slice可以访问底层数组的某个子序列，也可以访问整个数组。一个slice由三个部分组成：指针、长度、容量，指针指向了slice中第一个元素对应的底层数组元素的地址，因为slice未必是从数组第一个元素开始，因此slice中的第一个元素未必是数组中的第一个元素。长度对应slice中的元素数目，长度是不能超过容量的；容量一般是从slice中第一个元素对应底层数组中的开始位置，到底层数组的结尾的长度。内置函数len和cap分别返回一个slice的长度和容量。多个slice可以共享底层的数组，甚至它们引用的底层数组部分可以重叠。图4.1表示了一个数组，它的元素是每个月份的字符串名，还有两个slice,它们重叠引用了底层数组。数组定义：months := [...]string{1:"January",/* ... */,12:"December"}这里一月份是months[1]，十二月是months[12]。通常来说，数组第一元素索引从0开始，但是月份一般是从1月开始到12月，因此 ...继续阅读 (65)

Slice（切片）代表变长的序列，序列中每个元素都有相同的类型。一个slice类型一般写作[]T，其中T代表slice中元素的类型；slice的语法和数组很像，只是没有固定长度而已。数组和slice之间有着紧密的联系。一个slice是一个轻量级的数据结构，提供了访问数组子序列（或者全部）元素的功能，而且slice的底层确实引用一个数组对象。一个slice由三个部分构成：指针、长度和容量。指针指向第一个slice元素对应的底层数组元素的地址，要注意的是slice的第一个元素并不一定就是数组的第一个元素。长度对应slice中元素的数目；长度不能超过容量，容量一般是从slice的开始位置到底层数据的结尾位置。内置的len和cap函数分别返回slice的长度和容量。多个slice之间可以共享底层的数据，并且引用的数组部分区间可能重叠。图4.1显示了表示一年中每个月份名字的字符串数组，还有重叠引用了该数组的两个slice。数组这样定义months := [...]string{1:"January",/* ... */,12:"December"}因此一月份是months[1]，十二月份是months[12]。通常，数组的第一个元素从索引0开始，但是月份一般是从1开始的，因此我们声明数组时直接跳过第0个元素，第0个元素会被自动初始化为空字符串。slice的切片操作s[i:j]，其中0 ≤ i ...继续阅读 (30)

上一章我们深入学习了基本数据类型，它们是构建复杂数据类型的基础，是组成Go语言世界的原子。本章，我们将学习复合数据类型：通过不同的方式将基本类型组合起来。主要有四种复合类型－－数组，切片(slice)，map,结构体(struct)，在本章末尾，我们将展示如何通过struct来进行JSON编解码，同时配合template模板来生成HTML页面。数组和结构体都是聚合类型：数组是由元素组成，结构体由字段组成，无论是元素还是字段，在内存中都是连续排列的(这个极大的增加了内存的连续访问性，也是Go的一个重要优点，内存排列很紧密)。数组是同构类型－－每个元素的类型都是相同的；结构体是异构类型－－每个字段的类型都可以不同。数组和结构体的内存大小在初始化后都是固定的，相比之下，切片和map则是动态数据结构，它们的内存会按需增长。数组是同一类型元素组成的序列,长度是固定的，一个数组可以由零个或多个元素组成。因为数组长度是固定的，所以Go语言中很少直接使用数组，更多使用的是slice(切片)。slice是长度可变的元素序列，使用起来非常灵活，但是要理解切片，首先要理解数组(slice是底层数组的引用)。数组元素可以通过下标来访问，下标的取值范围是0到数组长度减1，内置len函数可以获取数组的长度(元素个数)：vara [3]int// 整形数组，包含3个元素fmt.Println(a[0])// 打 ...继续阅读 (39)

在Go语言中，常量表达式是在编译器求值的，因此在程序运行时是没有性能损耗的。常量的底层类型是前面提过的基本类型：布尔值，字符串，数值变量。常量的声明方式和变量很相似，但是常量的值是不可变的，因此在运行期是不可以对常量进行修改的。例如，对于π这种数学常数，常量显然比变量更适合，因为我们不允许这个值发生任何变化：constpi =3.14159// approximately; math.Pi is a better approximation可以同时声明多个常量：const( e =2.71828182845904523536028747135266249775724709369995957496696763pi =3.14159265358979323846264338327950288419716939937510582097494459)常量的相关运算也是在编译期完成的，这样不仅可以做相应的编译优化，也可以提升运行时的性能。如果一个表达式的操作数是常量，那么一些运行时的错误就可以提前在编译期发现：整数除以零、字符串索引越界、浮点数计算导致的正负无穷等等。常量作为操作数时，以下表达式的结果都是常量：算术、逻辑、比较运算，类型转换，len、cap、real、imag、comlex、unsafe.Sizeof。因为常量是在编译器确定的，因此可以作为一些类型的组成部分，比如数 ...继续阅读 (44)

写在最前:本文主要描述在网站的不同的并发访问量级下，Mysql架构的演变可扩展性架构的可扩展性往往和并发是息息相关，没有并发的增长，也就没有必要做高可扩展性的架构，这里对可扩展性进行简单介绍一下，常用的扩展手段有以下两种Scale-up :  纵向扩展，通过替换为更好的机器和资源来实现伸缩，提升服务能力Scale-out : 横向扩展,  通过加节点（机器）来实现伸缩，提升服务能力对于互联网的高并发应用来说，无疑Scale out才是出路，通过纵向的买更高端的机器一直是我们所避讳的问题，也不是长久之计，在scale out的理论下，可扩展性的理想状态是什么？可扩展性的理想状态一个服务，当面临更高的并发的时候，能够通过简单增加机器来提升服务支撑的并发度，且增加机器过程中对线上服务无影响(no down time)，这就是可扩展性的理想状态！ 架构的演变V1.0  简单网站架构一个简单的小型网站或者应用背后的架构可以非常简单,  数据存储只需要一个mysql instance就能满足数据读取和写入需求（这里忽略掉了数据备份的实例），处于这个时间段的网站，一般会把所有的信息存到一个database instance里面。在这样的架构下，我们来看看数据存储的瓶颈是什么？1.数据量的总大小  一个机器放不下时2.数据的索引 ...继续阅读 (67)

字符串是不可变的字节序列，虽然可以包含任意数据，包括0这个字节，不过字符串通常是用来包含可读性较强的文本。文本字符串通常采用UTF-8编码，由Unicode码点(rune)组成。内置的len函数会返回字符串的所有字节(byte)数(注意不是rune的数目！！一个rune可能包含多个字节)，下标操作s[i]可以获取字符串的第i 个字节(从0开始),   其中i >= 0 并且 i < len(s)：s := "hello, world" fmt.Println(len(s)) // "12" fmt.Println(s[0], s[7]) // "104 119" ('h' and 'w')访问索引边界外的字节会造成运行时panic：c := s[len(s)] // panic: index out of range字符串的第i个字节未必是字符串的第i个字符，因为对非ASCII码字符进行UTF-8编码时需要两个或者更多的字节。s[i:j]会基于原始字符串创建一个新的子字符串，这里取第i个字节到第j-1个字节：fmt.Println(s[0:5]) // "hello"如果索引越界或者j 小于i，会造成panic。也可以省略i或者j，或者两者都省略。如果省略i，那么默认从0开 ...继续阅读 (81)

布尔值有两种：true和false。if和for语句中的条件都是布尔值，比较运算符== 、<等也会产生一个布尔值。一元运算符! 是逻辑取反操作，所以!true就是false。Go语言提倡简洁的风格，因此我们会将x == true这种表达式直接写成x：if x {..} 。布尔值可以结合&&(AND) 、|| (OR)一起使用，这两个操作符都有短路特性，如果操作符的左边表达式就能决定结果了，那操作符右边的表达式不会求值：s != "" && s[0] == 'x'如果s是空字符串，那s[0]会panic，但是因为s为""的时候，&&左边的表达式是false，因此根据短路规则，&&右边的表达式不会求值，也就不会panic。因为&&比||的优先级更高，所以下面的条件表达式不需要括号：if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9' { // ...ASCII letter or digit... }在布尔值和数值之间并没有隐式的类型转换(再次强调，Go是强类型静态语 ...继续阅读 (21)

Go提供了两种大小的复数类型：complex64和complex128，分别由float32和float64组成。内置函数complex从指定的实部和虚部构建复数，内置函数real和imag用来获取复数的实部和虚部：var x complex128 = complex(1, 2) // 1+2i var y complex128 = complex(3, 4) // 3+4i fmt.Println(x*y) // "(-5+10i)" fmt.Println(real(x*y)) // "-5" fmt.Println(imag(x*y)) // "10"如果一个浮点数的字面量后面跟着一个i，例如3.141592i或2i，那么它将变成一个复数的虚部，这个复数的实部是0：fmt.Println(1i * 1i) // "(-1+0i)", i² = -1在常数运算规则中，复数常量可以加到普通数值常量上(整数或浮点，实部或虚部)，因此我们可以这样书写复数：1 + 2i 或者等价的 2i + 1。上面的x和y的声明语句可以这样简化：x := 1 + 2i y := 3 + 4i复数可以通过== 或 !=进行比较。两个复数相等当且仅当它们 ...继续阅读 (21)

Go提供了两种size的浮点数，float32和float64。它们的算术规范是由IEEE754国际标准定义，现代CPU都实现了这个规范。浮点数能够表示的范围可以从很小到很巨大，这个极限值范围可以在math包中获取，math.MaxFloat32表示float32的最大值，大约是3.4e38，math.MaxFloat64大约是1.8e308，两个类型最小的非负值大约是1.4e-45和4.9e-324。float32大约可以提供小数点后6位的精度，作为对比，float64可以提供小数点后15位的精度。通常情况应该优先选择float64，因此float32的精确度较低，在累积计算时误差扩散很快，而且float32能精确表达的最小正整数并不大，因为浮点数和整数的底层解释方式完全不同，具体见IEEE754详解。var f float32 = 16777216 // 1 << 24 fmt.Println(f == f+1) // "true"!浮点数字面量可以使用十进制数字表示：const e = 2.71828 // (非精确值)小数点前面或者后面的数字都可以省略，例如：.707 ， 1.   ，对于那种很小或者很大的数值最好用科学计数法，在指数前加上e或者E:const Avogadro = 6.02214129e23 // 阿伏伽德 ...继续阅读 (33)

第二章 序在计算机底层，一切都是比特位。然而计算机一般操作的都是固定大小的值，称之为字(word)。字会被解释为整数、浮点数、比特位数组、内存地址等，这些字又可以进一步聚合成数据包(packet)、像素点、作品集、诗歌或者其它任何对象。Go语言提供了多样化的数据组织方式，这些数据类型既有硬件层面的兼容性，又能让程序员方便的组合成更复杂的数据类型。Go语言的数据类型分为四大类：基本类型，复合类型，引用类型及接口类型。本章将介绍基本类型：数字，字符串，布尔值。    一、整数Go语言的数值数据类型包括以下几种：整数，浮点数，复数，每一种都包含了大小(size)不同的数值类型，例如有符号整数包含int8,int16,int32,int64,int。每一种数值类型都会决定值的大小和符号(正负)，我们首先从整数类型开始讲起。Go提供了有符号和无符号整数运算。有符号整数类型分为8bit,16bit,32bit,64bit四种：int8,int16,int32,int64，还有对应的无符号整数：uint8,uint16,uint32,uint64。还有两种整数类型，它们的大小是取决于机器平台的CPU字长的：int和uint，其中int是使用最广的。两种类型在不同平台上可能有不同的大小，32或64bit,但是我们在使用过程中不能有任何的假设，因为即使是在同一个机器平台 ...继续阅读 (29)

变量的作用域是指程序代码中可以有效使用这个变量的范围。不要将作用域和生命期混在一起。作用域是代码中的一块区域，是一个编译期的属性；生命期是程序运行期间变量存活的时间段，在此时间段内，变量可以被程序的其它部分所引用，是运行期的概念。语法块是包含在花括号内的一系列语句，例如函数体或者循环体。语法块内部声明的变量是无法被语法块外部代码访问的。我们可以扩展局部语法块的概念，在某些场景下，是不需要花括号的，这种形式称之为词法块。词法块分为几种：全局词法块，包含所有源代码；包 词法块，包含整个package;文件词法块，包含整个文件；for、if、switch语句的词法块；switch或select中的case分支的词法块；当然也包含之前提到的语法块。声明语句的词法块决定了变量的作用域。Go语言的内置类型、内置函数、内置常量都是全局词法块，因此它们都是全局作用域的，例如int、len、true等，可以在整个程序直接使用；对于导入的包，例如temconv导入的fmt包，是文件词法块，因此只能在当前文件中访问fmt包，这里fmt是全文件范围的作用域；tempconv.CToF函数中的变量c，则是局部词法块(语法块)的，因此它的作用域是函数的内部。控制语句后面的标签(label)，例如break、continue或goto后的标签，它们的作用域是在控制语句所在的函数内部。一个程序可能会有多个相同的变 ...继续阅读 (50)

一、PackageGo语言中的包(Package)就像其它语言的库(Library)或模块(Module)一样，支持模块化，封装性，可重用性，单独编译等特点。包的源码是由数个.go文件组成，这些文件所在的目录名是import路径的最后一个词，例如github.com/sunface/corego包的所有文件都存储在$GOPATH/src/github.com/sunface/corego底下。每个包都有独立的命名空间。例如，在image包中的Decode和unicode/utf16中的Decode是完全不同的函数。如果要引用第三方库的函数，我们要使用package.Func的形式，例如image.Decode和utf16.Decode。包也允许我们自己控制包内变量、函数的可见性。在Go语言中，变量、函数等的导出只取决于一个因素：名字首字母的大小写。想象一下，如果我们的温度转换软件开始流行了，然后希望贡献给开源社区，应该怎么做？首先让我们创建一个包github.com/sunface/temconv,在1.3节的例子基础上做一些变化。这个包中包含了两个文件，演示了怎么样把数据声明和数据访问分开，在现实项目中，这个包实际只需要一个文件。temconv.go包含了类型声明，常量，类型的method：package tempconv import "fmt" typ ...继续阅读 (15)

赋值(Assignment)变量的值可以通过赋值操作符 = 来更新， v = 10。x = 1 // 具名变量x *p = true // 指针变量 person.name = "bob" // 结构体struct的字段 count[x] = count[x] * scale // 数组、切片或者map的某个元素算数操作符和位操作符都有对应的一元操作符形式， v = v + x 等价于 v += x，例如：count[x] *= scale这样的缩略形式能省去不少重复的工作，同时数字变量还能通过++递增或者--递减：v := 1 v++ // same as v = v + 1; v becomes 2 v-- // same as v = v - 1; v becomes 1 again1.元组(tuple) 赋值元组赋值允许一次性给多个变量赋值。= 右边的表达式会在左边的变量被更新之前先求值，当＝左右两边都有同样的变量时，这种求值方式会非常有用,例如交换两个变量的值：x, y = y, x a[i], a[j] = a[j], a[i]再比如计算两个数的最大公约数(GCD)：func gcd(x, y int) int { for y != ...继续阅读 (36)

三.变量1声明变量使用var关键字可以创建一个指定类型的变量：var i int = 0 var i = 0 var i int以上三个表达式均是合法的，第三个表达式会将i初始化为int类型的零值，0；如果i是bool类型，则为false；i是float64类型，则为0.0；i为string类型，则为""；i为interface类型，则为nil；i为引用类型，则为nil；如果i是struct，则是将struct中所有的字段初始化为对应类型的零值。这种初始化机制可以保证任何一个变量都是有初始值的，这样在做边界条件条件检查时不需要担心值未初始化，可以避免一些潜在的错误，相信C和C++程序员的体会更加深入。var s string fmt.Println(s) // "" 这里的s是可以正常打印的，而不是导致某种不可预期的错误。可以在同一条语句中声明多个变量：var i, j, k int // int, int, int var b, f, s = true, 2.3, "four" // bool, float64, string包内可见的变量在main函数开始执行之前初始化，本地变量在函数执行到对应的声明语句时初始化。       变量也可以 ...继续阅读 (16)

Go语言核心技术系列文章都是我原创、或从国外的书籍和博客中收集优秀的文章进行翻译的，因此转载时请注明转载出处，不胜感激。欢迎大家加入Go语言核心技术QQ群894864，里面热心大神很多哦！ ...继续阅读 (16)

一.命名篇1.Go的函数、变量、常量、自定义类型、包(Package)的命名方式遵循以下规则：1）首字符可以是任意的Unicode字符或者下划线2）剩余字符可以是Unicode字符、下划线、数字   3）字符长度不限2.Go只有25个关键字break default func interface select case defer go map struct chan else goto package switch const fallthrough if range type continue for import return var3.Go还有37个保留字Constants:true false iota nil Types: int int8 int16 int32 int64 uint uint8 uint16 uint32 uint64 uintptr float32 float64 complex128 com ...继续阅读 (24)

  图7：三个策略的分区和key的位置。甲，乙，丙描述三个独立的节点，形成keyk1在一致性哈希环上的首选列表(N＝3)。阴影部分表示节点A，B和C形式的首选列表负责的keyrangee。黑色箭头标明各节点的Token的位置。策略3：每个节点Q/S个Token，大小相等的分区：类似策略2，这一策略空间划分成同样大小为Q的散列分区，以及分区布局(placement of partition)与划分方法(partitioning scheme)脱钩。此外，每个节点被分配Q/S个Token其中S是系统的节点数。当一个节点离开系统，为使这些属性被保留，它的Token随机分发到其他节点。同样，当一个节点加入系统，新节点将通过一种可以保留这种属性的方式从系统的其他节点“偷”Token。对这三个策略的效率评估使用S=30和N=3配置的系统。然而，以一个比较公平的方式这些不同的策略是很难的，因为不同的策略有不同的配置来调整他们的效率。例如，策略1取决于负荷的适当分配(即T)，而策略3信赖于分区的个数(即Q)。一个公平的比较方式是在所有策略中使用相同数量的空间来维持他们的成员信息时，通过评估负荷分布的偏斜. 例如，策略1每个节点需要维护所有环内的Token位置，策略3每个节点需要维护分配到每个节点的分区信息。在我们的下一个实验，通过改变相关的参数(T 和 Q),对这些策略进行了评 ...继续阅读 (15)

这也引入了一个耐用性漏洞(vulnerability)窗口：即使它只是在少数几个节点上持久化了但写入请求成功返回到客户端。传统的观点认为，耐用性和可用性关系总是非常紧密(hand-in-hand手牵手^-^)。但是，这并不一定总是真的。例如，耐用性漏洞窗口可以通过增加W来减少，但这将增加请求被拒绝的机率(从而减少可用性)，因为为处理一个写请求需要更多的存储主机需要活着。被好几个Dynamo实例采用的(n，R，W)配置通常为(3,2,2)。选择这些值是为满足性能，耐用性，一致性和可用性SLAs的需求。所有在本节中测量的是一个在线系统，其工作在(3,2,2)配置并运行在几百个同质硬件配置上。如前所述，每一个实例包含位于多个数据中心的Dynamo节点。这些数据中心通常是通过高速网络连接。回想一下，产生一个成功的get(或put)响应，R(或W)个节点需要响应协调员。显然，数据中心之间的网络延时会影响响应时间，因此节点(及其数据中心位置)的选择要使得应用的目标SLAs得到满足。6.1平衡性能和耐久性 虽然Dynamo的主要的设计目标是建立一个高度可用的数据存储，性能是在Amazon平台中是一个同样重要的衡量标准。如前所述，为客户提供一致的客户体验，Amazon的服务定在较高的百分位(如99.9或99.99)，一个典型的使用Dynamo的服务的SLA要求99.9％的读取和写入请求在 ...继续阅读 (12)

使用暗示移交，Dynamo确保读取和写入操作不会因为节点临时或网络故障而失败。需要最高级别的可用性的应用程序可以设置W为1，这确保了只要系统中有一个节点将key已经持久化到本地存储 ,　一个写是可以接受(即一个写操作完成即意味着成功)。因此，只有系统中的所有节点都无法使用时写操作才会被拒绝。然而，在实践中，大多数Amazon生产服务设置了更高的W来满足耐久性极别的要求。对N, R和W的更详细的配置讨论在后续的第6节。一个高度可用的存储系统具备处理整个数据中心故障的能力是非常重要的。数据中心由于断电，冷却装置故障，网络故障和自然灾害发生故障。Dynamo可以配置成跨多个数据中心地对每个对象进行复制。从本质上讲，一个key的首选列表的构造是基于跨多个数据中心的节点的。这些数据中心通过高速网络连接。这种跨多个数据中心的复制方案使我们能够处理整个数据中心故障。4.7处理永久性故障：副本同步 Hinted Handoff在系统成员流动性(churn)低，节点短暂的失效的情况下工作良好。有些情况下，在hinted副本移交回原来的副本节点之前，暗示副本是不可用的。为了处理这样的以及其他威胁的耐久性问题，Dynamo实现了反熵(anti-entropy，或叫副本同步)协议来保持副本同步。为了更快地检测副本之间的不一致性，并且减少传输的数据量，Dynamo采用MerkleTree[13]。 ...继续阅读 (15)

图2：Dynamo的划分和键的复制。一个负责存储一个特定的键的节点列表被称为首选列表(preference list)。该系统的设计，如将4.8节中解释，让系统中每一个节点可以决定对于任意key哪些节点应该在这个清单中。出于对节点故障的考虑，首选清单可以包含起过N个节点。请注意，因使用虚拟节点，对于一个特定的key的第一个N个后继位置可能属于少于N个物理所节点(即节点可以持有多个第一个N个位置)。为了解决这个问题，一个key首选列表的构建将跳过环上的一些位置，以确保该列表只包含不同的物理节点。4.4版本的数据 Dynamo提供最终一致性，从而允许更新操作可以异步地传播到所有副本。put()调用可能在更新操作被所有的副本执行之前就返回给调用者，这可能会导致一个场景：在随后的get()操作可能会返回一个不是最新的对象。如果没有失败，那么更新操作的传播时间将有一个上限。但是，在某些故障情况下(如服务器故障或网络partitions)，更新操作可能在一个较长时间内无法到达所有的副本。在Amazon的平台，有一种类型的应用可以容忍这种不一致，并且可以建造并操作在这种条件下。例如，购物车应用程序要求一个“添加到购物车“动作从来没有被忘记或拒绝。如果购物车的最近的状态是不可用，并且用户对一个较旧版本的购物车做了更改，这种变化仍然是有意义的并且应该保留。但同时它不应取代当前不可用的状态， ...继续阅读 (34)

对称性：每个Dynamo节点应该与它的对等节点(peers)有一样的责任;不应该存在有区别的节点或采取特殊的角色或额外的责任的节。根据我们的经验，对称性(symmetry)简化了系统的配置和维护。去中心化：是对对称性的延伸，设计应采用有利于去中心化而不是集中控制的技术。在过去，集中控制的设计造成系统中断(outages)，而本目标是尽可能避免它。这最终造就一个更简单，更具扩展性，更可用的系统。异质性：系统必须能够利用异质性的基础设施运行。例如，负载的分配必须与各个独立的服务器的能力成比例。这样就可以一次只增加一个高处理能力的节点，而无需一次升级所有的主机。3相关工作3.1点对点系统已经有几个点对点(P2P)系统研究过数据存储和分配的问题。如第一代P2P系统Freenet和Gnutella，被主要用作文件共享系统。这些都是由链路任意建立的非结构化P2P的网络的例子。在这些网络中，通常是充斥着通过网络的搜索查询以找到尽可能多地共享数据的对等节点。P2P系统演进到下一代是广泛被称为结构化P2P。这些网络采用了全局一致的协议，以确保任何节点都可以有效率地传送一个搜索查询到那些需要数据的节点。系统，如Pastry[16]和Chord[20]使用路由机制，以确保查询可以在有限的跳数(hops)内得到回答。为了减少多跳路由引入的额外延时，有些P2P系统(例如，[14])采用O(1)路由，每个节点 ...继续阅读 (20)

Dynamo：Amazon的高可用性的键-值存储系统摘要 巨大规模系统的可靠性是我们在Amazon.com，这个世界上最大的电子商务公司之一，面对最大的挑战之一，即使最轻微的系统中断都有显着的经济后果并且影响到客户的信赖。Amazon.com平台，它为全球许多网站服务，是实现在位于世界各地的许多数据中心中的成千上万的服务器和网络基础设施之上。在这一规模中，各种大大小小的部件故障持续不断发生，管理持久化状态的方法在面对这些故障时，驱使软件系统的可靠性和可扩展性。本文介绍Dynamo的设计和实现，一个高度可用的key-value存储系统，一些Amazon的核心服务使用它用以提供一个“永远在线”的用户体验。为了达到这个级别的可用性，Dynamo在某些故障的场景中将牺牲一致性。它大量使用对象版本和应用程序协助的冲突协调方式以提供一个开发人员可以使用的新颖接口。1简介 Amazon运行一个全球性的电子商务服务平台，在繁忙时段使用位于世界各地的许多数据中心的数千台服务器为几千万的客户服务。Amazon平台有严格的性能，可靠性和效率方面操作要求，并支持持续增长，因此平台需要高度可扩展性。可靠性是最重要的要求之一，因为即使最轻微的系统中断都有显著的经济后果和影响客户的信赖。此外，为了支持持续增长，平台需要高度可扩展性。我们组织在运营Amazon平台时所获得的教训之一是，一个系统 ...继续阅读 (11)

当我们在生产线上用一台服务器来提供数据服务的时候，我会遇到如下的两个问题：1）一台服务器的性能不足以提供足够的能力服务于所有的网络请求。2）我们总是害怕我们的这台服务器停机，造成服务不可用或是数据丢失。于是我们不得不对我们的服务器进行扩展，加入更多的机器来分担性能上的问题，以及来解决单点故障问题。 通常，我们会通过两种手段来扩展我们的数据服务：1）数据分区：就是把数据分块放在不同的服务器上（如：uid % 16，一致性哈希等）。2）数据镜像：让所有的服务器都有相同的数据，提供相当的服务。对于第一种情况，我们无法解决数据丢失的问题，单台服务器出问题时，会有部分数据丢失。所以，数据服务的高可用性只能通过第二种方法来完成——数据的冗余存储（一般工业界认为比较安全的备份数应该是3份，如：Hadoop和Dynamo）。 但是，加入更多的机器，会让我们的数据服务变得很复杂，尤其是跨服务器的事务处理，也就是跨服务器的数据一致性。这个是一个很难的问题。 让我们用最经典的Use Case：“A帐号向B帐号汇钱”来说明一下，熟悉RDBMS事务的都知道从帐号A到帐号B需要6个操作：从A帐号中把余额读出来。对A帐号做减法操作。把结果写回A帐号中。从B帐号中把余额读出来。对B帐号做加法操作。把结果写回B帐号中。为了数据的一致性，这6件事，要么都成功做完，要么都不成功，而且这个操作的过程中，对A、B帐号的其它 ...继续阅读 (14)

最近项目中遇到了一个分布式系统的并发控制问题。该问题可以抽象为：某分布式系统由一个数据中心D和若干业务处理中心L1，L2 … Ln组成；D本质上是一个key-value存储，它对外提供基于HTTP协议的CRUD操作接口。L的业务逻辑可以抽象为下面3个步骤：read: 根据keySet {k1, … kn}从D获取keyValueSet {k1:v1, … kn:vn}do: 根据keyValueSet进行业务处理，得到需要更新的数据集keyValueSet’ {k1′:v1′, … km’:vm’} (注：读取的keySet和更新的keySet’可能不同)update: 把keyValueSet’更新到D （注：D保证在一次调用更新多个key的原子性）在没有事务支持的情况下，多个L进行并发处理可能会导致数据一致性问题。比如，考虑L1和L2的如下执行顺序：L1从D读取key:123对应的值100L2从D读取key:123对应的100L1将key:123更新为100 + 1L2将key:123更新为100 + 2如果L1和L2串行执行，key:123对应的值将为103，但上面并发执行中L1的执行效果完全被L2所覆盖，实际key:123所对应的值变成了102。解决方案1：基于锁的事务为了让L的处理具有可串行化特性(Serializability)，一种最直接的解决方案就是考虑为D加上基于 ...继续阅读 (33)

 系统级别perf top, dstat -tam, vtune 都能很好分析beam 瓶颈，本文主要erlang 级别排查：1. 反编译   确认线上运行代码是否正确，reltools没掌握好，升级偶尔出现问题decompile(Mod) ->{ok,{_,[{abstract_code,{_,AC}}]}}=beam_lib:chunks(code:which(Mod), [abstract_code]), io:format("~s~n", [erl_prettypr:format(erl_syntax:form_list(AC))]). 2. 进程栈    类似于jstack，发现大量进程挂起，进程数过高，运行慢，hang住等问题用到pstack(Reg)whenis_atom(Reg) ->casewhereis(Reg)ofundefined->undefined; Pid->pstack(Pid)end; pstack(Pid)->io:format("~s~n", [element(2, process_info(Pid, backtrace))]). 3. etop  分析内存、cpu占用进程 ...继续阅读 (34)