大规模Web服务开发技术


大规模Web服务的开发定位——掌握整体

大规模和小规模服务

小规模服务和大规模服务的区别

  1. 保证可扩展性, 负载均衡的必要性
    • 横向扩展(scale out):通过增加服务器数量来提高系统整体的处理能力并分担负载。
    • 纵向扩展(scale up):通过提高硬件性能来提高处理能力。
  2. 保证冗余性
  3. 低成本运维的重要性
  4. 开发人数和开发方法的变化

应对大规模数据量

现代计算机的特点, 就是各层之间的速度差异非常大。即使操作系统和中间件再努力,也是有极限的。数据量增大, 就会经常发生缓存不命中, 结果就要多次访问低速磁盘。进入磁盘I/O(输入输出)等待队列的程序在等待读取完成之时,即使其他资源空闲, 也无法进行下一步处理。这就会导致系统整体的速度下降。


持续增长的服务和大规模化的障碍

系统增长战略——最小化开端, 预见变化的管理和设计

  1. 事先考虑到未来系统规模会变大,从而一开始就建立完善的负载均衡系统的话,成本实在是太高了。
  2. 不假思索地开始也是欠考虑的。数据规模增大引起的I/O负载上升并不是平滑增加。从缓存不命中开始只需片刻, 问题就会急剧显露出来, 引起人们注意时, 系统速度就已经开始下降了——这种事情是极其常见的。
  3. 最小化开端, 在关键的地方为将来的增长做好规划, 又不致花费过多的开销。

大规模数据处理入门——内存和磁盘,Web应用程序和负载

大规模数据处理的难点——内存和磁盘

为何处理大规模数据如此困难——因为无法在内存中计算

无法在内存中计算的话, 就必须搜索磁盘上的数据, 但是磁盘十分缓慢, I/O十分耗费时间。

内存和磁盘的速度差异——内存要快10^5-10^6倍

内存比磁盘快10w-100w倍。

操作系统层的加速处理

操作系统将连续的数据放在同一处, 一次性读取4KB(kilobytes)左右。其结果就是将磁盘旋转次数降到最低。这种处理尽量减少磁盘旋转。尽管如此, 旋转一次也需要花费毫秒级,所以与内存的速度差异还是不可避免的。

传输速度和总线的速度差异

内存的搜索速度是磁盘的10^5-10^6倍以上, 不论内存还是磁盘, 都用总线与CPU连接。 这些总线的传输速度也有差异。连接内存和CPU的总线相当快,能达到7.5G/s, 但磁盘只能达到58M/s。SSD(solid State Drive, 固态硬盘)不需要物理旋转即可进行高速搜索, 但由于总线速度的瓶颈以及其他结构的影响, 其速度还是无法与内存相比。

在现代计算机上编写应用程序时, 必须考虑到内存和磁盘的速度差异。这是考虑可扩展性(scalability)时及其主要的一点, 也是非常困难的一点。

不要推测, 要测量——将一台服务器的性能发挥到极致

负载均衡也不例外。通过测量找出系统的瓶颈,然后努力消除瓶颈以发挥性能。

寻找瓶颈的基本流程

查看平均负载

查找CPU和I/O的瓶颈

平均负载过高时, 要在CPU或者I/O中寻找原因。sar或vmstate可以查看CPU使用情况和I/O等待率随着时间的推移情况,作为参考。

“CPU负载”过高时, 用以下流程寻找原因:

“I/O负载”过高, 多半是程序发出的I/O请求过多导致负载过高, 或是发生页面交换导致频繁访问磁盘。

如果是发生页面交换的情况, 应该从以下几点着手调查:

如果是没有交换发生, 而且磁盘I/O频繁的情况, 可能是用于缓存的内存不足。 根据服务器拥有的数据量和可增加的内存量, 按照一下步骤选择应对方法:

操作系统调优, 就是找出负载原因并去除之

调优的真正含义是 “找到瓶颈并去除之”


可扩展性的要点

扩展和可扩展性

将大量廉价的, 性能一般的硬件放在一起以提升系统性能的“横向扩展”(scale out)方案流行。因为它更适合大多数Web服务,虽然原因多种多样,但价格低廉和系统结构灵活是最重要的原因。

可扩展性的要点——CPU负载和I/O负载

代理服务器或应用服务器,基本上只消耗CPU。相反,数据库服务器需要较多I/O资源。

Web应用程序和负载的关系

CPU负载服务器, 只须增加与原有服务器结构完全相同的服务器, 负载均衡器(load balancer)负责均匀的分发请求, 这样就OK了。

数据库的可扩展性很难保证

大规模环境中产生I/O负载的服务器本来就很难分散, 再加上频繁产生的磁盘I/O, 很容易导致服务器变慢, 这才是本质的问题。

两种负载与Web应用程序

  1. CPU负载 程序的处理速度依赖于CPU的计算速度。也称为“计算密集型程序”(CPU bound)
  2. I/O负载 程序的处理速度依赖于磁盘的读取速度, 即依赖于输入/输出。这种给I/O加上负载的程序成为“I/O密集型程序”

多任务操作系统和负载

top的输出结果包含为“load average”(平均负载)的数字。平均负载从左到右分别为1分钟,5分钟, 15分钟内单位时间中处于等待状态的任务数。平均负载高, 说明有相应数量的任务在等待, 可以认为运行有延迟, 也就是负载过高。

平均负载揭示的实际负载状况

硬件每隔一定周期给CPU发送中断信号。每次发生中断时, CPU就会进行与时间相关的处理。平均负载就是在每次定时器中断(Timer Interrupt)发生时计算的。

平均负载中的负载的意思就是:

平均负载本身是将两种负载综合的结果, 单凭该数字无法判断是CPU负载高, 还是I/O负载高。


处理大规模数据的基础知识

面向程序员的大规模数据的基础

  1. 处理大规模数据的三个重点——写程序的技巧
    • 能在内存中完成多少? 将磁盘寻道次数降到最低。实现分布式, 有效利用局部性。
    • 能应对数据量增加的算法和数据结构 例如:线性搜索->二叉树搜索
    • 数据压缩, 信息搜索技术
  2. 处理大规模数据之前的三大前提知识——程序开发的底层基础
    • 操作系统的缓存
    • 以分布式为前提的RDBMS应用
    • 算法和数据结构

平均负载之后是CPU使用率和I/O等待率

负载过大而导致性能下降的原因绝大多数都是CPU或I/O某个出了问题, 可以按照以下方法调查哪个出了问题。

  1. 通过sar查看CPU使用率和I/O等待率 %user是CPU在用户模式下的使用率, %system为系统模式下的使用率
  2. I/O密集型场合的sar状态 %iowait 是I/O等待率
  3. 多CPU与CPU使用率 sar -P ALL

操作系统的缓存和分布式——高效处理大规模数据的原则

操作系统的缓存机制

在理解操作系统缓存的基础上编写应用程序——页面缓存

Linux上有页面缓存(page cache),文件缓存(file cache),缓存区缓存(buffer cache)这些机制。

虚拟内存机制

由于操作系统将物理硬件抽象化, 因此才产生了虚拟内存。

Linux页面缓存原理

内核分配过的内存不会释放, 而是一直保留下来(即页面缓存)

VFS

磁盘缓存就是像这样由页面缓存实现的, 但实际上操作磁盘的设备驱动程序和操作系统之间还夹着一层文件系统VFS(Virtual File System, 虚拟文件系统), 负责将不同实现方式的文件系统抽象化。

Linux以页面为单位缓存磁盘

操作系统以块为单位读出缓存的内存, 所以只能对文件某一部分, 或读出部分缓存。

页面=虚拟内存的最小单位

LRU(Least Recently Used), 放弃最老的内容, 留下最新的内容。

Linux使用inode编号来识别文件, 以文件的inode编号和表示内容在文件中位置的偏移量两个值作为键进行缓存。操作系统内部使用了名为Radix Tree的数据结构, 保证缓存的搜索速度不会降低。

内存空闲时就缓存——通过sar确认

Linux会把全部空闲内存用于缓存, 通过sar -rkbcachedkilo byte cached的省略, 即用于缓存的容量。

增加内存降低I/O负载

页面缓存是透明的

降低I/O负载的策略

以缓存为前提的降低I/O负载的策略

  1. 如果数据规模小于物理内存, 就全部缓存;
    • 以缓存为前提的降低I/O负载的策略是有效的
    • 大规模数据处理时数据压缩很重要, 比如一般的压缩算法如LZ算法等, 对于文本文件能压缩到一半左右
  2. 考虑与经济成本的平衡性
    • 选择性能上最为经济的服务器
    • 硬件成本突然增加时,改进软件更合适

扩展到多台服务器——无法全部缓存的情况

单纯增加数量无法保证可扩展性

无法缓存的比例依然不变, 立即再次成为瓶颈

降低I/O负载和页面缓存

Linux以4KB的小块来管理内存空间, 这种4KB的块成为“页面”。

  1. 页面缓存起到的降低I/O负载的效果
  2. 要先读取一次磁盘才会页面缓存

利用局部性的分布式

  1. 根据访问模式实施分布式
  2. 不再有无法缓存的数据

Partitioning——考虑局部性的分布式

Partitioning 就是将一个数据库分割到多台服务器上。

  1. 以RDBMS的表为单位分割
  2. 从数据中间分割
  3. 根据用途将系统分成不同的“岛”

根据访问模式分割成“岛”——考虑局部性的分布式

一般请求, 爬虫和图像分别分到不同的“岛”上。

以页面缓存为前提的基本应用规则


数据库的横向扩展策略——以分布式为基础的MySQL应用

正确应用索引——分布式MySQL应用的打前提

分布式MySQL应用的三大要点

灵活应用操作系统缓存

  1. 考虑全部数据量
    • 保持数据量小于物理内存
    • 内存不足时增加内存等
  2. 考虑表结构设计对数据大小的影响(亿条数据, 表结构稍有错误, 数据量就会以GB为单位增减)

索引的重点——B树

  1. index=索引
  2. B+树
    • 搜索外部存储设备时能将寻道次数最小化的树结构(可以将各节点的大小设定在一个合适的范围内——4KB左右
    • 搜索复杂度:O(n) -> O(logn)

索引的效果

不仅能改善复杂度, 还能改善磁盘寻道次数。这是B树与其他复杂度同样是O(logn)的树的区别

确认索引是否有效的方法——explain命令


MySQL的分布式——以扩展为前提的系统设计

MySQL的replication功能

  1. master/slave的架构
  2. 查询发给slave, 更新发给master
    • 通过ORM来控制

master/slave的特性——对参照系进行扩展, 更新类不扩展

  1. 查询可以扩展
    • 只需增加服务器即可
    • 但是, 在增加服务器之前要先安装适当的内存
  2. master无法扩展
    • 更新类的查询增加后情况更加严峻
    • 但是, Web应用程序多数情况下90%都是读取查询
    • master的负载通过表分割或更换实现方法来解决

MySQL的横向扩展和Partitioning

MySQL的横向扩展策略

若无法增加内存就用Partitioning

关于Partitioning(表分割)的补充

Partitioning就是充分利用局部性进行分散, 提高缓存利用效率。

以Partitioning为前提的设计

避免JOIN——利用where…in…

Partitioning的代价

实现冗余化需要几台服务器

master1台+slave2台的话, 假设某台slave发生故障, 而准备好新的数据库服务器要复制数据, 但要复制数据, 就必须把剩下的那台slave停机(停止master无法写入, 停止slave无法读取)

要想完美的冗余化, 4台1组是必要的

Partitiong的代价

  1. 优点
    • 降低负载
    • 增加局部性, 提高缓存效果
  2. 缺点
    • 运维变得复杂后, 经济成本也会上升
    • 故障率上升
  3. Partitioning毕竟只是杀手锏

大规模数据处理“实践”入门

特殊用途索引——处理大规模数据

超出RDBMS处理器能力时怎么办?

特殊用途索引——使用调优后的数据结构

  1. 搜索用的逆向索引
  2. 关键字用的Trie
    • 正则表达式拥有自动机中的NFA(Nondeterministic Finite Automaton, 非确定性有限自动机), 用OR链接之后, 匹配时的计算量就会迅速膨胀
    • Trie和Common Prefix Search(公共前缀搜索)的组合才是王道
    • 实现Common PrefixSearch有Aho-Corasick, Double Array Trie
  3. 文本分类器
    • Complement Naive Bytes 自动进行机器学习并分类
  4. 全文索引

压缩数据——考虑数据大小和I/O加速之间的关系

以紧凑,简洁方式保存整数数据

可变字节码——用紧凑格式保存整数数据

可变字节码(variable Byte Code)中, 各字节的8比特的最高位1比特为标志位, 因此表示整数的只有7比特。第一字节的低7比特表示0-127, 高位字节表示128×(1-127), 更高位表示128^2(1-127)

用“差”存储已排序整数

  1. 求出与前一个数值之差
  2. 数值分布变成大量较小的数值和少量较大的数值
    • 将结果用可变字节码编码, 压缩效果来源于偏离分布

压缩的基础

  1. 根据符号的概率分布, 给出现频率较高的分配较短的编码, 出现频率低的分配较长的编码

压缩对象是整形的情形——背景理论

  1. 压缩对象本身就有整数的含义
  2. 巧妙的利用整数的特征进行压缩

可变字节吗和速度的感觉


算法实用化——从身边的例子来看理论,研究的实践投入

算法和算法评测

数据规模和复杂度的差异

学习算法的意义——计算机资源有限, 工程师的通用语言

灵活应用第三方实现——CPAN等


Hatena Diary的关键字链接

用模式匹配实现关键字链接的问题

Perl的正则表达式采用的是NFA(Nondeterministic Finite Automata, 非确定性有穷自动机)

从正则表达式到Trie——改变匹配的实现方式

Aho-Corasick算法


Hatena Bookmark的文章分类

什么是文章分类

用贝叶斯过滤器判断类别

机器学习和大规模数据

贝叶斯过滤器的原理

  1. 贝叶斯过滤器的核心是朴素贝叶斯算法
  2. 页贝斯公式 P(B A)=P(A B)P(B)/P(A)

拼写错误改正功能的制作方法

  1. 使用正确数据字典, 可以下载Wikipedia等的数据
  2. 计算搜索查询与字典中语句的编辑距离, 定量衡量错误程度——Levenshtein
  3. 以一定的错误程度为基准, 从字典中找出某个单词作为候补正确答案——使用n-gram缩小比较对象, 之后逐个计算编辑距离(常用的是二元的Bi-Gram和三元的Tri-Gram)
  4. 将候补正确答案以文章中的单词使用频率为基准,按照正确的可能性排列
  5. 将使用频率最高的单词作为正确答案提示给用户

挑战全文搜索技术——各种各样的大规模数据处理经验技巧

搜索系统的架构

搜索引擎中最重要的元素之一——逆向索引(inverted index), 由Dicitionary(字典文件)和Postings(置入文件)两个基本要素组成。

搜索系统的架构

搜索系统所需的步骤

  1. 爬行, 存储, 建立索引, 搜索, 评分, 结果显示
  2. 6个阶段分别有各自的课题

全文搜索的种类

  1. grep类型——grep, Shunsaku
    • 从头开始读取搜索对象
    • 即时性良好, 搜索无遗漏,并行化,查询扩展很容易
    • 朴素算法——O(mn), text:m, word:n
    • KMP(Knuth-Morris-Pratt)算法——O(m+n)
    • BM算法(Boyer-Moore)——最坏情况(mn), 最好情况O(n/m)
  2. 后缀类型——Sedue
    • 用可搜索的形式存储搜索对象的全文
    • 数据结构有:Trie, Suffix Tree, Suffix Array, Compressed Suffix Array
    • 理论上可能
    • 信息量过大,难以实现
  3. 逆向索引类型(Inverted Index,倒排索引)——主流(Google)
    • 建立term(单词)和文档的关系
    • 平衡性良好的架构——实际系统大多使用逆向索引
    • 即时性不佳,可能有搜索遗漏

搜索引擎的内部结构

逆向索引的结构——Dicitonary+Postings

  1. term和文档的关系
  2. term
    • 文档中的单词
    • 所有term的集合称为Dictionary
  3. 逆向索引=Dictionary+Postings
    • 能够即时发现包含在term中的文档

Dictionary的创建方法——逆向索引的创建方法

  1. 将单词当作term处理
    • 字典+Aho-Corasick算法切分单词
    • 使用语素分析——(MeCab日文分词器,MMSEG中文分词器
  2. 将n-gram当作term处理
    • 将n-gram作为term处理会存在错误搜索的问题(查准率降低),因此对搜索结果配合过滤比较好,但是当搜索文档内容较多时,全文匹配搜索花费时间多,不太适用。解决方法是同时使用单词逆向索引和N-gram逆向索引。正文使用单词逆向索引,标题、评价、url等使用N-gram逆向索引。
    • 扫描搜索结果进行确认
    • 对象过大时计算量大——对象越小越好
  3. 查全率和查准率
    • 搜索的恰当性的评测标准
    • 差准率=正确结果数/返回总数
    • 查全率=正确结果数/相关结果数

Postings的创建方法——逆向索引的创建方法

  1. 同时保存出现位置
    • Full Inverted Index
    • 很容易实现snippet,评分, 过滤
  2. 只保存文档ID
    • Inverted File Index
    • 索引较小,容易实现

Postings和数据结构

  1. 文档ID顺序
    • 排序——可变字节码
    • 较好的压缩比和快速压缩解压性能
  2. 结构:term——压缩后的Posting List
    • 适合使用key-value存储

支持大规模数据处理的服务器/基础设施入门——Web服务的后台

企业软件vs Web服务——应用范围上的差异

  1. Web服务的流量更大
  2. Web服务可能发生爆炸性增长
  3. Web服务有时允许暂时的不一致

Web服务的基础设施——三个重点

  1. 低成本,高效率
    • 不应当追求100%可靠性
  2. 设计很重要
    • 可扩展性,响应性很重要
  3. 开发速度很重要
    • 应当为服务提供灵活的资源

云Vs.自行构建基础设施

云计算仍处于过渡期?

  1. 优点
    • 价格便宜,灵活的可扩展性
  2. 缺点
    • 统一的主机规格
    • 模糊不清的负载均衡器
    • 时常停机

自行构建基础设施的优点:


保证可扩展性的必要思路——规模扩大和系统扩展

层和可扩展性

  1. 应用的程序服务器
    • 配置相同,不持有状态——扩展容易
  2. 数据源(数据库,文件服务器等
    • read分布式——比较容易
    • write分布式——难

掌握负载均衡进行调优

掌握负载——可视化的管理界面

测量负载的指标——平均负载,内存和CPU相关信息

根据用途进行调优——面向用户的服务器和面向爬虫的服务器

应用程序服务器,数据库服务器的调优策略和服务器数量

服务规模和调优

保证可扩展性


保证冗余性和系统的稳定化——实现100%在效率的原理

最重要的就是去除SPOF(single point of failure), 即单点故障

保证冗余性

保证冗余性——应用程序服务器

  1. 增加服务器数量, 即使一两台停机也能保证充足的处理能力
  2. 用负载均衡实现失败转移(failover)和失败恢复(failback)

保证冗余性——数据库服务器

  1. Multi-master, 服务器用VRRP协议(Virtual Router Redundancy Protocol, 虚拟路由器冗余协议)互相监视, 一旦通过VRRP发现对方停机, 就将自己提升为Active master
  2. 互相replication
  3. 切换时会有不同步的风险, 有问题时人工恢复

保证冗余性——存储服务器

系统稳定化

保持系统稳定的权衡

  1. 内存只使用7成左右, CPU只使用7成左右

不稳定的因素——负载增大

  1. 功能增加, 内存泄漏, 地雷, 用户访问模式, 数据量增加, 外部关联程序增加
    • 地雷:某些URL一旦读取(踩到)就无法返回应答
    • slashdot效应, digg效应等, 链接被贴到著名网站上, 被大量用户访问导致系统停机
  2. 硬件的不稳定定因素——性能下降
    • 内存,硬盘,网卡故障

系统稳定对策

实际的系统稳定对策——维持适当余量,消灭不稳定因素

  1. 维持适当余量(buffer)
    • 内存容量,CPU负载——使用极限的7成
  2. 去除不稳定因素
    • 规定SQL负载上限——必要时将负载过高的SQL移到其他主机上
    • 减少内存泄漏
  3. 异常行为的自主判断/自动控制
    • 自动Dos判断(mod_dossdetector)
    • 自动重启
    • 自动终止耗时查询(KILL掉耗时过长的SQL

提高效率——提高硬件资源的使用率

虚拟化技术

引入虚拟化技术

  1. 可扩展性
    • 将额外开销降至最低
  2. 性价比
    • 提高资源使用率
    • 提高运维的灵活程度
  3. 高可用性
    • 环境隔离

虚拟化技术的效果

  1. 掩盖硬件差异(环境抽象化
  2. 使用准虚拟化(para Virtualization
  3. 控制资源消耗

虚拟服务器的构建策略

  1. 提高硬件资源的利用率
    • 加入能主要利用空闲资源的虚拟化操作系统(DomU
    • CPU空闲——Web服务器
    • I/O空闲——数据库服务器
    • 内存空闲——缓存服务器
  2. 避免在一起的组合
    • 资源消耗倾向相同, 且负载较高的同类服务器应避免放在一起
  3. 不使用中央存储设备

总结虚拟化的优势

  1. 解除物理的资源限制
    • 动态更改资源
    • VM的迁移和复制
  2. 软件层面更强大的主机控制
    • 异常行为局部化
    • 主机控制更容易

硬件和提高效率——实现低成本的关键技术

提高处理器性能

有效利用廉价硬件

  1. 最低限度的管理功能
  2. 多核CPU
  3. 大量内存
  4. 灵活的I/O性能
    • 无盘
    • 硬件RAID-10
    • SSD RAID-0

SSD

  1. 良好的随机访问性能
  2. 内存>SSD>HHD RAID-0/10>HDD RAID-1
  3. SSD损耗程度的指标是S.M.A.R.T值中的E9(media wearout indicator)项目, 随着平均擦除次数的增加, 该值会从100减少到0(smartctl命令获得

Web服务和网络——通过网络看服务增长

网络的分界点

  1. 超过1Gbps(300kpps)——PC路由器的极限(成品路由器
  2. 超过500台主机——一个子网的极限
  3. 全球化——一个数据中心的极限(可选CDN

挑战更高的极限

超越10Gbps的世界

  1. 获取AS编号
  2. 连接IX进行流量交换
  3. 用BGP控制路由

当前构建Web服务需要的实践技术——应对大规模Web服务须知

作业队列系统TheSchwartz, Gearman

  1. 客户端放入作业
  2. 作业队列存储队列
  3. worker访问作业队列,取出未运行的作业并加以运行

Gearman

  1. 轻量作业队列, 不用RDBMS, 而是采用自带的守护进程(daemon)作业信息保存在内存中, 以保证性能
  2. 三种模式
    • 同步的顺序处理
    • 同步的并行处理
    • 异步的后台处理

存储方式的选择 RDBMS还是key-value存储

分布式文件系统

  1. MogileFS

缓存系统——Squid,Varnish

计算集群——Hadoop


Yan Peipan 26 February 2015