代码的将来-读书笔记(2)
第4章云计算时代的编程
1、可扩展性
信息的尺度感
和人不同，计算机无论需要多少时间，最终都会完成任务。然而，如果无法在现实的时间范围内得出结果，那也是毫无用处的。
当数据量变得很大时，就会出现以前从来没有考虑过的各种问题，对于这些问题的对策必须要仔细考虑
(1) 二分法查找
能把直接查找的O(n)提高到O(logN)级别，书中列出了编程珠玑上面的一道题，上面会导致int出现溢出的问题：
mid = (lo + hi) /2;应该换成mid = lo + ((hi - lo) / 2);才能避免溢出
(2) 散列表
散列表通过使用散列函数避免了线性查找，从而使得计算量大幅度减少，是一种巧妙的算法。
如果事先得知数据的取值范围，则构造完美散列函数是可能的。
在采用链地址法的ruby的hash中，当冲突产生的链表最大长度超过5时，就会增加散列表的槽数，并对散列表进行重组。而在采用链地址法的python中，当三分之二的槽被填满时，也会进行重组。
(3) 布隆过滤器
运用了散列函数，拥有极高的时间效率O(1)，并且拥有极高的空间效率，理论上说(假设误判率为1%)，平均每个数据只需要9.6比特的空间。包括散列表在内，其他表示集合的数据结构中都需要包含袁术数据，相比之下，这样的空间效率简直是压倒性的
在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。在信息大爆炸所引发的大规模数据处理中，像布隆过滤器这样的算法，应该会变得愈发重要
(4) DHT(分布式散列表)
在分布式环境下工作的散列表被称为DHT(Distributed Hash Table)。DHT并非指的是一种特定的算法，而是指将散列表在分布式环境中进行事先的技术的统称。事先DHT的算法包括CAN、Chord、Pastry、Tapestry等。
DHT的算法非常复杂，这种复杂性是有原因的。在分布式环境中，尤其是P2P环境中实现散列表，会遇到以下问题：
由于机器故障等原因导致节点消失、节点的复原和添加、伴随上述问题产生的数据位置超找(路由)的困难问题等
近年来，运用DHT技术，在分布式环境下实现非关系型数据库的键值存储数据库受到越来越多的关注，同样的还有GFS和HFS
(5) Roma
一款作者实现的键值存储数据库，并且是开源的，难点在于节点的增减。因为大量的计算机所构成的系统，必须时刻考虑到发生故障的情况。
其特点如下：
a、所有数据都存放在内存中的内存数据库(In-Memort Database, IMDB)
b、采用环状的分布式架构
c、数据冗余化：所有数据除了其本身之外，还各种拥有两个副本
d、运行中可*增减节点
e、以开源形式发布
(6) MapReduce
数据存储的问题，通过键值存储和分布式文件熊，在一定程度上可以得到解决，但是在高度分布式环境中进行编程依然十分困难。要解决多个进程的启动、相互同步、并发控制、机器故障应对等分布式环境特有的课题， 程序就会变得非常复杂，在这种情况下，MapReduce出现了，google通过这一技术，实现了对分布式处理描述的高效化。
2、C10K问题
Client 10000 Problem。即“在同时连接到服务器的客户端数量超过10000个的环境中，即便硬件性能足够，依然无法正常提供服务”这样一个问题。
这个问题的发生，有很多背景，主要的背景如下：
a、由于互联网的普及导致客户量的增加
b、keep-alive等连接保持技术的普及
更大的问题在于keep-alive。在使用套接字的网络连接中，不能忽视第一次建立连接所需要的开销。在HTTP访问中，如果对一个一个的小数据传输请求每次都进行套接字连接，当访问数增加时，反复连接所需要的开销是相当大的。为了避免这种开销，从HTTP1.1开始，对同一台服务器产生的多个请求，都通过相同的套接字连接来完成，这就是keep-alive
最后作者提出，要解决这个问题的方式有：
a、最好使用epoll功能(因为它相对select模型，没有最大限制，windows平台下可以考虑完成端口IOCP模型)
b、使用libev框架
libev是一个提供高性能事件循环功能的库。libev是通过在loop结构体中设定一个回调函数，当发生事件(可读/可写，或者经过一定时间)时，回调函数就会被调用。
libev可以根据不同的平台自动使用epoll、kqueue、/dev/poll等事件监视API。如果这些API都不可用，则会使用select系统调用，使用了libev，就可以在监视并发连接时无需担心移植性了
在使用像libev这样的事件驱动库时，比需要注意回调函数不能发生阻塞。由于时间循环是在单线程下工作的，因此在回调函数执行过程中，是无法对别的事件进行处理的。不仅是libev，在所有事件驱动架构的程序中，都必须尽快结束回调的处理。如果一项工作需要花费很多时间，则可以将其转发给其他进程/线程来完成
c、使用EventMachine
同样是事件驱动框架，但和libev在功能上有很大的不同
libev的目的只是提供最基本的事件监视功能，而在套接字连接、内存管理等方面还需要用户自己来操心。同时，它能够支持定时器、信号、子进程状态变化等各种事件。libev是用于c语言的库，虽然程序可能会变得很繁琐，但却拥有可以应付各种状况的灵活性。
作为C语言的库，libev的功能专注于对事件的监视；而作为面向ruby的框架，EventMachine则支持包括服务器、客户端的网络连接和输入输出，甚至是SSL加密
3、HashFold
MapReduce通过分解、提取数据流的Map函数和化简、计算数据的Reduce函数，对处理进行分割，从而实现了对大量数据的高效分布式处理。
相对地，HashFold的功能是以散列表的方式接受Map后的数据，然后通过Fold过程来实现对散列元素的去重复。这种模型将MapReduce中一些没有细化的部分，如Map后的数据如何排序再进行Reduce等，通过散列表这一数据结构的性质做了清晰的描述。不过成为主流爱是很困难。
对于使用Hash而非流(stream)的这个主意作者还是挺感兴趣的。不过目前已经完全消亡了。
4、进程间通信
在Linux等Unix系操作系统中，同一台计算机上进行进程间通信的手段有以下几种：
(1) 管道(pipe)
(2) 消息(message)
(3) 信号量(semaphore)
(4) 共享内存
(5) TCP套接字
(6) UDP套接字
(7) Unix域套接字
消息、信号量和共享内存都是unix的System V(5)版本中加入的进程间通信Api。其中消息用于数据通信，信号量用于互斥锁，共享内存用于在进程间共享内存状态。他们结合起来被称为sysvipc
5、Rack与Unicorn
两个都是基于ruby的web服务器。
Unicorn的关键是，不是有http服务器来主动进行负载均衡，而是采用了完成工作的Slave主动获取请求的拉模式。对于Slave之间的任务分配则通过操作系统的任务切换来完成。
近年来，由于考虑到C10K问题而采用事件驱动模型等，web应用程序也在用户应用程序的水平上变得越来越复杂。但Unicorn却通过将复杂的工作交给操作系统来完成，从而实现了简洁的架构。因为事件处理、任务切换等等本来就是操作系统所具备的功能。当然，仅凭Unicorn在客户端并发连接的处理上还是存在极限，如果请求数量过大也有可能处理不过来，但我们可以使用反向代理，将多个Unicorn系统捆绑起来，从而实现横向扩展。
第5章支撑大数据的数据存储技术
1、键值存储
键值存储是数据库中的一种。在云计算愈发流行的今天，键值存储正在受到越来越多的关注。以关系型数据库管理系统(RDBMS)为代表的现有数据库系统正接近其极限，而键值存储则拥有超越这种极限的可能
使用键值存储方式的数据库，大多数都在数据查找技术上使用了散列表这种数据结构。散列表是通过调用散列函数来生成由键到散列值的映射，通过散列值来确定数据的存放位置。散列表中的数据量无论如何增大，其查找数据所需的时间几乎是固定不变的，因此是一种非常适合大规模数据的技术。
(1) 数据库的ACID特性
ACID是4个单词首字母的缩写，它们分别是：Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)和Durability(持久性)
(2) CAP原理
当组成计算机环境的集群很大时，ACID特性就很难满足，换句话说，ACID是不可扩展的。对此，有人提出了CAP原理，即在大规模环境中：
a、Consistency(一致性)
b、Availability(可用性)
c、Partition Tolerance(分裂容忍性)
这三个性质中，只能同时满足其中的两个
(3) 大规模环境下的键值存储
分布键值存储的基本架构并不复杂。多态计算机组成一个虚拟的圆环，其中每个节点负责某个范围的散列值所对应的数据
当客户端程序对数据进行访问时，首先通过作为键的数据(字符串)计算出散列值，然后找到负责该散列值的节点，直接向该节点请求取出或者存放数据。
作者的ROMA为了突破性能的瓶颈，加上了连接池技术，让各个应用程序都持有一张记载组成键值存储自从所有节点信息的表(路由表)，并直接对节点进行访问，而且必须保持路由表处于最新状态。
一些其他比较重要的机制，比如数据的有效期、虚拟节点(为了让节点之间因分配调整而进行的数据传输更加高效，将若干个键组织起来形成“虚拟节点”的机制)、散列树(使用了环状节点分布和浮点小数散列值，实际上的算法使用的是SHA-1散列和Merkle散列树，因为效率更高)
2、NoSql
NoSql数据库只是一个统称，大体上，可以分为三种：
(1) 键值存储数据库
所谓键值存储一般都指的是分布式键值存储系统。符合这样的条件的键值存储数据库包括“memcached”、“ROMA”、“Redis”等
(2) 面向文档数据库
代表为CouchDB、MongoDB，对键值存储中的“值”的部分，存储的不是单纯的字符串或数字，而是拥有结构的文档。和单纯的键值存储不同，由于它可以保存文档结构，因此可以基于文档内存进行查询
(3) 面向对象数据库
将面向对象语言中的对象直接进行保存的数据库，比如作者的ObjectStore
3、sql的反击
这章挺有深度的，因为大数据的处理，导致人们并不看好sql。不过作者认为可以把数据(例如SNS)用奇偶进行水平分割，然后分别放进不同的机器上面的数据库中，便完成了一个数据的分开存放。
尽管通过Sharding技术将数据库进行分割，就能够在分布式环境中使用sql数据库，但却无法做到像一部分NoSql数据库那样，能够根据需要自动增加节点来实现性能的扩充。此外，如果用sql数据库来实现NoSql中这种简单的查询处理，大多数情况下在性能都不及NoSql
数据库之父在一篇blog中指出，sql的性能瓶颈在：
(1) 日志管理(向数据库执行一次写入，再向日志执行一次写入)，写到磁盘总是非常慢的
(2) 事务锁，在对记录进行操作之前，为了防止其他线程对记录进行修改，需要对事物加锁，这也是一项巨大的开销
(3) 内存锁，这里指对锁和B树等共享数据结构进行访问时需要的一种排他处理方式，这也是开销
(4) 缓存处理，一般来说，数据库的数据是写入到固定长度的磁盘页面中的。对于哪个数据写入哪个页面，或者是哪个页面的数据缓存在内存中，都需要由数据库进行管理。这也是一项开销很大的处理。
(5) 他自己设计了VoltDB数据库，但是不支持sql来查询，内部是通过使用存储过程来改善性能的
4、memcached和它的伙伴们
提到缓存，往往会包含以下含义：
(1) 可以高速访问
(2) 以改善性能为目的
(3) 仅用临时存放数据，当空姐已满时可以任意丢弃多出来的数据
(4) 数据是否存放在缓存中，不会产生性能以外的其他影响
memcached非常好用，应用也非常广泛。其具备以下特征：
(1) 以字符串为对象的键值存储
(2) 数据只保存在内存中，重启memcached服务器将导致数据丢失
(3) 可以对数据设置有效期
(4) 达到一定容量后将清除最少被访问的数据
(5) 键的长度上线为250B，值得长度上限为1MB
作者对memcached的不满：
(1) 数据长度：对键和值的长度分别限制在250B和1MB
过于严格。越是大的数据查询起来就要花很长的世杰
(2) 分布：一台服务器的内存容量有限，如果能将缓存分布到多台服务器上就可以增加总的数据容量。然后memcached并没有提供分布功能
(3) 持久性：memcached只是一个缓存，重启服务器数据就会丢失，且为了保持一定的缓存带下，还会自动舍弃旧数据
不过作者最后又说，memcached的这些不满，并不是memcached的缺点。顾名思义，memcached原本是作为数据缓存服务器诞生的，因此这些都超出原来目的的场景中所导致的结果
5、另一种数据库Redis
(1) 内存型：数据库的操作基本都在内存中进行，速度非常快
(2) 支持永久化：提供了异步输出文件的功能。发生故障时，最后输出的文件之后的变更会丢失。虽然并不具备严格的可靠性，但却可以避免数据的完全丢失
(3) 支持分布：Redis Cluster分布层的开发还在计划中。具备服务器端复制功能
(4) 除字符串之外的数据结构：还支持list、set、有序集和散列表，在memcached中必须强制转换为字符串才能存放的数据结构，在Redis中可以直接存放
(5) 高速：全面使用C语言编写的Redis速度非常快
(6) 原子性：由于Redis内部是采用单线程实现的，因此各命令都具备原子性
(7) 不兼容memcached协议
6、后记
数据存储逐步过渡到采用以闪存为基础的SSD，同时MRAM、FeRAM等下一代内存也开始崭露头角。在下一代内存得到广泛运用的时代，曾经像Smalltalk、Lisp那样将内存空间直接保存下来的模型，说不定会东山再起。