技术面试要了解的算法和数据结构知识

目录

  • 在线练习
  • 在线编程面试
  • 数据结构
  • 算法
  • 贪心算法
  • 位运算
  • 复杂度分析
  • 视频教程
  • 面试宝典
  • 计算机科学资讯
  • 文件结构

在线练习

在线编程面试

数据结构

链表

  • 链表是一种由节点(Node)组成的线性数据集合,每个节点通过指针指向下一个节点。它是一种由节点组成,并能用于表示序列的数据结构。
  • 单链表 :每个节点仅指向下一个节点,最后一个节点指向空(null)。
  • 双链表 :每个节点有两个指针p,n。p指向前一个节点,n指向下一个节点;最后一个节点指向空。
  • 循环链表 :每个节点指向下一个节点,最后一个节点指向第一个节点。
  • 时间复杂度:
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

  • 栈是一个元素集合,支持两个基本操作:push用于将元素压入栈,pop用于删除栈顶元素。
  • 后进先出的数据结构(Last In First Out, LIFO)
  • 时间复杂度
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

队列

  • 队列是一个元素集合,支持两种基本操作:enqueue 用于添加一个元素到队列,dequeue 用于删除队列中的一个元素。
  • 先进先出的数据结构(First In First Out, FIFO)。
  • 时间复杂度
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

  • 树是无向、联通的无环图。

二叉树

  • 二叉树是一个树形数据结构,每个节点最多可以有两个子节点,称为左子节点和右子节点。
  • 满二叉树(Full Tree) :二叉树中的每个节点有 0 或者 2 个子节点。

大数据

  • 完美二叉树(Perfect Binary) :二叉树中的每个节点有两个子节点,并且所有的叶子节点的深度是一样的。
  • 完全二叉树 :二叉树中除最后一层外其他各层的节点数均达到最大值,最后一层的节点都连续集中在最左边。

二叉查找树

  • 二叉查找树(BST)是一种二叉树。其任何节点的值都大于等于左子树中的值,小于等于右子树中的值。
  • 时间复杂度
    • 索引:O(log(n))
    • 查找:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))

大数据

字典树

  • 字典树,又称为基数树或前缀树,是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值,而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀,根节点则是空字符串。

大数据

树状数组

  • 树状数组,又称为二进制索引树(Binary Indexed Tree,BIT),其概念上是树,但以数组实现。数组中的下标代表树中的节点,每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和,在整个树更新的过程中,这些计算的值也同样会被更新。
  • 时间复杂度
    • 区间求和:O(log(n))
    • 更新:O(log(n))

大数据

线段树

  • 线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。
  • 时间复杂度
    • 区间查找:O(log(n))
    • 更新:O(log(n))

大数据

  • 堆是一种基于树的满足某些特性的数据结构:整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中,父节点的键值永远大于等于所有子节点的键值,根节点的键值是最大的。最小堆中,父节点的键值永远小于等于所有子节点的键值,根节点的键值是最小的。
  • 时间复杂度
    • 索引:O(log(n))
    • 查找:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))
    • 删除最大值/最小值:O(1)

大数据

哈希

  • 哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值,则发生了冲突。
  • Hash Maphash map  是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标,从而便于指定值的查找。
  • 冲突解决
    • 链地址法( Separate Chaining :在链地址法中,每个桶(bucket)是相互独立的,每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间(常量)与遍历列表元素的时间之和。
    • 开放地址法( Open Addressing :在开放地址方法中,当插入新值时,会判断该值对应的哈希桶是否存在,如果存在则根据某种算法依次选择下一个可能的位置,直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。

大数据

  • 图是G =(V,E)的有序对,其包括顶点或节点的集合 V 以及边或弧的集合E,其中E包括了两个来自V的元素(即边与两个顶点相关联 ,并且该关联为这两个顶点的无序对)。
  • 无向图 :图的邻接矩阵是对称的,因此如果存在节点 u 到节点 v 的边,那节点 v 到节点 u 的边也一定存在。
  • 有向图 :图的邻接矩阵不是对称的。因此如果存在节点 u 到节点 v 的边并不意味着一定存在节点 v 到节点 u 的边。

大数据

算法

排序

快速排序

  • 稳定:否
  • 时间复杂度
    • 最优:O(nlog(n))
    • 最差:O(n^2)
    • 平均:O(nlog(n))

大数据

合并排序

  • 合并排序是一种分治算法。这个算法不断地将一个数组分为两部分,分别对左子数组和右子数组排序,然后将两个数组合并为新的有序数组。
  • 稳定:是
  • 时间复杂度:
    • 最优:O(nlog(n))
    • 最差:O(nlog(n))
    • 平均:O(nlog(n))

桶排序

  • 桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序,或递归调用桶排序。
  • 时间复杂度
    • 最优:Ω(n + k)
    • 最差: O(n^2)
    • 平均:Θ(n + k)

大数据

基数排序

  • 基数排序类似于桶排序,将元素分发到一定数目的桶中。不同的是,基数排序在分割元素之后没有让每个桶单独进行排序,而是直接做了合并操作。
  • 时间复杂度
    • 最优:Ω(nk)
    • 最差: O(nk)
    • 平均:Θ(nk)

图算法

深度优先 搜索

  • 深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

大数据

广度优先 搜索

  • 广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

大数据

拓扑排序

  • 拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v 的边,u 的下标先于 v。
  • 时间复杂度:O(|V| + |E|)

Dijkstra算法

  • Dijkstra 算法是一种在有向图中查找单源最短路径的算法。
  • 时间复杂度:O(|V|^2)

大数据

Bellman-Ford算法

  • Bellman-Ford  是一种在带权图中查找单一源点到其他节点最短路径的算法。
  • 虽然时间复杂度大于 Dijkstra 算法,但它可以处理包含了负值边的图。
  • 时间复杂度:
    • 最优:O(|E|)
    • 最差:O(|V||E|)

大数据

Floyd-Warshall 算法

  • Floyd-Warshall  算法是一种在无环带权图中寻找任意节点间最短路径的算法。
  • 该算法执行一次即可找到所有节点间的最短路径(路径权重和)。
  • 时间复杂度:
    • 最优:O(|V|^3)
    • 最差:O(|V|^3)
    • 平均:O(|V|^3)

最小生成树算法

  • 最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之,最小生成树算法能在一个图中找到连接所有节点的边的最小子集。
  • 时间复杂度:O(|V|^2)

Kruskal 算法

  • Kruskal  算法也是一个计算最小生成树的贪心算法,但在 Kruskal 算法中,图不一定是连通的。
  • 时间复杂度:O(|E|log|V|)

贪心算法

  • 贪心算法总是做出在当前看来最优的选择,并希望最后整体也是最优的。
  • 使用贪心算法可以解决的问题必须具有如下两种特性:
    • 最优子结构
      • 问题的最优解包含其子问题的最优解。
    • 贪心选择
      • 每一步的贪心选择可以得到问题的整体最优解。
  • 实例-硬币选择问题
  • 给定期望的硬币总和为 V 分,以及 n 种硬币,即类型是 i 的硬币共有 coinValue[i] 分,i的范围是 [0…n – 1]。假设每种类型的硬币都有无限个,求解为使和为 V 分最少需要多少硬币?
  • 硬币:便士(1美分),镍(5美分),一角(10美分),四分之一(25美分)。
  • 假设总和 V 为41,。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币,然后从 V 中减掉该硬币的值,如此重复进行。
    • V = 41 | 使用了0个硬币
    • V = 16 | 使用了1个硬币(41 – 25 = 16)
    • V = 6 | 使用了2个硬币(16 – 10 = 6)
    • V = 1 | 使用了3个硬币(6 – 5 = 1)
    • V = 0 | 使用了4个硬币(1 – 1 = 0)

运算

  • 位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。
  • 测试第 k 位:s & (1 << k);
  • 设置第k位:s |= (1 << k);
  • 关闭第k位:s &= ~(1 << k);
  • 切换第k位:s ^= (1 << k);
  • 乘以2n:s << n;
  • 除以2n:s >> n;
  • 交集:s & t;
  • 并集:s | t;
  • 减法:s & ~t;
  • 提取最小非0位:s & (-s);
  • 提取最小0位:~s & (s + 1);
  • 交换值:x ^= y; y ^= x; x ^= y;

运行时分析

大 O 表示

  • 大 O 表示用于表示某个算法的上界,用于描述最坏的情况。

大数据

小 O 表示

  • 小 O 表示用于描述某个算法的渐进上界,二者逐渐趋近。

大 Ω 表示

  • 大 Ω 表示用于描述某个算法的渐进下界。

大数据

小 ω 表示

  • 小 ω 表示用于描述某个算法的渐进下界,二者逐渐趋近。

Theta Θ 表示

  • Theta Θ 表示用于描述某个算法的确界,包括最小上界和最大下界。

大数据

视频教程

面试宝典

 

技术面试要了解的算法和数据结构知识

机器学习工程师必知的十大算法

毫无疑问,机器学习/人工智能的子领域在过去几年越来越受欢迎。目前大数据在科技行业已经炙手可热,而基于大量数据来进行预测或者得出建议的机器学习无疑是非常强大的。一些最常见的机器学习例子,比如Netflix的算法可以根据你以前看过的电影来进行电影推荐,而Amazon的算法则可以根据你以前买过的书来推荐书籍。

所以如果你想了解更多有关机器学习的内容,那么你该如何入门?对于我来说,我的入门课程是我在哥本哈根出国留学时参加的人工智能课。当时我的讲师是丹麦技术大学(Technical University of Denmark)的应用数学和计算机科学的全职教授,他的研究方向是逻辑与人工智能,侧重于使用逻辑学来对人性化的规划、推理和解决问题进行建模。这个课程包括对理论/核心概念的讨论和自己动手解决问题。我们使用的教材是AI经典之一:Peter Norvig的Artificial Intelligence—A Modern Approach(中文译本:《人工智能:一种现代的方法》),这本书主要讲了智能体、搜索解决问题、对抗搜索、概率论、多智能体系统、社会AI和AI的哲学/伦理/未来等等。在课程结束时,我们三个人的团队实现了一个简单的编程项目,也就是基于搜索的智能体解决虚拟环境中的运输任务问题。

在那门课程上我已经学到了很多知识,并决定继续学习相关的课题。在过去的几个星期里,我在旧金山参加了多次相关的技术讲座,涉及到深度学习、神经网络和数据结构,并且参加了一个有很多该领域的知名专家学者参加的机器学习会议。最重要的是,我在6月初参加了Udacity上的Intro to Machine Learning(机器学习入门)在线课程,前几天才完成。在这篇文章中,我想分享一下我从课程中学到的一些最常用的机器学习算法。

机器学习算法可以分为三大类:监督学习、无监督学习和强化学习。监督学习可用于一个特定的数据集(训练集)具有某一属性(标签),但是其他数据没有标签或者需要预测标签的情况。无监督学习可用于给定的没有标签的数据集(数据不是预分配好的),目的就是要找出数据间的潜在关系。强化学习位于这两者之间,每次预测都有一定形式的反馈,但是没有精确的标签或者错误信息。因为这是一个介绍课程,我没有学习过强化学习的相关内容,但是我希望以下10个关于监督学习和无监督学习的算法足以让你感兴趣。

监督学习

1.决策树(Decision Trees)

决策树是一个决策支持工具,它使用树形图或者决策模型以及可能性序列,包括偶然事件的结果、资源成本和效用。下图是其基本原理:

从业务决策的角度来看,决策树是人们必须了解的最少的是/否问题,这样才能评估大多数时候做出正确决策的概率。作为一种方法,它允许你以结构化和系统化的方式来解决问题,从而得出合乎逻辑的结论。

2.朴素贝叶斯分类(Naive Bayesian classification)

朴素贝叶斯分类器是一类简单的概率分类器,它基于贝叶斯定理和特征间的强大的(朴素的)独立假设。图中是贝叶斯公式,其中P(A|B)是后验概率,P(B|A)是似然,P(A)是类先验概率,P(B)是预测先验概率。

一些应用例子:

  • 判断垃圾邮件
  • 对新闻的类别进行分类,比如科技、政治、运动
  • 判断文本表达的感情是积极的还是消极的
  • 人脸识别

3.最小二乘法(Ordinary Least Squares Regression)

如果你懂统计学的话,你可能以前听说过线性回归。最小二乘法是一种计算线性回归的方法。你可以将线性回归看做通过一组点来拟合一条直线。实现这个有很多种方法,“最小二乘法”就像这样:你可以画一条直线,然后对于每一个数据点,计算每个点到直线的垂直距离,然后把它们加起来,那么最后得到的拟合直线就是距离和尽可能小的直线。

线性指的是你用来拟合数据的模型,而最小二乘法指的是你最小化的误差度量。

4.逻辑回归(Logistic Regression)

逻辑回归是一个强大的统计学方法,它可以用一个或多个解释变量来表示一个二项式结果。它通过使用逻辑函数来估计概率,从而衡量类别依赖变量和一个或多个独立变量之间的关系,后者服从累计逻辑分布。

总的来说,逻辑回归可以用于以下几个真实应用场景:

  • 信用评分
  • 计算营销活动的成功率
  • 预测某个产品的收入
  • 特定的某一天是否会发生地震

5.支持向量机(Support Vector Machine,SVM)

SVM是二进制分类算法。给定N维坐标下两种类型的点,SVM生成(N-1)维的超平面来将这些点分成两组。假设你在平面上有两种类型的可以线性分离的点,SVM将找到一条直线,将这些点分成两种类型,并且这条直线尽可能远离所有这些点。

从规模上看,使用SVM(经过适当的修改)解决的一些最大的问题包括显示广告、人类剪切位点识别(human splice site recognition)、基于图像的性别检测,大规模图像分类……

6.集成方法(Ensemble methods)

集成方法是学习算法,它通过构建一组分类器,然后通过它们的预测结果进行加权投票来对新的数据点进行分类。原始的集成方法是贝叶斯平均,但是最近的算法包括纠错输出编码、Bagging和Boosting。

那么集成方法如何工作?并且为什么它们要优于单个模型?

  • 它们平均了单个模型的偏差:如果你将民主党的民意调查和共和党的民意调查在一起平均化,那么你将得到一个均衡的结果,不偏向任何一方。
  • 它们减少了方差:一组模型的总体意见比其中任何一个模型的单一意见更加统一。在金融领域,这就是所谓的多元化,有许多股票的组合比一个单独的股票的不确定性更少,这也为什么你的模型在数据多的情况下会更好的原因。
  • 它们不太可能过拟合:如果你有单个的模型没有过拟合,那么把这些模型的预测简单结合起来(平均、加权平均、逻辑回归),那么最后得到的模型也不会过拟合。

无监督学习

7.聚类算法(Clustering Algorithms)

聚类是将一系列对象分组的任务,目标是使相同组(集群)中的对象之间比其他组的对象更相似。

每一种聚类算法都不相同,下面是一些例子:

  • 基于质心的算法
  • 基于连接的算法
  • 基于密度的算法
  • 概率
  • 降维
  • 神经网络/深度学习

8.主成分分析(Principal Component Analysis,PCA)

PCA是一个统计学过程,它通过使用正交变换将一组可能存在相关性的变量的观测值转换为一组线性不相关的变量的值,转换后的变量就是所谓的主分量。

PCA的一些应用包括压缩、简化数据便于学习、可视化等。请注意,领域知识在选择是否继续使用PCA时非常重要。 数据嘈杂的情况(PCA的所有成分具有很高的方差)并不适用。

9.奇异值分解(Singular Value Decomposition,SVD)

在线性代数中,SVD是复杂矩阵的因式分解。对于给定的m * n矩阵M,存在分解使得M=UΣV,其中U和V是酉矩阵,Σ是对角矩阵。

实际上,PCA是SVD的一个简单应用。在计算机视觉中,第一个人脸识别算法使用PCA和SVD来将面部表示为“特征面”的线性组合,进行降维,然后通过简单的方法将面部匹配到身份,虽然现代方法更复杂,但很多方面仍然依赖于类似的技术。

10.独立成分分析(Independent Component Analysis,ICA)

ICA是一种统计技术,主要用于揭示随机变量、测量值或信号集中的隐藏因素。ICA对观测到的多变量数据定义了一个生成模型,这通常是作为样本的一个大的数据库。在模型中,假设数据变量由一些未知的潜在变量线性混合,混合方式也是未知的。潜在变量被假定为非高斯分布并且相互独立,它们被称为观测数据的独立分量。

ICA与PCA有关,但是当这些经典方法完全失效时,它是一种更强大的技术,能够找出源的潜在因素。 其应用包括数字图像、文档数据库、经济指标和心理测量。

现在运用你对这些算法的理解去创造机器学习应用,为世界各地的人们带来更好的体验吧。

查看英文原文:The 10 Algorithms Machine Learning Engineers Need to Know

from:http://www.infoq.com/cn/articles/10-algorithms-machine-learning-engineers-need-to-know

大型分布式网站术语分析

1. I/O优化

  1. 增加缓存,减少磁盘的访问次数。
  2. 优化磁盘的管理系统,设计最优的磁盘方式策略,以及磁盘的寻址策略,这是在底层操作系统层面考虑的。
  3. 设计合理的磁盘存储数据块,以及访问这些数据库的策略,这是在应用层面考虑的。例如,我们可以给存放的数据设计索引,通过寻址索引来加快和减少磁盘的访问量,还可以采用异步和非阻塞的方式加快磁盘的访问速度。
  4. 应用合理的RAID策略提升磁盘I/O。

2. Web前端调优

  1. 减少网络交互的次数(多次请求合并)
  2. 减少网络传输数据量的大小(压缩)
  3. 尽量减少编码(尽量提前将字符转化为字节,或者减少从字符到字节的转化过程。)
  4. 使用浏览器缓存
  5. 减少Cookie传输
  6. 合理布局页面
  7. 使用页面压缩
  8. 延迟加载页面
  9. CSS在最上面,JS在最下面
  10. CDN
  11. 反向代理
  12. 页面静态化
  13. 异地部署

3.服务降级(自动优雅降级)

拒绝服务和关闭服务

4.幂等性设计

有些服务天然具有幂等性,比如讲用户性别设置为男性,不管设置多少次,结果都一样。但是对转账交易等操作,问题就会比较复杂,需要通过交易编号等信息进行服务调用有效性校验,只有有效的操作才能继续执行。

(注:幂等性是系统的接口对外一种承诺(而不是实现), 承诺只要调用接口成功, 外部多次调用对系统的影响是一致的. 声明为幂等的接口会认为外部调用失败是常态, 并且失败之后必然会有重试.)

5.失效转移

若数据服务器集群中任何一台服务器宕机,那么应用程序针对这台服务器的所有读写操作都需要重新路由到其他服务器,保证数据访问不会失败,这个过程叫失效转移。
失效转移包括:失效确认(心跳检测和应用程序访问失败报告)、访问转移、数据恢复。
失效转移保证当一个数据副本不可访问时,可以快速切换访问数据的其他副本,保证系统可用。

6.性能优化

根据网站分层架构,性能优化可分为:web前端性能优化、应用服务器性能优化、存储服务器性能优化。

  1. web前端性能优化
    • 浏览器访问优化:减少http请求;使用浏览器缓存;启用压缩;css放在页面最上面、javaScript放在页面最下面;减少Cookie传输
    • CDN加速
    • 反向代理
  2. 应用服务器性能优化
    • 分布式缓存(Redis等)
    • 异步操作(消息队列)
    • 使用集群(负载均衡)
    • 代码优化
  3. 存储性能优化
    • 机械硬盘vs固态硬盘
    • B+树 vs LSM树
    • RAID vs HDFS

7. 代码优化

  • 多线程(Q:怎么确保线程安全?无锁机制有哪些?)
  • 资源复用(单例模式,连接池,线程池)
  • 数据结构
  • 垃圾回收

8. 负载均衡

  • HTTP重定向负载均衡
    当用户发来请求的时候,Web服务器通过修改HTTP响应头中的Location标记来返回一个新的url,然后浏览器再继续请求这个新url,实际上就是页面重定向。通过重定向,来达到“负载均衡”的目标。例如,我们在下载PHP源码包的时候,点击下载链接时,为了解决不同国家和地域下载速度的问题,它会返回一个离我们近的下载地址。重定向的HTTP返回码是302。
    优点:比较简单。
    缺点:浏览器需要两次请求服务器才能完成一次访问,性能较差。重定向服务自身的处理能力有可能成为瓶颈,整个集群的伸缩性国模有限;使用HTTP302响应码重定向,有可能使搜索引擎判断为SEO作弊,降低搜索排名。
  • DNS域名解析负载均衡
    DNS(Domain Name System)负责域名解析的服务,域名url实际上是服务器的别名,实际映射是一个IP地址,解析过程,就是DNS完成域名到IP的映射。而一个域名是可以配置成对应多个IP的。因此,DNS也就可以作为负载均衡服务。
    事实上,大型网站总是部分使用DNS域名解析,利用域名解析作为第一级负载均衡手段,即域名解析得到的一组服务器并不是实际提供Web服务的物理服务器,而是同样提供负载均衡服务的内部服务器,这组内部负载均衡服务器再进行负载均衡,将请求分发到真是的Web服务器上。
    优点:将负载均衡的工作转交给DNS,省掉了网站管理维护负载均衡服务器的麻烦,同时许多DNS还支持基于地理位置的域名解析,即会将域名解析成举例用户地理最近的一个服务器地址,这样可以加快用户访问速度,改善性能。
    缺点:不能自由定义规则,而且变更被映射的IP或者机器故障时很麻烦,还存在DNS生效延迟的问题。而且DNS负载均衡的控制权在域名服务商那里,网站无法对其做更多改善和更强大的管理。
  • 反向代理负载均衡
    反向代理服务可以缓存资源以改善网站性能。实际上,在部署位置上,反向代理服务器处于Web服务器前面(这样才可能缓存Web相应,加速访问),这个位置也正好是负载均衡服务器的位置,所以大多数反向代理服务器同时提供负载均衡的功能,管理一组Web服务器,将请求根据负载均衡算法转发到不同的Web服务器上。Web服务器处理完成的响应也需要通过反向代理服务器返回给用户。由于web服务器不直接对外提供访问,因此Web服务器不需要使用外部ip地址,而反向代理服务器则需要配置双网卡和内部外部两套IP地址。
    优点:和反向代理服务器功能集成在一起,部署简单。
    缺点:反向代理服务器是所有请求和响应的中转站,其性能可能会成为瓶颈。
  • LVS-NAT:修改IP地址
  • LVS-TUN: 一个IP报文封装在另一个IP报文的技术。
  • LVS-DR:将数据帧的MAC地址改为选出服务器的MAC地址,再将修改后的数据帧在与服务器组的局域网上发送。

9.缓存

缓存就是将数据存放在距离计算最近的位置以加快处理速度。缓存是改善软件性能的第一手段,现在CPU越来越快的一个重要因素就是使用了更多的缓存,在复杂的软件设计中,缓存几乎无处不在。大型网站架构设计在很多方面都使用了缓存设计。

  • CDN: 及内容分发网络,部署在距离终端用户最近的网络服务商,用户的网络请求总是先到达他的网络服务商哪里,在这里缓存网站的一些静态资源(较少变化的数据),可以就近以最快速度返回给用户,如视频网站和门户网站会将用户访问量大的热点内容缓存在CDN中。
  • 反向代理:反向代理属于网站前端架构的一部分,部署在网站的前端,当用户请求到达网站的数据中心时,最先访问到的就是反向代理服务器,这里缓存网站的静态资源,无需将请求继续转发给应用服务器就能返回给用户。
  • 本地缓存:在应用服务器本地缓存着热点数据,应用程序可以在本机内存中直接访问数据,而无需访问数据库。
  • 分布式缓存:大型网站的数据量非常庞大,即使只缓存一小部分,需要的内存空间也不是单机能承受的,所以除了本地缓存,还需要分布式缓存,将数据缓存在一个专门的分布式缓存集群中,应用程序通过网络通信访问缓存数据。

使用缓存有两个前提条件,一是数据访问热点不均衡,某些数据会被更频繁的访问,这些数据应该放在缓存中;二是数据在某个时间段内有效,不会很快过期,否则缓存的数据就会因已经失效而产生脏读,影响结果的正确性。网站应用中,缓存处理可以加快数据访问速度,还可以减轻后端应用和数据存储的负载压力,这一点对网站数据库架构至关重要,网站数据库几乎都是按照有缓存的前提进行负载能力设计的。

10. 负载均衡算法

轮询 Round Robin
加强轮询 Weight Round Robin
随机 Random
加强随机 Weight Random
最少连接 Least Connections
加强最少连接
源地址散列 Hash
其他算法

  • 最快算法(Fastest):传递连接给那些响应最快的服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP 就把其从服务器队列中拿出,不参加下一次的用户请求的分配,直到其恢复正常。
  • 观察算法(Observed):连接数目和响应时间以这两项的最佳平衡为依据为新的请求选择服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP就把其从服务器队列中拿出,不参加下一次的用户请求的分配,直到其恢复正常。
  • 预测算法(Predictive):BIG-IP利用收集到的服务器当前的性能指标,进行预测分析,选择一台服务器在下一个时间片内,其性能将达到最佳的服务器相应用户的请求。(被BIG-IP 进行检测)
  • 动态性能分配算法(Dynamic Ratio-APM):BIG-IP 收集到的应用程序和应用服务器的各项性能参数,动态调整流量分配。
  • 动态服务器补充算法(Dynamic Server Act.):当主服务器群中因故障导致数量减少时,动态地将备份服务器补充至主服务器群。
  • 服务质量算法(QoS):按不同的优先级对数据流进行分配。
  • 服务类型算法(ToS): 按不同的服务类型(在Type of Field中标识)负载均衡对数据流进行分配。
  • 规则模式算法:针对不同的数据流设置导向规则,用户可自行

11. 扩展性和伸缩性的区别

扩展性:指对现有系统影响最小的情况下,系统功能可持续扩展或替身的能力。表现在系统基础设施稳定不需要经常变更,应用之间较少依赖和耦合,对需求变更可以敏捷响应。它是系统架构设计层面的开闭原则(对扩展开放,对修改关闭),架构设计考虑未来功能扩展,当系统增加新功能时,不需要对现有系统的结构和代码进行修改。

衡量网站架构扩展性好坏的主要标准就是在网站增加新的业务产品时,是否可以实现对现有产品透明无影响,不需要任何改动或者很少改动既有业务功能就可以上线新产品。不同产品之间是否很少耦合,一个产品改动对其他产品无影响,其他产品和功能不需要受牵连进行改动。

伸缩性:所谓网站的伸缩性指是不需要改变网站的软硬件设计,仅仅通过改变部署的服务器数量就可以扩大或者缩小网站的服务处理能力。

指系统能够增加(减少)自身资源规模的方式增强(减少)自己计算处理事务的能力。如果这种增减是成比例的,就被称作线性伸缩性。在网站架构中,通常指利用集群的方式增加服务器数量、提高系统的整体事务吞吐能力。

衡量架构伸缩性的主要标准就是可以用多台服务器构建集群,是否容易向集群中添加新的服务器。加入新的服务器后是否可以提供和原来服务无差别的服务、集群中的可容纳的总的服务器数量是否有限制。

12.分布式缓存的一致性hash

具体算法过程:先构造一个长度为2^32的整数环(这个环被称作一致性Hash环)根据节点名称的Hash值(其分布范围为[0,2^32 – 1])将缓存服务器阶段设置在这个Hash环上。然后根据需要缓存的数据的Key值计算得到Hash值(其分布范围也同样为[0,2^32 – 1]),然后在Hash环上顺时针查找举例这个KEY的hash值最近的缓存服务器节点,完成KEY到服务器的Hash映射查找。

优化策略:将每台物理服务器虚拟为一组虚拟缓存服务器,将虚拟服务器的Hash值放置在Hash环上,key在换上先找到虚拟服务器节点,再得到物理服务器的信息。

一台物理服务器设置多少个虚拟服务器节点合适呢?经验值:150。

13. 网络安全

  1. XSS攻击
    跨站点脚本攻击(Cross Site Script),指黑客通过篡改网页,注入恶意的HTML脚本,在用户浏览网页时,控制用户浏览器进行恶意操作的一种攻击方式。
    防范手段:消毒(XSS攻击者一般都是通过在请求中嵌入恶意脚本大道攻击的目的,这些脚本是一般用户输入中不使用的,如果进行过滤和消毒处理,即对某些html危险字符转移,如“>”转译为“& gt;”);HttpOnly(防止XSS攻击者窃取Cookie).
  2. 注入攻击:SQL注入和OS注入
    SQL防范:预编译语句PreparedStatement; ORM;避免密码明文存放;处理好相应的异常。
  3. CSRF(Cross Site Request Forgery,跨站点请求伪造)。听起来与XSS有点相似,事实上两者区别很大,XSS利用的是站内的信任用户,而CSRF则是通过伪装来自受信任用户的请求来利用受信任的网站。
    防范:httpOnly;增加token;通过Referer识别。
  4. 文件上传漏洞
  5. DDos攻击

14. 加密技术

  1. 摘要加密:MD5, SHA
  2. 对称加密:DES算法,RC算法, AES
  3. 非对称加密:RSA
    非对称加密技术通常用在信息安全传输,数字签名等场合。
    HTTPS传输中浏览器使用的数字证书实质上是经过权威机构认证的非对称加密的公钥。

15. 流控(流量控制)

  1. 流量丢弃
  2. 通过单机内存队列来进行有限的等待,直接丢弃用户请求的处理方式显得简单而粗暴,并且如果是I/O密集型应用(包括网络I/O和磁盘I/O),瓶颈一般不再CPU和内存。因此,适当的等待,既能够替身用户体验,又能够提高资源利用率。
  3. 通过分布式消息队列来将用户的请求异步化。

参考资料
1. LVS:三种负载均衡方式比较+另三种负载均衡方式
2. 《大型网站技术架构——核心原理与技术分析》李智慧 著。
3. 亿级Web系统搭建:单机到分布式集群
4. 《大型分布式网站架构设计与实现》陈康贤 著。

from:http://www.importnew.com/24198.html

分布式服务化系统一致性的“最佳实干”

1 背景

一致性是一个抽象的、具有多重含义的计算机术语,在不同应用场景下,有不同的定义和含义。在传统的IT时代,一致性通常指强一致性,强一致性通常体现在你中有我、我中有你、浑然一体;而在互联网时代,一致性的含义远远超出了它原有的含义,在我们讨论互联网时代的一致性之前,我们先了解一下互联网时代的特点,互联网时代信息量巨大、需要计算能力巨大,不但对用户响应速度要求快,而且吞吐量指标也要向外扩展(既:水平伸缩),于是单节点的服务器无法满足需求,服务节点开始池化,想想那个经典的故事,一只筷子一折就断,一把筷子怎么都折不断,可见人多力量大的思想是多么的重要,但是人多也不一定能解决所有事情,还得进行有序、合理的分配任务,进行有效的管理,于是互联网时代谈论最多的话题就是拆分,拆分一般分为“水平拆分”和“垂直拆分”(大家不要对应到数据库或者缓存拆分,这里主要表达一种逻辑)。这里,“水平拆分”指的是同一个功能由于单机节点无法满足性能需求,需要扩展成为多节点,多个节点具有一致的功能,组成一个服务池,一个节点服务一部分的请求量,团结起来共同处理大规模高并发的请求量。“垂直拆分”指的是按照功能拆分,秉着“专业的人干专业的事儿”的原则,把一个复杂的功能拆分到多个单一的简单的元功能,不同的元功能组合在一起,和未拆分前完成的功能是一致的,由于每个元功能职责单一、功能简单,让维护和变更都变得更简单、安全,更易于产品版本的迭代,在这样的一个互联网的时代和环境,一致性指分布式服务化系统之间的弱一致性,包括应用系统一致性和数据一致性。

无论是水平拆分还是垂直拆分,都解决了特定场景下的特定问题,凡事有好的一面,都会有坏的一面,拆分后的系统或者服务化的系统最大的问题就是一致性问题,这么多个具有元功能的模块,或者同一个功能池中的多个节点之间,如何保证他们的信息是一致的、工作步伐是一致的、状态是一致的、互相协调有序的工作呢?

本文根据作者在互联网企业的实际项目经验,对服务化系统中最难解决的一致性问题进行研究和探讨,试图从实践经验中找到规律,抽象出模式,分享给大家,希望对大家的项目实施有所帮助,在对实践的总结中也会对相关的一致性术语做最朴实的解释,希望能帮助大家彻底理解一致性的本质,并能将其应用到实践,解决读者现实中遇到的服务化系统的一致性问题,本文使用理论与实践相结合的方法,突出在实践中解决问题的模式,因此叫做《分布式服务化系统一致性的“最佳实干”》。

2 问题

本节列举不一致会导致的种种问题,这也包括一例生活中的问题。

案例1:买房

假如你想要享受生活的随意,只想买个两居,不想让房贷有太大压力,而你媳妇却想要买个三居,还得带花园的,那么你们就不一致了,不一致导致生活不愉快、不协调,严重情况下还会吵架,可见生活中的不一致问题影响很大。

案例2:转账

转账是经典的不一致案例,设想一下银行为你处理一笔转账,扣减你账户上的余额,然后增加别人账户的余额;如果扣减你的账户余额成功,增加别人账户余额失败,那么你就会损失这笔资金。反过来,如果扣减你的账户余额失败,增加别人账户余额成功,那么银行就会损失这笔资金,银行需要赔付。对于资金处理系统来说,上面任何一种场景都是不允许发生的,一旦发生就会有资金损失,后果是不堪设想的,严重情况会让一个公司瞬间倒闭,可参考案例

案例3:下订单和扣库存

电商系统中也有一个经典的案例,下订单和扣库存如何保持一致,如果先下订单,扣库存失败,那么将会导致超卖;如果下订单没有成功,扣库存成功,那么会导致少卖。两种情况都会导致运营成本的增加,严重情况下需要赔付。

案例4:同步超时

服务化的系统间调用常常因为网络问题导致系统间调用超时,即使是网络很好的机房,在亿次流量的基数下,同步调用超时也是家常便饭。系统A同步调用系统B超时,系统A可以明确得到超时反馈,但是无法确定系统B是否已经完成了预定的功能或者没有完成预定的功能。于是,系统A就迷茫了,不知道应该继续做什么,如何反馈给使用方。(曾经的一个B2B产品的客户要求接口超时重新通知他们,这个在技术上是难以实现的,因为服务器本身可能并不知道自己超时,可能会继续正常的返回数据,只是客户端并没有接受到结果罢了,因此这不是一个合理的解决方案)。

案例5:异步回调超时

此案例和上一个同步超时案例类似,不过这个场景使用了异步回调,系统A同步调用系统B发起指令,系统B采用受理模式,受理后则返回受理成功,然后系统B异步通知系统A。在这个过程中,如果系统A由于某种原因迟迟没有收到回调结果,那么两个系统间的状态就不一致,互相认知不同会导致系统间发生错误,严重情况下会影响核心事务,甚至会导致资金损失。

案例6:掉单

分布式系统中,两个系统协作处理一个流程,分别为对方的上下游,如果一个系统中存在一个请求,通常指订单,另外一个系统不存在,则导致掉单,掉单的后果很严重,有时候也会导致资金损失。

案例7:系统间状态不一致

这个案例与上面掉单案例类似,不同的是两个系统间都存在请求,但是请求的状态不一致。

案例8:缓存和数据库不一致

交易相关系统基本离不开关系型数据库,依赖关系型数据库提供的ACID特性(后面介绍),但是在大规模高并发的互联网系统里,一些特殊的场景对读的性能要求极高,服务于交易的数据库难以抗住大规模的读流量,通常需要在数据库前垫缓存,那么缓存和数据库之间的数据如何保持一致性?是要保持强一致呢还是弱一致性呢?

案例9:本地缓存节点间不一致

一个服务池上的多个节点为了满足较高的性能需求,需要使用本地缓存,使用了本地缓存,每个节点都会有一份缓存数据的拷贝,如果这些数据是静态的、不变的,那永远都不会有问题,但是如果这些数据是半静态的或者常被更新的,当被更新的时候,各个节点更新是有先后顺序的,在更新的瞬间,各个节点的数据是不一致的,如果这些数据是为某一个开关服务的,想象一下重复的请求走进了不同的节点(在failover或者补偿导致的场景下,重复请求是一定会发生的,也是服务化系统必须处理的),一个请求走了开关打开的逻辑,同时另外一个请求走了开关关闭的逻辑,这导致请求被处理两次,最坏的情况下会导致灾难性的后果,就是资金损失。

案例10:缓存数据结构不一致

这个案例会时有发生,某系统需要种某一数据结构的缓存,这一数据结构有多个数据元素组成,其中,某个数据元素都需要从数据库中或者服务中获取,如果一部分数据元素获取失败,由于程序处理不正确,仍然将不完全的数据结构存入缓存,那么缓存的消费者消费的时候很有可能因为没有合理处理异常情况而出错。

3 模式

3.1 生活中不一致问题的解决

大家回顾一下上一节列举的生活中的案例1-买房,如果置身事外来看,解决这种不一致的办法有两个,一个是避免不一致的发生,如果已经是媳妇了就不好办了:),还有一种方法就是慢慢的补偿,先买个两居,然后慢慢的等资金充裕了再换三居,买比特币赚了再换带花园的房子,于是问题最终被解决了,最终大家处于一致的状态,都开心了。这样可以解决案例1的问题,很自然由于有了过渡的方法,问题在不经意间就消失了,可见“过渡”也是解决一致性问题的一个模式。

从案例1的解决方案来看,我们要解决一致性问题,一个最直接最简单的方法就是保持强一致性,对于案例1的情况,尽量避免在结婚前两个人能够互相了解达成一致,避免不一致问题的发生;不过有些事情事已至此,发生了就是发生了,出现了不一致的问题,我们应该考虑去补偿,尽最大的努力从不一致状态修复到一致状态,避免损失全部或者一部分,也不失为一个好方法。

因此,避免不一致是上策,出现了不一致及时发现及时修复是中策,有问题不积极解决留给他人解决是下策。

3.2 酸碱平衡理论

ACID在英文中的意思是“酸”,BASE的意识是“碱”,这一段讲的是“酸碱平衡”的故事。

1. ACID(酸)

如何保证强一致性呢?计算机专业的童鞋在学习关系型数据库的时候都学习了ACID原理,这里对ACID做个简单的介绍。如果想全面的学习ACID原理,请参考ACID

关系型数据库天生就是解决具有复杂事务场景的问题,关系型数据库完全满足ACID的特性。

ACID指的是:

  • A: Atomicity,原子性
  • C: Consistency,一致性
  • I: Isolation,隔离性
  • D: Durability,持久性

具有ACID的特性的数据库支持强一致性,强一致性代表数据库本身不会出现不一致,每个事务是原子的,或者成功或者失败,事物间是隔离的,互相完全不影响,而且最终状态是持久落盘的,因此,数据库会从一个明确的状态到另外一个明确的状态,中间的临时状态是不会出现的,如果出现也会及时的自动的修复,因此是强一致的。

3个典型的关系型数据库Oracle、Mysql、Db2都能保证强一致性,Oracle和Mysql使用多版本控制协议实现,而DB2使用改进的两阶段提交协议来实现。

如果你在为交易相关系统做技术选型,交易的存储应该只考虑关系型数据库,对于核心系统,如果需要较好的性能,可以考虑使用更强悍的硬件,这种向上扩展(升级硬件)虽然成本较高,但是是最简单粗暴有效的方式,另外,Nosql完全不适合交易场景,Nosql主要用来做数据分析、ETL、报表、数据挖掘、推荐、日志处理等非交易场景。

前面提到的案例2-转账案例3-下订单和扣库存都可以利用关系型数据库的强一致性解决。

然而,前面提到,互联网项目多数具有大规模高并发的特性,必须应用拆分的理念,对高并发的压力采取“大而化小、小而化了”的方法,否则难以满足动辄亿级流量的需求,即使使用关系型数据库,单机也难以满足存储和TPS上的需求。为了保证案例2-转账可以利用关系型数据库的强一致性,在拆分的时候尽量的把转账相关的账户放入一个数据库分片,对于案例3,尽量的保证把订单和库存放入同一个数据库分片,这样通过关系型数据库自然就解决了不一致的问题。

然而,有些时候事与愿违,由于业务规则的限制,无法将相关的数据分到同一个数据库分片,这个时候我们就需要实现最终一致性。

对于案例2-转账场景,假设账户数量巨大,对账户存储进行了拆分,关系型数据库一共分了8个实例,每个实例8个库,每个库8个表,共512张表,假如要转账的两个账户正好落在了一个库里,那么可以依赖关系型数据库的事务保持强一致性。

如果要转账的两个账户正好落在了不同的库里,转账操作是无法封装在同一个数据库事务中的,这个时候会发生一个库的账户扣减余额成功,另外一个库的账户增加余额失败的情况。

对于这种情况,我们需要继续探讨解决之道,CAP原理和BASE原理,BASE原理通过记录事务的中间的临时状态,实现最终一致性。

2. CAP(帽子理论)

如果想深入的学习CAP理论,请参考CAP

由于对系统或者数据进行了拆分,我们的系统不再是单机系统,而是分布式系统,针对分布式系的帽子理论包含三个元素:

  • C:Consistency,一致性, 数据一致更新,所有数据变动都是同步的
  • A:Availability,可用性, 好的响应性能,完全的可用性指的是在任何故障模型下,服务都会在有限的时间处理响应
  • P:Partition tolerance,分区容错性,可靠性

帽子理论证明,任何分布式系统只可同时满足二点,没法三者兼顾。关系型数据库由于关系型数据库是单节点的,因此,不具有分区容错性,但是具有一致性和可用性,而分布式的服务化系统都需要满足分区容错性,那么我们必须在一致性和可用性中进行权衡,具体表现在服务化系统处理的异常请求在某一个时间段内可能是不完全的,但是经过自动的或者手工的补偿后,达到了最终的一致性。

3. BASE(碱)

BASE理论解决CAP理论提出了分布式系统的一致性和可用性不能兼得的问题,如果想全面的学习BASE原理,请参考Eventual consistency

BASE在英文中有“碱”的意思,对应本节开头的ACID在英文中“酸”的意思,基于这两个名词提出了酸碱平衡的结论,简单来说是在不同的场景下,可以分别利用ACID和BASE来解决分布式服务化系统的一致性问题。

BASE模型与ACID模型截然不同,满足CAP理论,通过牺牲强一致性,获得可用性,一般应用在服务化系统的应用层或者大数据处理系统,通过达到最终一致性来尽量满足业务的绝大部分需求。

BASE模型包含个三个元素:

  • BA:Basically Available,基本可用
  • S:Soft State,软状态,状态可以有一段时间不同步
  • E:Eventually Consistent,最终一致,最终数据是一致的就可以了,而不是时时保持强一致

BASE模型的软状态是实现BASE理论的方法,基本可用和最终一致是目标。按照BASE模型实现的系统,由于不保证强一致性,系统在处理请求的过程中,可以存在短暂的不一致,在短暂的不一致窗口请求处理处在临时状态中,系统在做每步操作的时候,通过记录每一个临时状态,在系统出现故障的时候,可以从这些中间状态继续未完成的请求处理或者退回到原始状态,最后达到一致的状态。

案例1-转账为例,我们把用户A给用户B转账分成四个阶段,第一个阶段用户A准备转账,第二个阶段从用户A账户扣减余额,第三个阶段对用户B增加余额,第四个阶段完成转账。系统需要记录操作过程中每一步骤的状态,一旦系统出现故障,系统能够自动发现没有完成的任务,然后,根据任务所处的状态,继续执行任务,最终完成任务,达到一致的最终状态。

在实际应用中,上面这个过程通常是通过持久化执行任务的状态和环境信息,一旦出现问题,定时任务会捞取未执行完的任务,继续未执行完的任务,直到执行完成为止,或者取消已经完成的部分操作回到原始状态。这种方法在任务完成每个阶段的时候,都要更新数据库中任务的状态,这在大规模高并发系统中不会有太好的性能,一个更好的办法是用Write-Ahead Log(写前日志),这和数据库的Bin Log(操作日志)相似,在做每一个操作步骤,都先写入日志,如果操作遇到问题而停止的时候,可以读取日志按照步骤进行恢复,并且继续执行未完成的工作,最后达到一致。写前日志可以利用机械硬盘的追加写而达到较好性能,因此,这是一种专业化的实现方式,多数业务系系统还是使用数据库记录的字段来记录任务的执行状态,也就是记录中间的“软状态”,一个任务的状态流转一般可以通过数据库的行级锁来实现,这比使用Write-Ahead Log实现更简单、更快速。

有了BASE理论作为基础,我们对复杂的分布式事务进行拆解,对其中的每一步骤都记录其状态,有问题的时候可以根据记录的状态来继续执行任务,达到最终的一致,通过这个方法我们可以解决案例2-转账案例3-下订单和扣库存中遇到的问题。

4. 酸碱平衡的总结

  1. 使用向上扩展(强悍的硬件)运行专业的关系型数据库(例如:Oracle或者DB2)能够保证强一致性,钱能解决的问题就不是问题
  2. 如果钱是问题,可以对廉价硬件运行的开源关系型数据库(例如:Mysql)进行分片,将相关的数据分到数据库的同一个片,仍然能够使用关系型数据库保证事务
  3. 如果业务规则限制,无法将相关的数据分到同一个片,就需要实现最终一致性,通过记录事务的软状态(中间状态、临时状态),一旦处于不一致,可以通过系统自动化或者人工干预来修复不一致的情况

3.3 分布式一致性协议

国际开放标准组织Open Group定义了DTS(分布式事务处理模型),模型中包含4个角色:应用程序、事务管理器、资源管理器、通信资源管理器四部分。事务处理器是统管全局的管理者,资源处理器和通信资源处理器是事务的参与者。

J2EE规范也包含此分布式事务处理模型的规范,并在所有的AppServer中进行实现,J2EE规范中定义了TX协议和XA协议,TX协议定义应用程序与事务管理器之间的接口,而XA协议定义了事务管理器与资源处理器之间的接口,在过去,大家使用AppServer,例如:Websphere、Weblogic、Jboss等配置数据源的时候会看见类似XADatasource的数据源,这就是实现了DTS的关系型数据库的数据源。企业级开发JEE中,关系型数据库、JMS服务扮演资源管理器的角色,而EJB容器则扮演事务管理器的角色。

下面我们就介绍两阶段提交协议三阶段提交协议以及阿里巴巴提出的TCC,它们都是根据DTS这一思想演变出来的。

1. 两阶段提交协议

上面描述的JEE的XA协议就是根据两阶段提交来保证事务的完整性,并实现分布式服务化的强一致性。

两阶段提交协议把分布式事务分成两个过程,一个是准备阶段,一个是提交阶段,准备阶段和提交阶段都是由事务管理器发起的,为了接下来讲解方便,我们把事务管理器称为协调者,把资管管理器称为参与者。

两阶段如下:

  1. 准备阶段:协调者向参与者发起指令,参与者评估自己的状态,如果参与者评估指令可以完成,参与者会写redo或者undo日志(这也是前面提起的Write-Ahead Log的一种),然后锁定资源,执行操作,但是并不提交
  2. 提交阶段:如果每个参与者明确返回准备成功,也就是预留资源和执行操作成功,协调者向参与者发起提交指令,参与者提交资源变更的事务,释放锁定的资源;如果任何一个参与者明确返回准备失败,也就是预留资源或者执行操作失败,协调者向参与者发起中止指令,参与者取消已经变更的事务,执行undo日志,释放锁定的资源

两阶段提交协议成功场景示意图如下:

两阶段提交协议

我们看到两阶段提交协议在准备阶段锁定资源,是一个重量级的操作,并能保证强一致性,但是实现起来复杂、成本较高,不够灵活,更重要的是它有如下致命的问题:

  1. 阻塞:从上面的描述来看,对于任何一次指令必须收到明确的响应,才会继续做下一步,否则处于阻塞状态,占用的资源被一直锁定,不会被释放
  2. 单点故障:如果协调者宕机,参与者没有了协调者指挥,会一直阻塞,尽管可以通过选举新的协调者替代原有协调者,但是如果之前协调者在发送一个提交指令后宕机,而提交指令仅仅被一个参与者接受,并且参与者接收后也宕机,新上任的协调者无法处理这种情况
  3. 脑裂:协调者发送提交指令,有的参与者接收到执行了事务,有的参与者没有接收到事务,就没有执行事务,多个参与者之间是不一致的

上面所有的这些问题,都是需要人工干预处理,没有自动化的解决方案,因此两阶段提交协议在正常情况下能保证系统的强一致性,但是在出现异常情况下,当前处理的操作处于错误状态,需要管理员人工干预解决,因此可用性不够好,这也符合CAP协议的一致性和可用性不能兼得的原理。

2. 三阶段提交协议

三阶段提交协议是两阶段提交协议的改进版本。它通过超时机制解决了阻塞的问题,并且把两个阶段增加为三个阶段:

  1. 询问阶段:协调者询问参与者是否可以完成指令,协调者只需要回答是还是不是,而不需要做真正的操作,这个阶段超时导致中止
  2. 准备阶段:如果在询问阶段所有的参与者都返回可以执行操作,协调者向参与者发送预执行请求,然后参与者写redo和undo日志,执行操作,但是不提交操作;如果在询问阶段任何参与者返回不能执行操作的结果,则协调者向参与者发送中止请求,这里的逻辑与两阶段提交协议的的准备阶段是相似的,这个阶段超时导致成功
  3. 提交阶段:如果每个参与者在准备阶段返回准备成功,也就是预留资源和执行操作成功,协调者向参与者发起提交指令,参与者提交资源变更的事务,释放锁定的资源;如果任何一个参与者返回准备失败,也就是预留资源或者执行操作失败,协调者向参与者发起中止指令,参与者取消已经变更的事务,执行undo日志,释放锁定的资源,这里的逻辑与两阶段提交协议的提交阶段一致

三阶段提交协议成功场景示意图如下:

三阶段提交协议

然而,这里与两阶段提交协议有两个主要的不同:

  1. 增加了一个询问阶段,询问阶段可以确保尽可能早的发现无法执行操作而需要中止的行为,但是它并不能发现所有的这种行为,只会减少这种情况的发生
  2. 在准备阶段以后,协调者和参与者执行的任务中都增加了超时,一旦超时,协调者和参与者都继续提交事务,默认为成功,这也是根据概率统计上超时后默认成功的正确性最大

三阶段提交协议与两阶段提交协议相比,具有如上的优点,但是一旦发生超时,系统仍然会发生不一致,只不过这种情况很少见罢了,好处就是至少不会阻塞和永远锁定资源。

3. TCC

上面两节讲解了两阶段提交协议和三阶段提交协议,实际上他们能解决案例2-转账案例3-下订单和扣库存中的分布式事务的问题,但是遇到极端情况,系统会发生阻塞或者不一致的问题,需要运营或者技术人工解决。无论两阶段还是三阶段方案中都包含多个参与者、多个阶段实现一个事务,实现复杂,性能也是一个很大的问题,因此,在互联网高并发系统中,鲜有使用两阶段提交和三阶段提交协议的场景。

阿里巴巴提出了新的TCC协议,TCC协议将一个任务拆分成Try、Confirm、Cancel,正常的流程会先执行Try,如果执行没有问题,再执行Confirm,如果执行过程中出了问题,则执行操作的逆操Cancel,从正常的流程上讲,这仍然是一个两阶段的提交协议,但是,在执行出现问题的时候,有一定的自我修复能力,如果任何一个参与者出现了问题,协调者通过执行操作的逆操作来取消之前的操作,达到最终的一致状态。

可以看出,从时序上,如果遇到极端情况下TCC会有很多问题的,例如,如果在Cancel的时候一些参与者收到指令,而一些参与者没有收到指令,整个系统仍然是不一致的,这种复杂的情况,系统首先会通过补偿的方式,尝试自动修复的,如果系统无法修复,必须由人工参与解决。

从TCC的逻辑上看,可以说TCC是简化版的三阶段提交协议,解决了两阶段提交协议的阻塞问题,但是没有解决极端情况下会出现不一致和脑裂的问题。然而,TCC通过自动化补偿手段,会把需要人工处理的不一致情况降到到最少,也是一种非常有用的解决方案,根据线人,阿里在内部的一些中间件上实现了TCC模式。

我们给出一个使用TCC的实际案例,在秒杀的场景,用户发起下单请求,应用层先查询库存,确认商品库存还有余量,则锁定库存,此时订单状态为待支付,然后指引用户去支付,由于某种原因用户支付失败,或者支付超时,系统会自动将锁定的库存解锁供其他用户秒杀。

TCC协议使用场景示意图如下:

TCC

总结一下,两阶段提交协议、三阶段提交协议、TCC协议都能保证分布式事务的一致性,他们保证的分布式系统的一致性从强到弱,TCC达到的目标是最终一致性,其中任何一种方法都可以不同程度的解决案例2:转账、案例3:下订单和扣库存的问题,只是实现的一致性的级别不一样而已,对于案例4:同步超时可以通过TCC的理念解决,如果同步调用超时,调用方可以使用fastfail策略,返回调用方的使用方失败的结果,同时调用服务的逆向cancel操作,保证服务的最终一致性。

3.4 保证最终一致性的模式

在大规模高并发服务化系统中,一个功能被拆分成多个具有单一功能的元功能,一个流程会有多个系统的多个元功能组合实现,如果使用两阶段提交协议和三阶段提交协议,确实能解决系统间一致性问题,除了这两个协议带来的自身的问题,这些协议的实现比较复杂、成本比较高,最重要的是性能并不好,相比来看,TCC协议更简单、容易实现,但是TCC协议由于每个事务都需要执行Try,再执行Confirm,略微显得臃肿,因此,在现实的系统中,底线要求仅仅需要能达到最终一致性,而不需要实现专业的、复杂的一致性协议,实现最终一致性有一些非常有效的、简单粗暴的模式,下面就介绍这些模式及其应用场景。

1. 查询模式

任何一个服务操作都需要提供一个查询接口,用来向外部输出操作执行的状态。服务操作的使用方可以通过查询接口,得知服务操作执行的状态,然后根据不同状态来做不同的处理操作。

为了能够实现查询,每个服务操作都需要有唯一的流水号标识,也可使用此次服务操作对应的资源ID来标志,例如:请求流水号、订单号等。

首先,单笔查询操作是必须提供的,我们也鼓励使用单笔订单查询,这是因为每次调用需要占用的负载是可控的,批量查询则根据需要来提供,如果使用了批量查询,需要有合理的分页机制,并且必须限制分页的大小,以及对批量查询的QPS需要有容量评估和流控等。

查询模式的示意图如下:

查询模式

对于案例4:同步超时、案例5:异步回调超时、案例6:掉单、案例7:系统间状态不一致,我们都需要使用查询模式来了解被调用服务的处理情况,来决定下一步做什么:补偿未完成的操作还是回滚已经完成的操作。

2. 补偿模式

有了上面的查询模式,在任何情况下,我们都能得知具体的操作所处的状态,如果整个操作处于不正常的状态,我们需要修正操作中有问题的子操作,这可能需要重新执行未完成的子操作,后者取消已经完成的子操作,通过修复使整个分布式系统达到一致,为了让系统最终一致而做的努力都叫做补偿。

对于服务化系统中同步调用的操作,业务操作发起的主动方在还没有得到业务操作执行方的明确返回或者调用超时,场景可参考案例4:同步超时,这个时候业务发起的主动方需要及时的调用业务执行方获得操作执行的状态,这里使用查询模式,获得业务操作的执行方的状态后,如果业务执行方已经完预设的工作,则业务发起方给业务的使用方返回成功,如果业务操作的执行方的状态为失败或者未知,则会立即告诉业务的使用方失败,然后调用业务操作的逆向操作,保证操作不被执行或者回滚已经执行的操作,让业务的使用方、业务发起的主动方、业务的操作方最终达成一致的状态。

补偿模式的示意图如下:

补偿模式

补偿操作根据发起形式分为:

  1. 自动恢复:程序根据发生不一致的环境,通过继续未完成的操作,或者回滚已经完成的操作,自动来达到一致
  2. 通知运营:如果程序无法自动恢复,并且设计时考虑到了不一致的场景,可以提供运营功能,通过运营手工进行补偿
  3. 通知技术:如果很不巧,系统无法自动回复,又没有运营功能,那必须通过技术手段来解决,技术手段包括走数据库变更或者代码变更来解决,这是最糟的一种场景

3. 异步确保模式

异步确保模式是补偿模式的一个典型案例,经常应用到使用方对响应时间要求并不太高,我们通常把这类操作从主流程中摘除,通过异步的方式进行处理,处理后把结果通过通知系统通知给使用方,这个方案最大的好处能够对高并发流量进行消峰,例如:电商系统中的物流、配送,以及支付系统中的计费、入账等。

实践中,将要执行的异步操作封装后持久入库,然后通过定时捞取未完成的任务进行补偿操作来实现异步确保模式,只要定时系统足够健壮,任何一个任务最终会被成功执行。

异步确保模式的示意图如下:

异步确保模式

对于案例5:异步回调超时,使用的就是异步确保模式,这种情况下对于某个操作,如果迟迟没有收到响应,我们通过查询模式和补偿模式来继续未完成的操作。

4. 定期校对模式

既然我们在系统中实现最终一致性,系统在没有达到一致之前,系统间的状态是不一致的,甚至是混乱的,需要补偿操作来达到一致的目的,但是我们如何来发现需要补偿的操作呢?

在操作的主流程中的系统间执行校对操作,我们可以事后异步的批量校对操作的状态,如果发现不一致的操作,则进行补偿,补偿操作与补偿模式中的补偿操作是一致的。

另外,实现定期校对的一个关键就是分布式系统中需要有一个自始至终唯一的ID,ID的生成请参考SnowFlake

在分布式系统中,全局唯一ID的示意图如下:

唯一ID

一般情况下,生成全局唯一ID有两种方法:

  1. 持久型:使用数据库表自增字段或者Sequence生成,为了提高效率,每个应用节点可以缓存一批次的ID,如果机器重启可能会损失一部分ID,但是这并不会产生任何问题
  2. 时间型:一般由机器号、业务号、时间、单节点内自增ID组成,由于时间一般精确到秒或者毫秒,因此不需要持久就能保证在分布式系统中全局唯一、粗略递增能特点

实践中,为了能在分布式系统中迅速的定位问题,一般的分布式系统都有技术支持系统,它能够跟踪一个请求的调用链,调用链是在二维的维度跟踪一个调用请求,最后形成一个调用树,原理可参考谷歌的论文Dapper, a Large-Scale Distributed Systems Tracing Infrastructure,一个开源的参考实现为pinpoint

在分布式系统中,调用链的示意图如下:

调用链

全局的唯一流水ID可以把一个请求在分布式系统中的流转的路径聚合,而调用链中的spanid可以把聚合的请求路径通过树形结构进行展示,让技术支持人员轻松的发现系统出现的问题,能够快速定位出现问题的服务节点,提高应急效率。

关于订单跟踪、调用链跟踪、业务链跟踪,我们会在后续文章中详细介绍。

在分布式系统中构建了唯一ID,调用链等基础设施,我们很容易对系统间的不一致进行核对,通常我们需要构建第三方的定期核对系统,以第三方的角度来监控服务执行的健康程度。

定期核对系统示意图如下:

定期核对模式

对于案例6:掉单、案例7:系统间状态不一致通常通过定期校对模式发现问题,并通过补偿模式来修复,最后完成系统间的最终一致性。

定期校对模式多应用在金融系统,金融系统由于涉及到资金安全,需要保证百分之百的准确性,所以,需要多重的一致性保证机制,包括:系统间的一致性对账、现金对账、账务对账、手续费对账等等,这些都属于定期校对模式,顺便说一下,金融系统与社交应用在技术上本质的区别在于社交应用在于量大,而金融系统在于数据的准确性。

到现在为止,我们看到通过查询模式、补偿模式、定期核对模式可以解决案例4到案例7的所有问题,对于案例4:同步超时,如果同步超时,我们需要查询状态进行补偿,对于案例5:异步回调超时,如果迟迟没有收到回调响应,我们也会通过查询状态进行补偿,对于案例6:掉单、案例7:系统间状态不一致,我们通过定期核对模式可以保证系统间操作的一致性,避免掉单和状态不一致导致问题。

5. 可靠消息模式

在分布式系统中,对于主流程中优先级比较低的操作,大多采用异步的方式执行,也就是前面提到的异步确保型,为了让异步操作的调用方和被调用方充分的解耦,也由于专业的消息队列本身具有可伸缩、可分片、可持久等功能,我们通常通过消息队列实现异步化,对于消息队列,我们需要建立特殊的设施保证可靠的消息发送以及处理机的幂等等。

消息的可靠发送

消息的可靠发送可以认为是尽最大努力发送消息通知,有两种实现方法:

第一种,发送消息之前,把消息持久到数据库,状态标记为待发送,然后发送消息,如果发送成功,将消息改为发送成功。定时任务定时从数据库捞取一定时间内未发送的消息,将消息发送。

消息发送模式1

第二种,实现方式与第一种类似,不同的是持久消息的数据库是独立的,并不耦合在业务系统中。发送消息之前,先发送一个预消息给某一个第三方的消息管理器,消息管理器将其持久到数据库,并标记状态为待发送,发送成功后,标记消息为发送成功。定时任务定时从数据库捞取一定时间内未发送的消息,回查业务系统是否要继续发送,根据查询结果来确定消息的状态。

消息发送模式2

一些公司把消息的可靠发送实现在了中间件里,通过Spring的注入,在消息发送的时候自动持久消息记录,如果有消息记录没有发送成功,定时会补偿发送。

消息处理器的幂等性

如果我们要保证消息可靠的发送,简单来说,要保证消息一定要发送出去,那么就需要有重试机制,有了重试机制,消息一定会重复,那么我们需要对重复做处理。

处理重复的最佳方式为保证操作的幂等性,幂等性的数学公式为:

f(f(x)) = f(x)

保证操作的幂等性常用的几个方法:

  1. 使用数据库表的唯一键进行滤重,拒绝重复的请求
  2. 使用分布式表对请求进行滤重
  3. 使用状态流转的方向性来滤重,通常使用行级锁来实现(后续在锁相关的文章中详细说明)
  4. 根据业务的特点,操作本身就是幂等的,例如:删除一个资源、增加一个资源、获得一个资源等

6. 缓存一致性模型

大规模高并发系统中一个常见的核心需求就是亿级的读需求,显然,关系型数据库并不是解决高并发读需求的最佳方案,互联网的经典做法就是使用缓存抗读需求,下面有一些使用缓存的保证一致性的最佳实践:

  1. 如果性能要求不是非常的高,尽量使用分布式缓存,而不要使用本地缓存
  2. 种缓存的时候一定种完全,如果缓存数据的一部分有效,一部分无效,宁可放弃种缓存,也不要把部分数据种入缓存
  3. 数据库与缓存只需要保持弱一致性,而不需要强一致性,读的顺序要先缓存,后数据库,写的顺序要先数据库,后缓存

这里的最佳实践能够解决案例8:缓存和数据库不一致、案例9:本地缓存节点间不一致、案例10:缓存数据结构不一致的问题,对于数据存储层、缓存与数据库、Nosql等的一致性是更深入的存储一致性技术,将会在后续文章单独介绍,这里的数据一致性主要是处理应用层与缓存、应用层与数据库、一部分的缓存与数据库的一致性。

3.5 专题模式

这一节介绍特殊场景下的一致性问题和解决方案。

迁移开关的设计

在大多数企业里,新项目和老项目一般会共存,大家都在努力的下掉老项目,但是由于种种原因总是下不掉,如果要彻底的下掉老项目,就必须要有非常完善的迁移方案,迁移是一项非常复杂而艰巨的任务,我会在将来的文章中详细探讨迁移方案、流程和技术,这里我们只对迁移中使用的开关进行描述。

迁移过程必须使用开关,开关一般都会基于多个维度来设计,例如:全局的、用户的、角色的、商户的、产品的等等,如果迁移过程中遇到问题,我们需要关闭开关,迁移回老的系统,这需要我们的新系统兼容老的数据,老的系统也兼容新的数据,从某种意义上来讲,迁移比实现新系统更加困难。

曾经看过很多简单的开关设计,有的开关设计在应用层次,通过一个curl语句调用,没有权限控制,这样的开关在服务池的每个节点都是不同步的、不一致的;还有的系统把开关配置放在中心化的配置系统、数据库或者缓存等,处理的每个请求都通过统一的开关来判断是否迁移等等,这样的开关有一个致命的缺点,服务请求在处理过程中,开关可能会变化,各个节点之间开关可能不同步、不一致,导致重复的请求可能走到新的逻辑又走了老的逻辑,如果新的逻辑和老的逻辑没有保证幂等性,这个请求就被重复处理了,如果是金融行业的应用,可能会导致资金损失,电商系统可能会导致发货并退款等问题。

这里面我们推荐使用订单开关,不管我们在什么维度上设计了开关,接收到服务请求后,我们在请求创建的关联实体(例如:订单)上标记开关,以后的任何处理流程,包括同步的和异步的处理流程,都通过订单上的开关来判断,而不是通过全局的或者基于配置的开关,这样在订单创建的时候,开关已经确定,不再变更,一旦一份数据不再发生变化,那么它永远是线程安全的,并且不会有不一致的问题。

这个模式在生产中使用比较频繁,建议每个企业都把这个模式作为设计评审的一项,如果不检查这一项,很多开发童鞋都会偷懒,直接在配置中或者数据库中做个开关就上线了。

4 总结

本文从一致性问题的实践出发,从大规模高并发服务化系统的实践经验中进行总结,列举导致不一致的具体问题,围绕着具体问题,总结出解决不一致的方法,并且抽象成模式,供大家在开发服务化系统的过程中参考。

另外,由于篇幅有限,还有一些关于分布式一致性的技术无法在一篇文章中与大家分享,包括:paxos算法、raft算法、zab算法、nwr算法、一致性哈希等,我会在后续文章中详细介绍。

5 反馈与建议

from:http://www.jianshu.com/p/1156151e20c8

当你在浏览器中输入 google.com 并且按下回车之后发生了什么?

这个仓库试图回答一个古老的面试问题:当你在浏览器中输入 google.com 并且按下回车之后发生了什么?

不过我们不再局限于平常的回答,而是想办法回答地尽可能具体,不遗漏任何细节。

这将是一个协作的过程,所以深入挖掘吧,并且帮助我们一起完善它。仍然有大量的细节等待着你来添加,欢迎向我们发送 Pull Requset!

这些内容使用 Creative Commons Zero 协议发布。

目录

按下”g”键

接下来的内容介绍了物理键盘和系统中断的工作原理,但是有一部分内容却没有涉及。当你按下“g”键,浏览器接收到这个消息之后,会触发自动完成机制。浏览器根据自己的算法,以及你是否处于隐私浏览模式,会在浏览器的地址框下方给出输入建议。大部分算法会优先考虑根据你的搜索历史和书签等内容给出建议。你打算输入 “google.com”,因此给出的建议并不匹配。但是输入过程中仍然有大量的代码在后台运行,你的每一次按键都会使得给出的建议更加准确。甚至有可能在你输入之前,浏览器就将 “google.com” 建议给你。

回车键按下

为了从零开始,我们选择键盘上的回车键被按到最低处作为起点。在这个时刻,一个专用于回车键的电流回路被直接地或者通过电容器间接地闭合了,使得少量的电流进入了键盘的逻辑电路系统。这个系统会扫描每个键的状态,对于按键开关的电位弹跳变化进行噪音消除(debounce),并将其转化为键盘码值。在这里,回车的码值是13。键盘控制器在得到码值之后,将其编码,用于之后的传输。现在这个传输过程几乎都是通过通用串行总线(USB)或者蓝牙(Bluetooth)来进行的,以前是通过PS/2或者ADB连接进行。

USB键盘:

  • 键盘的USB元件通过计算机上的USB接口与USB控制器相连接,USB接口中的第一号针为它提供了5V的电压
  • 键码值存储在键盘内部电路一个叫做”endpoint”的寄存器内
  • USB控制器大概每隔10ms便查询一次”endpoint”以得到存储的键码值数据,这个最短时间间隔由键盘提供
  • 键值码值通过USB串行接口引擎被转换成一个或者多个遵循低层USB协议的USB数据包
  • 这些数据包通过D+针或者D-针(中间的两个针),以最高1.5Mb/s的速度从键盘传输至计算机。速度限制是因为人机交互设备总是被声明成”低速设备”(USB 2.0 compliance)
  • 这个串行信号在计算机的USB控制器处被解码,然后被人机交互设备通用键盘驱动进行进一步解释。之后按键的码值被传输到操作系统的硬件抽象层

虚拟键盘(触屏设备):

  • 在现代电容屏上,当用户把手指放在屏幕上时,一小部分电流从传导层的静电域经过手指传导,形成了一个回路,使得屏幕上触控的那一点电压下降,屏幕控制器产生一个中断,报告这次“点击”的坐标
  • 然后移动操作系统通知当前活跃的应用,有一个点击事件发生在它的某个GUI部件上了,现在这个部件是虚拟键盘的按钮
  • 虚拟键盘引发一个软中断,返回给OS一个“按键按下”消息
  • 这个消息又返回来向当前活跃的应用通知一个“按键按下”事件

产生中断[非USB键盘]

键盘在它的中断请求线(IRQ)上发送信号,信号会被中断控制器映射到一个中断向量,实际上就是一个整型数 。CPU使用中断描述符表(IDT)把中断向量映射到对应函数,这些函数被称为中断处理器,它们由操作系统内核提供。当一个中断到达时,CPU根据IDT和中断向量索引到对应的中断处理器,然后操作系统内核出场了。

(Windows)一个 WM_KEYDOWN 消息被发往应用程序

HID把键盘按下的事件传送给 KBDHID.sys 驱动,把HID的信号转换成一个扫描码(Scancode),这里回车的扫描码是 VK_RETURN(0x0d)KBDHID.sys 驱动和 KBDCLASS.sys (键盘类驱动,keyboard class driver)进行交互,这个驱动负责安全地处理所有键盘和小键盘的输入事件。之后它又去调用 Win32K.sys ,在这之前有可能把消息传递给安装的第三方键盘过滤器。这些都是发生在内核模式。

Win32K.sys 通过 GetForegroundWindow() API函数找到当前哪个窗口是活跃的。这个API函数提供了当前浏览器的地址栏的句柄。Windows系统的”message pump”机制调用 SendMessage(hWnd, WM_KEYDOWN, VK_RETURN, lParam) 函数, lParam 是一个用来指示这个按键的更多信息的掩码,这些信息包括按键重复次数(这里是0),实际扫描码(可能依赖于OEM厂商,不过通常不会是 VK_RETURN ),功能键(alt, shift, ctrl)是否被按下(在这里没有),以及一些其他状态。

Windows的 SendMessage API直接将消息添加到特定窗口句柄 hWnd 的消息队列中,之后赋给 hWnd 的主要消息处理函数 WindowProc 将会被调用,用于处理队列中的消息。

当前活跃的句柄 hWnd 实际上是一个edit control控件,这种情况下,WindowProc 有一个用于处理 WM_KEYDOWN 消息的处理器,这段代码会查看 SendMessage 传入的第三个参数 wParam ,因为这个参数是 VK_RETURN ,于是它知道用户按下了回车键。

(Mac OS X)一个 KeyDown NSEvent被发往应用程序

中断信号引发了I/O Kit Kext键盘驱动的中断处理事件,驱动把信号翻译成键码值,然后传给OS X的 WindowServer 进程。然后, WindowServer 将这个事件通过Mach端口分发给合适的(活跃的,或者正在监听的)应用程序,这个信号会被放到应用程序的消息队列里。队列中的消息可以被拥有足够高权限的线程使用 mach_ipc_dispatch 函数读取到。这个过程通常是由 NSApplication 主事件循环产生并且处理的,通过 NSEventTypeKeyDownNSEvent

(GNU/Linux)Xorg 服务器监听键码值

当使用图形化的 X Server 时,X Server 会按照特定的规则把键码值再一次映射,映射成扫描码。当这个映射过程完成之后, X Server 把这个按键字符发送给窗口管理器(DWM,metacity, i3等等),窗口管理器再把字符发送给当前窗口。当前窗口使用有关图形API把文字打印在输入框内。

解析URL

  • 浏览器通过 URL 能够知道下面的信息:
    • Protocol “http”
      使用HTTP协议
    • Resource “/”
      请求的资源是主页(index)

输入的是 URL 还是搜索的关键字?

当协议或主机名不合法时,浏览器会将地址栏中输入的文字传给默认的搜索引擎。大部分情况下,在把文字传递给搜索引擎的时候,URL会带有特定的一串字符,用来告诉搜索引擎这次搜索来自这个特定浏览器。

转换非 ASCII 的 Unicode 字符

  • 浏览器检查输入是否含有不是 a-zA-Z0-9- 或者 . 的字符
  • 这里主机名是 google.com ,所以没有非ASCII的字符;如果有的话,浏览器会对主机名部分使用 Punycode 编码

检查 HSTS 列表···

  • 浏览器检查自带的“预加载 HSTS(HTTP严格传输安全)”列表,这个列表里包含了那些请求浏览器只使用HTTPS进行连接的网站
  • 如果网站在这个列表里,浏览器会使用 HTTPS 而不是 HTTP 协议,否则,最初的请求会使用HTTP协议发送
  • 注意,一个网站哪怕不在 HSTS 列表里,也可以要求浏览器对自己使用 HSTS 政策进行访问。浏览器向网站发出第一个 HTTP 请求之后,网站会返回浏览器一个响应,请求浏览器只使用 HTTPS 发送请求。然而,就是这第一个 HTTP 请求,却可能会使用户收到 downgrade attack 的威胁,这也是为什么现代浏览器都预置了 HSTS 列表。

DNS 查询···

  • 浏览器检查域名是否在缓存当中(要查看 Chrome 当中的缓存, 打开 chrome://net-internals/#dns)。
  • 如果缓存中没有,就去调用 gethostbyname 库函数(操作系统不同函数也不同)进行查询。
  • gethostbyname 函数在试图进行DNS解析之前首先检查域名是否在本地 Hosts 里,Hosts 的位置 不同的操作系统有所不同
  • 如果 gethostbyname 没有这个域名的缓存记录,也没有在 hosts 里找到,它将会向 DNS 服务器发送一条 DNS 查询请求。DNS 服务器是由网络通信栈提供的,通常是本地路由器或者 ISP 的缓存 DNS 服务器。
  • 查询本地 DNS 服务器
  • 如果 DNS 服务器和我们的主机在同一个子网内,系统会按照下面的 ARP 过程对 DNS 服务器进行 ARP查询
  • 如果 DNS 服务器和我们的主机在不同的子网,系统会按照下面的 ARP 过程对默认网关进行查询

ARP 过程

要想发送 ARP(地址解析协议)广播,我们需要有一个目标 IP 地址,同时还需要知道用于发送 ARP 广播的接口的 MAC 地址。

  • 首先查询 ARP 缓存,如果缓存命中,我们返回结果:目标 IP = MAC

如果缓存没有命中:

  • 查看路由表,看看目标 IP 地址是不是在本地路由表中的某个子网内。是的话,使用跟那个子网相连的接口,否则使用与默认网关相连的接口。
  • 查询选择的网络接口的 MAC 地址
  • 我们发送一个二层( OSI 模型 中的数据链路层)ARP 请求:

ARP Request:

Sender MAC: interface:mac:address:here
Sender IP: interface.ip.goes.here
Target MAC: FF:FF:FF:FF:FF:FF (Broadcast)
Target IP: target.ip.goes.here

根据连接主机和路由器的硬件类型不同,可以分为以下几种情况:

直连:

  • 如果我们和路由器是直接连接的,路由器会返回一个 ARP Reply (见下面)。

集线器:

  • 如果我们连接到一个集线器,集线器会把 ARP 请求向所有其它端口广播,如果路由器也“连接”在其中,它会返回一个 ARP Reply

交换机:

  • 如果我们连接到了一个交换机,交换机会检查本地 CAM/MAC 表,看看哪个端口有我们要找的那个 MAC 地址,如果没有找到,交换机会向所有其它端口广播这个 ARP 请求。
  • 如果交换机的 MAC/CAM 表中有对应的条目,交换机会向有我们想要查询的 MAC 地址的那个端口发送 ARP 请求
  • 如果路由器也“连接”在其中,它会返回一个 ARP Reply

ARP Reply:

Sender MAC: target:mac:address:here
Sender IP: target.ip.goes.here
Target MAC: interface:mac:address:here
Target IP: interface.ip.goes.here

现在我们有了 DNS 服务器或者默认网关的 IP 地址,我们可以继续 DNS 请求了:

  • 使用 53 端口向 DNS 服务器发送 UDP 请求包,如果响应包太大,会使用 TCP 协议
  • 如果本地/ISP DNS 服务器没有找到结果,它会发送一个递归查询请求,一层一层向高层 DNS 服务器做查询,直到查询到起始授权机构,如果找到会把结果返回

使用套接字

当浏览器得到了目标服务器的 IP 地址,以及 URL 中给出来端口号(http 协议默认端口号是 80, https 默认端口号是 443),它会调用系统库函数 socket ,请求一个 TCP流套接字,对应的参数是 AF_INET/AF_INET6SOCK_STREAM

  • 这个请求首先被交给传输层,在传输层请求被封装成 TCP segment。目标端口会被加入头部,源端口会在系统内核的动态端口范围内选取(Linux下是ip_local_port_range)
  • TCP segment 被送往网络层,网络层会在其中再加入一个 IP 头部,里面包含了目标服务器的IP地址以及本机的IP地址,把它封装成一个TCP packet。
  • 这个 TCP packet 接下来会进入链路层,链路层会在封包中加入 frame头 部,里面包含了本地内置网卡的MAC地址以及网关(本地路由器)的 MAC 地址。像前面说的一样,如果内核不知道网关的 MAC 地址,它必须进行 ARP 广播来查询其地址。

到了现在,TCP 封包已经准备好了,可以使用下面的方式进行传输:

对于大部分家庭网络和小型企业网络来说,封包会从本地计算机出发,经过本地网络,再通过调制解调器把数字信号转换成模拟信号,使其适于在电话线路,有线电视光缆和无线电话线路上传输。在传输线路的另一端,是另外一个调制解调器,它把模拟信号转换回数字信号,交由下一个 网络节点 处理。节点的目标地址和源地址将在后面讨论。

大型企业和比较新的住宅通常使用光纤或直接以太网连接,这种情况下信号一直是数字的,会被直接传到下一个 网络节点 进行处理。

最终封包会到达管理本地子网的路由器。在那里出发,它会继续经过自治区域的边界路由器,其他自治区域,最终到达目标服务器。一路上经过的这些路由器会从IP数据报头部里提取出目标地址,并将封包正确地路由到下一个目的地。IP数据报头部TTL域的值每经过一个路由器就减1,如果封包的TTL变为0,或者路由器由于网络拥堵等原因封包队列满了,那么这个包会被路由器丢弃。

上面的发送和接受过程在 TCP 连接期间会发生很多次:

  • 客户端选择一个初始序列号(ISN),将设置了 SYN 位的封包发送给服务器端,表明自己要建立连接并设置了初始序列号
  • 服务器端接收到 SYN 包,如果它可以建立连接:
    • 服务器端选择它自己的初始序列号
    • 服务器端设置 SYN 位,表明自己选择了一个初始序列号
    • 服务器端把 (客户端ISN + 1) 复制到 ACK 域,并且设置 ACK 位,表明自己接收到了客户端的第一个封包
  • 客户端通过发送下面一个封包来确认这次连接:
    • 自己的序列号+1
    • 接收端 ACK+1
    • 设置 ACK 位
  • 数据通过下面的方式传输:
    • 当一方发送了N个 Bytes 的数据之后,将自己的 SEQ 序列号也增加N
    • 另一方确认接收到这个数据包(或者一系列数据包)之后,它发送一个 ACK 包,ACK 的值设置为接收到的数据包的最后一个序列号
  • 关闭连接时:
    • 要关闭连接的一方发送一个 FIN 包
    • 另一方确认这个 FIN 包,并且发送自己的 FIN 包
    • 要关闭的一方使用 ACK 包来确认接收到了 FIN

UDP 数据包

TLS 握手

  • 客户端发送一个 Client hello 消息到服务器端,消息中同时包含了它的TLS版本,可用的加密算法和压缩算法。
  • 服务器端向客户端返回一个 Server hello 消息,消息中包含了服务器端的TLS版本,服务器选择了哪个加密和压缩算法,以及服务器的公开证书,证书中包含了公钥。客户端会使用这个公钥加密接下来的握手过程,直到协商生成一个新的对称密钥
  • 客户端根据自己的信任CA列表,验证服务器端的证书是否有效。如果有效,客户端会生成一串伪随机数,使用服务器的公钥加密它。这串随机数会被用于生成新的对称密钥
  • 服务器端使用自己的私钥解密上面提到的随机数,然后使用这串随机数生成自己的对称主密钥
  • 客户端发送一个 Finished 消息给服务器端,使用对称密钥加密这次通讯的一个散列值
  • 服务器端生成自己的 hash 值,然后解密客户端发送来的信息,检查这两个值是否对应。如果对应,就向客户端发送一个 Finished 消息,也使用协商好的对称密钥加密
  • 从现在开始,接下来整个 TLS 会话都使用对称秘钥进行加密,传输应用层(HTTP)内容

TCP 数据包

HTTP 协议···

如果浏览器是 Google 出品的,它不会使用 HTTP 协议来获取页面信息,而是会与服务器端发送请求,商讨使用 SPDY 协议。

如果浏览器使用 HTTP 协议,它会向服务器发送这样的一个请求:

GET / HTTP/1.1
Host: google.com
[其他头部]

“其他头部”包含了一系列的由冒号分割开的键值对,它们的格式符合HTTP协议标准,它们之间由一个换行符分割开来。这里我们假设浏览器没有违反HTTP协议标准的bug,同时浏览器使用 HTTP/1.1 协议,不然的话头部可能不包含 Host 字段,同时 GET 请求中的版本号会变成 HTTP/1.0 或者 HTTP/0.9

HTTP/1.1 定义了“关闭连接”的选项 “close”,发送者使用这个选项指示这次连接在响应结束之后会断开:

Connection:close

不支持持久连接的 HTTP/1.1 必须在每条消息中都包含 “close” 选项。

在发送完这些请求和头部之后,浏览器发送一个换行符,表示要发送的内容已经结束了。

服务器端返回一个响应码,指示这次请求的状态,响应的形式是这样的:

200 OK
[响应头部]

然后是一个换行,接下来有效载荷(payload),也就是 www.google.com 的HTML内容。服务器下面可能会关闭连接,如果客户端请求保持连接的话,服务器端会保持连接打开,以供以后的请求重用。

如果浏览器发送的HTTP头部包含了足够多的信息(例如包含了 Etag 头部,以至于服务器可以判断出,浏览器缓存的文件版本自从上次获取之后没有再更改过,服务器可能会返回这样的响应:

304 Not Modified
[响应头部]

这个响应没有有效载荷,浏览器会从自己的缓存中取出想要的内容。

在解析完 HTML 之后,浏览器和客户端会重复上面的过程,直到HTML页面引入的所有资源(图片,CSS,favicon.ico等等)全部都获取完毕,区别只是头部的 GET / HTTP/1.1 会变成 GET /$(相对www.google.com的URL) HTTP/1.1

如果HTML引入了 www.google.com 域名之外的资源,浏览器会回到上面解析域名那一步,按照下面的步骤往下一步一步执行,请求中的 Host 头部会变成另外的域名。

HTTP 服务器请求处理

HTTPD(HTTP Daemon)在服务器端处理请求/响应。最常见的 HTTPD 有 Linux 上常用的 Apache 和 nginx,以及 Windows 上的 IIS。

  • HTTPD 接收请求
  • 服务器把请求拆分为以下几个参数:
    • HTTP 请求方法(GET, POST, HEAD, PUT, DELETE, CONNECT, OPTIONS, 或者 TRACE)。直接在地址栏中输入 URL 这种情况下,使用的是 GET 方法
    • 域名:google.com
    • 请求路径/页面:/ (我们没有请求google.com下的指定的页面,因此 / 是默认的路径)
  • 服务器验证其上已经配置了 google.com 的虚拟主机
  • 服务器验证 google.com 接受 GET 方法
  • 服务器验证该用户可以使用 GET 方法(根据 IP 地址,身份信息等)
  • 如果服务器安装了 URL 重写模块(例如 Apache 的 mod_rewrite 和 IIS 的 URL Rewrite),服务器会尝试匹配重写规则,如果匹配上的话,服务器会按照规则重写这个请求
  • 服务器根据请求信息获取相应的响应内容,这种情况下由于访问路径是 “/” ,会访问首页文件(你可以重写这个规则,但是这个是最常用的)。
  • 服务器会使用指定的处理程序分析处理这个文件,假如 Google 使用 PHP,服务器会使用 PHP 解析 index 文件,并捕获输出,把 PHP 的输出结果返回给请求者

浏览器背后的故事

当服务器提供了资源之后(HTML,CSS,JS,图片等),浏览器会执行下面的操作:

  • 解析 —— HTML,CSS,JS
  • 渲染 —— 构建 DOM 树 -> 渲染 -> 布局 -> 绘制

浏览器

浏览器的功能是从服务器上取回你想要的资源,然后展示在浏览器窗口当中。资源通常是 HTML 文件,也可能是 PDF,图片,或者其他类型的内容。资源的位置通过用户提供的 URI(Uniform Resource Identifier) 来确定。

浏览器解释和展示 HTML 文件的方法,在 HTML 和 CSS 的标准中有详细介绍。这些标准由 Web 标准组织 W3C(World Wide Web Consortium) 维护。

不同浏览器的用户界面大都十分接近,有很多共同的 UI 元素:

  • 一个地址栏
  • 后退和前进按钮
  • 书签选项
  • 刷新和停止按钮
  • 主页按钮

浏览器高层架构

组成浏览器的组件有:

  • 用户界面 用户界面包含了地址栏,前进后退按钮,书签菜单等等,除了请求页面之外所有你看到的内容都是用户界面的一部分
  • 浏览器引擎 浏览器引擎负责让 UI 和渲染引擎协调工作
  • 渲染引擎 渲染引擎负责展示请求内容。如果请求的内容是 HTML,渲染引擎会解析 HTML 和 CSS,然后将内容展示在屏幕上
  • 网络组件 网络组件负责网络调用,例如 HTTP 请求等,使用一个平台无关接口,下层是针对不同平台的具体实现
  • UI后端 UI 后端用于绘制基本 UI 组件,例如下拉列表框和窗口。UI 后端暴露一个统一的平台无关的接口,下层使用操作系统的 UI 方法实现
  • Javascript 引擎 Javascript 引擎用于解析和执行 Javascript 代码
  • 数据存储 数据存储组件是一个持久层。浏览器可能需要在本地存储各种各样的数据,例如 Cookie 等。浏览器也需要支持诸如 localStorage,IndexedDB,WebSQL 和 FileSystem 之类的存储机制

HTML 解析

浏览器渲染引擎从网络层取得请求的文档,一般情况下文档会分成8kB大小的分块传输。

HTML 解析器的主要工作是对 HTML 文档进行解析,生成解析树。

解析树是以 DOM 元素以及属性为节点的树。DOM是文档对象模型(Document Object Model)的缩写,它是 HTML 文档的对象表示,同时也是 HTML 元素面向外部(如Javascript)的接口。树的根部是”Document”对象。整个 DOM 和 HTML 文档几乎是一对一的关系。

解析算法

HTML不能使用常见的自顶向下或自底向上方法来进行分析。主要原因有以下几点:

  • 语言本身的“宽容”特性
  • HTML 本身可能是残缺的,对于常见的残缺,浏览器需要有传统的容错机制来支持它们
  • 解析过程需要反复。对于其他语言来说,源码不会在解析过程中发生变化,但是对于 HTML 来说,动态代码,例如脚本元素中包含的 document.write() 方法会在源码中添加内容,也就是说,解析过程实际上会改变输入的内容

由于不能使用常用的解析技术,浏览器创造了专门用于解析 HTML 的解析器。解析算法在 HTML5 标准规范中有详细介绍,算法主要包含了两个阶段:标记化(tokenization)和树的构建。

解析结束之后

浏览器开始加载网页的外部资源(CSS,图像,Javascript 文件等)。

此时浏览器把文档标记为“可交互的”,浏览器开始解析处于“推迟”模式的脚本,也就是那些需要在文档解析完毕之后再执行的脚本。之后文档的状态会变为“完成”,浏览器会进行“加载”事件。

注意解析 HTML 网页时永远不会出现“语法错误”,浏览器会修复所有错误,然后继续解析。

执行同步 Javascript 代码。

CSS 解析

  • 根据 CSS词法和句法 分析CSS文件和 <style> 标签包含的内容
  • 每个CSS文件都被解析成一个样式表对象,这个对象里包含了带有选择器的CSS规则,和对应CSS语法的对象
  • CSS解析器可能是自顶向下的,也可能是使用解析器生成器生成的自底向上的解析器

页面渲染

  • 通过遍历DOM节点树创建一个“Frame 树”或“渲染树”,并计算每个节点的各个CSS样式值
  • 通过累加子节点的宽度,该节点的水平内边距(padding)、边框(border)和外边距(margin),自底向上的计算”Frame 树”中每个节点首的选(preferred)宽度
  • 通过自顶向下的给每个节点的子节点分配可行宽度,计算每个节点的实际宽度
  • 通过应用文字折行、累加子节点的高度和此节点的内边距(padding)、边框(border)和外边距(margin),自底向上的计算每个节点的高度
  • 使用上面的计算结果构建每个节点的坐标
  • 当存在元素使用 floated,位置有 absolutelyrelatively 属性的时候,会有更多复杂的计算,详见http://dev.w3.org/csswg/css2/http://www.w3.org/Style/CSS/current-work
  • 创建layer(层)来表示页面中的哪些部分可以成组的被绘制,而不用被重新栅格化处理。每个帧对象都被分配给一个层
  • 页面上的每个层都被分配了纹理(?)
  • 每个层的帧对象都会被遍历,计算机执行绘图命令绘制各个层,此过程可能由CPU执行栅格化处理,或者直接通过D2D/SkiaGL在GPU上绘制
  • 上面所有步骤都可能利用到最近一次页面渲染时计算出来的各个值,这样可以减少不少计算量
  • 计算出各个层的最终位置,一组命令由 Direct3D/OpenGL发出,GPU命令缓冲区清空,命令传至GPU并异步渲染,帧被送到Window Server。

GPU 渲染

  • 在渲染过程中,图形处理层可能使用通用用途的 CPU,也可能使用图形处理器 GPU
  • 当使用 GPU 用于图形渲染时,图形驱动软件会把任务分成多个部分,这样可以充分利用 GPU 强大的并行计算能力,用于在渲染过程中进行大量的浮点计算。

Window Server

后期渲染与用户引发的处理

渲染结束后,浏览器根据某些时间机制运行JavaScript代码(比如Google Doodle动画)或与用户交互(在搜索栏输入关键字获得搜索建议)。类似Flash和Java的插件也会运行,尽管Google主页里没有。这些脚本可以触发网络请求,也可能改变网页的内容和布局,产生又一轮渲染与绘制。

from:https://github.com/skyline75489/what-happens-when-zh_CN