A Coder is a Poet

每一个最初学习网络的人都会听到这样的一句话，TCP 是面向连接的基于字节流的传输协议，而UDP是基于数据包的无连接协议。这种把 TCP 比喻成为流的描述是非常形象的，因为我们知道 TCP 的滑动窗口协议能够保证数据源源不断的进入网络。可是问题是，如果我们仔细的观察每条 TCP 连接的表现，TCP 真的如我们想象的那样像水流一样顺滑的传输数据吗？

上面这个问题，如果仔细想一下应该就会回答不是。我们知道 TCP 也是一个数据包一个数据包进入网络，不同的数据包之间也是有发送间隔的，这种间隔就使得 TCP 在微观上看起来不是一个完整的流。不过，只能认识到这一点，并不能完全解答上面的问题。事实上，由于从收到包，网卡产生中断，拷贝数据到内核栈，内核向应用层递交数据是一个复杂的过程，TCP 的具体传输表现也会因此而受到种种影响。

TCP 中的 Train

早在 1986 年，Jain（如果你觉得 Jain 这个名字很熟，那就对了。这个人就是传说中的 Raj Jain，Jain’s Fairness Index 就是以他命名的，网络方面的大牛之一）以及 Routhier 就仔细地研究了MIT校园网络里面的 TCP 表现。他们发现TCP的数据流并没有呈现出流的形态，而是一个 burst 接着另一个 burst。这种传输形态使得 TCP 的数据包并没有在统计上满足一个泊松分布。他们为这种现象起了一个我觉得非常形象的名字：train（火车）。不得不说这个名字比现在的 flowlet，flowcell，flight，flier 的说法不知道好到哪里去了。

当一个程序涉及到多个线程的时候，线程之间的同步和互斥就显得尤其重要。为了避免一个线程中的敏感数据被另一个线程修改，程序中往往需要显式的使用线程同步机制来保证线程运行环境的安全。当前的编程库环境（例如pthread库）就为多线程的同步和互斥提供了多种不同的机制，包括互斥锁，读写锁，自旋锁，条件变量和信号量等等。本文简要记载使用不同的同步机制时应该注意的问题。

互斥锁

互斥锁指的就是不同的锁之间相互排斥。对于某个临界区而言，任何时间都只能有一个互斥锁的锁住该临界区。当该互斥锁未释放之前，任何其他企图对该临界区进行加锁访问的线程都会被挂起而阻塞。等到该临界区上的锁释放的时候，其他进程才能被唤醒来访问该临界区。

Gossip是分布式系统中被广泛使用的协议，其主要用于实现分布式节点或者进程之间的信息交换。Gossip协议同时满足应用层多播协议所要求的低负载，高可靠和可扩展性的要求。由于其简单而易于实现，当前很多系统（例如Amazon S3，Usenet NNTP等）选择基于Gossip协议以实现应用层多播的功能。

什么是Gossip协议

Gossip Protocol利用一种随机的方式将信息散播到整个网络中。正如Gossip本身的含义一样，Gossip协议的工作流程即类似于绯闻的传播，或者流行病的传播。具体而言Gossip Protocol可以分为Push-based和Pull-based两种。Push-based Gossip Protocol的具体工作流程如下：

1. 网络中的某个节点随机的选择其他$b$个节点作为传输对象。
2. 该节点向其选中的$b$个节点传输相应的信息
3. 接收到信息的节点重复完成相同的工作

Pull-based Gossip Protol的协议过程刚好相反：

1. 某个节点$v$随机的选择$b$个节点询问有没有最新的信息
2. 收到请求的节点回复节点$v$其最近未收到的信息

当然，为了提高Gossip协议的性能，还有基于Push-Pull的混合协议。同时需要注意的是Gossip协议并不对网络的质量做出任何要求，也不需要loss-free的网络协议。Gossip协议一般基于UDP实现，其自身即在应用层保证了协议的robustness。

Monte Hall问题又称为三门问题，是一个源自于game theory和概率论的经典问题。Monte Hall这个名字来源于美国的电视游戏节目Let’s Make a Deal中的主持人Monte Hall，而该问题为大多数非数学专业人士所知晓却是因为08年的著名美国影片《决胜21点》。

##问题

以下是Monte Hall问题的一个著名的叙述，它来自于Craig F. Whitaker于1990年寄给《展示杂志》（Parade Magazine）玛丽莲·沃斯·莎凡特（Marilyn vos Savant）专栏的信件：

假设你正在参加一个电视节目，你被要求在三扇门中选择一扇：其中一扇门后面有一辆车；其余两扇门后面则是山羊。你选择了一道门，假设是1号门，然后知道门后面有什么的主持人，开启了另一扇门后面有山羊的门，假设是3号门。他然后问你：“你现在想不想换选2号门？”，这种转换的决定对你来说是一种优势吗？

这个问题也被称为了Monte Hall悖论：虽然在问题的答案逻辑上并没有出现任何矛盾，但是却非常违反直觉。由于其非常强烈的反直觉性，该问题曾引起各界广泛的讨论。

这几天一直在看sigcomm14上面的文章，总体感觉就是今年Application-aware networking这个topic突然就火了。在我看来今年在此领域最引人关注的文章是来自Mosharaf Chowhury的Varys[1]（B.T.W M.Chowhury这位Berkeley的大牛相当猛，最近几年基本每年都有1到2篇的sigcomm）。Varys延续了MC在2012年HotNets上面发表的coflow （有关coflow的工作模型，以后有时间再写吧）的工作，主要针对并行的data-sensitive的应用，比如MapReduce进行相关的流处理优化。 这篇文章中通过inter-Coflow scheduling来提高应用通讯性能的思想，提供了很多关于Application-aware networking的直观启示。为了深入地理解一下MapReduce的工作模型，以及其具有的Application Characteristics，打算仔细学习一下Hadoop的相关内容。相信对以后的生涯一定会产生帮助。

什么是Hadoop？

说到什么是Hadoop，就不得不提google在2003年以及2004年间发表的那几篇掉咋天的文章“The Google File System”和”MapReduce: Simplified Data Processing on Large Clustres”。就是这两篇文章直接促成了Hadoop的诞生。当时的开源搜索引擎之父Doug Cutting为了提高集群的性能正一筹莫展之时，看到了google的这两篇文章。顿时Cutting犹如拨云见日，花了两年的时间开发了Hadoop的前身。后来Doug Cutting加入Yahoo！，这个项目也被单独剥离出来开发，成为了现在的Hadoop。有关Hadoop是怎么写出来的就不多说了，感兴趣的可以自己查查野史。但是需要说明的是Hadoop并不是大象的意思，只是Doug Cutting的小孩给他的一个大象玩具起的名字而已。

在针对计算机网络，信息网络，生物网络图的研究过程中，研究者发现了大量的结构特性，比如 small-world property，clustering property 等。而在这些图特性中，Community Structure（社交结构）得到了学术界最为广泛的关注和最为深入的探索。

在一个网络中，一个 Community Structure 代表图中的某些节点的集合。这些节点内部具有高度的耦合性（表现在内部的连通性非常高，内部节点之间的边非常丰富），同时与外界的其他节点保持着较为稀疏的连接。在一个 Community Structure 内部，节点之间的紧密连接使得信息的传输速度非常快。同时，Community Structure 的存在也使得网络具有天然可被分割的性质。