刘洪江的流水帐

拾起点点滴滴, 聚沙成石.

一个连咖啡都要趁热一饮而尽的男子

The Cathedral and the Bazaar

记得还是在读大学的时候读到的这篇文章，那个时候对文章的理解不是很深刻，工作多年以后再读这篇文章，对里面的很多思想有可比较深刻的认识，特别是关于软件管理方面的。 也许没有实践经验，有的东西就很难理解吧。

大师的思想不会随着时间的变化而失去光辉的，快20年过去了，依然闪烁着智慧。而且随着开源社区的壮大，git这样的工具出现，我们不的不佩服大师看待未来的眼光，对前沿的敏锐观察力。

英文版：The Cathedral and the Bazaar

中文版：大教堂和集市

规则

这篇博文是由两个问题想到的。

一是火车票实名制后，但是仍然还是有黄牛党倒票。倒票的手法是，先用几百张身份证抢下火车票，然后联系买主，联系到买主后，在乘车时间的前一两天，在一个窗口退票，另外一个窗口买票，一退票后系统上显示有一张鱼票后，马上买入。虽然理论上还是有被其它人抢走，失手的可能，但由于该车次的票早早就买光了，临开车的前1、2天，很少会有人去查询，所以还是比较安全的。 针对这种倒票方式，设置怎样的规则杜绝呢？首先一个方法就是，退掉的票，半个小时后才能买入。这样就可以增加退掉的票被被人抢走的可能性。开车前半个小时，退掉的票可以立马买进。这样就讲黄牛党的倒票时间窗口缩短到了开车前半个小时。 复杂的规则，就还有调查哪些身份证存在大量这种买了票后，又退票的行为，并加以惩罚。例如半年内不能买车票，或在春运期间不能买火车票。但这里有个风险，就是如果黄牛党用假身份证买票，那么这条规则就会伤及到真身份证的那个无辜的人。

第二个问题是成都的公交车票，有两种，一种是电子钱包，就是充一定数量的钱，这个钱永远在卡里，一直可以用，主要目的是方便，不用每次乘公交都要准备零钱，而且还打9折。 还有一种是次卡，就是用前买一定数量的乘车次数，相当于打5折，而且用次卡乘车，2个小时内免费换乘公交车3次。而电子钱包换乘的时候，是要再次给钱的。对于我们这些上班族，每天上班要换乘几次的，非常划算。 但次卡有个规定，买的次数是当月有效的，一到下个月，无论你买了多少次，就作废了。我想公交公司是想用这种方式，吃点别人多充次数的油头。最开始的时候，次卡只能10块钱的倍数买，后来大家反对，于是可以1块钱的倍数买。乘公交用次卡的最低单位也是1块钱，所以基本上，公交公司就没有什么油头了。

Go语言学习

| Tags: Language

一点体会

下面这篇博文是在看《go语言编程》书的笔记。 在看书的过程中，其实也没有对go语言进行深入的学习。仅仅是停留在对语法的简单了解。

总的来说，go语言没有它多的新东西，仅仅是将各个语言比较有特色的内容，集中到以一个语言中，而且还是基于C语言的，因为go语言的作者就是C语言的作者。哪些比较有特色的呢，例如闭包，接口，垃圾回收，还有必然语言级别支持协程。这种炒大杂烩的方式，个人感觉不可能会成功。只不过go语言已一个比较强大的干爹google，所有才多多少少掀起了几个波浪。

很有意思的一件事情是，虽然这个语言生在美国，生在google，但是目前go语言的社区最活跃的，还是我们中国的屌丝程序员。我认为这是一件极好的事情，说明了我们中国在IT方面对新事物的开明态度和勇于追逐，虽然成功可能不在go语言，但是有这种态度，终会有所作为。

go语言简介

go语言是google推出的一个可以提高并发编程的语言，它着不同一般的背景。

  • 回溯至1969 年, 肯·汤普逊（Ken Thompson）和丹尼斯·里奇（Dennis Ritchie ）在贝尔实验室的计算科学研究中心里开发出了Unix ，还因为开发Unix而衍生——C语言。
  • 80年代，开始Plan 9 的操作系统研究项目，解决Unix 中的一些问题, 又演变出了Inferno 的项目分支，以及一个名为Limbo 的编程语言
  • Limbo是用于开发运行在小型计算机上的分布式应用的编程语言，它支持模块化编程，编译期和运行时的强类型检查，进程内基于具有类型的通信通道，原子性垃圾收集和简单的抽象数据类型。它被设计为：即便是在没有硬件内存保护的小型设备上，也能安全运行。
  • Limbo 语言被认为是Go语言的前身，不仅仅因为是同一批人设计的语言，而是Go语言确实从Limbo 语言中继承了众多优秀的特性。
  • 贝尔实验室后来经历了多次的动荡，包括肯·汤普逊在内的Plan 9 项目原班人马加入了Google 。在Google ，他们创造了Go语言。
  • 2007 年9月，Go语言还是这帮大牛的20% 自由时间的实验项目
  • 2008 年5月，Google 发现了Go语言的巨大潜力，从而开始全力支持这个项目
  • 2009年11 月，发布第一个版本在
  • 2012年3月28 日，发布第一个正式版本

go语言特性

  • 自动垃圾回收
  • 更丰富的内置类型
  • 函数多返回值
  • 错误处理
  • 匿名函数和闭包
  • 类型和接口
  • 并发编程
  • 反射
  • 语言交互性 (Cgo, C语言库)

数据结构–树

| Tags: Data structure

摘要： 本文介绍了一种重要的数据结构树。绝大部分内容都是收集于网络博客。

树，计算机中比较纠结的一种数据结构。种类太多了，涉及到的算法也太多了。主要目的是汇总一下。参考了网上的几篇博客。12

二叉树

就是binary tree，搜索二叉数特点：

  1. 所有非叶子结点至多拥有两个儿子（Left和Right）；
  2. 所有结点存储一个关键字；
  3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

但二叉树在经过多次插入与删除后，有可能导致不同的结构, 例如下图也是一个二叉数，但是其查找效率已经是线性的了：

所以，使用二叉树还要考虑尽可能让二叉树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题； 实际使用的二叉数都是在原二叉树的基础上加上平衡算法, 即“平衡二叉树”;如何保持二叉树结点分布均匀的平衡算法是平衡二叉树的关键; 平衡算法是一种在二叉数中插入和删除结点的策略。

Lisp笔记

下面是在看《ANSI common lisp》这本书和做习题的时候的一些笔记。

lisp

约翰麦卡锡和他的学生于 1958 年展开 Lisp 的初次实现工作。 Lisp 是继 FORTRAN 之后，仍在使用的最古老的程序语言。 更值得注意的是，它仍走在程序语言技术的最前面。懂 Lisp 的程序员会告诉你，有某种东西使 Lisp 与众不同。

Lisp 与众不同的部分原因是，它被设计成能够自己进化。你能用 Lisp 定义新的 Lisp 操作符。当新的抽象概念风行时（如面向对象程序设计），我们总是发现这些新概念在 Lisp 是最容易来实现的。Lisp 就像生物的 DNA 一样，这样的语言永远不会过时。

Lisp能够自己进化的特点，注定了它有很多方言存在(真的是方言，英语里面用的是dialects)。 其中common lisp就是其中的一种方言。

下面几篇关于lisp的文章值得一读：

Pegasos算法

| Tags: Machine Learning

摘要： 本文介绍了svm的一种online learning算法pegasos，并基于pegasoso算法实现了一个数字手写识别脚本。

本文参考了博文Online Learning in Clojure和论文Pegasos: Primal Estimated sub-GrAdient SOlver for SVM(PDF)

online learning

Online learning的算法结构是非常简单的，下面的描述是监督的online learning算法框架，其中有经验损失函数$L$，样本流$S$，样本的格式为$(x,y)$:

Initialise a starting model w
While there are more examples in S
    Get the next feature vector x
    Predict the label y' for x using the model w
    Get the true label y for x and incur a penaly L(y,y')
    Update the model w if y ≠ y'

一般来是，训练出来的模型都是一个与样本相同维度的向量。对应二分的分类器，往往涉及到的是计算内积$\langle w,x \rangle$，模型的更新是沿着损失函数的梯度下降方向的。

Pegasos

论文Pegasos: Primal Estimated sub-GrAdient SOlver for SVM是一种svm的online learning算法。

ZooKeeper Overview

| Tags: 3rd tools

摘要： 简单介绍了zookeeper的概要，主要是翻译了apache zookeeper overview的内容。

ZooKeeper 简介

ZooKeeper是Hadoop的正式子项目，它是一个针对大型分布式系统的可靠协调系统，提供的功能包括：配置维护、名字服务、分布式同步、组服务等。ZooKeeper的目标就是封装好复杂易出错的关键服务，将简单易用的接口和性能高效、功能稳定的系统提供给用户。1

Zookeeper是Google的Chubby一个开源的实现，关于Chubby，可以google一下，有论文介绍的。zookeeper是高有效和可靠的协同工作系统。Zookeeper能够用来leader选举，配置信息维护等。在一个分布式的环境中，我们需要一个Master实例或存储一些配置信息，确保文件写入的一致性等。

ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，包含一个简单的原语集，是Hadoop和Hbase的重要组件。目前提供Java和C的接口。

在Zookeeper中，znode是一个跟Unix文件系统路径相似的节点,可以往这个节点存储或获取数据.如果在创建znode时Flag设置为EPHEMERAL,那么当这个创建这个znode的节点和Zookeeper失去连接后,这个znode将不再存在在Zookeeper 里.Zookeeper使用Watcher察觉事件信息,当客户端接收到事件信息,比如连接超时,节点数据改变,子节点改变,可以调用相应的行为来处理数 据.Zookeeper的Wiki页面展示了如何使用Zookeeper来处理事件通知,队列,优先队列,锁,共享锁,可撤销的共享锁,两阶段提交.

znodes与Unix文件系统路径相似相似，但是还是不同的，znode的中间节点是可以保存数据的，对应于文件系统，就即是文件又是目录。为了达到高吞吐的能力，znode在zookeeper中是放在内存中的。

ZooKeeper是以Fast Paxos算法为基础的，paxos算法存在活锁的问题，即当有多个proposer交错提交时，有可能互相排斥导致没有一个proposer能提交成功，而Fast Paxos作了一些优化，通过选举产生一个leader，只有leader才能提交propose，具体算法可见Fast Paxos。因此，要想弄懂ZooKeeper首先得对Fast Paxos有所了解。

ZooKeeper的基本运转流程：

1、选举Leader。
2、同步数据。
3、选举Leader过程中算法有很多，但要达到的选举标准是一致的。
4、Leader要具有最高的zxid。
5、集群中大多数的机器得到响应并follow选出的Leader。

使用https连接github

| Tags: Fuck GFW

火车票插件拖垮github的事件的结果，就是github被悲催地墙掉了。愤慨啊。Fuck GFW!

不过有了goagent的代理，github的网站是可以上了，但是命令行上面pull，push就不灵了。新浪微博上@蒋伟找到了一个通过https连接github的办法，总结一下如下：

  1. 安装goagent

  2. 导入ca.crt证书 导入goagent目录下的local/CA.crt
    ubuntu导入证书
    http://askubuntu.com/questions/73287/how-do-i-install-a-root-certificate

  3. 启动代理 python proxy.py
  4. 设置代理： export HTTPS_PROXY=”http://127.0.0.1:8087”
  5. github配置，关键一步是remote add的时候，方法是：
    git remote add origin https://liuhongjiang@github.com/liuhongjiang/tech.git
    这样就可以正常地pull和push了，麻烦的是，每次都要输入秘密。

  6. 接下来就是octopress的rake deploy了： 需要修改Rakefile：

     # user = repo_url.match(/:([^\/]+)/)[1]
 user = repo_url.match(/github\.com.([^\/]+)/)[1]
 # branch = (repo_url.match(/\/[\w-]+.github.com/).nil?) ? 'gh-pages' : 'master'
 branch = (repo_url.match(/\/[\w-]+\.github\.com$/).nil?) ? 'gh-pages' : 'master'
 # project = (branch == 'gh-pages') ? repo_url.match(/\/([^\.]+)/)[1] : ''
 project = (branch == 'gh-pages') ? repo_url.match(/\/([^\/^\.]+)$/)[1] : ''

    然后在rake setup_github_pages命令中填https的url地址：
    https://liuhongjiang@github.com/liuhongjiang/tech
    同样在部署的时候，还是要输入密码

我的2012

一直说写一篇2012年的总结，但元旦以来的这段时间忙东忙西，再加上自己的拖延症，始终没有写。今天终于鼓起勇气，下定决心，要把这篇总结写完，在旁边放了一把菜刀，写不完，不自刎谢罪，也要卸下一只胳膊。

2012年多多少少也是特别的一年，最主要的是那部有名的《2012》。现在庆幸时间没有终结在2012年12月21日，劫后余生。《2012》对我的影响不是那震撼的场面，也不是世界终结的恐慌，而是对人生的认识。也许明天世界就终结了，那我们应该怎么办，今天还有什么意义？12月20日那天，网上、微博上各种调侃，各种问题，五花八门。其中有个问题是这样的：明天世界都要结束了，今天晚上怎么过？各种答案，去酒吧疯狂一晚上，或者喝个天昏地暗，处男就去花点钱。我当时想的是回家早点洗洗睡了，明天还要上班啊。

把最后一天当成每一天度过，没有什么特别的，做自己该做的，完成该完成的，一步一步地往前走。这也许就是我2012年的寄语吧。

霸道算法和环选举算法

| Tags: Algorithm

摘要： 本文介绍了两种简单的master算法，霸道算法和环选举算法，另外还提出了一个没有验证的假象算法，它是在同一个host上基于文件锁的霸道选举算法。

现在主流的分布式集群一致性问题大多都吸收了PAXOS算法1的思想。然而，如果完全按照Leslie Lamport的论文2，实现复杂度比较高。因此，大多数实现都采用PAXOS的某种变形。Lamport的重要贡献，献是把分布式一致性的问题，形式化并给出了证明，给出了理论指导。3

关于Paxos算法，在网上看到了一个Fast Paxos算法，见淘宝核心系统团队博客, paxos 实现

Paxos算法看起来还是很复杂的，没有仔细研究，倒是在网上另外找到了两个简单的master选举算法。

霸道算法

Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法（Bully Algorithm）4。当一个进程 P 发现协调者进程不再响应时，这个进程就召集选举。由于进程的独立性，在同一个时刻，系统中可能有多个召集选举的过程。假设 P 是召集选举的进程，每个召集选举的过程如下：

  1. P 向所有比自己编号大的进程发送一条 ELECTION（选举）消息。
  2. 如果 P 得不到任何回复，则 P 赢得选举，P 向所有进程发送 COORDINATOR（协调者）消息，宣布自己的胜利。
  3. 如果 P 得到任何一个回复，回复一定来自于比自己编号大的进程。P 的召集选举的工作结束，因为 P 此时已经不可能赢得选举。