咖啡伴侣

呆在上海
posts - 163, comments - 156, trackbacks - 0, articles - 2

new(T) 分配了零值填充的T
类型的内存空间,并且返回其地址,一个*T 类型的值。用Go 的术语说,它返回了一个
指针,指向新分配的类型T 的零值。有一点非常重要:
new 返回指针。

内建函数make(T, args) 与new(T) 有着不同的功能。它只能创建slice,map
和channel,并且返回一个有初始值(非零)的T 类型,而不是*T。本质来讲,导致这
三个类型有所不同的原因是指向数据结构的引用在使用前必须被初始化。

T{name:"aaa",age:11}
返回 T类型 而不是*T

posted @ 2013-10-08 10:49 oathleo 阅读(422) | 评论 (0)编辑 收藏

接着上回,对象序列化和反序的效率已经很高,试试原生数据的效率

先上代码
package main

import (
    "fmt"
    "math/rand"
    "opbuf"
    "time"
)

type RTValue struct {
    Time   int32
    Status int16
    Value  float32
}

func main() {

    size := 1000000
    col := make([]RTValue, size)
    for i := 0; i < size; i++ {
        col[i] = RTValue{Time: int32(i), Status: int16(i), Value: rand.Float32()}
    }

    fmt.Println("send data:", col[size-1])
    var opbuff *opbuf.OPBuffer = opbuf.NewOPBuffer()
    start := time.Now().UnixNano()
    for i := 0; i < size; i++ {
        //        opbuff.PutByte(col[i].Data)
        opbuff.PutInt32(col[i].Time)
        opbuff.PutInt16(col[i].Status)
        opbuff.PutFloat32(col[i].Value)
    }
    fmt.Println("send cost:", (time.Now().UnixNano()-start)/1000000)

    opbuff.Flush()

    start = time.Now().UnixNano()
    for i := 0; i < size; i++ {
        col[i].Time,_ = opbuff.GetInt32()
        col[i].Status,_ = opbuff.GetInt16()
        col[i].Value,_ = opbuff.GetFloat32()
    }
    fmt.Println("rev cost:", (time.Now().UnixNano()-start)/1000000)
    fmt.Println("rev data:", col[size-1])

}
123

Go原生代码性能:
total record: 1000000
send data: {999999 16959 0.69153386}
send cost: 93
rev cost: 61
rev data: {999999 16959 0.69153386}
 
结论:
1.不管什么语言,大批量同类型数据的传输,原生性能还是比第三方序列化 效率高很多
2.C++ 使用memcpy put 原始类型,效率还是比go高很多
C++原生代码性能:
total record 1000000
time pack 11 ms
time unpack 57 ms
 
 

posted @ 2013-09-29 09:57 oathleo 阅读(1153) | 评论 (0)编辑 收藏

模拟测试1,000, 000条数据 每条10个字节  也就是10M不到的 数据(高度结构化的数据)
过程
1.对象序列化为 byte
2.byte反序为对象
3.gzip压缩byte

测试语言go
测试方案: raw byte,json ,bson, msgpack (protostuff需要先做对象配置文件,比较麻烦,通常认为和msgpack性能相当 )
结果:msgpack 胜出


大小
gzip压缩后大小
对象到byte耗时
byte到对象耗时
raw 10000000
6573252(65%) 未测试
未测试
json
47515988 7919511 (17%) 3248ms 5280ms
bson
49888910 9506965 (19%)
3863ms 6235ms
msgpack
29934223 7448484 2046ms 3113ms


raw data: 1000000
raw data gzip compress: 6573252 //gzip压缩后大小

start: 1000000
Marshal cost: 3248  //json 序列化耗时
json string: 47515988 
json byte: 47515988  //二进制数组大小
Unmarshal cost: 5280  //json 反序列化耗时
test data: {1 100 0.9405091}
json gzip compress: 7919511 //gzip压缩后大小

start
Marshal cost: 3863
bson byte: 49888910
Unmarshal cost: 6235
test data: {1 100 0.9405091}
bson gzip compress: 9506965


start: 1000000
Marshal cost: 2046
msgpack: 29934223
Unmarshal cost: 3113
test data: {1 100 0.9405091}
msgpack gzip compress: 7448484

posted @ 2013-09-29 09:52 oathleo 阅读(3054) | 评论 (0)编辑 收藏

(本文包括章节:1、由来,2、算法简单回顾,3、演习道具,4、演习,5、算法提出者Leslie的八卦。hoho)

1、由来:

刘备接受了诸葛亮的提议,决定将paxos算法的思想应用到蜀帝国的决策机制上。然而,玄德生性谨慎,决定先行试点,实践下可行性。孔明提议,由蜀国五大肌肉男:关羽、张飞、赵云、马超、黄忠,做为决策者,而廖化、周仓、魏延分别无序的提出关于同一件事的水火不容的三个提案,孔明坚信:即使脑残者使用了paxos算法,也不会出现冲突的政令不一情况。paxos算法理论以及刘备是怎么被孔明忽悠的部分,同学们可以参考上篇《paxos分布式一致性算法--讲述诸葛亮的反穿越》:http://blog.csdn.net/russell_tao/article/details/7244530


闲话少叙,书接上文。

为了少打点字,刘备与诸葛亮俩玻璃不再以对话形式出现了。他们设置了五个官署(五虎将办公地,相当于Server),三个提案点(周仓等三人,发起提案时的办公地。相当于Client),当然都不在一起,信使们从提案点到官署传递信息的话,正常情况下需要半个小时,也就是30分钟。这次演习,哥俩不关注学习情况,所以paxos第三段就不在演习内容里了。诸葛亮为廖化、周他、魏延对于事件e准备了三个自相矛盾的提案,我们分别用p1、p2和p3代替吧。先行说明提案:


事件e(也就是本次paxos实例):蜀国今后的发展路线

提案p1:学习红色锤子镰刀,走激进主义,一切发展按照计划进行,小民们凭票消费,银子多了也没用,集中力量办大事,崇尚国家垄断主义。

提案p2:学习自由联盟,走自由主义,宁失去效率也不失去公正,发展民营经济为先,民主、法制、新闻自由,通过这种公正来激发社会的整体创造力。

提案p3:坚持孔孟之道,走保守主义,兼顾黄老之学,坚信中学为体、西学为用,国体不可大改,走有大汉国情的老路让别人说去吧。


2、算法简单回顾

我们再简单回顾下提案者和作为决策者的五虎将行动准则,共有六步,书记官(暂让五虎将兼职)负责记录下通过的提案p(通过了就叫法令了),这样,我们用1a,1b,2a,2b,3a,3c来表述全部的六步。(这六步就是三段式提交了,这在上篇《paxos分布式一致性算法--讲述诸葛亮的反穿越》里讲过,不再复述。)

魏延、廖化、周仓:

1a,作为提案者,首先向刘备要到个编号,搞清楚自己对事件e的态度。记录下当前时间,接下来向五虎将的多数派(3个或以上)发送事件+编号。

2a,此时开始处理五虎将的回应,这就有多种情况了。收到明确拒绝就得放弃!检查沙漏,如果到达时间限制了,还没有足够的多数派回应,那么就试着给五虎将的其他人再发送提案看看。如果收到了足够的五虎将里多数派的回应,那么,确定在2a这步里,如果要提案,到底提哪个提议?是自己现在要提的提案?

3a,提案者如果收到足够的五虎将多数派回应通过,则记录提案为通过的政策法令,同时通知所有书记官,也就是兼职的五虎将,把法令记录到羊皮纸上来。

五虎将:

1b,作为决策者,也需要沙漏,主要用于2b步骤后批准政策法令后,给自己设定个超时时间,若第三步信使没有过来,则超时后自动把提案变成政策法令记录到羊皮纸上。1b这个步骤是收到了信使的消息,来自于1a步骤里的提案者。收到事件e和编号N。五虎将这时将有可能出现三个动作:拒绝、通过以及第三个复杂点的动作,虽然通过但告诉魏延廖化,哥曾经批准过某提案了。(三种条件的达成请参考上篇文章《paxos分布式一致性算法--讲述诸葛亮的反穿越》)

2b,与1b步骤相同,唯一不一样的是,如果决定批准某个提案,必须先把该提案和编号记录到羊皮纸的背面。(羊皮纸的详细用途参见演习前提)

3b,记录法案到羊皮纸的正面上。(本步骤不在下面演习中出现)


3、演习道具

先解释下我们用到的道具吧。

羊皮纸(相当于硬盘):其正面记录真正通过的法令,背面相当于永久有效的草纸,背面记录一个三元组(S,V,Sh),S表示上次批准的提案编号,V表示上次批准的提案,Sh表示处理过的最大提案编号。(羊皮纸丢掉后的效果在演习结束后说明)

草纸:与羊皮纸背面相同,记录三元组。唯一不同的是,草纸容易丢失。

沙漏:记录时间。我们简单的认为,任何两个地方一次通讯时间为30分钟。所以,如果我们从提案者那出发,信使到五虎将再回来,我们认为一个小时足矣(忽略五虎将或者提案者的处理时间)。


下面的演习中,只有消息的丢失,实际上对于消息的重发和延迟,也不会有任何问题。只是对五虎将的缺席,需要做说明。如果五虎将的羊皮纸丢失,是不能直接再次加入进五人决策团的,必须学习到最新的状态。没丢羊皮纸,则可以随时加入进来。

书记官记录法令中的不一致情况这里不加讨论。


为了方便在图表中表示,我们先给五虎将五个字母编号:关羽a,张飞b,赵云c,马超d,黄忠e。

三种颜色表示不同的提案者:黄色表示廖化,蓝色表示周仓,红色表示魏延。


下面这幅图,表示不同的时间点,五虎将和三个提案者当时的状态。

->表示第一步预提案。包括1a和1b两步。

-->表示第二步提交提案,包括2a和2b。

五虎将记录的(s,v,sh)表示的三元组上面讲过了。法令项下面对应的是提案者魏、廖、周三人的状态。(wait)表示刚发出提案,1小时内等待返回呢。

e is drop表示发送给e黄忠的提案消息丢失了。

好了,可以往下看了。


4、演习

先放图,解释在下面。



详细说明上图:

8:30分上班了,红色周仓同学首先向关羽、赵云、黄忠三人发出了提案p1,编号为100,周仓开始等返回,预计9:30分时能收到三位的返回。我们假定,发给黄忠的信使出门就被孔明的跑车撞了。孔明闯祸后老实了,以下,不再出现信使失误事件了。

8:40分,崇尚民主的廖化同学向关羽、张飞、黄忠三人发出了编号为101的提案p2,预计9:40分收到返回的信使。

8:50分,喜欢孔孟的魏延同学向赵云、马超、黄忠三人发出了编号为110(魏延就是搞到大编号了啊)的提案p3,预计9:50收到返回的信使。

9:00整,周仓的提案p1到了关羽、赵云手里(黄忠没收到),两人无条件接受,记录(100,p1,100),承诺编号低于100的提案我可不会再处理了,然后两个信使开始返回。

9:10分,廖化编号为101的提案p2到了关羽、张飞、黄忠之手,张飞、黄忠哥俩从没收过事件e的提案,毫无疑问记为(101,p2,101),让信使回复接受。关羽则不然,红脸兄在10分钟前收到了周仓的编号为100的p1提案。所以,按规则办,关羽改自己的记录为(100,p1,101),让信使给廖化回复:你的编号101比较大,我同意你继续,不过我之前同意过一个编号为100的提案p1,请注意哦。

9:20分,魏延的p3提案到了赵云、马超、黄忠三人之手,马超第一次收到提案,记为(110,p3,110),回复批准。赵云和黄忠则不同,赵云收到过周仓的p1提案,这时要比提案编号了,魏延的110大于周仓的100,于是赵云记为(100,p1,110),告诉信使:我通过了,我承诺编号小于110的我不会处理,同时,我曾经批准过编号为100的提案p1。同理,黄忠记为(101,p2,110),也告诉信使:我曾经批准过编号为101的提案p2。

9:30分,周仓同学检测返回的信使了,关羽和赵云都返回批准,但是黄忠没有返回。因为必须N/2+1,也就是大多数人批准才行,所以,周仓向张飞发出提案p1。

9:40分,廖化收到了来自关羽、张飞、黄忠的回复,三人皆表示同意,但关羽表示:关某曾收到过编号100的p1提案。所以按照规则,廖化此时不能坚持自己原来的提案p2,而要改成关羽返回的提案p1,然后发起提交皆段,同样是让信使带给关羽、张飞、黄忠三人,我们用->>(a,b,e)表示。

9:50分,魏延收到了赵云、马超、黄忠三人在9:20分的答复,三人都同意了,但回答各不相同。马超没有多话,赵云说我曾收到过编号为100的p1提案,黄忠说我曾经收到过编号为101的p2提案。于是,魏延根据规则,不再提自己原来的p3提案,改为101编号对应的提案p2。接着,魏延开始向这三人发出提交请求,编号为110的提案p2。

10:00整,张飞收到了9:30分周仓补发的编号为100的提案p1,这之前,张飞在9:10分时曾经批准过来自廖化的提案p2,编号是101。所以,张飞在9:10时就已经承诺了,以后决不再处理编号小于101的提案。于是,张飞大吼一声:我拒绝。当然信使将会在10:30才能把消息带给周仓。

10:10分,关羽、张飞、黄忠收到了来自廖化于9:40分发出的(101,p1)提案,关羽和张飞都发现自己可以批准,记录到羊皮纸的背面,同时告诉信使:告诉廖化P1提案我批准了,我承诺编号小于101的提案不予理会。黄忠则不然,老将黄忠在9:20分时收到过魏延编号为110的提案,那时他批准了,意味着,所有小于110的提案他都会拒绝掉。这次廖化的提案才101,当然被拒绝掉了。三人的回复将于10:40会到达廖化处。

10:20分,魏延编号为110的P2提案到达赵云、马超、黄忠,三人没有疑问,毕竟110编号最大,都表示批准,并记录(110,p2,110)到各自的羊皮纸背面,回复信使通过。

10:30分,周仓收到了他在9:30分发给张飞的回复,张飞在10:00拒绝了,所以周仓这个提案就此作废。

10:40分,廖化收到了10:10来自关羽、张飞、黄忠的回复,关张二人批准,然而老黄忠明确表示拒绝,于是这次编号101的提案作废。

10:50分,魏延收到了赵云、马超、黄忠的回复,三人都表示批准,于是编号为110的提案p2最终作为法令记录下来(之后的3b学习过程略过),从此以后,蜀国的路线被确立为走民主路线,许多年后,蜀国统一了银河系。完。


以上任何步骤,大家可以任意制造难度,例如让同一个信使重复投递消息,或者延迟一天后消息到达某虎将处。或者让某个虎将正常如厕,而后正常归来。大家会发现,一致性是可以达到的,无论怎样,对于同一个事件e,互相冲突的三个法案:p1,p1,p3,一定只有一个可以达成。

对于任一虎将兄的挂掉,我们要分情况。如果是去大便,那么他的羊皮纸是不能丢的。大便完了,可以正常回到自己的官署办公。但是如果把羊皮纸丢了,那就不能立刻加入,必须向所有其他人学习,把失落的过程都学到,才能正常加入。这点至关重要,就是说,只要硬盘不坏,随时SERVER重启都能加入。硬盘一坏,对不起,学习完了才能继续办公。


5、后记---Leslie的八卦:

paxos算法是解决分布式服务数据一致性的终极算法,google的基础服务chubby(GFS的基础服务)的开发者说, “there is only one consensus(一致性) protocol, and that’s Paxos”。Microsoft有fast paxos论文,yahoo的zookeeper也用了paxos算法。可见,paxos是解决完全的分布式服务(无单点)间数据一致性的最好方法。但是paxos比较复杂,特别是网上的中文资料里少有能说得清楚的(主要是太多paxos变种算法了,掺合到一起搅得人头大),例如中文wiki上的paxos解释,光看这个是不可能搞懂paxos的。


paxos算法由Leslie Lamport在1990年提出,毫无疑问,paxos想解决的就是分布式环境下(server会挂掉,通讯协议不可靠,消息可能延迟、丢失、重发)如何保持数据一致性的问题。Leslie Lamport同学在1982年提出的“拜占庭将军”问题上尝到了甜头,这也是个分布式环境下的一致性问题,Leslie通过类比的方式,伪造了“拜占庭将军”历史,通过这种简单的类比成功的简化了复杂的分布式环境,效果非常好。于是在1990年Leslie同样用类比的方式提出了paxos算法,该问题跟“拜占庭将军”问题的区别是,“拜占庭将军”允许有叛徒,也就是允许伪造消息(默许被黑客攻击),而paxos则不允许消息被伪造。

Leslie很有幽默感的把论文写成一个考古发现,至始至终都在虚构他的“考古发现”。他说在考古中发现了失落的文明:希腊的paxos小岛。这里的议员通过邮递员传递消息,议会中一个议员提出法案,多数议员批准后法案获得通过。当然无论议员还是邮递员,都是兼职的,他们不可靠,随时可能走人,呵,典型的分布式环境,server可以挂,消息可以丢。Leslie根据考古文献反推出了paxos议会如何搞定法案一致性的问题。

发表论文时,Leslie一直用这种语气在写论文,于是《ACM Transactions on Computer Systems》编辑们认为太荒诞了,不能从头到尾虚构故事吧?毕竟是严谨的科学杂志,于是打回。Leslie同学身为牛人,坚持自己的看法,同时认为编辑们没有幽默感,拒绝修改。时间流逝,一晃九年过去,九年后有团队根据该论文开发出一个paxos实现,终于,编辑们低头了,允许发布Leslie的论文,但还是加了段编者著,在其中表示Leslie其实是个热爱计算机技术的考古学家!也算稍事解嘲。


写这两篇文章,我也试了下借喻的手段,用我们熟悉的三国人物,看看能否讲清楚paxos。其实paxos的算法本身算不得很复杂,但如果想讲清楚在各种异常情形下paxos算法的表现,给大家带来的明确的直观感受:paxos确实能解决一致性问题,这就不容易了。所以篇幅所限,只写了丢失一个消息的情况。不过大家如果从头看到这,应该可以简单的任意推导出其他异常吧?


最后,上面说的只是算法机制,如果需要了解现有的各种产品实现,最方便的还是看zookeeper源码,毕竟是开源的,例如去:http://zookeeper.apache.org/doc/r3.3.2/zookeeperOver.html,可以看下概述。淘宝开发团队有许多关于zookeeper实现的文章,到网上搜下就能看到。

对google的chubby实现,因为不是开源的,只有篇论文可以看:http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/zh-CN/us/archive/chubby-osdi06.pdf

posted @ 2013-09-28 10:16 oathleo 阅读(646) | 评论 (0)编辑 收藏

一日,诸葛亮找到刘备,突然献上一曲《独角戏》,而后放声大哭。刘备正沉醉于新曲,暗叹孔明大才,竟作得如此不凡仙乐,看到孔明忽而大悲,慌问:“水,何事悲恸?”
 
诸葛亮止住抽泣:“亮自主公三顾茅庐出山以来,蒙主公厚爱,自比如鱼得水,敢不尽力?然每日击鼓升帐,皆亮一人在上唱独角戏,众将在下唯唯诺诺,只是照亮的安排做事。如此下去,亮日后定会被司马懿那厮累死呀。”
刘备眨着充满问号的大眼睛:“孔明可是说曹贼丞相府小小的主薄司马懿?他有何德何能。。。”
诸葛亮慌打断:“亮心有些乱,且不提司马懿那小子。”
诸葛亮正襟危坐:“主公,我们要法制不要人制呀!万一哪天亮西去。。。”(刘备止含泪花握住孔明双手,孔明亦紧紧反握住刘备的大手)
半晌,诸葛亮续道:“岂不人亡政息?且主公百年后,阿斗与亮的关系又怎能比得如今亮与主公般相敬如宾?若亮在外争战,阿斗与亮政见不合要亮退兵,决策没有一致性,必将造成大错!如此,我大蜀何以恢复汉室江山呀?!”
刘备:“备深感如此。”
诸葛亮:“亮昨夜夜观天象。。。”
刘备大喜:“孔明可有良法?”
诸葛亮:“。。。亮昨夜夜观天象,竟然睡着,原来近日太耗心力。做一梦,数千年弹指间,亮醒来才觉泪流满面。梦中一帅哥自称陶辉,献上色目人大牛Leslie一法名paxos,或可解我等燃眉之急。”
刘备狂喜:“好!”继而搔了搔头:“先请孔明试言我大蜀帝国决策上有哪些问题?”
诸葛亮:“喏。”



1、蜀国现在决策制度的缺陷
诸葛亮:“主公,当下蜀国所有决策皆来自亮,这有两个问题,一、若亮身体有恙则政令必有耽误。二、随着汉中的收复,我们的地盘越来越大,事务也越来越多,目前亮乃五百年不世出奇才,尚能支撑,可若是将来收复长安,亮一人之力必不堪重负。请问主公有何策解此二难?”


刘备沉吟着:“可让法正法孝直,黄权黄公衡为你副手,平日助你共同议政决策,能帮你减负呀。孔明你老习惯在初一十五深入民间依红偎翠,那时他们都可暂时顶替于你,如此也不怕政令耽误了。”
诸葛亮咳嗽了下:“此二人皆治世之才!然,若子龙请求黄公衡允许蜀棉私营,而同时主公又请求亮加强垄断这有钱途的行业--禁止蜀棉私营,文武百官令行两出,或听亮的搞国家垄断,或听黄公衡的搞民营经济,百姓何以自处?”

刘备沉思半晌,方答道:“我们把决策分为两部分,一种是新增政策,如我正准备加税。另一种是下级官员请求政令的解释,比如马超出征归来时问伤兵抚恤金是多少等等。这样,孔明可处理所有新增决策,法正与黄权只负责解释已有决策。下面官员在执行时,任意找你三人中清闲者,就某个事件询问有何政令可指导,需要增加新的法令时,则只能找孔明你,孔明你决定新法令后,再通知法正和黄权这哥俩,这样法令就同步且一致了。当孔明不在时,由法正顶上这个决策位置;法正不在时,由黄权顶上。如此可好?”
诸葛亮惊喜道:“善!这可是master-slave设计呀!”
刘备也睁大了双眼闪着问号。诸葛亮咳嗽了下:“亮昨夜未睡好,失言了。”

诸葛亮又说道:“可这样还有问题,日后若我们收复许昌洛阳建业后,那时新法令会更多,只允许一人处理新法令新决策,必然还会忙不过来!而且,人为的指定亮的第二顺拉继承者是法正,黄权为第三顺位,这样也不妥,在地位不平等时,若以后决策组又增加许多新人,或者同一时间多人一起吃酒吃坏肚子,都会非常麻烦。”

刘备拍案而起:“孔明你主张大家都是同样地位,没有主次之分?这样无论哪个人出问题了,都不会对蜀国有什么影响?而且多人之间信息共享后,不会因人废事,也不会有人亡政息之事了?”
诸葛亮:“Bingo! 全对!这是真正的分布式!”
刘备大声叫好:“分布式?好名字,和八阵图一样响亮呀!”
诸葛亮:“但这完全平等的分布式决策机制,仍然必须政令统一,不能有不一致的法令,例如黄权认为他昨天中午通过的法令是嚼口香糖者一律杖责十板,免得有人随地乱吐影响市容(好象他们还立法大便后必须冲马桶)。而法正却在昨天上午就接受番邦李光耀的提议,允许嚼外国进口环保口香糖,百姓到底听谁的呢?”
刘备:“我知道孔明你很讨厌威权国家,别老抱怨,新加坡又没碍你事。上面这就是一致性问题了。孔明别卖关子了,快说你的paxos解决方法吧。”



2、paxos需要解决的分布式问题
诸葛亮激动道:“paxos可是真正的民主呀,两千年后我们汉人仍然做不到,这不是汉人的劣根性(乌坎村都能办好的),实是历史遗毒呀。闲话少叙,我们先来看看除了能保持一致性,paxos能解决哪些问题吧。

一、决策委员会里缺了哪个人都可以,蜀国照常做出决策。

二、大家的办公地又不在一起,平时通过信使小吏们传递消息,若信使在路上传消息时被马车撞死,仍然不会有政令不一致。

三、若信使被马车撞伤了,医治后迟了几个月才送到某人(例如法正),还不会出现政令不一致。

四、若信使被马车撞失忆了,以为刚送过消息的黄权还没送过,又跑去告诉黄权一次,同样不会有不一致出现。”
刘备:“孔明,我知道你马车机关多,开名车也不用总提嘛!若是信使被曹操的间谍收买了也没事吗?”
诸葛亮尴尬道:“这个不行,我们还是要相信人性本善嘛。呃,蜀国大部分都是好人。嗯,好吧,我们国安局不是吃干饭的,信使可以丢失、重复传递、延迟,但是我们保证不会被收买的。”
刘备:“好吧,能解决这四个问题也很不错,基本异常都考虑到了。快说说这个paxos解决之道吧。”



3、paxos的约束条件
诸葛亮:“刚刚不是说了民主吗?民主是个宝呀,它能解决一切问题。决策者之间不分高下,所以既然想要他们保持一致,我们就要用投票,少数服从多数!”
刘备:“怎么个投法?”
诸葛亮:“如果主公手下五虎上将是五个决策者。。。”刘备:“那五个肌肉男?”
诸葛亮:“正是,这证明即使五个头脑简单的武夫也能做好。”(五虎将齐打喷嚏。)
诸葛亮:“谁提议新政令(提案者),谁就发起投票。我们保证,投票者必须是决策者中的大多数。”
刘备:“怎么定大多数呢?”
诸葛亮:“任意两次投票中,必须有重合的决策者,这就是大多数了。比如五虎将做决策者,每次政令通过中,必须有三个人或更多投票的人才能决定,这样两次投票中至少有一人都参加了,他就可以拍板!对提案者来说,如果大多数投票者都投赞成这个提议,法令就通过。”
刘备沉重地说道:“孔明,万一总是凑不成大多数,岂不是耽误我们的现代化进程?民主,对中国国情来说,太复杂了。”

诸葛亮又激动了:“主公,不复杂的,长远来看好处很明显,不要短视!如果能做到以个三个基本点,所有政令绝对不会出现不一致,而且不会出现无法进行下去的事。一、所有政令必须被提出后才能批准;二、一次提出政令的过程中,只能批准一条政令;三、书记官(负责永久记录政令的官员)只能学习已经批准的政令。只要做到这三点,肯定不会政令不一致!”
刘备:“可是孔明,你在说什么呀?我只想知道决策者该怎么做。”
诸葛亮自信满满:“别急主公,从数学上可以证明,只要满足上面三条,一定不会出现政令不一。当然,这三条太宽泛了,不能对决策者做出指导。我还有更加严格的约束。一、每个决策者必须接受他收到的第一个提议政令。”
刘备:“凭什么呀?”诸葛亮:“我们要假定提议者已经搞清楚了一切,肯定是好提案啦。这不是我们的重点,别打断我。”
诸葛亮:“二、一旦关于一件事,我们通过一条法令后,之后关于这件事通过的任何法令,都还得是这个法令。”
刘备呆了下:“这不废话吗?”
诸葛亮自信满满:“虽然是废话,但你想,保证了这第2条,是不是所有的政令都必须一致呀?”
刘备:“可是对决策者没指导意义呀。”
诸葛亮自信满满:“是的,所以,我们加强约束,三、如果一条法令批准后,之后每一个决策者如果关于这件事又通过法令,那这个法令还得是同一条。”
刘备傻了:“你说得是没错,可这有什么用呢?”
诸葛亮自信满满:“所以继续加强约束:四、如果一条法令被批准通过了,之后提议者关于这件事,又提新法令,必须还得是同一个法令。”
刘备怒了:“孔明我想揍你了,你说这些有个屁用啊!”
诸葛亮自信满满:“别急主公,现在我要祭出最强约束条件作为我的奥义了:五、每个提案都得有个独一无二的编号,如果编号N的提案通过了,那么大多数决策者们,要么从没接受者编号小于N的任何提议,要么最近一次批准通过的法令就是这个提案。”
刘备开始追打诸葛亮:“孔明你个坏人,你玩我呀!这屁话你对我说!”
诸葛亮边逃边喊:“wiki里就是这么解释的,哎,主公你不懂数学别打我嘛。Leslie的论文也是这么写的。。。”



4、paxos执行流程
刘备:“真爽,孔明你手感不错。说点实在的吧,不懂的东西少扯。”
诸葛亮:“主公,你不懂数学嘛。好吧,我来说说paxos算法的流程,就三段式,六个步骤而已。角色包括,提案者,决策者,书记官(学习政令的)。
一、提案者先从主公那里搞到个独一无二的编号,例如N。找到决策者们的多数派,就说五虎将吧,找到三个肌肉男先。假设,这个提案者来自成都,想提的是,外地蜀国将级官员不得无故进入魏国使者驻蜀驿馆。那么,提案者发给三个五虎将,提案中说,我现在有个编号N的提案,关于蜀国高级将领进出魏国使者驿馆的事,请回答我。”

二、五虎将们收到了关于使者驿馆事件的提案,编号是N。其中任一个决策者,比如赵云,他在收到N提案后,首先检查,之前关于魏国使者驿馆事件,有没有收到过提案啊?如果没收到,当然回复提案通过,同时赵云拿出自己的小本本记上,已经回复编号N的提案。如果收到过关于驿馆事件的编号M的提案,就检查编号M,如果M大于N,那么跟信使说,我拒绝这个提案。如果M小于N,回复通过,并且说,关于这事,上次我已经收到了编号M的提案了。

三、提案者如果收到多数决策者的通过回复,就开始正式提议了。这时,先检查五虎将的回复,如果都简单的回复通过,那么就正式提议之前想提议的《蜀国将级官员不得无故进入魏国使者驻蜀国驿馆》提案。如果决策者们不是简单的回复通过,而是说:这次我赵云通过了,但是我曾经回复过编号M的提案。这样,提案者需要从这次决策者们的回复中,找出所有编号M中的最大值。假设就赵云复杂的回复了,其他四人都是简单的回复通过。那么,提案者这次不能正式提议自己原来想提的,而要提议编号M对应的提案。

四、同第二步骤一样,五虎将们根据二步骤的准则,选择通过还是不通过。
五、提案者如果发现多数决策者同意了,意味着法令通过,这时他要记录法令,同时告诉书记官们。
六、书记官们在羊皮纸上记录法令。“



5、paxos算法里的各角色该做的事
刘备搔搔头:“孔明,你再说说提案者,决策者要做的事吧,书记官的很简单,就不用说了。”
诸葛亮:“主公,书记官的工作不简单啊,信使会传丢消息的,书记官也会生病的。我们既要在法令通过时主动通知书记官,又要允许书记官在对法令不清楚时过来主动询问。不过,既然主公想多了解提案者和决策者的工作,我就来详细说说。
一、提案者。首先他得从主公那搞来一个独一无二的编号。”
刘备:“我很忙的孔明,我是一把手哎。”
诸葛亮有些无奈:“就光给编号也不干呀!那让他们自己维护自己的编号吧,遇到编号相同时,按级别排序,例如按关羽、张飞、赵云、马超、黄忠排序。然后要找到五虎将的多数派,例如关张赵这三人,发自己要决定的事以及编号过去。这是第一步。在第三步时,又到了提案者要做工作了。如果关羽又不响应自己了,那么再发给黄忠问问看。直到有大多数人响应自己。对于响应的处理,有以下情况:
A、这些响应中,如果有人明确拒绝,比如赵云说,关于驿馆事件,我已经批了编号大于N的提案,那么这次提案最好就放弃吧,或者加大自己的编号,重复第一步再提!
B、张飞说我可以通过,但是之前我批准过驿馆事件编号小于N的提案,内容是允许进入达到政治避难目的。那么,这次提案内容必须变更为张飞之前提交的方案。
C、所有人都无条件通过。继续正式提交自己的方案。
到第五步,如果多数派批准了,那么方案正式成为法令。提案者要告诉书记官记录哦。”
刘备:“你这么说我就明白了嘛。多简单?先前搞七搞八的说了一大通。”
诸葛亮:“唉,先前的证明嘛。当然,微软还搞了个两段式提交,号称fast paxos,那个雅虎的zookeeper也是的,其实也就对第五步做了优化。主公,不要打我,你不用管我刚才说了什么。我们继续说决策者的工作。
第二步,决策者开始工作了。例如还是说赵云,他在收到N提案后,首先检查,之前关于魏国使者驿馆事件,有没有收到过提案啊?如果没收到,简单的回复提案通过,同时赵云拿出自己的小本本记上,已经回复编号N的提案。赵云同时承诺,以后收到编号小于N的关于驿馆事件的提案,保证不批!如果收到过编号M的提案,检查这上次编号M,如果M大于N,那么跟信使说,我拒绝这个提案。如果M小于N,回复通过,并且说,关于这事,上次我已经收到了编号M的提案了。
第四步决策者批准时也和上面一样。不过fast paxos等两段式的paxos改进算法,在这里决策者们已经可以记录法案了。”
刘备:“好孔明!我有些明白了,不过光说不练假把式,演习下吧。把五个肌肉男叫来,你我来提案,外加捣乱,你可以用你的跑车撞信使了,看看是否出现不一致。”
诸葛亮:“No problem。不过现在我口干舌燥,咱们下回再说吧。”(想从具体的演习,从时间和各种容错上看paxos的效用,敬请期待下篇《paxos算法如何容错的--讲述五虎将的实践》

posted @ 2013-09-28 10:15 oathleo 阅读(198) | 评论 (0)编辑 收藏

测试1000个数据 每个数据10个字节,分别使用字节、json、bson方式 存储,并用gzip压缩

结果bson比json还大一点,确实出乎意料

个人结论是BSON对比json更加适合存储,在传输上没有太大优势

  BSON相对JSon
1.更快的遍历速度
2.操作更简易
3.增加了额外的数据类型

raw data: 10000
raw data gzip compress: 6553

json string: 44524
json byte: 44524
json gzip compress: 8125

bson byte: 46910
bson gzip compress: 9721


package main

import (
    "bytes"
    "compress/gzip"
    "fmt"
    "labix.org/v2/mgo/bson"
    "math/rand"
)

type HisCollection struct {
    RTValues []RTValue
}

type RTValue struct {
    Time   int32
    Status int16
    Value  float32
}

func main() {
    fmt.Println("start")

    size := 1000
    col := make([]RTValue, size)

    for i := 0; i < size; i++ {
        col[i] = RTValue{Time: int32(i), Status: 100, Value: rand.Float32()}
    }

    his := HisCollection{RTValues: col}
    data, err := bson.Marshal(&his)
    if err != nil {
        panic(err)
    }
    //    fmt.Println(data)
    fmt.Println("bson byte:", len(data))

    var compress_data_buf bytes.Buffer
    writer := gzip.NewWriter(&compress_data_buf)
    defer writer.Close()

    writer.Write(data)
    writer.Flush()

    fmt.Println("bson gzip compress:",len(compress_data_buf.Bytes()))

}

package main

import (
    "bytes"
    "compress/gzip"
    "fmt"
    "math/rand"
    "openplant/opnet"
)

func main() {
    var compress_data_buf bytes.Buffer
    writer := gzip.NewWriter(&compress_data_buf)
    defer writer.Close()

    size := 1000
    for i := 0; i < size; i++ {
        writer.Write(opnet.WarpInt32ToByte(int32(i)))
        writer.Write(opnet.WarpInt16ToByte(int16(100)))
        writer.Write(opnet.WarpFloat32ToByte(rand.Float32()))
    }

    writer.Flush()

    fmt.Println("raw data:", 10000)

    fmt.Println("raw data gzip compress:", len(compress_data_buf.Bytes()))

}
111

package main

import (
    "bytes"
    "compress/gzip"
    "encoding/json"
    "fmt"
    "math/rand"
)

type HisCollection struct {
    RTValues []RTValue
}

type RTValue struct {
    Time   int32
    Status int16
    Value  float32
}

func main() {
    fmt.Println("start")

    size := 1000
    col := make([]RTValue, size)

    for i := 0; i < size; i++ {
        col[i] = RTValue{Time: int32(i), Status: 100, Value: rand.Float32()}
    }

    his := HisCollection{RTValues: col}

    data, err := json.Marshal(&his)

    fmt.Println("json string:", string(data))
    fmt.Println("json string:", len(string(data)))

    if err != nil {
        panic(err)
    }
    //    fmt.Println(data)
    fmt.Println("json byte:", len(data))

    var compress_data_buf bytes.Buffer
    writer := gzip.NewWriter(&compress_data_buf)
    defer writer.Close()

    writer.Write(data)
    writer.Flush()

    fmt.Println("json gzip compress:", len(compress_data_buf.Bytes()))

}

posted @ 2013-09-23 14:08 oathleo 阅读(3279) | 评论 (0)编辑 收藏

     摘要: 工作项目需要在java和c/c++之间进行socket通信,socket通信是以字节流或者字节包进行的,socket发送方须将数据转换为字节流或者字节包,而接收方则将字节流和字节包再转换回相应的数据类型。如果发送方和接收方都是同种语言,则一般只涉及到字节序的调整。而对于java和c/c++的通信,则情况就要复杂一些,主要是因为java中没有unsigned类型,并且java和c在某些数据类型上的长...  阅读全文

posted @ 2013-09-23 10:02 oathleo 阅读(215) | 评论 (0)编辑 收藏

bson的介绍不说了
golang下的解析包找到2个 一个是mongo的http://labix.org/gobson
,另外一个比较小众https://github.com/sbunce/bson

这里用的是mongo的作为例子。
对象加上不同的注解,
可以轻松转成xml json bson 想想都兴奋 
package main

import (
    "fmt"
    "labix.org/v2/mgo/bson"
)

type TestStruct struct {
    Name string
    ID   int32
}

func main() {
    fmt.Println("start")
    data, err := bson.Marshal(&TestStruct{Name: "Bob"})
    if err != nil {
        panic(err)
    }
    fmt.Println("%q", data)

    value := TestStruct{}
    err2 := bson.Unmarshal(data, &value)
    if err2 != nil {
        panic(err)
    }
    fmt.Println("value:", value)

    mmap := bson.M{}
    err3 := bson.Unmarshal(data, mmap)
    if err3 != nil {
        panic(err)
    }
    fmt.Println("mmap:", mmap)

}

posted @ 2013-09-22 16:08 oathleo 阅读(7618) | 评论 (0)编辑 收藏

Panic和Recover

Go没有像Java那样的异常机制,它不能抛出异常,而是使用了panicrecover机制。一定要记住,你应当把它作为最后的手段来使用,也就是说,你的代码中应当没有,或者很少有panic的东西。这是个强大的工具,请明智地使用它。那么,我们应该如何使用它呢?

Panic

是一个内建函数,可以中断原有的控制流程,进入一个令人恐慌的流程中。当函数F调用panic,函数F的执行被中断,但是F中的延迟函数会正常执行,然后F返回到调用它的地方。在调用的地方,F的行为就像调用了panic。这一过程继续向上,直到发生panicgoroutine中所有调用的函数返回,此时程序退出。恐慌可以直接调用panic产生。也可以由运行时错误产生,例如访问越界的数组。

Recover

是一个内建的函数,可以让进入令人恐慌的流程中的goroutine恢复过来。recover仅在延迟函数中有效。在正常的执行过程中,调用recover会返回nil,并且没有其它任何效果。如果当前的goroutine陷入恐慌,调用recover可以捕获到panic的输入值,并且恢复正常的执行。

下面这个函数演示了如何在过程中使用panic

var user = os.Getenv("USER")  func init() {     if user == "" {         panic("no value for $USER")     } } 

下面这个函数检查作为其参数的函数在执行时是否会产生panic

func throwsPanic(f func()) (b bool) {     defer func() {         if x := recover(); x != nil {             b = true         }     }()     f() //执行函数f,如果f中出现了panic,那么就可以恢复回来     return } 

最容易理解就是给个例子,文章里有例子:

package main  import(     "fmt"     //"os" )  var user = "" func inita() {     defer func(){         fmt.Print("defer##\n")     }()     if user == "" {         fmt.Print("@@@before panic\n")         panic("no value for user\n")         fmt.Print("!!after panic\n")     } }  func throwsPanic (f func()) (b bool){     defer func(){         if x:= recover(); x != nil{             fmt.Print(x)             b = true         }     }()     f()     fmt.Print("after the func run")     return }  func main(){     throwsPanic(inita) } 

执行结果:

D:\go>go run b.go
@@@before panic
defer##
no value for user

如上面所说的:

panicuser=""时,打断了函数的执行,fmt.Print("!!after panic\n")没有执行。 但函数中的延迟函数会正常执行,打印了 defer##。然后返回到调用该函数的地方,继续上面的过程。

直到执行完所有函数的defer,退出程序。Recover可以捕获到panic的值,上面的打印no value for user。并且恢复正常的执行。

posted @ 2013-09-22 09:32 oathleo 阅读(2221) | 评论 (0)编辑 收藏

Go语言的传参和传引用[OSC源创会主题补充1]

66人收藏此文章, 我要收藏发表于2天前(2013-09-14 22:10) , 已有1496次阅读 ,共12个评论

OSC源创会主题补充系列:

  1. Go语言的传参和传引用
  2. Go语言的类型转换和类型断言

Go语言规范虽然很简单, 但是深入掌握Go语言却需要很多底层知识.

本来第20期的武汉OSC源创会有Go语言的专题讲座, 谁知道说取消就取消了.

我最近也整理了一些Go语言资料, 有Go语言的历史/现状/未来发展的八卦和Go语言常见的问题和陷阱两个部分, 本来打算OSC源创会能和武汉的Gopher分享 下的, 谁知道(由于不是赞助商也不是微软的大牛)主办方根本不给任何的机会.

100+人数的交流会基本都是扯淡, 还是小规模的讨论沙龙比较靠谱, 以后再也不会去OSC源创会当听众了.

现在计划将各个小问题暂时作为博客发表.

传参和传引用的问题

很多非官方的文档和教材(包括一些已经出版的图书), 对Go语言的传参和引用的讲解 都有很多问题. 导致众多Go语言新手对Go的函数参数传参有很多误解.

而传参和传引用是编程语言的根本问题, 如果这个问题理解错误可能会导致很多问题.

slice不是引用!

首先, Go语言的函数调用参数全部是传值的, 包括 slice/map/chan 在内所有类型, 没有传引用的说法.

具体请看Go语言的规范:

After they are evaluated, the parameters of the call are passed by value to the function and the called function begins execution.

from: http://golang.org/ref/spec#Calls

什么叫引用?

比如有以下代码:

var a Object doSomething(a) // 修改a的值 print(a) 

如果函数doSomething修改a的值, 然后print打印出来的也是修改后的值, 那么就可以认为doSomething是通过引用的方式使用了参数a.

为什么slice不是引用?

我们构造以下的代码:

func main() {     a := []int{1,2,3}     fmt.Println(a)     modifySlice(a)     fmt.Println(a) }  func modifySlice(data []int) {     data = nil } 

其中modifySlice修改了切片a, 输出结果如下:

[1 2 3] [1 2 3] 

说明a在调用modifySlice前后并没有任何变化, 因此a必然是传值的!

为什么很多人误以为slice是引用呢?

可能是 因为很多新接触Go语言的新手, 看到Go语言的文档说Go的切片和C语言的数组类型, 而C语言的数组是传地址的(注意: 不是传引用!).

下面这个代码可能是错误的根源:

func main() {     a := []int{1,2,3}     fmt.Println(a)     modifySliceData(a)     fmt.Println(a) }  func modifySliceData(data []int) {     data[0] = 0 } 

输出为:

[1 2 3] [0 2 3] 

函数modifySliceData确实通过参数修改了切片的内容.

但是请注意: 修改通过函数修改参数内容的机制有很多, 其中传参数的地址就可以修改参数的值(其实是修改参数中指针指向的数据), 并不是只有引用一种方式!

传指针和传引用是等价的吗?

比如有以下代码:

func main() {     a := new(int)     fmt.Println(a)     modify(a)     fmt.Println(a) }  func modify(a *int) {     a = nil } 

输出为:

0xc010000000 0xc010000000 

可以看出指针a本身并没有变化. 传指针或传地址也只能修改指针指向的内存的值, 并不能改变指针本身在值.

因此, 函数参数传传指针也是传值的, 并不是传引用!

所有类型的函数参数都是传值的!

包括slice/map/chan等基础类型和自定义的类型都是传值的.

但是因为slicemap/chan底层结构的差异, 又导致了它们传值的影响并不完全等同.

重点归纳如下:

  • GoSpec: the parameters of the call are passed by value!
  • map/slice/chan 都是传值, 不是传引用
  • map/chan 对应指针, 和引用类似
  • slice 是结构体和指针的混合体

  • slice 含 values/count/capacity 等信息, 是按值传递

  • slice 中的 values 是指针, 按值传递
  • 按值传递的 slice 只能修改values指向的数据, 其他都不能修改

  • 以指针或结构体的角度看, 都是值传递!

那Go语言有传引用的说法吗?

Go语言其实也是有传引用的地方的, 但是不是函数的参数, 而是闭包对外部环境是通过引用访问的.

查看以下的代码:

func main() {     a := new(int)     fmt.Println(a)     func() {         a = nil     }()     fmt.Println(a) } 

输出为:

0xc010000000 <nil> 

因为闭包是通过引用的方式使用外部环境的a变量, 因此可以直接修改a的值.

比如下面2段代码的输出是截然不同的, 原因就是第二个代码是通过闭包引用的方式输出i变量:

for i := 0; i < 5; i++ {     defer fmt.Printf("%d ", i)     // Output: 4 3 2 1 0 }  fmt.Printf("\n")     for i := 0; i < 5; i++ {     defer func(){ fmt.Printf("%d ", i) } ()     // Output: 5 5 5 5 5 } 

像第二个代码就是于闭包引用导致的副作用, 回避这个副作用的办法是通过参数传值或每次闭包构造不同的临时变量:

// 方法1: 每次循环构造一个临时变量 i for i := 0; i < 5; i++ {     i := i     defer func(){ fmt.Printf("%d ", i) } ()     // Output: 4 3 2 1 0 } // 方法2: 通过函数参数传惨 for i := 0; i < 5; i++ {     defer func(i int){ fmt.Printf("%d ", i) } (i)     // Output: 4 3 2 1 0 } 

总结

  • 函数参数传值, 闭包传引用!
  • slice 含 values/count/capacity 等信息, 是按值传递
  • 按值传递的 slice 只能修改values指向的数据, 其他都不能修改
  • slice 是结构体和指针的混合体

posted @ 2013-09-16 09:23 oathleo 阅读(3987) | 评论 (1)编辑 收藏

仅列出标题
共17页: 上一页 1 2 3 4 5 6 7 8 9 下一页 Last