1. 逻辑回归

对于逻辑回归而言,y 的取值不是 0 就是 1,所以 $h_θ(x)$ 可以写为
$$h_θ(x) = g(θ^{T}x)=\frac1{1+e^{-θ^{T}x}}$$

其中
$$g(z)=\frac1{1+e^{-z}}$$;

g(z) 被称为 logistic function 或 sigmoid function,其二维坐标下的曲线为:
sigmoid function

我们先取 g(z) 为 sigmoid function,如果有其他使得 y 值从 0 到 1 平滑递增的函数也可以使用。但由于一些列原因(在后续的一般化回归模型 GLM 中会谈到为什么选用这个函数),g(z) is a fairly natural one.

g(z) 的导数我们可以先进行推导:
$$g’(z)=\frac{d}{dz}\frac{1}{1+e^{-z}}= \frac{1}{(1+e^{-z})^2}(e^{-z})$$
$$= \frac{1}{1+e^{-z}}*(1 - \frac{1}{1+e^{-z}})= g(z)(1-g(z))$$

2. 梯度上升法求解逻辑回归

对于给定的逻辑回归函数,我们使用最小二乘法来推导出最大似然估计,假设:
$P(y=1|x;θ)=h_θ(x)$,代表对于给定的 θ,y 取值为 1 的概率。
$P(y=0|x;θ)=1-h_θ(x)$,代表对于给定的 θ,y 取值为 0 的概率。

以上两者可以合并为:
$$P(y|x;θ)=(h_θ(x))^y(1 − h_θ(x))^{(1−y)}$$

假设 m 个训练集是相互独立的,则似然估计为:
$$L(θ)=P(\overrightarrow{y}|X;θ)$$
$$= \prod^m_{i=1}P(y^i|x^i;θ)$$
$$= \prod^m_{i=1}{(h_θ(x^{(i)}))^{y^{(i)}}(1 − h_θ(x^{(i)}))^{(1−y^{(i)})}}$$

和之前一样,上式可以简化为:


$l(θ) = logL(θ)
= \sum_{m}^{i=1}{y^{(i)}}log{h(x^{(i)}) + {(1−y^{(i)})}log(1 − h(x^{(i)}))}$

那么,
如何去最大化似然函数呢,可以应用梯度上升法,因为我们要使 P 的取值足够大,也是就预测准确的概率最够大。

随机梯度上升的公式为:
$$θ:= θ + \alpha\Deltaθl(θ)$$

下面来求$\Deltaθl(θ)$的取值:

$$\frac\partial{\partial\theta_j}l(\theta)$$
$$= (y\frac1{g(\theta^Tx)} - (1-y)\frac1{1-g(\theta^Tx)})\frac\partial{\partial\theta_j}g(\theta^Tx)$$
$$= (y\frac1{g(\theta^Tx)} - (1-y)\frac1{1-g(\theta^Tx)}) g(\theta^Tx)(1-g(\theta^Tx))\frac\partial{\partial\theta_j}\theta^Tx$$
$$= ({y(1-g(\theta^Tx))-(1-y)g(\theta^Tx)})x_j$$
$$= (y - h_{\theta}(x))x_j$$

附上手写的推导过程:
手写推导过程

所以,最终随机梯度上升的公式为:
$$θ_j:=θ_j + \alpha\sum_{i=1}^{m}(y^{(i)} - h_{\theta}(x^{(i))})x_j^{(i)}$$

如何和线性回归的公式放在一起比较,

$$θ_j = θ_j - α \frac1m * \sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})}*x_j^{(i)}$$

会发现,这两者非常相似,实际上却不然,因为这里的 $(h_θ(x^{(i)})$ 定义的不是线性函数。后续我们谈到 GLM 时会发现这并不是巧合,而是有更深层次的原因。

3. 牛顿迭代法求解逻辑回归

牛顿迭代法可以利用到曲线本身的信息,比梯度下降法更容易收敛,即迭代更少次数。

3.1 牛顿迭代法简述

假设我们要求解方程 f(x)=0 的根,首先随便找一个初始值 x0,如果 x0 不是解,做一个经过 (x0,f(x0)) 这个点的切线,与 x 轴的交点为 x1。同样的道理,如果 x1 不是解,做一个经过 (x1,f(x1)) 这个点的切线,与 x 轴的交点为 x2。 以此类推。以这样的方式得到的 xi 会无限趋近于 f(x)=0 的解。

对于任意一点 $(x_n,y_n)$ 做切线,切线的斜率为 $f’(x_n)$,则有方程:
$$ y-f(x_n) = f’(x_n)(x-x_n) $$

3.2 迭代过程

求解 $f(\theta)$ = 0 时 $\theta$ 的取值。
设下一次迭代时 $\theta^{(t+1)}$ 的取值与前一次迭代 $\theta^{(t)}$ 的取值(在 x 轴)距离为 $\Delta$。

则 $\theta^{(t+1)} = \theta^{(t)} - \Delta$,且 $\Delta = \frac{f(\theta^{(t)})}{f’(\theta^{(t)})}$,
所以有:
$$\theta^{(t+1)} = \theta^{(t)} - \frac{f(\theta^{(t)})}{f’(\theta^{(t)})}$$

从泰勒展开到牛顿迭代

也可以由泰勒展开中推导牛顿迭代的公式。这次为了求解方程 f′=0 的根,把原函数 f(x) 的做泰勒展开,展开到二阶形式:
$$ f(x+\Delta x) = f(x)+f’(x)\Delta x+ \frac1{2}f’’(x)\Delta x^2 $$

当且仅当 $\Delta x$ 逼近 0 时,上式成立,此时忽略 1/2 系数的作用,所以有:
$$ f’(x)+ \frac1{2}f’’(x)\Delta x = 0 $$
故:
$$\Delta x = -\frac{f’(x)}{f’’(x)} $$

对函数求极大值的方法
>

  1. 将原函数y=f(x),对x求一次导数,得到dy/dx;
  2. 令dy/dx = 0,解得一次导函数的零点;
  3. 将原函数对x求二次导函数;
  4. 将解得的零点坐标的x值代入二次导函数,
    如果是正值,零点所在位置,就是极小值点,再将该x值代入原函数,得到极小值;
    如果是值值,零点所在位置,就是极大值点,再将该x值代入原函数,得到极大值;
    如果是0,零点所在位置,既不是极小值点,也不是极大值点,是拐点。

所以求 $l(\theta)$ 在极大值处 $\theta$ 的取值,则是求 $l’(\theta) = 0$ 时 $\theta$ 的值,应用牛顿迭代法则有:

$$\theta^{(t+1)} = \theta^{(t)} - \frac{l’(\theta^{(t)})}{l’’(\theta^{(t)})}$$

3.3 多维向量的牛顿迭代

对于多维向量 $\overrightarrow{X}$ 求解。
$$\theta := \theta - H^{-1} \nabla l(\theta)$$
其中
$\nabla l(\theta)$ 是对 $l(\theta)$ 求导的值。

H 是一个 n*n 的矩阵,n 是特征数量,元素的计算公式为:
$$H_ij= \frac{\partial^2{l({\theta)}}}{\partial{\theta_i}\partial{\theta_j}}$$

3.4 牛顿迭代法的特点

是否收敛

通常情况下是收敛的,但是需要满足一些条件,对于逻辑回归来讲,是收敛的。

迭代速度

每次迭代后,有解数字的误差是成平方倍减小的,是二次收敛函数。

优缺点

优点:收敛快
缺点:特征多(上千个)时,每次迭代成本大

Reference

http://blog.csdn.net/baimafujinji/article/details/51179381
http://blog.csdn.net/baimafujinji/article/details/51167852
如何通过牛顿方法解决Logistic回归问题

1. 欠拟合与过拟合

欠拟合:underfitting,与训练数据贴合的不够好,不能准确预测未来目标值。
过拟合:overfitting,与训练数据贴合的太好了,预测未来目标值的准确性有较大风险。

2. 线性模型的概率解释

思考:我们为什么要用最小二乘的指标作为 cost function?为什么不是绝对值或四次方?

最小二乘法(又称最小平方法)是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。
最小二乘是从函数形式上来看的,极大似然是从概率意义上来看的。事实上,最小二乘可以由高斯噪声假设+极大似然估计推导出来。当然极大似然估计还可以推导出其他的loss function, 比如logistic回归中,loss function是交叉熵。
最大似然估计与最小二乘估计的区别

一般的最小二乘法实际上是在假设误差项满足高斯分布且独立同分布的情况下,使似然性最大化。

推导过程

回到预测房价的例子,假设最终的预测函数,每一次预测都有误差,用$ε^{(i)}$表示误差,则预测函数可以写为:
$$y^{(i)}=\theta^Tx^{(i)} + ε^{(i)} $$

其中,误差是随机分布的,均值为 0,服从高斯分布 $N(0,σ^2)$。

Andrew Ng 讲到在大多数情况下,线性回归的误差值如果综合来看,就是符合高斯分布的。并且根据中心极限定律,正态分布确实是对误差项分布的合理猜想。

所以
$$P(y^{(i)}|x^{(i)}; θ) = \frac{1}{\sqrt{2\pi}\sigma}exp(- \frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})$$

$P(y^{(i)}|x^{(i)}; θ)$ 表示:在 θ 为给定的参数的情况下,概率 $y^{(i)}$ 以 $x^{(i)}$ 为随机变量的概率分布,注意 θ 不是随机变量。

由于 ε(i) 是独立的同分布(IID:independentlyidentically distribution),所以以 θ 为变量的似然函数为:
$$
L(θ)=L(θ;X,Y)=p(Y|X;θ) = \prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}exp(- \frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})
$$

对 L(θ) 取对数有:
$$
l(\theta)=logL(\theta)
= log\prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}exp(- \frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})
$$
$$
= m\sum_{i=1}^{m}log\frac{1}{\sqrt{2\pi}\sigma} - \frac1{2\sigma^2}\sum_{i=1}^{m}(y^{(i)}-\theta^Tx^{(i)})^2
$$

最大化 $l(\theta)$ 即是最小化 $\frac1{2\sigma^2}\sum_{i=1}^{m}(y^{(i)}-\theta^Tx^{(i)})^2$,这样就是 cost function.

由于目标变量服从正态分布,但分布的均值和方差都未知,对均值和方差两个参数的合理估计是选取两个参数使得在正态分布的前提下,抽到各样本中的 y 值的概率最大,这就是最大似然估计的思想。

Reference

http://www.holehouse.org/mlclass/07_Regularization.html
http://rstudio-pubs-static.s3.amazonaws.com/4810_06e3d8fd26ed40eb8c31aff35eae81ae.html
https://rpubs.com/badbye/ml03
http://www.qiujiawei.com/linear-algebra-15/
最大似然估计

1. 多变量的线性回归

n: 特征(features) 数量
m: 训练集数量
$x^{(i)}$:

  • 表示一条训练数据的向量
  • i is an index into the training set
  • So
    • x is an n-dimensional feature vector
    • $x^{(3)}$ is, for example, the 3rd training data

$x^{(j)}_i$: The value of feature j in the ith training example

例如,当 n=4 时:
$$h_θ(x) = θ_0 + θ_1x_1 + θ_2x_2 + θ_3x_3 + θ_4x_4$$

For convenience of notation, $x_0$ = 1, 所以最后的特征向量的维度是 n+1,从 0 开始,记为”X”,
则有:
$$h_θ(x)=θ^TX$$
$θ^T$: [1 * (n+1)] matrix

1.1 多变量的梯度下降

Cost Function

$$J(θ_0, θ_1, …,θ_n) = \frac1{2m}\sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})^2}$$

Gradient descent

Repeat {
$$ θ_j = θ_j - α\frac\partial{\partial J(θ_0, θ_1, …,θ_n)} $$
}

every iterator

  • θj = θj - learning rate (α) times the partial derivative of J(θ) with respect to θJ(…)
  • We do this through a simultaneous update of every θj value

$$ \frac\partial{\partial J(θ_0, θ_1, …,θ_n)} $$
$$ = \frac1m * \sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})}*x_j^{(i)} $$

2. Gradient Decent in practice

2.1 Feature Scaling

假设只有 $x_1$,$x_2$ 两个变量,其中:$x_1\in(0,2000), x_2\in(1,5)$,则最后的 J(θ) 图形是一个椭圆,在椭圆下用梯度下降法会比圆形要耗时更久,So we need to rescale this input so it’s more effective,有很多方式,一种是将各个 feature 除以其本身的最大值,缩小范围至[0,1],一种是各个 feature 减去 mean 然后除以最大值,缩小范围至[-0.5,0.5]

Learning Rate α

  • working correctly: If gradient descent is working then J(θ) should decrease after every iteration
  • convergence: 收敛是指每经过一次迭代,J(θ)的值都变化甚小。
  • choose α
    1. When to use a smaller α
      • If J(θ) is increasing, see below picture
      • If J(θ) looks like a series of waves, decreasing and increasing again
      • But if α is too small then rate is too slow
    2. Try a range of α values
      • Plot J(θ) vs number of iterations for each version of alpha
      • Go for roughly threefold increases: 0.001, 0.003, 0.01, 0.03. 0.1, 0.3

2.2 Features and polynomial regression

Can create new features

如何选择 features 和表达式尤为关键,例如房价与房子的长,房子的宽组成的表达式就会麻烦很多,若将房子的长乘以房子的宽得出面积,则有房价与房子面积的表达式,将会更容易拟合出房价的走势。

Polynomial regression

例如房价的走势,如下图,横坐标 x 为房子的面积,纵坐标为房价,使用一元二次的方程,会得出下图的蓝色曲线。容易得到房价今后会有一个下降的过程,可实际上房价是不会随着面积的增大而下降的。所以需要重新选定 Polynomial regression,可以改为使用一元三次的方程或者使用平凡根的方程。

所以选择合适的 Features 和 Polynomial regression 都非常重要。

3. Normal equation 求解多变量线性回归

3.1 Normal equation

举例说明,假设 J(θ) 是一元二次方程,如:J(θ)=a$θ^2$+bθ+c,则令 $$ \frac{d}{dθ}J(θ)=2aθ+b=0$$ 即可,求出最终的 θ 则得到了线性回归方程,可以预测出今后的 y 值。

更普遍地,当 θ 是一个 n+1 维的向量时,θ $\in$ $R^{n+1}$,则 cost function 如下:
$$ J(θ_0, θ_1, …,θ_n) = \frac1{2m}\sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})^2} $$
只需要令:
$$ \frac\partial{\partial θ_j}J(θ_0, θ_1, …,θ_n) = … = 0 $$,其中 j = 0,1,2,…,n
设 X 代表训练集的 features 的值的矩阵,y 代表训练集的结果的值的矩阵,假设训练集数量为 m, features 个数为 n, 则 X 为 (m*n) 的矩阵,y 为 (m*1) 的矩阵,可以推导出求 θ 向量的公式如下:
$$θ = (X^TX)^{-1}X^Ty$$

4. Gradient descent Vs Normal equation

Gradient descent

  • Need to chose learning rate
  • Needs many iterations - could make it slower
  • Works well even when n is massive (millions)
  • Better suited to big data
  • What is a big n though: 100 or even a 1000 is still (relativity) small, If n is 10000 then look at using gradient descent
  • 适用于线性回归会逻辑回归

Normal equation

  • No need to chose a learning rate
  • No need to iterate, check for convergence etc.
  • Normal equation needs to compute $(X^TX)^{-1}$
    • This is the inverse of an n x n matrix
    • With most implementations computing a matrix inverse grows by O(n3), So not great
  • Slow of n is large, Can be much slower
  • 仅适用于线性回归

5. 局部加权线性回归

局部加权回归(locally weighted regression)简称 loess,其思想是,针对对某训练数据的每一个点,选取这个点及其临近的一批点做线性回归;同时也需要考虑整个训练数据,考虑的原则是距离该区域越近的点贡献越大,反之则贡献越小,这也正说明局部的思想。其 cost function 为:
$$J(\theta) = \sum_{i=1}^{m} w^{(i)}( y^{(i)}-\theta^Tx^{(i)} )^2$$

其中
$$ w^{(i)} = exp (-\frac{(x^{(i)}-x)^2}{\tau^2})$$

$w^{(i)}$的形式跟正态分布很相似,但二者没有任何关系,仅仅只是便于计算。可以发现,$x^{(j)}$ 离 $x^{(i)}$ 非常近时,${w^{(i)}_j}$ 的值接近于1,此时 j 点的贡献很大,当 $x^{(j)}$ 离 $x^{(i)}$ 非常远时,${w^{(i)}_j}$ 的值接近于 0,此时 j 点的贡献很小。

$\tau^2$ 是波长函数(bandwidth), 控制权重随距离下降的速度,τ 越小则 x 离 $x^{(i)}$ 越远时 $w^{(i)}$ 的值下降的越快。

所以,如果沿着 x 轴的每个点都进行局部直线拟合,那么你会发现对于这个数据集合来说,局部加权的预测结果,能够最终跟踪这条非线性的曲线。

但局部加权回归也有其缺点:

  • 每次对一个点的预测都需要整个数据集的参与,样本量大且需要多点预测时效率低。提高效率的方法参考 Andrew More’s KD Tree
  • 不可外推,对样本所包含的区域外的点进行预测时效果不好,事实上这也是一般线性回归的弱点

对于线性回归算法,一旦拟合出适合训练数据的参数θ,保存这些参数θ,对于之后的预测,不需要再使用原始训练数据集,所以是参数学习算法。

对于局部加权线性回归算法,每次进行预测都需要全部的训练数据(每次进行的预测得到不同的参数θ),没有固定的参数θ,所以是非参数算法(non-parametric algorithm)。

Reference

http://www.holehouse.org/mlclass/04_Linear_Regression_with_multiple_variables.html

引言

本系列的课程来源是 斯坦福大学公开课 CS229: 机器学习课程,也可以看网易公开课的资源,是带字幕的。斯坦福的 CS229 课程相比于 Course 上的 Machine Learning 课程,理论更强,讲解的也更深入,需要有一些的高数基础。两个课程都看了前半部分,更推荐前者,所以相关笔记对应的都是 CS229 课程。

1. 线性回归的定义

适用于监督学习,根据已有的数据集合(x, y),来推断出将来的数据趋势。

2. 单变量线性回归

最后的函数应该是 y = ax + b,假设 hypothesis 为:

$h_{\theta}$(x) = $\theta_{0}$ + $\theta_{1}$

则问题转化为求 $\theta_{0}$ 和 $\theta_{1}$ 的值。要求这两个值需要转化上式,并根据已有的数据来求解。下面介绍损失函数,又叫代价函数的概念。

3. Cost Function

针对每一组数据,公式的值是 $h_{\theta}$($x_{i}$), 实际的值是 $y_{i}$,我们要达到的效果则是公式能够尽量表达已有的 m 组数据集合,即 $( h_{\theta}(x^{(i)}) - y_{i})^{2}$ 的值尽量小。
所以,对于所有数据集合,需要求使得
$$ \frac1{2m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)}) - y^{(i)})^2}$$ 最小的 $\theta$ 值。

上式又称为 Cost Function,可以写为:

$$ J(\theta_0, \theta_1) = \frac1{2m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)}) - y^{(i)})^2} $$

我们需要最小化这个 Cost Function。

Cost Function 的作用

假设 $\theta_0$ = 0,则有 $\theta_1$ 和 J($\theta_1$) 的关系,且图形如下:

所以当 $\theta_1$ = 1 时,
$$ J(\theta_1)= \frac1{2m}\sum_{i=1}^{m}{(\theta_1x^{(i)} - y^{(i)})^2} $$
很容易看出,$J(\theta_1)$ 是关于 $\theta_1$ 的一元二次方程,对于所有的训练数据,每个 $\theta_1$ 的取值都会得到一个 $J(\theta_1)$ 值,而 $J(\theta_1)$ 和 $\theta_1$ 的对应关系根据一元二次方程可知,函数曲线如上图。
当 $J(\theta_1)$ 最小时,求得 $\theta_1$ 结果。

当 $\theta_0$ 和 $\theta_1$ 都不为 0 时,J($\theta_0$, $\theta_1$) 的图形如下:

对于两个系数的情况不如一个系数是一个二维坐标系的抛物线那么简单。下面将介绍梯度下降法。

4. 梯度下降法

  • Start with initial guesses
  • Start at 0,0 (or any other value)
  • Keeping changing $\theta_0$ and $\theta_1$ a little bit to try and reduce J($\theta_0$, $\theta_1$)
  • Each time you change the parameters, you select the gradient which reduces J($\theta_0$, $\theta_1$) the most possible
  • Repeat
  • Do so until you converge to a local minimum
    Has an interesting property
    • Where you start can determine which minimum you end up
    • Here we can see one initialization point led to one local minimum
    • The other led to a different one

4.1 具体的计算过程

$$ \theta_j := \theta_j - \alpha \frac\partial{\partial\theta_j}J(\theta_0, \theta_1)$$
(for j = 0 and j = 1)

4.2 Notation

$\alpha$

  • Is a number called the learning rate
  • Controls how big a step you take
    • If α is big have an aggressive gradient descent
    • If α is small take tiny steps
  • Too small
    • Take baby steps
    • Takes too long
  • Too large
    • Can overshoot the minimum and fail to converge

4.3 Computer

每次都是同时计算 $\theta_0, \theta_1$ 的值,如下:
$$ temp0:= \theta_0 - \alpha \frac\partial{\partial\theta_0}J(\theta_0, \theta_1)$$
$$ temp1:= \theta_1 - \alpha \frac\partial{\partial\theta_1}J(\theta_0, \theta_1)$$
$$ \theta_0 := temp0 $$
$$ \theta_1 := temp1 $$

4.4 利用梯度下降法求解线性回归问题

$$ \frac\partial{\partial\theta_j}J(\theta_0, \theta_1) $$

$$ =\frac\partial{\partial\theta_j} * \frac1{2m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)}) - y^{(i)})^2} $$

$$ =\frac\partial{\partial\theta_j} * \frac1{2m}\sum_{i=1}^{m}{(\theta_0 +\theta_1x^{(i)} - y^{(i)})^2} $$

对于 j = 0 or 1 的情况有:
j = 0:
$$ \frac\partial{\partial\theta_0}J(\theta_0, \theta_1) = \frac1{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})$$
j = 1:
$$ \frac\partial{\partial\theta_1}J(\theta_0, \theta_1) = \frac1{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})*x^{(i)}$$

4.5 梯度下降法的证明

1、如果优化函数存在解析解。例如我们求最值一般是对优化函数求导,找到导数为0的点。如果代价函数能简单求导,并且求导后为0的式子存在解析解,那么我们就可以直接得到最优的参数。

2、如果式子很难求导,例如函数里面存在隐含的变量或者变量相互间存在耦合,互相依赖的情况。或者求导后式子得不到解释解,或者未知参数的个数大于方程组的个数等。这时候使用迭代算法来一步一步找到最优解。

  • 当目标函数是凸函数时,梯度下降法的解是全局最优解
  • 一般情况下,其解不保证是全局最优解

凸函数

凸函数就是一个定义在某个向量空间的凸子集C(区间)上的实值函数 f,而且对于凸子集C中任意两个向量 $x_1$, $x_2$ 有:
$$f(\frac{x_1+x_2}{2}) \le \frac{f(x_1)+f(x_2)}{2}$$
于是容易得出对于任意(0,1)中有理数 p,有:
$$f(px_1+(1-p)x_2) \le pf(x_1)+(1-p)f(x_2)$$
如果 f 连续,那么 p 可以改成任意(0,1)中实数。则 f 称为 I 上的凸函数,当且仅当其上境图(在函数图像上方的点集)为一个凸集。

梯度下降法的使用

我们首先在函数上任选一点,计算其损失(即我们上面的L(w)) ,然后按照某一规则寻找更低的一点计算新的损失,只要新损失更小(最小化问题),我们就继续下降,直到达到一个可接受的优化目标。
梯度下降方法分为两个部分,第一部分是整体上,我们使用某步长不断下降求损失函数,第二部分是为了防止步长太长导致最后无法收敛,每次当损失上升的时候都调整步长。
通常实践中使用时,都是用一些开源算法,很少需要深度改进,比如使用 libsvm 可以直接求解逻辑回归。

Reference

http://www.cnblogs.com/yysblog/p/3268508.html
http://52opencourse.com/125/coursera%E5%85%AC%E5%BC%80%E8%AF%BE%E7%AC%94%E8%AE%B0-%E6%96%AF%E5%9D%A6%E7%A6%8F%E5%A4%A7%E5%AD%A6%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AC%AC%E5%85%AD%E8%AF%BE-%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92-logistic-regression
http://www.cnblogs.com/chaoren399/p/4851658.html

要解决的问题

json 反序列化 bean 时,当某个字段在 json 中为 null 时,使用 bean 中声明的默认值。

Person 类我们改造下:

1
2
3
4
5
public class Person {
private String name;
// Address is a enum: {CH, US, GZ}
private Region region = Region.GZ;
}

仍然以 Person 类举例,如果 json 串是:

1
{"name":"robert", "region":null}

希望反序列化后的 bean 为

1
Person(name="robert", region=Region.GZ)

解决过程

在上一篇文章 lombok 的 AllArgs 导致 Jackson 反序列化丢失字段默认值 中可以看到 json 反序列化为 bean 的过程,一般情况下,是先调用默认构造函数生成 bean,然后根据 json 中出现的字段挨个赋值。
所以反序列化生成的 bean 的 region 肯定为 null。

解决方案

1. @JsonInclude(Include.NON_NULL) 可行吗?

不可行,这个注解是序列化时忽略 null 值,反序列化时不生效,基本上反序列化时我们不能做什么事情。

2. JsonCreator 可行吗?

在 Region 枚举里写 JsonCreator:

1
2
3
4
5
6
7
8
9
10
@JsonCreator
public static Region getRegion(String value) {
for (Region region : Region.values()) {
if (region.name().equals(value)) {
return region;
}
}
return Region.GZ;
}

直接将 {"region": null} 反序列化为 Region 是可行的,会调用 JsonCreator,但是如果是反序列化 Person 则不会调用到 JsonCreator,为什么呢?

debug 过程:
如前文所述,会调用到 com.fasterxml.jackson.databind.deser.BeanDeserializer#deserialize 这个函数中,然后会调用到
com.fasterxml.jackson.databind.deser.SettableBeanProperty#deserialize,这个函数的实现是:

1
2
3
4
5
6
7
8
9
10
11
public final Object deserialize(JsonParser p, DeserializationContext ctxt) throws IOException {
JsonToken t = p.getCurrentToken();
if (t == JsonToken.VALUE_NULL) {
return _valueDeserializer.getNullValue(ctxt);
}
if (_valueTypeDeserializer != null) {
return _valueDeserializer.deserializeWithType(p, ctxt, _valueTypeDeserializer);
}
return _valueDeserializer.deserialize(p, ctxt);
}

所以在这里会把 null 值拦住,直接返回 getNullValue 的结果。

3.自定义 deserializer

实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class RegionDeserializer extends JsonDeserializer<Region> {
@Override
public Region deserialize(JsonParser jsonParser, DeserializationContext deserializationContext)
throws IOException {
JsonNode node = jsonParser.getCodec().readTree(jsonParser);
Region region = Region.GZ;
try {
if (StringUtils.isNotEmpty(node.textValue())) {
return Region.getRegion(node.textValue());
}
} catch (Exception e) {
type = Region.GZ;
}
return region;
}
@Override
public Region getNullValue(DeserializationContext ctxt) {
return Region.GZ;
}
}

Person 类改为:

1
2
3
4
5
6
7
public class Person {
private String name;
// Address is a enum: {CH, US, GZ}
@JsonDeserialize(using = RegionDeserializer.class)
private Region region = Region.GZ;
}

这样,在com.fasterxml.jackson.databind.deser.SettableBeanProperty#deserialize这个方法里,碰到 null 值,就会返回 getNullValue 的结果,即 Region.GZ,如果不是 null 会进入 getRegion 函数处理,也能处理其他情况。

要解决的问题

希望在反序列化 json 到 bean 时,对于 json 中未出现的字段,在 bean 中赋上默认值。

例如
Person 类如下:

1
2
3
4
5
6
7
8
@Data
@AllArgsConstructor
@NoArgsConstructor
@JsonIgnoreProperties(ignoreUnknown = true)
public class Person {
private String name;
private String address = "beijing"; // default value if json missing the age field
}

json:

1
{"name":"robert"}

反序列化后的 bean 为

1
Person(name="robert", address="beijing")

但实际上,发序列化的结果为

1
Person(name="robert", address=null)

解决过程

1. 查看 maven 版本

项目中 jackson 的配置如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<dependency>
<groupId>com.fasterxml.jackson.core</groupId>
<artifactId>jackson-annotations</artifactId>
<version>${jackson.version}</version>
</dependency>
<dependency>
<groupId>com.fasterxml.jackson.core</groupId>
<artifactId>jackson-core</artifactId>
<version>${jackson.version}</version>
</dependency>
<dependency>
<groupId>com.fasterxml.jackson.core</groupId>
<artifactId>jackson-databind</artifactId>
<version>${jackson.version}</version>
</dependency>
<!-- Jackson dependency versions -->
<jackson.version>2.6.5</jackson.version>

配置升到最新后问题仍然存在。

2. debug json 反序列化过程,找到原因

json 反序列化是从

1
com.fasterxml.jackson.databind.ObjectMapper#_readMapAndClose

这个方法调用开始的,里面的一段代码为:

1
2
3
4
5
6
7
8
9
DeserializationConfig cfg = getDeserializationConfig();
DeserializationContext ctxt = createDeserializationContext(jp, cfg);
JsonDeserializer<Object> deser = _findRootDeserializer(ctxt, valueType);
if (cfg.useRootWrapping()) {
result = _unwrapAndDeserialize(jp, ctxt, cfg, valueType, deser);
} else {
result = deser.deserialize(jp, ctxt);
}
ctxt.checkUnresolvedObjectId();

在第 3 行找到的 JsonDeserializer 是 com.fasterxml.jackson.databind.deser.BeanDeserializer
从第 7 行代表进入 com.fasterxml.jackson.databind.deser.BeanDeserializer#deserialize(com.fasterxml.jackson.core.JsonParser, com.fasterxml.jackson.databind.DeserializationContext)

函数实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public Object deserialize(JsonParser p, DeserializationContext ctxt) throws IOException {
// common case first
if (p.isExpectedStartObjectToken()) {
if (_vanillaProcessing) {
return vanillaDeserialize(p, ctxt, p.nextToken());
}
p.nextToken();
if (_objectIdReader != null) {
return deserializeWithObjectId(p, ctxt);
}
return deserializeFromObject(p, ctxt);
}
JsonToken t = p.getCurrentToken();
return _deserializeOther(p, ctxt, t);
}

vanillaDeserialize 为 false,最后走到了第 11 行,最后到了

1
com.fasterxml.jackson.databind.deser.BeanDeserializer#_deserializeUsingPropertyBased

然后到

1
com.fasterxml.jackson.databind.deser.impl.PropertyBasedCreator#build

在这个函数里有这样一段代码:

1
Object bean = _valueInstantiator.createFromObjectWith(ctxt, buffer.getParameters(_allProperties));

调用的是

1
com.fasterxml.jackson.databind.deser.ValueInstantiator#createFromObjectWith(com.fasterxml.jackson.databind.DeserializationContext, java.lang.Object[])

可以发现,createFromObjectWith 的第二个参数是数组,json 解出来的字段都放在了这个数组里。然后调用了 Person 类的全参构造函数,对于
缺失的字段自动补 null 值,这样就导致了 address 字段为 null。

3. 解决方案

去掉 @AllArgsConstructor 时,没有问题了,因为此时找到的 com.fasterxml.jackson.databind.deser.BeanDeserializer 的 vanillaDeserialize 字段为 true,会调用 vanillaDeserialize(p, ctxt, p.nextToken());,这个函数的实现非常明确:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private final Object vanillaDeserialize(JsonParser p, DeserializationContext ctxt, JsonToken t) throws IOException {
final Object bean = _valueInstantiator.createUsingDefault(ctxt);
// [databind#631]: Assign current value, to be accessible by custom serializers
p.setCurrentValue(bean);
if (p.hasTokenId(JsonTokenId.ID_FIELD_NAME)) {
String propName = p.getCurrentName();
do {
p.nextToken();
SettableBeanProperty prop = _beanProperties.find(propName);
if (prop != null) { // normal case
try {
prop.deserializeAndSet(p, ctxt, bean);
} catch (Exception e) {
wrapAndThrow(e, bean, propName, ctxt);
}
continue;
}
handleUnknownVanilla(p, ctxt, bean, propName);
} while ((propName = p.nextFieldName()) != null);
}
return bean;
}

先用默认构造函数生成 bean,此时的 bean 是有默认值的,然后将 json 中出现的字段的值赋值给 bean,这样 address 就有值了。

4. 根本原因

看上去是声明了全参构造函数导致的,所以想尝试自己写全参构造函数,在 address 为 null 时给其赋默认值。
写完如下:

1
2
3
4
5
6
7
public Person(String name, String address){
this.name = name;
this.address = address;
if(this.address == null){
this.address = "beijing";
}
}

继续走刚才 debug 的流程,发现居然没有请求这个全参构造函数。

那问题就是 @AllArgsConstructor 生成的全参函数有不同之处,jackson 能够识别出来并用于反序列化。查看 jar 包中 Person 类的代码发现其全参构造函数如下:

1
2
3
4
5
@ConstructorProperties({"name", "address"})
public Person(String name, String address){
this.name = name;
this.address = address;
}

所以,区别就是 @ConstructorProperties({"name", "address"}) 这个注解,这个注解的作用是指定构造函数参数的名字,Spring 可根据参数的名字注入 bean。

(补充自 liwei)
jackson 调用了全参构造函数的原因在于@AllArgsConstructor 的构造函数有ConstructorProperties ,jackson在选择构造函数的时候会调用BasicDeserializerFactory._addDeserialzerContructors方法,他首先选择无参构造函数,并遍历所有的构造函数,如果存在具有@ConstructProperties注解的构造函数,则把该构造函数作为默认创建bean的构造函数,如下:

可以通过设置 @AllArgsConstructor(suppressConstructorProperties=true) 来禁用 @ConstructorProperties.

结论

Lombok 的 @AllArgsConstructor 注解导致 Jackson 反序列化时调用了全参构造函数,将没有出现的字段都赋值为 null 了。

修改方式:

  1. 不使用 @AllArgsConstructor
  2. 使用 @AllArgsConstructor 但是不让其在全参构造函数上加入 ConstructorProperties 注解,声明方式改为 @AllArgsConstructor(suppressConstructorProperties = true)

目录

  1. 服务异常的处理流程
  2. 负载
  3. 内存
  4. 服务指标
  5. 工具

1. 服务异常的处理流程

2. 负载

2.1 查看机器 cpu 的负载

1
top -b -n 1 |grep java|awk '{print "VIRT:"$5,"RES:"$6,"cpu:"$9"%","mem:"$10"%"}'

2.2 查找 cpu 占用率高的线程

top -p 25603 -H
printf 0x%x 25842
jstack 25603 | grep 0x64f2

cat /proc/interrupts

(1)CPU
(2)Memory
(3)IO
(4)Network

可以从以下几个方面监控CPU的信息:
(1)中断;
(2)上下文切换;
(3)可运行队列;
(4)CPU 利用率。

3. 内存

3.1 系统内存

free 命令
[root@server ~]# free

1
2
3
4
total used free shared buffers cached
Mem: 3266180 3250000 10000 0 201000 3002000
-/+ buffers/cache: 47000 3213000
Swap: 2048276 80160 1968116

这里的默认显示单位是kb。
各项指标解释

  • total:总计物理内存的大小。
  • used:已使用多大。
  • free:可用有多少。
  • Shared:多个进程共享的内存总额。
  • buffers: 磁盘缓存的大小。
  • cache:磁盘缓存的大小。
  • -/+ buffers/cached): used:已使用多大,free:可用有多少。
  • 已用内存 = 系统used memory - buffers - cached
    (47000 = 3250000-201000-3002000)
  • 可用内存 = 系统free memory + buffers + cached
    (3213000 = 10000+201000+3002000)

什么是buffer/cache?

  • buffer 指 Linux 内存的:Buffer cache,缓冲区缓
  • cache 指 Linux内存中的:Page cache,页面缓存

page cache
page cache 主要用来作为文件系统上的文件数据的缓存来用,尤其是针对当进程对文件有 read/write 操作的时候。如果你仔细想想的话,作为可以映射文件到内存的系统调用:mmap是不是很自然的也应该用到 page cache?在当前的系统实现里,page cache 也被作为其它文件类型的缓存设备来用,所以事实上 page cache 也负责了大部分的块设备文件的缓存工作。

buffer cache
buffer cache 主要用来在系统对块设备进行读写的时候,对块进行数据缓存的系统来使用。这意味着某些对块的操作会使用 buffer cache 进行缓存,比如我们在格式化文件系统的时候。一般情况下两个缓存系统是一起配合使用的,比如当我们对一个文件进行写操作的时候,page cache 的内容会被改变,而 buffer cache 则可以用来将 page 标记为不同的缓冲区,并记录是哪一个缓冲区被修改了。这样,内核在后续执行脏数据的回写(writeback)时,就不用将整个 page 写回,而只需要写回修改的部分即可。

在当前的内核中,page cache 是针对内存页的缓存,说白了就是,如果有内存是以page进行分配管理的,都可以使用page cache作为其缓存来管理使用。
当然,不是所有的内存都是以页(page)进行管理的,也有很多是针对块(block)进行管理的,这部分内存使用如果要用到 cache 功能,则都集中到buffer cache中来使用。(从这个角度出发,是不是buffer cache改名叫做block cache更好?)然而,也不是所有块(block)都有固定长度,系统上块的长度主要是根据所使用的块设备决定的,而页长度在X86上无论是32位还是64位都是4k。

系统如何回收cache?

Linux内核会在内存将要耗尽的时候,触发内存回收的工作,以便释放出内存给急需内存的进程使用。一般情况下,这个操作中主要的内存释放都来自于对buffer/cache的释放。尤其是被使用更多的cache空间。既然它主要用来做缓存,只是在内存够用的时候加快进程对文件的读写速度,那么在内存压力较大的情况下,当然有必要清空释放cache,作为free空间分给相关进程使用。所以一般情况下,我们认为buffer/cache空间可以被释放,这个理解是正确的。

但是这种清缓存的工作也并不是没有成本。理解cache是干什么的就可以明白清缓存必须保证cache中的数据跟对应文件中的数据一致,才能对cache进行释放。所以伴随着cache清除的行为的,一般都是系统IO飙高。因为内核要对比cache中的数据和对应硬盘文件上的数据是否一致,如果不一致需要写回,之后才能回收。

在系统中除了内存将被耗尽的时候可以清缓存以外,我们还可以人工触发缓存清除的操作。

3.2 进程内存

3.2.1 进程内存统计

/proc/[pid]/status
通过/proc//status可以查看进程的内存使用情况,包括虚拟内存大小(VmSize),物理内存大小(VmRSS),数据段大小(VmData),栈的大小(VmStk),代码段的大小(VmExe),共享库的代码段大小(VmLib)等等。

cat /proc/[pid]/status

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Name: gedit /*进程的程序名*/
State: S (sleeping) /*进程的状态信息,具体参见http://blog.chinaunix.net/u2/73528/showart_1106510.html*/
Tgid: 9744 /*线程组号*/
Pid: 9744 /*进程pid*/
PPid: 7672 /*父进程的pid*/
TracerPid: 0 /*跟踪进程的pid*/
VmPeak: 60184 kB /*进程地址空间的大小*/
VmSize: 60180 kB /*进程虚拟地址空间的大小reserved_vm:进程在预留或特殊的内存间的物理页*/
VmLck: 0 kB /*进程已经锁住的物理内存的大小.锁住的物理内存不能交换到硬盘*/
VmHWM: 18020 kB /*文件内存映射和匿名内存映射的大小*/
VmRSS: 18020 kB /*应用程序正在使用的物理内存的大小,就是用ps命令的参数rss的值 (rss)*/
VmData: 12240 kB /*程序数据段的大小(所占虚拟内存的大小),存放初始化了的数据*/
VmStk: 84 kB /*进程在用户态的栈的大小*/
VmExe: 576 kB /*程序所拥有的可执行虚拟内存的大小,代码段,不包括任务使用的库 */
VmLib: 21072 kB /*被映像到任务的虚拟内存空间的库的大小*/
VmPTE: 56 kB /*该进程的所有页表的大小*/
Threads: 1 /*共享使用该信号描述符的任务的个数*/

3.2.2 JVM 内存分配

java内存组成介绍:堆(Heap)和非堆(Non-heap)内存

按照官方的说法:“Java 虚拟机具有一个堆,堆是运行时数据区域,所有类实例和数组的内存均从此处分配。堆是在 Java 虚拟机启动时创建的。”“在JVM中堆之外的内存称为非堆内存(Non-heap memory)”。可以看出JVM主要管理两种类型的内存:堆和非堆。简单来说堆就是Java代码可及的内存,是留给开发人员使用的;非堆就是JVM留给 自己用的,所以方法区、JVM内部处理或优化所需的内存(如JIT编译后的代码缓存)、每个类结构(如运行时常数池、字段和方法数据)以及方法和构造方法 的代码都在非堆内存中。

IMAGE

  1. JVM本身需要的内存,包括其加载的第三方库以及这些库分配的内存
  2. NIO的DirectBuffer是分配的native memory
  3. 内存映射文件,包括JVM加载的一些JAR和第三方库,以及程序内部用到的。上面 pmap 输出的内容里,有一些静态文件所占用的大小不在Java的heap里,因此作为一个Web服务器,赶紧把静态文件从这个Web服务器中人移开吧,放到nginx或者CDN里去吧。
  4. JIT, JVM会将Class编译成native代码,这些内存也不会少,如果使用了Spring的AOP,CGLIB会生成更多的类,JIT的内存开销也会随之变大,而且Class本身JVM的GC会将其放到Perm Generation里去,很难被回收掉,面对这种情况,应该让JVM使用ConcurrentMarkSweep GC,并启用这个GC的相关参数允许将不使用的class从Perm Generation中移除, 参数配置: -XX:+UseConcMarkSweepGC -X:+CMSPermGenSweepingEnabled -X:+CMSClassUnloadingEnabled,如果不需要移除而Perm Generation空间不够,可以加大一点: -X:PermSize=256M -X:MaxPermSize=512M
  5. JNI,一些JNI接口调用的native库也会分配一些内存,如果遇到JNI库的内存泄露,可以使用valgrind等内存泄露工具来检测
  6. 线程栈,每个线程都会有自己的栈空间,如果线程一多,这个的开销就很明显了
  7. jmap/jstack 采样,频繁的采样也会增加内存占用,如果你有服务器健康监控,记得这个频率别太高,否则健康监控变成致病监控了。

1.方法区

也称”永久代” 、“非堆”,它用于存储虚拟机加载的类信息、常量、静态变量、是各个线程共享的内存区域。默认最小值为16MB,最大值为64MB,可以通过-XX:PermSize 和 -XX:MaxPermSize 参数限制方法区的大小。

运行时常量池:是方法区的一部分,Class文件中除了有类的版本、字段、方法、接口等描述信息外,还有一项信息是常量池,用于存放编译器生成的各种符号引用,这部分内容将在类加载后放到方法区的运行时常量池中。

2.虚拟机栈

描述的是java 方法执行的内存模型:每个方法被执行的时候 都会创建一个“栈帧”用于存储局部变量表(包括参数)、操作栈、方法出口等信息。每个方法被调用到执行完的过程,就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。声明周期与线程相同,是线程私有的。

局部变量表存放了编译器可知的各种基本数据类型(boolean、byte、char、short、int、float、long、double)、对象引用(引用指针,并非对象本身),其中64位长度的long和double类型的数据会占用2个局部变量的空间,其余数据类型只占1个。局部变量表所需的内存空间在编译期间完成分配,当进入一个方法时,这个方法需要在栈帧中分配多大的局部变量是完全确定的,在运行期间栈帧不会改变局部变量表的大小空间。

3.本地方法栈

与虚拟机栈基本类似,区别在于虚拟机栈为虚拟机执行的java方法服务,而本地方法栈则是为Native方法服务。

4.堆

也叫做java 堆、GC堆是java虚拟机所管理的内存中最大的一块内存区域,也是被各个线程共享的内存区域,在JVM启动时创建。该内存区域存放了对象实例及数组(所有new的对象)。其大小通过-Xms(最小值)和-Xmx(最大值)参数设置,-Xms为JVM启动时申请的最小内存,默认为操作系统物理内存的1/64但小于1G,-Xmx为JVM可申请的最大内存,默认为物理内存的1/4但小于1G,默认当空余堆内存小于40%时,JVM会增大Heap到-Xmx指定的大小,可通过-XX:MinHeapFreeRation=来指定这个比列;当空余堆内存大于70%时,JVM会减小heap的大小到-Xms指定的大小,可通过XX:MaxHeapFreeRation=来指定这个比列,对于运行系统,为避免在运行时频繁调整Heap的大小,通常-Xms与-Xmx的值设成一样。

由于现在收集器都是采用分代收集算法,堆被划分为新生代和老年代。新生代主要存储新创建的对象和尚未进入老年代的对象。老年代存储经过多次新生代GC(Minor GC)任然存活的对象。

5.程序计数器

是最小的一块内存区域,它的作用是当前线程所执行的字节码的行号指示器,在虚拟机的模型里,字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令,分支、循环、异常处理、线程恢复等基础功能都需要依赖计数器完成。

3.2.3 直接内存

直接内存并不是虚拟机内存的一部分,也不是Java虚拟机规范中定义的内存区域。jdk1.4中新加入的NIO,引入了通道与缓冲区的IO方式,它可以调用Native方法直接分配堆外内存,这个堆外内存就是本机内存,不会影响到堆内存的大小。

3.2.4 JVM 内存分析

查看 JVM 堆内存情况

jmap -heap [pid]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
[root@server ~]$ jmap -heap 837
Attaching to process ID 837, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 24.71-b01
using thread-local object allocation.
Parallel GC with 4 thread(s)//GC 方式
Heap Configuration: //堆内存初始化配置
MinHeapFreeRatio = 0 //对应jvm启动参数-XX:MinHeapFreeRatio设置JVM堆最小空闲比率(default 40)
MaxHeapFreeRatio = 100 //对应jvm启动参数 -XX:MaxHeapFreeRatio设置JVM堆最大空闲比率(default 70)
MaxHeapSize = 2082471936 (1986.0MB) //对应jvm启动参数-XX:MaxHeapSize=设置JVM堆的最大大小
NewSize = 1310720 (1.25MB)//对应jvm启动参数-XX:NewSize=设置JVM堆的‘新生代’的默认大小
MaxNewSize = 17592186044415 MB//对应jvm启动参数-XX:MaxNewSize=设置JVM堆的‘新生代’的最大大小
OldSize = 5439488 (5.1875MB)//对应jvm启动参数-XX:OldSize=<value>:设置JVM堆的‘老生代’的大小
NewRatio = 2 //对应jvm启动参数-XX:NewRatio=:‘新生代’和‘老生代’的大小比率
SurvivorRatio = 8 //对应jvm启动参数-XX:SurvivorRatio=设置年轻代中Eden区与Survivor区的大小比值
PermSize = 21757952 (20.75MB) //对应jvm启动参数-XX:PermSize=<value>:设置JVM堆的‘永生代’的初始大小
MaxPermSize = 85983232 (82.0MB)//对应jvm启动参数-XX:MaxPermSize=<value>:设置JVM堆的‘永生代’的最大大小
G1HeapRegionSize = 0 (0.0MB)
Heap Usage://堆内存使用情况
PS Young Generation
Eden Space://Eden区内存分布
capacity = 33030144 (31.5MB)//Eden区总容量
used = 1524040 (1.4534378051757812MB) //Eden区已使用
free = 31506104 (30.04656219482422MB) //Eden区剩余容量
4.614088270399305% used //Eden区使用比率
From Space: //其中一个Survivor区的内存分布
capacity = 5242880 (5.0MB)
used = 0 (0.0MB)
free = 5242880 (5.0MB)
0.0% used
To Space: //另一个Survivor区的内存分布
capacity = 5242880 (5.0MB)
used = 0 (0.0MB)
free = 5242880 (5.0MB)
0.0% used
PS Old Generation //当前的Old区内存分布
capacity = 86507520 (82.5MB)
used = 0 (0.0MB)
free = 86507520 (82.5MB)
0.0% used
PS Perm Generation//当前的 “永生代” 内存分布
capacity = 22020096 (21.0MB)
used = 2496528 (2.3808746337890625MB)
free = 19523568 (18.619125366210938MB)
11.337498256138392% used
670 interned Strings occupying 43720 bytes.

关于这里的几个generation网上资料一大把就不细说了,这里算一下求和可以得知前者总共给Java环境分配了644M的内存,而ps输出的VSZ和RSS分别是7.4G和2.9G,这到底是怎么回事呢?
前面jmap输出的内容里,MaxHeapSize 是在命令行上配的,-Xmx4096m,这个java程序可以用到的最大堆内存。
VSZ是指已分配的线性空间大小,这个大小通常并不等于程序实际用到的内存大小,产生这个的可能性很多,比如内存映射,共享的动态库,或者向系统申请了更多的堆,都会扩展线性空间大小,要查看一个进程有哪些内存映射,可以使用 pmap 命令来查看:
pmap -x [pid]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[root@server ~]$ pmap -x 837
837: java
Address Kbytes RSS Dirty Mode Mapping
0000000040000000 36 4 0 r-x-- java
0000000040108000 8 8 8 rwx-- java
00000000418c9000 13676 13676 13676 rwx-- [ anon ]
00000006fae00000 83968 83968 83968 rwx-- [ anon ]
0000000700000000 527168 451636 451636 rwx-- [ anon ]
00000007202d0000 127040 0 0 ----- [ anon ]
...
...
00007f55ee124000 4 4 0 r-xs- az.png
00007fff017ff000 4 4 0 r-x-- [ anon ]
ffffffffff600000 4 0 0 r-x-- [ anon ]
---------------- ------ ------ ------
total kB 7796020 3037264 3023928

这里可以看到很多anon,这些表示这块内存是由mmap分配的。

RSZ是Resident Set Size,常驻内存大小,即进程实际占用的物理内存大小, 在现在这个例子当中,RSZ和实际堆内存占用差了2.3G,这2.3G的内存组成分别为:

查看 JVM 堆各个分区的内存情况

jstat -gcutil [pid]

1
2
3
4
[root@server ~]$ jstat -gcutil 837 1000 20
S0 S1 E O P YGC YGCT FGC FGCT GCT
0.00 80.43 24.62 87.44 98.29 7101 119.652 40 19.719 139.371
0.00 80.43 33.14 87.44 98.29 7101 119.652 40 19.719 139.371

分析 JVM 堆内存中的对象

查看存活的对象统计
jmap -histo:live [pid]

dump 内存
jmap -dump:format=b,file=heapDump [pid]

然后用jhat命令可以参看
jhat -port 5000 heapDump
在浏览器中访问:http://localhost:5000/ 查看详细信息

4. 服务指标

4.1 响应时间(RT)

响应时间是指系统对请求作出响应的时间。直观上看,这个指标与人对软件性能的主观感受是非常一致的,因为它完整地记录了整个计算机系统处理请求的时间。由于一个系统通常会提供许多功能,而不同功能的处理逻辑也千差万别,因而不同功能的响应时间也不尽相同,甚至同一功能在不同输入数据的情况下响应时间也不相同。所以,在讨论一个系统的响应时间时,人们通常是指该系统所有功能的平均时间或者所有功能的最大响应时间。当然,往往也需要对每个或每组功能讨论其平均响应时间和最大响应时间。

对于单机的没有并发操作的应用系统而言,人们普遍认为响应时间是一个合理且准确的性能指标。需要指出的是,响应时间的绝对值并不能直接反映软件的性能的高低,软件性能的高低实际上取决于用户对该响应时间的接受程度。对于一个游戏软件来说,响应时间小于100毫秒应该是不错的,响应时间在1秒左右可能属于勉强可以接受,如果响应时间达到3秒就完全难以接受了。而对于编译系统来说,完整编译一个较大规模软件的源代码可能需要几十分钟甚至更长时间,但这些响应时间对于用户来说都是可以接受的。

4.2 吞吐量(Throughput)

吞吐量是指系统在单位时间内处理请求的数量。对于无并发的应用系统而言,吞吐量与响应时间成严格的反比关系,实际上此时吞吐量就是响应时间的倒数。前面已经说过,对于单用户的系统,响应时间(或者系统响应时间和应用延迟时间)可以很好地度量系统的性能,但对于并发系统,通常需要用吞吐量作为性能指标。

对于一个多用户的系统,如果只有一个用户使用时系统的平均响应时间是t,当有你n个用户使用时,每个用户看到的响应时间通常并不是n×t,而往往比n×t小很多(当然,在某些特殊情况下也可能比n×t大,甚至大很多)。这是因为处理每个请求需要用到很多资源,由于每个请求的处理过程中有许多不走难以并发执行,这导致在具体的一个时间点,所占资源往往并不多。也就是说在处理单个请求时,在每个时间点都可能有许多资源被闲置,当处理多个请求时,如果资源配置合理,每个用户看到的平均响应时间并不随用户数的增加而线性增加。实际上,不同系统的平均响应时间随用户数增加而增长的速度也不大相同,这也是采用吞吐量来度量并发系统的性能的主要原因。一般而言,吞吐量是一个比较通用的指标,两个具有不同用户数和用户使用模式的系统,如果其最大吞吐量基本一致,则可以判断两个系统的处理能力基本一致。

4.3 并发用户数

并发用户数是指系统可以同时承载的正常使用系统功能的用户的数量。与吞吐量相比,并发用户数是一个更直观但也更笼统的性能指标。实际上,并发用户数是一个非常不准确的指标,因为用户不同的使用模式会导致不同用户在单位时间发出不同数量的请求。一网站系统为例,假设用户只有注册后才能使用,但注册用户并不是每时每刻都在使用该网站,因此具体一个时刻只有部分注册用户同时在线,在线用户就在浏览网站时会花很多时间阅读网站上的信息,因而具体一个时刻只有部分在线用户同时向系统发出请求。这样,对于网站系统我们会有三个关于用户数的统计数字:注册用户数、在线用户数和同时发请求用户数。由于注册用户可能长时间不登陆网站,使用注册用户数作为性能指标会造成很大的误差。而在线用户数和同事发请求用户数都可以作为性能指标。相比而言,以在线用户作为性能指标更直观些,而以同时发请求用户数作为性能指标更准确些。

4.4 QPS每秒查询率(Query Per Second)

每秒查询率QPS是对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准,在因特网上,作为域名系统服务器的机器的性能经常用每秒查询率来衡量。对应fetches/sec,即每秒的响应请求数,也即是最大吞吐能力。

从以上概念来看吞吐量和响应时间是衡量系统性能的重要指标,QPS虽然和吞吐量的计量单位不同,但应该是成正比的,任何一个指标都可以含量服务器的并行处理能力。当然Throughput更关心数据量,QPS更关心处理笔数。

4.5 CPU利用率

CPU Load Average < CPU个数 核数 0.7

Context Switch Rate
就是Process(Thread)的切换,如果切换过多,会让CPU忙于切换,也会导致影响吞吐量。《高性能服务器架构 》这篇文章的第2节就是说的是这个问题的。究竟多少算合适?google了一大圈,没有一个确切的解释。Context Switch大体上由两个部分组成:中断和进程(包括线程)切换,一次中断(Interrupt)会引起一次切换,进程(线程)的创建、激活之类的也会引起一次切换。CS的值也和TPS(Transaction Per Second)相关的,假设每次调用会引起N次CS,那么就可以得出

Context Switch Rate = Interrupt Rate + TPS* N

CSR减掉IR,就是进程/线程的切换,假如主进程收到请求交给线程处理,线程处理完毕归还给主进程,这里就是2次切换。也可以用CSR、IR、TPS的值代入公式中,得出每次事物导致的切换数。因此,要降低CSR,就必须在每个TPS引起的切换上下功夫,只有N这个值降下去,CSR就能降低,理想情况下N=0,但是无论如何如果N >= 4,则要好好检查检查。另外网上说的CSR<5000,我认为标准不该如此单一。

这三个指标在 LoadRunner 中可以监控到;另外,在 linux 中,也可以用 vmstat 查看r(Load Arerage),in(Interrupt)和cs(Context Switch)

5. 工具

uptime

dmesg

top
查看进程活动状态以及一些系统状况

vmstat
查看系统状态、硬件和系统信息等

iostat
查看CPU 负载,硬盘状况

sar
综合工具,查看系统状况

mpstat
查看多处理器状况

netstat
查看网络状况

iptraf
实时网络状况监测

tcpdump
抓取网络数据包,详细分析

mpstat
查看多处理器状况

tcptrace
数据包分析工具

netperf
网络带宽工具

dstat
综合工具,综合了 vmstat, iostat, ifstat, netstat 等多个信息

Reference

http://tmq.qq.com/2016/07/it-is-necessary-to-know-the-background-performance-test/
https://www.ibm.com/developerworks/java/library/j-nativememory-linux/
http://www.oracle.com/technetwork/java/javase/index-137495.html
http://www.hollischuang.com/archives/303

1. HBase 简介

HBase是Apache Hadoop的数据库,基于列存储、构建在HDFS上的分布式存储系统,能够对大型数据提供随机、实时的读写访问,是Google的BigTable的开源实现。HBase的目标是存储并处理大型的数据,仅用普通的硬件配置,就能够处理海量数据。

1.1 HBase 的优点

  1. 高可扩展性
    HBase 是真正意义上的线性水平扩展。数据量累计到一定程度(可配置),HBase系统会自动对数据进行水平切分,并分配不同的服务器来管理这些数据。这些数据可以被扩散到上千个普通服务器上。这样一方面可以由大量普通服务器组成大规模集群,来存放海量数据(从几个 TB 到几十 PB 的数据)。另一方面,当数据峰值接近系统设计容量时,可以简单通过增加服务器的方式来扩大容量。这个动态扩容过程无需停机,HBase系统可以照常运行并提供读写服务,完全实现动态无缝无宕机扩容。
  2. 高性能
    HBase 的设计目的之一是支持高并发用户数的高速读写访问。这是通过两方面来实现的。首先数据行被水平切分并分布到多台服务器上,在大量用户访问时,访问请求也被分散到了不同的服务器上,虽然每个服务器的服务能力有限,但是数千台服务器汇总后可以提供极高性能的访问能力。其次,HBase 设计了高效的缓存机制,有效提高了访问的命中率,提高了访问性能。
  3. 高可用性
    HBase 建立在 HDFS 之上。HDFS 提供了数据自动复制和容错的功能。HBase 的日志和数据都存放在 HDFS 上,即使在读写过程中当前服务器出现故障(硬盘、内存、网络等故障),日志也不会丢失,数据都可以从日志中自动恢复。HBase 系统会自动分配其他服务器接管并恢复这些数据。因此一旦成功写入数据,这些数据就保证被持久化并被冗余复制,整个系统的高可用性得到保证。

1.2 数据模型

    • 数据量:一张表可以有数十亿行,上百万列。
    • 最大版本数:通常是3,如果对于更新比较频繁的应用完全可以设置为1,能够快速的淘汰无用数据,对于节省存储空间和提高查询速度有效果。不过这类需求在海量数据领域比较小众。
    • 压缩算法:可以尝试一下最新出炉的snappy算法,相对lzo来说,压缩率接近,压缩效率稍高,解压效率高很多。
    • inmemory:表在内存中存放,一直会被忽略的属性。如果完全将数据存放在内存中,那么hbase和现在流行的内存数据库memorycached和redis性能差距有多少,尚待实测。
    • bloomfilter:根据应用来定,看需要精确到rowkey还是column。不过这里需要理解一下原理,bloomfilter的作用是对一个region下查找记录所在的hfile有用。即如果一个region下的hfile数量很多,bloomfilter的作用越明显。适合那种compaction赶不上flush速度的应用。
  1. 无模式
    每行都有一个可排序的主键和任意多的列,列可以根据需要动态的增加,同一张表中不同的行可以有截然不同的列;

  2. 面向列
    面向列(族)的存储和权限控制,列(族)独立检索;
  3. 稀疏
    对于空(null)的列,并不占用存储空间,表可以设计的非常稀疏;
  4. 数据多版本
    每个单元中的数据可以有多个版本,默认情况下版本号自动分配,是单元格插入时的时间戳;
  5. 数据类型单一
    HBase中的数据都是字符串,没有类型。
  6. 存储单元 Cell
    由{rowkey, colomnFamily:colomnQualifier, version} 确定的唯一单元,存储的数据是byte[]类型的。

2. HBase 的设计与实现

2.1 HBase 的架构


由上图可知,hbase包括Clinet、HMaster、HRegionServer、ZooKeeper组件
各组件功能介绍:

  1. Client
    Client主要通过ZooKeeper与Hbaser和HRegionServer通信,对于管理操作:client向master发起请求,对于数据读写操作:client向regionserver发起请求
  2. ZooKeeper
    zk负责存储root表的地址,也负责存储当前服务的master地址,regsion server也会将自身的信息注册到zk中,以便master能够感知region server的状态,zk也会协调active master,也就是可以提供一个选举master leader,也会协调各个region server的容灾流程
  3. HMaster
    master可以启动多个master,master主要负责table和region的管理工作,响应用户对表的CRUD操作,管理region server的负载均衡,调整region 的分布和分配,当region server停机后,负责对失效的regionn进行迁移操作
  4. HRegionServer
    region server主要负责响应用户的IO请求,并把IO请求转换为读写HDFS的操作

2.2 HBase 的架构详解

https://www.mapr.com/blog/in-depth-look-hbase-architecture#.VdMxvWSqqko

3. HBase, Mysql 的比较

Mysql 是关系型数据库,对于数据量不大(百万级别),强依赖事务的业务,使用Mysql。
HBase 适用于对大数据进行随机、实时访问的场合,支持海量数据,扩展性好。
HBase 不适用的场景:

  • 对分布式事务支持的不好
  • 不支持多表的联合查询
  • 对于复杂查询,需要扫描全表,且不支持索引

4. 设计 HBase 表

4.1 RowKey 的设计

Rowkey唯一原则,必须在设计上保证其唯一性。但是还有几点需要注意的地方:

4.1.1 RowKey 长度的设计

Rowkey是一个二进制码流,可以是任意字符串,最大长度64KB,实际应用中一般为10~100bytes,存为byte[]字节数组。

  1. 定长
    定长的好处是 RowKey 排序时是按字典序且不受不同长度的影响

  2. 不要超过16个字节。
    • 数据的持久化文件 HFile 是按照 KeyValue 存储的,如果 Rowkey 过长比如100个字节,1000万列数据光 Rowkey 就要占用100*1000万=10亿个字节,将近1G数据,这会极大影响 HFile 的存储效率;
    • MemStore 将缓存部分数据到内存,如果 Rowkey 字段过长内存的有效利用率会降低,系统将无法缓存更多的数据,这会降低检索效率。
  3. 16个字节
    目前操作系统是都是64位系统,内存8字节对齐。控制在16个字节,8字节的整数倍利用操作系统的最佳特性。

4.1.2 RowKey 含义的设计

RowKey 虽然是越短越好,但也需要考虑 RowKey 的含义。由于 HBase 是按字典序存储,所以 RowKey 设计的合理可以提高查询效率(因为这会提高 RegionServer 的缓存命中率),并且有意义的 RowKey 也便于在 scan 表的时候确定 startRow 和 stopRow。

  1. RowKey 包含时间
    不要将时间放在二进制码的前面,建议将 RowKey 的高位作为散列字段(或者本身就已经是散列的其他id,例如userId),低位放时间字段。否则最新的数据都集中放在某个 RegionServer,而访问量又都集中在最新的数据上,将会导致 Hotspotting 现象,降低了访问速度,同时也增加了 RegionServer Crash 的概率。
    但考虑到是按字典序存储,如果想让最新的数据在最前面,可以使用 Long.MAX_VALUE – timestamp 作为 RowKey 的一部分。
  2. RowKey 包含多个含义时
    各个含义用某种分隔符分开,比如包含用户,类型,时间三种含义的 RowKey, 可以设计为 userId#type#timestamp,这样如果需要查找某个用户某段时间的数据,scan 时只需要根据 userId 设置 startRow 和 stopRow 即可。

4.1.3 RowKey 性能的设计

RowKey 是按照字典序存储,利用这个排序特点,将经常一起读取或者最近可能被访问到的数据存储到一块可以提高查询效率。

  1. Hotspotting
    It is always advisable not to use sequential row keys, even though you get better scan results. More info here.
    Salting Row Key. To prevent hot spotting on writes, the row key may be “salted” by inserting a leading byte into the row key which is a mod over N buckets of the hash of the entire row key. This ensures even distribution of writes when the row key is a monotonically increasing value (often a timestamp representing the current time).
  2. Length of row key
    For each cell, rowkey details, column family, and qualifier details are stored. So it is always advisable to keep them as shot as possible, mainly because the same information is repeated on large scale.
  3. So whats next
    salt usage and its prefixing will help to distribute the rows among region servers.This can help you.

4.2 ColumnFamily 的设计

4.2.1 ColumnFamily 的长度

The column family and column qualifier names are repeated for each row. Therefore, keep the names as short as possible to reduce the amount of data that HBase stores and reads. For example, use f:q instead of mycolumnfamily:mycolumnqualifier.

4.2.2 ColumnFamily 的数量

On the number of column families
HBase currently does not do well with anything above two or three column families so keep the number of column families in your schema low. Currently, flushing and compactions are done on a per Region basis so if one column family is carrying the bulk of the data bringing on flushes, the adjacent families will also be flushed though the amount of data they carry is small. When many column families the flushing and compaction interaction can make for a bunch of needless i/o loading (To be addressed by changing flushing and compaction to work on a per column family basis). For more information on compactions, see compaction. (具体的细节见第2节)

Try to make do with one column family if you can in your schemas. Only introduce a second and third column family in the case where data access is usually column scoped; i.e. you query one column family or the other but usually not both at the one time.

Where multiple ColumnFamilies exist in a single table, be aware of the cardinality (i.e., number of rows). If ColumnFamilyA has 1 million rows and ColumnFamilyB has 1 billion rows, ColumnFamilyA’s data will likely be spread across many, many regions (and RegionServers). This makes mass scans for ColumnFamilyA less efficient.

建议HBASE列族的数量设置的越少越好。由于HBASE的FLUSHING和压缩是基于REGION的当一个列族所存储的数据达到FLUSHING阀值时,该表的所有列族将同时进行FLASHING操作,这将带来不必要的I/O开销。同时还要考虑到同一个表中不同列族所存储的记录数量的差别,即列族的势。当列族数量差别过大将会使包含记录数量较少的列族的数据分散在多个Region之上,而Region可能是分布是不同的RegionServer上。这样当进行查询等操作系统的效率会受到一定影响。

4.3 Column 的设计

4.3.1 Column 的长度

The column family and column qualifier names are repeated for each row. Therefore, keep the names as short as possible to reduce the amount of data that HBase stores and reads. For example, use f:q instead of mycolumnfamily:mycolumnqualifier.

4.3.2 Column 的数量

Column mapping: one to many
You can map a single HBase entity (row key or a column) to multiple SQL columns. This kind of mapping is called one to many. HBase stores a lot of information for each value. If you stored each SQL column individually, the required storage space would be very large. For the best performance, put columns that are queried together into a single dense HBase column to help reduce the data that is fetched from HBase. A dense column is a single HBase column that maps to multiple SQL columns.

For example, if table T1 has nine columns with 1.5 million rows. and you use a one-to-one mapping, this table requires 522 MB of storage. However, if table T1 uses a one-to-many mapping, the table requires only 276 MB of storage.

5. 读 HBase 的性能

5.1 HBase Pool

Use pool of workers to parallel requests. You may find useful HTablePool class for managing connections in workers.

5.2 批量读

通过调用 HTable.get(Get) 方法可以根据一个指定的 RowKey 获取一行记录,同样 HBase 提供了另一个方法:通过调用 HTable.get(List) 方法可以根据一个指定的 RowKey 列表,批量获取多行记录,这样做的好处是批量执行,只需要一次网络I/O开销,这对于对数据实时性要求高而且网络传输RTT高的情景下可能带来明显的性能提升。

5.3 Scan

  1. Scanner Caching
    hbase.client.scanner.caching配置项可以设置HBase scanner一次从服务端抓取的数据条数,默认情况下一次一条。通过将其设置成一个合理的值,可以减少scan过程中next()的时间开销,代价是 scanner需要通过客户端的内存来维持这些被cache的行记录。
  2. Scan AttributeSelection
    scan时指定需要的Column Family,可以减少网络传输数据量,否则默认scan操作会返回整行所有Column Family的数据。
  3. Close ResultScanner
    通过scan取完数据后,记得要关闭ResultScanner,否则RegionServer可能会出现问题(对应的Server资源无法释放)。

5.4 PrefixFilter

5.4.1 PefixFilter Vs Scan

  • HBase filters - even row filters - are really slow, since in most cases these do a complete table scan, and then filter on those results.
  • Row key range scans however, are indeed much faster - they do the equivalent of a filtered table scan. This is because the row keys are stored in sorted order (this is one of the basic guarantees of HBase, which is a BigTable-like solution), so the range scans on row keys are very fast.

5.4.2 Convert PrefixFilter to Scan

PrefixFilter: abc
Scan ‘mytable’, {STARTROW => ‘abc’, ENDROW => ‘abd’}

6. 如何解决事务

  1. transactions over hbase
    The way HBase works is that locks are held in the regionserver (not in the client) when the Puts are applied to make sure that rows are written in an atomic block but it does not provide snapshot isolation (you need to use something like omid if you want that).

Since HBase does not guarantee any consistency between regions (and each region is hosted at exactly one RegionServer) all MVCC data structures only need to be kept in memory on every region server.

I would probably not use HBase for a use case like this. but if you must you can lock the row, read, update if needed - read more about lock and some of its problems here ngdata.com/hbase-row-locks . Again, I’d try to rethink the scenario for instance, HBase support multiple version so you can update anyway and sort things later (e.g. in a coprocessor that runs after update)
RowLock and associated operations are deprecated in 0.94 and removed in 0.96.issues.apache.org/jira/browse/HBASE-7315 – Matt Ball

  1. hbase checkAndPut
    hbase checkandput performance
    When you use checkAndPut() you do one RPC-call per request. So, you can’t achieve performance more then 1 / rtt requests per second (rtt is Round Trip Time). If you have rtt 1ms between your client and region server, your theoretical maximum is 1000 rps. When using batch operations like put(List) you need a lot less RPC-calls causing performance increase.

Reference

http://blog.linezing.com/2012/03/hbase-performance-optimization/
https://www.ibm.com/support/knowledgecenter/SSPT3X_2.1.2/com.ibm.swg.im.infosphere.biginsights.analyze.doc/doc/bigsql_designhints.html
http://blog.kissdata.com/2014/07/30/hbase-scheme-tips.html
http://blog.chedushi.com/archives/9720
https://www.mapr.com/blog/in-depth-look-hbase-architecture#.VdMxvWSqqko
https://cloud.google.com/bigtable/docs/schema-design
http://www.slideshare.net/alexbaranau/transactions-over-hbase
https://hbase.apache.org/acid-semantics.html

什么是https

也称作HTTP over TLS

什么是SSL/TLS

1994年,NetScape公司设计了SSL协议(Secure Sockets Layer)的1.0版,但是未发布。
1995年,NetScape公司发布SSL 2.0版,很快发现有严重漏洞。
1996年,SSL 3.0版问世,得到大规模应用。
1999年,互联网标准化组织ISOC接替NetScape公司,发布了SSL的升级版TLS 1.0版。
2006年和2008年,TLS进行了两次升级,分别为TLS 1.1版和TLS 1.2版。最新的变动是2011年TLS 1.2的修订版。
TLS 1.0通常被标示为SSL 3.1,TLS 1.1为SSL 3.2,TLS 1.2为SSL 3.3。

为什么要有https

在说HTTPS之前先说说什么是HTTP,HTTP就是我们平时浏览网页时候使用的一种协议。HTTP协议传输的数据都是未加密的,也就是明文的,因此使用HTTP协议传输隐私信息非常不安全。为了保证这些隐私数据能加密传输,于是网景公司设计了SSL(Secure Sockets Layer)协议用于对HTTP协议传输的数据进行加密,从而就诞生了HTTPS。

https保证安全的原理

Client端和Server端如果用非对称加密的算法进行通信肯定是绝对安全的,因为私钥和密钥没有第三方知道。但是这样的问题是性能低下。但是如果用对称加密,很容易泄露密钥,安全性得不到保证。那么https是如何做的呢?
大概原理就是使用非对称加密来交换一个密钥来进行对称加密。这个过程被称为SSL/TSL的四次握手,具体过程如下:

  1. Client端向Server端的443端口发出请求,带上随机数client_random和支持的加密方式列表
  2. Server端返回随机数server_random ,选择的加密方式和服务器证书链
  3. Client端验证这个证书是否合法,如果非法则提示用户是否“继续接受这个不可信的网站”,如果合法则使用证书中的公钥加密premaster secret发送给服务端
  4. Server端使用私钥解密premaster secret,然后通过client_random,server_random 和premaster secret 生成master secret,用于对称加密后续通信内容。
  5. Sever端用master secret加密最终需要返回的网站内容
  6. Client端也用相同的方式生成这个master secret解密收到的消息

master_secret = PRF(pre_master_secret, “master secret”, ClientHello.random + ServerHello.random)[0..47];

随机数为什么要三个?
这是由于SSL/TLS设计,就假设服务器不相信所有的客户端都能够提供完全随机数,假如某个客户端提供的随机数不随机的话,就大大增加了“对话密钥”被破解的风险,所以由三组随机数组成最后的随机数,保证了随机数的随机性,以此来保证每次生成的“对话密钥”安全性。

那么问题来了

  1. 证书的安全性,Client端是如何验证证书合法性的,这个证书第三方无论如何都伪造不了吗?
  2. 对称加密密钥的安全性,生成的master secret密钥第三方为什么拿不到?

要解答这两个问题,首先得弄清楚什么是证书。

为什么证书是安全的?

什么是证书

数字证书就是互联网通讯中标志通讯各方身份信息的一串数字,提供了一种在Internet上验证通信实体身份的方式,数字证书不是数字身份证,而是身份认证机构盖在数字身份证上的一个章或印(或者说加在数字身份证上的一个签名)。它是由权威机构——CA机构,又称为证书授权(Certificate Authority)中心发行的,人们可以在网上用它来识别对方的身份。
数字证书的格式普遍采用的是X.509V3国际标准,一个标准的X.509数字证书包含以下一些内容:

  • 证书的版本信息;
  • 证书的序列号,每个证书都有一个唯一的证书序列号;
  • 证书所使用的签名算法;
  • 证书的发行机构名称,命名规则一般采用X.500格式;
  • 证书的有效期,通用的证书一般采用UTC时间格式,它的计时范围为1950-2049;
  • 证书所有人的名称,命名规则一般采用X.500格式;
  • 证书所有人的公开密钥;
  • 证书发行者对证书的签名。

证书里的公钥的作用?
证书里的签名的作用?
数字证书的签发机构CA,在接收到申请者的资料后进行核对并确定信息的真实有效,然后就会制作一份符合X.509标准的文件。证书中的证书内容包含的持有者信息和公钥等都是由申请者提供的,而数字签名则是CA机构对证书内容进行hash加密后得到的,而这个数字签名就是我们验证证书是否是有可信CA签发的数据。

证书的产生

证书的类型

实际上,我们使用的证书分很多种类型,SSL证书只是其中的一种。证书的格式是由X.509标准定义。SSL证书负责传输公钥,是一种PKI(Public Key Infrastructure,公钥基础结构)证书。
我们常见的证书根据用途不同大致有以下几种:
1、SSL证书,用于加密HTTP协议,也就是HTTPS。
2、代码签名证书,用于签名二进制文件,比如Windows内核驱动,Firefox插件,Java代码签名等等。
3、客户端证书,用于加密邮件。
4、双因素证书,网银专业版使用的USB Key里面用的就是这种类型的证书。
这些证书都是由受认证的证书颁发机构——我们称之为CA(Certificate Authority)机构来颁发,针对企业与个人的不同,可申请的证书的类型也不同,价格也不同。CA机构颁发的证书都是受信任的证书,对于SSL证书来说,如果访问的网站与证书绑定的网站一致就可以通过浏览器的验证而不会提示错误。

证书的安全问题

如果让证书安全,那么就需要让客户端拿到的证书是真正想要的证书,即不能让证书被冒充或者被篡改。
那么如何保证这一点呢?

  1. 如果证书自己有一个id
  2. 证书的这个id无法被伪造
  3. 客户端知道自己想要的证书id是多少

如果做到了这三点就能保证证书的安全性了。上面说提到的id就是证书的数字签名。那么什么是数字签名?

数字签名(digital signature)

数字签名是证书的防伪标签,是将待签名内容通过哈希和私钥加密处理后生成的。目前使用最广泛的 SHA-RSA 数字签名的制作和验证过程如下:

  1. 数字签名的签发。首先是使用哈希函数对待签名内容进行安全哈希,生成数字摘要,然后使用CA自己的私钥对数字摘要进行加密。
  2. 数字签名的校验。使用CA的公钥解密签名,然后使用相同的签名函数对待签名证书内容进行签名并和服务端数字签名里的签名内容进行比较,如果相同就认为校验成功。

签发:待签名内容 -> 哈希 -> 数字摘要 -> CA私钥加密 -> 数字签名
校验:

  • 数字签名 -> CA公钥解密 -> 数字摘要1
  • 待签名内容 -> 哈希 -> 数字摘要2
  • 比较「数字摘要1」和「数字摘要2」是否相等

这里有几点需要说明:

  • 数字签名签发和校验使用的密钥对是 CA 自己的公私密钥,跟证书申请者提交的公钥没有关系。
  • 数字签名的签发过程跟公钥加密的过程刚好相反,即是用私钥加密,公钥解密。
  • 现在大的 CA 都会有证书链,证书链的好处一是安全,保持根 CA 的私钥离线使用。第二个好处是方便部署和撤销,即如果证书出现问题,只需要撤销相应级别的证书,根证书依然安全。
  • 根 CA 证书都是自签名,即用自己的公钥和私钥完成了签名的制作和验证。而证书链上的证书签名都是使用上一级证书的密钥对完成签名和验证的。

那么问题又来了。
CA的私钥和公钥是安全的吗?可以被冒充吗?

CA的安全性

从根CA开始到直接给客户发放证书的各层次CA,都有其自身的密钥对。CA中心的密钥对一般由硬件加密服务器在机器内直接产生,并存储于加密硬件内,或以一定的加密形式存放于密钥数据库内。加密备份于IC卡或其他存储介质中,并以高等级的物理安全措施保护起来。密钥的销毁要以安全的密钥冲写标准,彻底清除原有的密钥痕迹。需要强调的是,根CA密钥的安全性至关重要,它的泄露意味着整个公钥信任体系的崩溃,所以CA的密钥保护必须按照最高安全级 的保护方式来进行设置和管理。

CA的私钥是自己靠上述方法保管的,不对外公开。
CA的公钥是厂商跟浏览器和操作系统合作,把公钥默认装到浏览器或者操作系统环境里。比如firefox 就自己维护了一个可信任的 CA 列表,而chrome 和 IE 使用的是操作系统的 CA 列表。

证书验证失败的原因

1、SSL证书不是由受信任的CA机构颁发的(注意这种情况并不一定说明有SSL劫持发生)
2、证书过期
3、访问的网站域名与证书绑定的域名不一致

至此,可以知道证书在一定程度上是非常安全的,客户端只要收到的证书是合法的,就能很大程度上保证整个会话是安全的。

客户端具体是如何验证SSL证书的

为了抵御这种中间人攻击,SSL证书需要由可信的SSL证书颁发机构颁发,形成一个证书链(比如Gmail的证书链为:最底层为网域 mail.google.com,上一层为Thawte SGC CA证书颁发机构,最顶层为很有名的VeriSign证书颁发机构)。那么,浏览器除了需要验证域和有效期外,还要检查证书链中的上级证书公钥是否有效,上级的上级证书公钥是否有效,直至根证书公钥为止。这样就可以有效避免中间人攻击了,因为根证书公钥都是预装在操作系统中的,黑客如果不是暴力破解,无法得到根证书的私钥。如果黑客自己生成一个私钥,浏览器验证根证书公钥的时候发现无法通过操作系统中预装的公钥加密数据后使用这个私钥进行解密,从而判定这个公钥是无效的。这个方案也是现在https通讯通常的方案。

那么,这个现在所有的浏览器正在使用的https通讯方案就无懈可击了吗?答案仍是否定的。我们可以看到,在后一个方案中,https的安全性需要在证书颁发机构公信力的强有力保障前提下才能发挥作用。如果证书颁发机构在没有验证黑客为mail.google.com的持游者的情况下,给黑客颁发了网域为mail.google.com的证书,那么黑客的中间人攻击又可以顺利实施然而,不验证域名持有者就颁发证书的情况在国外几乎不会发生,但是在国内就不一定了。针对破解目标,国内证书颁发机构WoSign(在此只是举例国内比较有名的证书颁发机构WoSign,并不代表WoSign今后一定会这么做)很有可能为了上级要求颁发了证书给非域名持有者的黑客,从而使得破解目标的Gmail密码被黑客截取。

涉及到的算法

非对称加密算法:RSA,DSA/DSS
对称加密算法:AES,RC4,3DES
HASH算法:MD5,SHA1,SHA256

总结

整个过程是递进的,一步一步了解https安全的原理。

  1. https如何保证安全又高效?
    https使用非对称加密算法来交换对称加密的密钥,最后使用对称加密算法来进行通信。
  2. 如何保证非对称加密时的安全性?
    服务端发送证书来传递非对称加密的公钥。保证了公钥和私钥的保密性。
  3. 客户端怎么知道证书是不是真的?
    客户端根据CA证书的公钥校验证书的数字签名来保证其合法性。
  4. 客户端的CA证书不会被伪造或泄露吗?
    CA证书是默认预装到浏览器和操作系统中的,所以CA证书的公钥是安全的。

Reference

http://op.baidu.com/2015/04/https-s01a01/
https://cipherstuff.wordpress.com/
http://oncenote.com/2014/10/21/Security-1-HTTPS/
http://www.williamlong.info/archives/2058.html
http://www.ruanyifeng.com/blog/2014/02/ssl_tls.html

Problem Description:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution:

Solution1:

Dynamic Programming
Time Complexity: O(n*sqrt(n))
Space: O(n)

Solution2:

Number Theory

  • Legendre’s three-square theorem
  • Lagrange’s four-square theorem

Time Complexity: O(sqrt(n))
Space: O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package com.zane.algorithm.leetcode;
/**
* Author: luojinping
* Date: 15/9/23
* Time: 17:23
* <p/>
* <p/>
* Given a positive integer n, find the least number of perfect square numbers
* (for example, 1, 4, 9, 16, ...) which sum to n.
* For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13,
* return 2 because 13 = 4 + 9.
*/
public class PerfectSquares_279 {
/**
* cannot use greedy algorithm, counter example:
* 98=81+16+1=49+49
* 101=100+1=49+1+49+2
* 7=4+1+1+1
* 12=4+4+4=9+1+1+1
* 思路:
* 使用DP, dp[]数组记录历史使用最少平方数的情况.例如dp[5]=2,记录的是使用最少(1+4)平方数的数量,即2.
*
* @param n
* @return
*/
public int numSquares(int n) {
if (n <= 2) {
return n;
}
// record the least number of perfect numbers when index = i
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
int leastNum = i;
for (int j = 1; j * j <= i; j++) {
leastNum = Math.min(leastNum, dp[i - j * j] + 1);
}
dp[i] = leastNum;
}
return dp[n];
}
private boolean isSquare(int n) {
int sqrt_n = (int) (Math.sqrt(n));
return (sqrt_n * sqrt_n == n);
}
/**
* Legendre's three-square theorem:
* The three squares theorem tells you that a positive integer n can be represented as the sum
* of 3 squares (n = x^2 + y^2 + z^2) if and only if it is not of the form n = 4^a * (8 * b+7)
* <p/>
* Lagrange's four-square theorem:
* Every natural number can be represented as the sum of four integer squares:
* n= a^2 + b^2 + c^2 + d^2
* <p/>
* <p/>
* So the are only 4 possible results: 1, 2, 3, 4.
* <p/>
* Refer:
* https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics
*/
public int numSquaresByMath(int n) {
// If n is a perfect square, return 1.
if (isSquare(n)) {
return 1;
}
// The result is 4 if and only if n can be written in the
// form of 4^k*(8*m + 7). Please refer to
// Legendre's three-square theorem.
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}
// Check whether 2 is the result.
int sqrt_n = (int) (Math.sqrt(n));
for (int i = 1; i <= sqrt_n; i++) {
if (isSquare(n - i * i)) {
return 2;
}
}
return 3;
}
public static void main(String[] args) {
PerfectSquares_279 perfectSquares279 = new PerfectSquares_279();
System.out.println(perfectSquares279.numSquares(4));
System.out.println(perfectSquares279.numSquares(7));
System.out.println(perfectSquares279.numSquares(12));
System.out.println(perfectSquares279.numSquares(61));
System.out.println(perfectSquares279.numSquares(100));
System.out.println(perfectSquares279.numSquares(101));
}
}

Refer:

https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics