这几天看了一些关于如何构建大型网站的文章：
http://www.blogjava.net/BlueDavy/archive/2008/09/03/226749.html?allyesid=81216_39113

http://www.docin.com/p-23547569.html#

这些知识对理解云计算的需求很有帮助。在这些大型网站的发展过程中，随着用户的增长，需要在两个方面进行扩展：硬件扩展和软件扩展。
硬件扩展包括更多的存储，更多的内存，更强劲的CPU，当然也包括带宽，负载均衡等等。
软件扩展包括负载均衡，缓存，业务和数据分离，高可用性，分布式文件系统，分布式数据库等等。
虽然各大网站的业务各不相同，平台也可能不一样。但是优化和扩展的思路却大同小异。那么，为什么不能把这些最佳实践综合起来，做成统一的平台哪？
以IaaS为例例，IaaS包括了计算单元，存储，网络，还有CDN等等，或者还有分布式的data center。在网站初期，不需要很多的资源，用户可以更加关注自己的业务，而把infrastructure交给cloud computing提供商去做。当业务扩展的时候，再增加更多的资源。
更进一步，在Paas里面，那些基础的软件，比如web/database/app framework等，都可以使用线程的，而用户只关注自己的逻辑。这里面就有一个平台选择的问题，在LAMP/java/.net之间选择，并不那么容易。而且很多公司以前都是倾向于自己做这部分工作。而且也把这个当做自己的核心竞争力。但是，未来做业务，就不需要再走老路了，有现成的东西用，何乐而不为哪？

虽然年纪不大，但吃程序这碗饭已经有年头了。今天和同事一起给人面试，同事问candidate的一个问题，让另一个“面试官”——我，也被雷到了：

“咱们聊聊霍夫曼编码。”

本来平时贫嘴话痨的我立刻闭嘴以避免出丑，魂游天外地做完了剩下的面试，回到座位上问谷歌老师。谷歌老师带我去找维基老师。

维基老师说：

“In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. …… Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix code (sometimes called “prefix-free codes”) (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. A method was later found to do this in linear time if input probabilities (also known as weights) are sorted.……Blah blah……”

看到这一大堆洋文，我又被雷了一下。这些东西是什么意思呢？幸好，有图有真相：
http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/350px-Huffman_tree_2.svg.png

闲聊哈希表 （上）
经典数据结构教科书中，“表”是数据结构的一个大家族。其中，有顺序表（数组）、单向链表、双向链表、循环链表等等。我们今天聊的不是这些，而是“表”中的异类——哈希表(Hash Table)。

为什么会有哈希表这种数据结构呢？让我们用一个通俗的例子来理解：
大家一定都查过字典吧，我们知道，《新华字典》是按照读音排序的，可以理解为一个以读音为key，按升序排列的数据库。对于读音已知的字，可以通过“二分查找法”，很快地查找到要找的字，其时间复杂度为O(log2n)。但是，对于不知道读音的字怎么办呢？如果使用“顺序查找”，一页一页地翻字典，假设一本新华字典600页，每翻查一页的时间开销为0.5分钟，那么，每查到一个字耗费的时间t的数学期望值E(t) = 600 * 0.5min / 2 =150min，也就是查一个字需要两个半小时！当然，这是难以接受的！
为了解决这个问题，《新华字典》的编辑们，很快就想出了解决办法，那就是在字典的前面加入一个“检字表”，如“四角号码检字表”“部首检字表”等，其特点是以每个字的字形为依据，计算出一个索引值，并映射到对应的页数。比如“法”字，按四角号码检字法，其索引值为34131，再根据这个数值，就可以找到相应的字了。在这种情况下，查找算法的时间复杂度接近于O(1)。换句话说，字典再厚，也不会明显地影响到查字典的效率了。

好，让我们回到计算机的世界中来。
哈希表的最大特点，是数据存储位置（偏移量）和数据记录的内容相关，存在着一个函数换算关系：
Offset = Hash (Key)

Data center的定义：

http://en.wikipedia.org/wiki/Data_center

构建data center有一些规则，tier 1 到 tier 4，可靠性越来越高。提高可靠性的目的是为了保证“business continuity”。这个很好理解，如果公司的业务是基于网络的，如果data center断了哪怕几分钟都会有很大的影响。物理的保证，比如冷却，冗余电源（UPS是一方面，有些要求供电必须是从两个不同的电厂进来，走不同的供电线路），防水灾，火灾，地震，等等。总之已知的危险要能预防（未知的就没办法了，比如地球毁灭，什么招都不好使）。从安全角度来讲，分布式的data center是必要的条件，只有这样，才能保证更好的安全性。

从软件角度来讲，所有的安全规则和措施，都是为了保证”business continuity”，这就是做安全的价值所在。软件保证安全的手段有些和物理安全类似，有些是不同的。

在data center里面，硬件需要冗余以保证可靠性。

在data center里面，需要哪些硬件？服务器，存储，网络，电源，制冷，机架，等等。需要哪些软件？调度，存储管理，网络管理，监控，报警等等。用户软件就更多了，没有限制。

我们接触data center，最直接的方式就是租用一个VPS空间，搭建一个网站。VPS有以下几种：

1）服务器托管。服务器托管在IDC的机房，通过IDC的网络接入internet。这种比较贵。

一些ppt，作者没找到，不知道是哪个大牛。

有几个问题需要考虑一下：

1）Distributed system是多个node协同工作，还是多个node用起来就像是一个node。如果是多个node协同工作，node之间如何相互发现，如何调用？如果看做是一个node，是不是相当于资源扩展了，那资源又如何命名？

2）虽然计算和存储是分布的，但是如何调度计算，如何分配和定位资源却需要集中处理。比如DNS系统，root DNS是必须的，否则没有最终的仲裁者，有些地址可能找不到，本地的DNS可以就近响应，无法响应的，需要向上反映，这是一个layered结构，应该也是无法避免的。

在分布式平台里面，corba是一个非常重要的标准，下面是几个开源的实现;

ACE and TAO:
http://www.cs.wustl.edu/~schmidt/TAO.html

ICE:
http://www.zeroc.com/index.html, 简化版本的CORBA，corba的协议太复杂了，需要一个精简的。

OSGi:
http://www.osgi.org/Main/HomePage，这个是做插件的一个标准，和分布式关系不大。

有很多与分布式相关的协议或者标准，比如RMI，RPC，以及SOA，不过这些远程调用的机制，能不能用在realtime system还需要考察一下。定制的调用机制，效率高；但是如果有通用的机制，编程方便，还能重用。

http://en.wikipedia.org/wiki/Distributed_computing
http://en.wikipedia.org/wiki/Grid_computing

Memory corruption是非常难调试的一类问题（multi threading也算是一类）。Multi thread有可能引起memory corruption（一个在分配，一个是释放；或者一个释放，一个在使用等等）。Memory write越界也是一个原因，double free也是一个原因。总之，这类问题需要对memory layout非常了解，对memory managment的结构要非常了解。接下来就是看代码了。
排除硬件的问题。如果数据被写坏，重启thread/process就可以了，数据可以重建，但是代码里的错误却不能自动修复。如果系统强制做越界检查，效率就不会很高。代码的质量只能通过review等手段提高，或者通过工具检查。运行过程中的检查就没办法做。10年前的代码还在使用，新人还是需要一步一步来学习。
不废话了，贴一个gdb的reference，一个tcp/ip的packet format，总之是在分析coredump时有用的东西。

security和privacy有时候是矛盾的，特别是在身份认证和访问控制的时候。为了保证access control是有效的，首先要保证identity是有效的。这就是为什么需要PKI。为保障privacy，有时需要隐藏身份和加密数据，但是为了security，却又需要身份认证和content inspection.

在网络上，没有人知道对方是不是条狗，为了避免这种情况发生，就有了实名制。有了实名制，有些不想让人看见或者知道的事情就没法做了，这也是大家抱怨的原因。第三方的监控大多数情况下是在为告知当事人的情况下进行的，这样做就侵犯了人的隐私权。

为了明确security和privacy的界限，法律至少应该有个明确的规定。哪些属于合法的，哪些是不合法的。当然，秘密进行的活动往往是不合法的，比如在家偷着看个A片之类的，如果警察对这个进行监控，全中国的正常男人都无法幸免。

在一个强制进行身份认证的环境里面（比如trust computing所做的事情），虽然是保证了安全，却使得生活少了许多乐趣。在security和privacy直接平衡，并不简单是一个技术问题，而是一个社会问题，政治问题。

l7filter用的是regular expression，是NFA，效率和signature的长度和复杂度有关；ipp2p直接把signature写在程序里面，效率高一点，但是不过灵活。可以把regular expression转换成DFA，匹配效率会高很多，当然内存占用会很多。没办法，空间换时间，没有其他选择。

写一个regular expression或者DFA的engine，需要考虑多线程safe，能够在多线程环境里面使用，更进一步，能够利用多线程的好处。现在很多库在写的时候都没有考虑多线程，所以效率不一定高。多线程的算法和单线程的算法是不一样的，有很多特殊的优化可以提高性能，需要关注一下这方面的信息。

Signature是application security里面一个非常重要的概念，IDP, AV, Application identification, ips等等，都需要用signature来过滤相应的威胁。

但是，什么是signature。

常见的，比如destination port是80，可以认为是HTTP协议。最简单的，当然是通过protocol, port来定义相应的协议。当这些不够用时，需要从内容里面来发现某个协议的特征，也就是signature。signature就是特征，同一个协议可能有多个signature。就像人也可以通过多种途径去识别，比如通过姓名，身份证号码，户口本，指纹，虹膜，脸型等等。

signature需要具有唯一性，不能一个signature可以标识多个人；signature也应该是稳定的，如果不稳定，就没法正确识别一个人。在这一点上，网络协议的signature就稍差一点，协议改动很容易，但是发现和定义signature却不太容易。有些协议，大家遵守相同的规定，signature相对稳定，有些私有协议，本身就是为了规避检查的，signature就非常不稳定。所以二代身份证要比一代身份证安全很多，因为它可以通过中央服务器来认证。signature应该是可以验证的，如果不能正确标识一个协议，signature也没有意义。

有很多版本的协议，也有很多版本的signature，所以signature也应该是进化的，没有一个signature是万能的。

如果给所有接入网络的主机都发放证书，做为signature，是不是就可以杜绝攻击哪？理论上应该是这样，这也就是为什么有可信计算平台的原因，还有网络实名制也是这个理由。当然，在虚拟世界里，人总有一些不想让人发现和知道的东西，这个和真实世界是一样的。所以security所做的工作就是在不可信的网络环境里面，建立相对可信的边界。这个难度可不小。

最近学习了一下application firewall，相关信息可以参考：

http://www.owasp.org/index.php/Main_Page

http://l7-filter.sourceforge.net/ 

     (http://protocolinfo.org/wiki/Main_Page)

http://ipp2p.org/

把web security做到网关上，有什么好处哪？

1）可以保护多个服务器，也可以保护多个应用。可以避免在多个服务器或者应用程序里面部署安全模块。但是，事实是这样的吗？多数时候，也就是多穿条裤子而已。

2）Service厂商对安全不精通，security厂商更懂安全。但是，事实上，security厂商不懂应用，基本上是在follow，未知的无法防护，已知的打补丁就行了，gateway倒是可以减小安全风险，从这一点来看还是有价值的。

坏处是什么哪？

1）Gateway上防护多个application security，复杂度会很高，性能无法保障。这就增加了gateway的研发难度。

2）Gateway坏了，网就断了。如果是一个server坏了，其他的还可以用。所以gateway的high availibility和reliability非常重要。这也是一流厂商也不入流厂商的区别。

3）管理的难度增加。如何写过滤规则，signature，单靠gateway厂商肯定是不行的，需要行业联盟来做这件事。不过相比在每个server部署安全模块，管理的成本和工作量倒是降低了。