程序设计 | 酷壳 - CoolShell

TCP 的那些事儿（下）

2014年05月28日陈皓评论 162 条评论 284,331 人阅读

这篇文章是下篇，所以如果你对TCP不熟悉的话，还请你先看看上篇《TCP的那些事儿（上）》上篇中，我们介绍了TCP的协议头、状态机、数据重传中的东西。但是TCP要解决一个很大的事，那就是要在一个网络根据不同的情况来动态调整自己的发包的速度，小则让自己的连接更稳定，大则让整个网络更稳定。在你阅读下篇之前，你需要做好准备，本篇文章有好些算法和策略，可能会引发你的各种思考，让你的大脑分配很多内存和计算资源，所以，不适合在厕所中阅读。

TCP的RTT算法

从前面的TCP重传机制我们知道Timeout的设置对于重传非常重要。

设长了，重发就慢，丢了老半天才重发，没有效率，性能差；
设短了，会导致可能并没有丢就重发。于是重发的就快，会增加网络拥塞，导致更多的超时，更多的超时导致更多的重发。

而且，这个超时时间在不同的网络的情况下，根本没有办法设置一个死的值。只能动态地设置。为了动态地设置，TCP引入了RTT——Round Trip Time，也就是一个数据包从发出去到回来的时间。这样发送端就大约知道需要多少的时间，从而可以方便地设置Timeout——RTO（Retransmission TimeOut），以让我们的重传机制更高效。听起来似乎很简单，好像就是在发送端发包时记下t0，然后接收端再把这个ack回来时再记一个t1，于是RTT = t1 – t0。没那么简单，这只是一个采样，不能代表普遍情况。

…

阅读全文 Read More

(102 人打了分，平均分： 4.75 )

TCP 的那些事儿（上）

2014年05月28日陈皓评论 237 条评论 488,655 人阅读

TCP是一个巨复杂的协议，因为他要解决很多问题，而这些问题又带出了很多子问题和阴暗面。所以学习TCP本身是个比较痛苦的过程，但对于学习的过程却能让人有很多收获。关于TCP这个协议的细节，我还是推荐你去看W.Richard Stevens的《TCP/IP 详解卷1：协议》（当然，你也可以去读一下RFC793以及后面N多的RFC）。另外，本文我会使用英文术语，这样方便你通过这些英文关键词来查找相关的技术文档。

之所以想写这篇文章，目的有三个，

一个是想锻炼一下自己是否可以用简单的篇幅把这么复杂的TCP协议描清楚的能力。
另一个是觉得现在的好多程序员基本上不会认认真真地读本书，喜欢快餐文化，所以，希望这篇快餐文章可以让你对TCP这个古典技术有所了解，并能体会到软件设计中的种种难处。并且你可以从中有一些软件设计上的收获。
最重要的希望这些基础知识可以让你搞清很多以前一些似是而非的东西，并且你能意识到基础的重要。

所以，本文不会面面俱到，只是对TCP协议、算法和原理的科普。

…

阅读全文 Read More

(128 人打了分，平均分： 4.82 )

C语言的整型溢出问题

2014年04月21日陈皓评论 96 条评论 109,697 人阅读

整型溢出有点老生常谈了，bla, bla, bla… 但似乎没有引起多少人的重视。整型溢出会有可能导致缓冲区溢出，缓冲区溢出会导致各种黑客攻击，比如最近OpenSSL的heartbleed事件，就是一个buffer overread的事件。在这里写下这篇文章，希望大家都了解一下整型溢出，编译器的行为，以及如何防范，以写出更安全的代码。

什么是整型溢出

C语言的整型问题相信大家并不陌生了。对于整型溢出，分为无符号整型溢出和有符号整型溢出。

对于unsigned整型溢出，C的规范是有定义的——“溢出后的数会以2^(8*sizeof(type))作模运算”，也就是说，如果一个unsigned char（1字符，8bits）溢出了，会把溢出的值与256求模。例如：

unsigned char x = 0xff;
printf("%d\n", ++x);

上面的代码会输出：0 （因为0xff + 1是256，与2^8求模后就是0）

对于signed整型的溢出，C的规范定义是“undefined behavior”，也就是说，编译器爱怎么实现就怎么实现。对于大多数编译器来说，算得啥就是啥。比如：

signed char x =0x7f; //注：0xff就是-1了，因为最高位是1也就是负数了
printf("%d\n", ++x);

上面的代码会输出：-128，因为0x7f + 0x01得到0x80，也就是二进制的1000 0000，符号位为1，负数，后面为全0，就是负的最小数，即-128。

…

阅读全文 Read More

(47 人打了分，平均分： 4.34 )

从LongAdder看更高效的无锁实现

2014年04月17日 liuinsect 评论 35 条评论 47,421 人阅读

（感谢 @jd刘锟洋投稿，更多文章参看他的博客：码梦为生）

原文链接：《比AtomicLong还高效的LongAdder 源码解析》

接触到AtomicLong的原因是在看guava的LoadingCache相关代码时，关于LoadingCache，其实思路也非常简单清晰：用模板模式解决了缓存不命中时获取数据的逻辑，这个思路我早前也正好在项目中使用到。

言归正传，为什么说LongAdder引起了我的注意，原因有二：

作者是Doug lea ，地位实在举足轻重。
他说这个比AtomicLong高效。

我们知道，AtomicLong已经是非常好的解决方案了，涉及并发的地方都是使用CAS操作，在硬件层次上去做 compare and set操作。效率非常高。

因此，我决定研究下，为什么LongAdder比AtomicLong高效。

首先，看LongAdder的继承树：

la1

继承自Striped64，这个类包装了一些很重要的内部类和操作。稍候会看到。

…

阅读全文 Read More

(23 人打了分，平均分： 3.91 )

Python修饰器的函数式编程

2014年03月20日陈皓评论 84 条评论 124,847 人阅读

Python的修饰器的英文名叫Decorator，当你看到这个英文名的时候，你可能会把其跟Design Pattern里的Decorator搞混了，其实这是完全不同的两个东西。虽然好像，他们要干的事都很相似——都是想要对一个已有的模块做一些“修饰工作”，所谓修饰工作就是想给现有的模块加上一些小装饰（一些小功能，这些小功能可能好多模块都会用到），但又不让这个小装饰（小功能）侵入到原有的模块中的代码里去。但是OO的Decorator简直就是一场恶梦，不信你就去看看wikipedia上的词条（Decorator Pattern）里的UML图和那些代码，这就是我在《从面向对象的设计模式看软件设计》“餐后甜点”一节中说的，OO鼓励了——“厚重地胶合和复杂层次”，也是《如此理解面向对象编程》中所说的“OO的狂热者们非常害怕处理数据”，Decorator Pattern搞出来的代码简直就是OO的反面教程。

Python 的 Decorator在使用上和Java/C#的Annotation很相似，就是在方法名前面加一个@XXX注解来为这个方法装饰一些东西。但是，Java/C#的Annotation也很让人望而却步，太TMD的复杂了，你要玩它，你需要了解一堆Annotation的类库文档，让人感觉就是在学另外一门语言。

而Python使用了一种相对于Decorator Pattern和Annotation来说非常优雅的方法，这种方法不需要你去掌握什么复杂的OO模型或是Annotation的各种类库规定，完全就是语言层面的玩法：一种函数式编程的技巧。如果你看过本站的《函数式编程》，你一定会为函数式编程的那种“描述你想干什么，而不是描述你要怎么去实现”的编程方式感到畅快。（如果你不了解函数式编程，那在读本文之前，还请你移步去看看《函数式编程》）好了，我们先来点感性认识，看一个Python修饰器的Hello World的代码。

…

阅读全文 Read More

(39 人打了分，平均分： 4.28 )

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 108,951 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

协程(coroutine)顾名思义就是“协作的例程”（co-operative routines）。跟具有操作系统概念的线程不一样，协程是在用户空间利用程序语言的语法语义就能实现逻辑上类似多任务的编程技巧。实际上协程的概念比线程还要早，按照 Knuth 的说法“子例程是协程的特例”，一个子例程就是一次子函数调用，那么实际上协程就是类函数一样的程序组件，你可以在一个线程里面轻松创建数十万个协程，就像数十万次函数调用一样。只不过子例程只有一个调用入口起始点，返回之后就结束了，而协程入口既可以是起始点，又可以从上一个返回点继续执行，也就是说协程之间可以通过 yield 方式转移执行权，对称（symmetric）、平级地调用对方，而不是像例程那样上下级调用关系。当然 Knuth 的“特例”指的是协程也可以模拟例程那样实现上下级调用关系，这就叫非对称协程（asymmetric coroutines）。

基于事件驱动模型

我们举一个例子来看看一种对称协程调用场景，大家最熟悉的“生产者-消费者”事件驱动模型，一个协程负责生产产品并将它们加入队列，另一个负责从队列中取出产品并使用它。为了提高效率，你想一次增加或删除多个产品。伪代码可以是这样的：

# producer coroutine
loop
while queue is not full
  create some new items
  add the items to queue
yield to consumer

# consumer coroutine
loop
while queue is not empty
  remove some items from queue
  use the items
yield to producer

…

阅读全文 Read More

(39 人打了分，平均分： 4.26 )

分布式系统的事务处理

2014年01月20日陈皓评论 181 条评论 284,595 人阅读

当我们在生产线上用一台服务器来提供数据服务的时候，我会遇到如下的两个问题：

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帐号的其它访问必需锁死，所谓锁死就是要排除其它的读写操作，不然会有脏数据的问题，这就是事务。那么，我们在加入了更多的机器后，这个事情会变得复杂起来：

…

阅读全文 Read More

(113 人打了分，平均分： 4.64 )

函数式编程

2013年12月27日陈皓评论 194 条评论 214,651 人阅读

当我们说起函数式编程来说，我们会看到如下函数式编程的长相：

函数式编程的三大特性：
- immutable data 不可变数据：像Clojure一样，默认上变量是不可变的，如果你要改变变量，你需要把变量copy出去修改。这样一来，可以让你的程序少很多Bug。因为，程序中的状态不好维护，在并发的时候更不好维护。（你可以试想一下如果你的程序有个复杂的状态，当以后别人改你代码的时候，是很容易出bug的，在并行中这样的问题就更多了）
- first class functions：这个技术可以让你的函数就像变量一样来使用。也就是说，你的函数可以像变量一样被创建，修改，并当成变量一样传递，返回或是在函数中嵌套函数。这个有点像Javascript的Prototype（参看Javascript的面向对象编程）
- 尾递归优化：我们知道递归的害处，那就是如果递归很深的话，stack受不了，并会导致性能大幅度下降。所以，我们使用尾递归优化技术——每次递归时都会重用stack，这样一来能够提升性能，当然，这需要语言或编译器的支持。Python就不支持。

函数式编程的几个技术
- map & reduce ：这个技术不用多说了，函数式编程最常见的技术就是对一个集合做Map和Reduce操作。这比起过程式的语言来说，在代码上要更容易阅读。（传统过程式的语言需要使用for/while循环，然后在各种变量中把数据倒过来倒过去的）这个很像C++中的STL中的foreach，find_if，count_if之流的函数的玩法。
- pipeline：这个技术的意思是，把函数实例成一个一个的action，然后，把一组action放到一个数组或是列表中，然后把数据传给这个action list，数据就像一个pipeline一样顺序地被各个函数所操作，最终得到我们想要的结果。
- recursing 递归 ：递归最大的好处就简化代码，他可以把一个复杂的问题用很简单的代码描述出来。注意：递归的精髓是描述问题，而这正是函数式编程的精髓。
- currying：把一个函数的多个参数分解成多个函数，然后把函数多层封装起来，每层函数都返回一个函数去接收下一个参数这样，可以简化函数的多个参数。在C++中，这个很像STL中的bind_1st或是bind2nd。
- higher order function 高阶函数：所谓高阶函数就是函数当参数，把传入的函数做一个封装，然后返回这个封装函数。现象上就是函数传进传出，就像面向对象对象满天飞一样。

…

阅读全文 Read More

(88 人打了分，平均分： 4.60 )

二维码的生成细节和原理

2013年10月29日陈皓评论 165 条评论 393,738 人阅读

二维码又称QR Code，QR全称Quick Response，是一个近几年来移动设备上超流行的一种编码方式，它比传统的Bar Code条形码能存更多的信息，也能表示更多的数据类型：比如：字符，数字，日文，中文等等。这两天学习了一下二维码图片生成的相关细节，觉得这个玩意就是一个密码算法，在此写一这篇文章，揭露一下。供好学的人一同学习之。

关于QR Code Specification，可参看这个PDF：http://raidenii.net/files/datasheets/misc/qr_code.pdf

基础知识

首先，我们先说一下二维码一共有40个尺寸。官方叫版本Version。Version 1是21 x 21的矩阵，Version 2是 25 x 25的矩阵，Version 3是29的尺寸，每增加一个version，就会增加4的尺寸，公式是：(V-1)*4 + 21（V是版本号）最高Version 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。

下面我们看看一个二维码的样例：

…

阅读全文 Read More

(96 人打了分，平均分： 4.41 )

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 65,184 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

提起buddy system相信很多人不会陌生，它是一种经典的内存分配算法，大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现，而仅仅是将该算法抽象提取出来，同时给出一份及其简洁的源码实现，以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；其缺点是内部碎片，因为按2的幂划分块，如果碰上66单位大小，那么必须划分128单位大小的块。但若需求本身就按2的幂分配，比如可以先分配若干个内存池，在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述，大体如是：

分配内存：

1.寻找大小合适的内存块（大于等于所需大小并且最接近2的幂，比如需要27，实际分配32）

1.如果找到了，分配给应用程序。
2.如果没找到，分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度，分配这个大小。
3.回溯到步骤1（寻找合适大小的块）
4.重复该步骤直到一个合适的块

…

阅读全文 Read More

(29 人打了分，平均分： 3.79 )

酷壳 – CoolShell

享受编程和技术所带来的快乐 – Coding Your Ambition

Browsed by
分类：程序设计

TCP 的那些事儿（下）

2014年05月28日陈皓评论 162 条评论 284,331 人阅读

TCP的RTT算法

TCP 的那些事儿（上）

2014年05月28日陈皓评论 237 条评论 488,655 人阅读

C语言的整型溢出问题

2014年04月21日陈皓评论 96 条评论 109,697 人阅读

什么是整型溢出

从LongAdder看更高效的无锁实现

2014年04月17日 liuinsect 评论 35 条评论 47,421 人阅读

Python修饰器的函数式编程

2014年03月20日陈皓评论 84 条评论 124,847 人阅读

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 108,951 人阅读

基于事件驱动模型

分布式系统的事务处理

2014年01月20日陈皓评论 181 条评论 284,595 人阅读

函数式编程

2013年12月27日陈皓评论 194 条评论 214,651 人阅读

二维码的生成细节和原理

2013年10月29日陈皓评论 165 条评论 393,738 人阅读

基础知识

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 65,184 人阅读