问题源于项目开发

最近项目中需要做一个权限管理模块,按照之前同事的做法是在controller层的每个接口调用之前上做逻辑判断，这样做也没有不妥，但是代码重复率太高,而且是体力劳动，so，便有了如题所说的使用spring aop做一个切点来实现通用功能的权限管理，这样也就降低了项目后期开发的可扩展性。

权限管理的代码实现与配置文件

在最小的代码修改程度上，aop无疑是最理想的选择。项目中有各种权限的复合，相对来说逻辑复杂度比较高，所以一步步来。因为权限涉及到的是后端接口的调用所以楼主选择在controller层代码做切面，而切点就是controller中的各个方法块，对于通用访问权限，我们使用execution表达式进行排除。

只读管理员权限的实现及切点选择

对于实现排除通用的controller，楼主采用的是execution表达式逻辑运算。因为只读管理员拥有全局读权限，而对于增删改权限，楼主采用的是使用切点切入是增删改的方法，so，这个时候规范的方法命名就很重要了。对于各种与只读管理员进行复合的各种管理员，我们在代码中做一下特殊判断即可。下面是spring aop的配置文件配置方法。

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

复制代码
<!--非法权限抛出异常的spring mvc的处理-->
<bean class="org.springframework.web.servlet.handler.SimpleMappingExceptionResolver">
    <property name="exceptionMappings">
        <props>
            <prop key="com.thundersoft.metadata.exception.AccessDeniedException">forward:/auth/readOnly</prop>
        </props>
    </property>
</bean>
    
 <bean id="usersPermissionsAdvice"
          class="com.thundersoft.metadata.aop.UsersPermissionsAdvice"/>
    <aop:config>
        <!--定义切面 -->
        <aop:aspect id="authAspect" ref="usersPermissionsAdvice">
            <!-- 定义切入点 (配置在com.thundersoft.metadata.web.controller下所有的类在调用之前都会被拦截) -->
            <aop:pointcut
                    expression="(execution(* com.thundersoft.metadata.web.controller.*.add*(..)) or
                    execution(* com.thundersoft.metadata.web.controller.*.edit*(..)) or
                    execution(* com.thundersoft.metadata.web.controller.*.del*(..)) or
                    execution(* com.thundersoft.metadata.web.controller.*.update*(..)) or
                    execution(* com.thundersoft.metadata.web.controller.*.insert*(..)) or
                    execution(* com.thundersoft.metadata.web.controller.*.modif*(..))) or
                    execution(* com.thundersoft.metadata.web.controller.*.down*(..))) and (
                    !execution(* com.thundersoft.metadata.web.controller.FindPasswordController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.SelfServiceController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.HomeController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.UserStatusController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.DashboardController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.MainController.*(..))))"
                    id="authPointCut"/>
            <!--方法被调用之前执行的 -->
            <aop:before method="readOnly"
                        pointcut-ref="authPointCut"/>
        </aop:aspect>
    </aop:config>

只读管理员权限管理代码实现

上面说了那么多，废话不多说了，下面是对只读权限与各种复合权限进行控制的切面代码实现。

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
111
112

复制代码 /**
     * 对只读管理员以及其复合管理员进行aop拦截判断.
     * @param joinPoint 切入点.
     * @throws IOException
     */
    public void readOnly(JoinPoint joinPoint) throws IOException {

        /**
         * 获取被拦截的方法.
         */
        String methodName = joinPoint.getSignature().getName();

        /**
         * 获取被拦截的对象.
         */
        Object object = joinPoint.getTarget();

        logger.info("权限管理aop,方法名称{}" + methodName);
        HttpServletRequest request =((ServletRequestAttributes) RequestContextHolder.getRequestAttributes()).getRequest();
        HttpServletResponse response =((ServletRequestAttributes) RequestContextHolder.getRequestAttributes()).getResponse();
        String roleFlag = GetLoginUserInfor.getLoginUserRole(request);

        /**
         * 超级管理员
         */
        if (PermissionsLabeled.super_Admin.equals(roleFlag)) {
            return;
        }

        /**
         * 只读管理员做数据更改权限的判断
         */
        if (PermissionsLabeled.reader_Admin.equals(roleFlag)) {
            if (methodName.contains("redirectToLogout")) {
                return;
            }
            logger.error("只读管理员无操作权限!");
            throw new AccessDeniedException("您无权操作！");
        }

        /**
         * 部门管理员,且为只读管理员,
         */
        if (PermissionsLabeled.dept_reader_Admin.equals(roleFlag)) {
            if (object instanceof DepartmentController) {
                return;
            }

            if (object instanceof UserController) {
                if (methodName.contains("addAdmin")) {
                    throw new AccessDeniedException("您无权操作！");
                }

                if (methodName.contains("deleteAdmin")) {
                    throw new AccessDeniedException("您无权操作！");
                }

                if (methodName.contains("updateAdmin")) {
                    throw new AccessDeniedException("您无权操作！");
                }
                return;
            }

            if (object instanceof GroupController) {
                return;
            }
            logger.error("部门管理员,且为只读管理员无操作权限!");
            throw new AccessDeniedException("您无权操作！");
        }

        /**
         * 应用管理员,且为只读管理员
         */
        if (PermissionsLabeled.app_reader_Admin.equals(roleFlag)) {
            if (object instanceof AppController) {
                return;
            }

            if (object instanceof AppPolicyController) {
                return;
            }
            logger.error("应用管理员,且为只读管理员无操作权限!");
            throw new AccessDeniedException("您无权操作！");
        }

        /**
         * 部门管理员,且为应用管理员,且为只读管理员
         */
        if (PermissionsLabeled.dept_app_reader_Admin.equals(roleFlag)) {
            if (object instanceof DepartmentController) {
                return;
            }

            if (object instanceof UserController) {
                return;
            }

            if (object instanceof GroupController) {
                return;
            }

            if (object instanceof AppController) {
                return;
            }

            if (object instanceof AppPolicyController) {
                return;
            }
            logger.error("部门管理员,且为应用管理员,且为只读管理员无操作权限");
            throw new AccessDeniedException("您无权操作！");
        }
    }

具有专门功能的管理员权限控制的切点选择

因为具有专门的管理员权限比较特殊，楼主采用的方式除了通用访问权限之外的controller全切，特殊情况在代码逻辑里面做实现即可。配置文件代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复制代码 <aop:config>
        <!--定义切面 -->
        <aop:aspect id="authAspect" ref="usersPermissionsAdvice">
            <!-- 定义切入点 (配置在com.thundersoft.metadata.web.controller下所有的类在调用之前都会被拦截) -->
            <aop:pointcut
                    expression="(execution(* com.thundersoft.metadata.web.controller.*.*(..)) and (
                    !execution(* com.thundersoft.metadata.web.controller.FindPasswordController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.SelfServiceController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.HomeController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.UserStatusController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.DashboardController.*(..)) and
                    !execution(* com.thundersoft.metadata.web.controller.MainController.*(..))))"
                    id="appAuthPointCut"/>
            <!--方法被调用之前执行的 -->
            <aop:before method="appDeptAuth"
                        pointcut-ref="appAuthPointCut"/>
        </aop:aspect>
    </aop:config>

权限管理的切面代码实现

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

复制代码 /**
     * 对应用管理员以及部门管理员进行aop拦截判断.
     * @param joinPoint 切入点.
     * @throws IOException
     */
    public void appDeptAuth(JoinPoint joinPoint) throws IOException {
        /**
         * 获取被拦截的方法.
         */
        String methodName = joinPoint.getSignature().getName();

        /**
         * 获取被拦截的对象.
         */
        Object object = joinPoint.getTarget();

        logger.info("权限管理aop,方法名称{}",methodName);
        HttpServletRequest request =((ServletRequestAttributes) RequestContextHolder.getRequestAttributes()).getRequest();
        HttpServletResponse response =((ServletRequestAttributes) RequestContextHolder.getRequestAttributes()).getResponse();
        String roleFlag = GetLoginUserInfor.getLoginUserRole(request);

        /**
         * 超级管理员
         */
        if (PermissionsLabeled.super_Admin.equals(roleFlag)) {
            return;
        }

        /**
         * 应用管理员做数据更改权限的判断
         */
        if (PermissionsLabeled.app_Admin.equals(roleFlag)) {
            if (object instanceof AppController) {
                return;
            }

            if (object instanceof AppPolicyController) {
                return;
            }

            logger.error("应用管理员无操作权限");
            throw new AccessDeniedException("您无权操作！");
        } else if (PermissionsLabeled.dept_Admin.equals(roleFlag)) {
            if (object instanceof DepartmentController) {
                return;
            }

            if (object instanceof UserController) {
                return;
            }

            if (object instanceof GroupController) {
                return;
            }
            if ("getAllDepartments".equals(methodName)) {
                return;
            }
            logger.error("应用管理员无操作权限");
            throw new AccessDeniedException("您无权操作！");
        } else {
            return;
        }
    }

自定义权限非法异常代码

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

复制代码
/**
 * @author wuhf0703@thundersoft.com
 * @date 2017/12/12
 */
public class AccessDeniedException extends RuntimeException {

    /**
     * Constructs a <code>AccessDeniedException</code> with the specified message.
     *
     * @param msg the detail message.
     */
    public AccessDeniedException(String msg) {
        super(msg);
    }

    /**
     * Constructs a {@code AccessDeniedException} with the specified message and root cause.
     *
     * @param msg the detail message.
     * @param t root cause
     */
    public AccessDeniedException(String msg, Throwable t) {
        super(msg, t);
    }
}

博客首发链接

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

支持向量机通俗导论（理解SVM的三层境界）

作者：July 。致谢：pluskid、白石、JerryLead。
说明：本文最初写于2012年6月，而后不断反反复复修改&优化，修改次数达上百次，最后修改于2016年11月。
声明：本文于 2012年便早已附上所有参考链接，并注明是篇“学习笔记”，且写明具体参考了pluskid等人的文章。文末2013年的PDF是为证。

前言

动笔写这个支持向量机(support vector machine )是费了不少劲和困难的，原因很简单，一者这个东西本身就并不好懂，要深入学习和研究下去需花费不少时间和精力，二者这个东西也不好讲清楚，尽管网上已经有朋友写得不错了(见文末参考链接)，但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明，我还是想尝试写一下，希望本文在兼顾通俗易懂的基础上，真真正正能足以成为一篇完整概括和介绍支持向量机的导论性的文章。


本文在写的过程中，参考了不少资料，包括《支持向量机导论》、《统计学习方法》及网友pluskid的支持向量机系列等等， 于此，还是一篇学习笔记，只是加入了自己的理解和总结，有任何不妥之处，还望海涵。全文宏观上整体认识支持向量机的概念和用处，微观上深究部分定理的来龙去脉，证明及原理细节，力保逻辑清晰 & 通俗易懂。


同时，阅读本文时建议大家尽量使用chrome等浏览器，如此公式才能更好的显示，再者，阅读时可拿张纸和笔出来，把本文所有定理.公式都亲自推导一遍或者直接打印下来（可直接打印网页版或本文文末附的PDF） 在文稿上演算，从而享受随时随地思考、演算的极致快感。


OK，还是那句话，有任何问题，欢迎任何人随时不吝指正 & 赐教，感谢。

第一层、了解SVM

支持向量机，因其英文名为support vector machine，故一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

1.1、分类标准的起源：Logistic回归

理解SVM，咱们必须先弄清楚一个概念：线性分类器。


给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点，用y表示类别（y可以取 1或者-1，分别代表两个不同的类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyper plane），这个超平面的方程可以表示为（ wT中的 T代表转置）：


                                                        ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/a2418383ac9b1caab2fcbdad2d79363b17004f45495078080af18f4becd0dbb2)


可能有读者对类别取1或-1 有疑问，事实上，这个1或-1的分类标准起源于logistic 回归 。


Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用 logistic函数（或称作sigmoid函数）将自变量映射到(0,1) 上，映射后的值被认为是属于y=1的概率。


假设函数

其中x是n维特征向量，函数g就是logistic函数。     而![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/5a79dbae5254f4aa7ceae738b63bc7c42f95099ef57f101e4e3e923b81d50092)的图像是

可以看到，将无穷映射到了(0,1)。     而假设函数就是特征属于y=1的概率。

从而，当我们要判别一个新来的特征属于哪个类时，只需求![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/374e87fe4485a38a3b30d6947041bebed025f30cea80fc9d1fc98910958a1f77)即可，若![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/374e87fe4485a38a3b30d6947041bebed025f30cea80fc9d1fc98910958a1f77)大于0.5 就是y=1的类，反之属于y=0类。


此外，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/374e87fe4485a38a3b30d6947041bebed025f30cea80fc9d1fc98910958a1f77)只和![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/4a5d6e1cb1d2c8cf0321f53e604e4dcfe65e336d2aff275aa8ccb4652bb4812d)有关，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/d78b965ff2d83938c84e9ccc58cce50075b65637ba5607acb3d4c132666b7d34)>0，那么![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/5a23ddc7e92da6a150d75f96533b5cfa500d7ff9deef59764fb822e14e9db8d1)，而g(z)只是用来映射，真实的类别决定权还是在于 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/eb23196849be2fae16e0e9c7275197c7df95889e61e0845f54176eb543a718f9)。再者，当![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6e44ff75d64f36321fbc858a05cd8f19a39baf659057474cac637061ed96a9e6)时，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/88680a1b444fc892c1f9cdda57bb4860c00545b6a79cb210d011a182ae5398d6)=1，反之![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/14de9425eb9d1fd1b41147b643c2d3a78f9f9203b11073404a6f6915cea044d6)=0 。如果我们只从![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/275888b519e0e880d4a74fb2bf7e611e08778c58ceadb17c286b6365e15b9d61)出发，希望模型达到的目标就是让训练数据中y=1的特征 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/903026cbacd5fe8e353f761bc15a36c2d0c4023e450c9a9070c6b7c3827f1d0d)，而是y=0的特征![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/00ff9933cb2453820267827801350aad7a7208a08db4adfc2f5bb1006646bcb7) 。Logistic回归就是要学习得到![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/9170c479f8768560b6a7f4e7bf4faa045d9e4ceaede2e80aad16b48ccf0fe9ac)，使得正例的特征远大于 0，负例的特征远小于0，而且要在全部训练实例上达到这个目标。


接下来，尝试把logistic回归做个变形。首先，将使用的结果标签y = 0和y = 1替换为y = -1,y = 1，然后将 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/aa602d1b7c12cfd0d0b57cb10003d3f96aacc7ea0a6099b4d359e39fea83bd80)（![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/75bf130c5f1d20f3732745e456b95d5c26f44e64c3cad10e53f8e766cf6ad74f)）中的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/0a438eba7cdd9c4644aa31ededa709d815b412d2f943d5172baecf0e8a966a38)替换为b，最后将后面的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/c116550ead583f17b5adca3f5f4826fe5dfebe19ecde33200f643c1ab1e1b5dd)替换为

)（即)）。如此，则有了。也就是说除了y由y=0变为y=-1外，线性分类函数跟logistic 回归的形式化表示没区别。

进一步，可以将假设函数![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/7b332bca065aec1030046d93554713f70d6224cadad5dbc9104f7327f8573a8b)中的g(z)做一个简化，将其简单映射到y=-1 和y=1上。映射关系如下：

1.2、线性分类的一个例子

下面举个简单的例子。如下图所示，现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是 -1 ，另一边所对应的y全是1。

这个超平面可以用分类函数![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6fc2f4fa6addfee6677f8235e89d11d7a7a34b8fcffda2672d628f3084d8512e)表示，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应  y=1 的数据点，f(x)小于0的点对应y=-1 的点，如下图所示：

注：有的资料上定义特征到结果的输出函数 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/78e4b1eed67163cb86c21ede1b20b9338eaa5447b207bd276a944677c161c337)，与这里定义的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6fc2f4fa6addfee6677f8235e89d11d7a7a34b8fcffda2672d628f3084d8512e) 实质是一样的。为什么？因为无论是![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/78e4b1eed67163cb86c21ede1b20b9338eaa5447b207bd276a944677c161c337)，还是![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6fc2f4fa6addfee6677f8235e89d11d7a7a34b8fcffda2672d628f3084d8512e)，不影响最终优化结果。下文你将看到，当我们转化到优化

)的时候，为了求解方便，会把yf(x)令为1，即yf(x)是y(w^x + b)，还是y(w^x - b)，对我们要优化的式子max1/||w||已无影响。

（有一朋友飞狗来自Mare\_Desiderii，看了上面的定义之后，问道：请教一下SVM functional margin 为![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3b5bce61760f5e8d32cf21714e81d3d1529e7bb24a129b09c306b6ab26cbb35e)=y(wTx+b)=yf(x)中的Y是只取1和-1 吗？y的唯一作用就是确保functional margin的非负性？真是这样的么？当然不是，详情请见本文评论下第43楼）



换言之，在进行分类的时候，遇到一个新的数据点x，将x代入f(x) 中，如果 f(x)小于0则将x的类别赋为-1 ，如果f(x)大于0则将x的类别赋为1。


接下来的问题是，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。

1.3、函数间隔 Functional margin与几何间隔Geometrical margin

在超平面w\*x+b=0 确定的情况下，|w\*x+b|能够表示点x到距离超平面的远近，而**通过观察w\*x+b的符号与类标记y的符号是否一致可判断** **分类是否正确**，所以，可以用(y\*(w\*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。


定义函数间隔（用![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/5b1ba71c0160c9731a218eaebbe498bcba79f063df1ba0a46fa56f94569cb3b9)表示）为：

而超平面(w，b)关于 T中所有样本点(xi，yi) 的函数间隔最小值（其中，x是特征，y是结果标签， i表示第i个样本），便为超平面(w, b)关于训练数据集T 的函数间隔：

= min i (i=1，…n)

但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w 和2b），则函数间隔的值f(x)却变成了原来的2 倍（虽然此时超平面没有改变），所以只有函数间隔还远远不够。


事实上，我们可以对法向量w加些约束条件，从而引出真正定义点到超平面的距离--几何间隔（geometrical margin）的概念。


假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0  ，w 是垂直于超平面的一个向量，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/067c2d4130c5667df6f2a79caf82ff471651496ab2520813f2b8cf73bef820db)为样本x 到超平面的距离，如下图所示： 

根据平面几何知识，有

其中||w||为w的二阶范数（范数是一个类似于模的表示长度的概念），![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/33827acaf8c76c041be399fb875d14956b92652f0dab47d353ab72153cc2087c)是单位向量（一个向量除以它的模称之为单位向量）。 


又由于 

x 0 是超平面上的点，满足
f (x 0 ) =0 ，代入超平面的方程)，可得)，即。

随即让此式![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/bc62e0929373512d9e71c19bc86e28f78a5b16ad821c935fb5f21f985009c257)的两边同时乘以![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b3a65bd5a18ed45c1c6ae399bcd18667ae894d38782c7612fb5b618f4b1ca507)，再根据

和 ，即可算出：

γ

为了得到)的绝对值，令乘上对应的类别 y，即可得出几何间隔（用
表示）的定义：

从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y\*(wx+b) = y\*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。

1.4、最大间隔分类器Maximum Margin Classifier 的定义

对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下图中的Gap的一半 。 

通过由前面的分析可知：函数间隔不适合用来最大化间隔值，因为在超平面固定以后，可以等比例地缩放w的长度和b 的值，这样可以使得![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6fc2f4fa6addfee6677f8235e89d11d7a7a34b8fcffda2672d628f3084d8512e)的值任意大，亦即函数间隔![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3b5bce61760f5e8d32cf21714e81d3d1529e7bb24a129b09c306b6ab26cbb35e)可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/2822ab1f2d54cbe29816fb078f5c258370c9c7dcee52476fab01d54c6c86dd00)，使得在缩放 w和b的时候几何间隔![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f1a77213632be09d8607113f9053ce94011d2a83d6e3dd83af42c4348df05065)的值是不会改变的，它只随着超平面的变动而变动，因此，这是更加合适的一个间隔。换言之，这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。

于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为：

同时需满足一些条件，根据间隔的定义，有

其中，s.t.，即subject to的意思，它导出的是约束条件。



回顾下几何间隔的定义![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/719c809c29612afaeff6de4af2ea75a4641e588a1f99071535555ce1c4625b23)， 可知：如果令函数间隔![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3b5bce61760f5e8d32cf21714e81d3d1529e7bb24a129b09c306b6ab26cbb35e) 等于1（之所以令![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3b5bce61760f5e8d32cf21714e81d3d1529e7bb24a129b09c306b6ab26cbb35e)等于1，是为了方便推导和优化，且这样做对目标函数的优化没有影响，至于为什么，请见本文评论下 第42楼回复 ），则有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f1a77213632be09d8607113f9053ce94011d2a83d6e3dd83af42c4348df05065)  = 1 / ||w||且![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/16b02d3f11cd054dd190dca9e9d26895dcac23fb6d8ed74630ed1d730343ad53)，从而上述目标函数转化成了 

相当于在相应的约束条件![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/16b02d3f11cd054dd190dca9e9d26895dcac23fb6d8ed74630ed1d730343ad53)下，最大化这个1/||w|| 值，而1/||w||便是几何间隔![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f1a77213632be09d8607113f9053ce94011d2a83d6e3dd83af42c4348df05065)。   


如下图所示，中间的实线便是寻找到的最优超平面（Optimal Hyper Plane ），其到两条虚线边界的距离相等，这个距离便是几何间隔![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f1a77213632be09d8607113f9053ce94011d2a83d6e3dd83af42c4348df05065) ，两条虚线间隔边界之间的距离等于2![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f1a77213632be09d8607113f9053ce94011d2a83d6e3dd83af42c4348df05065) ，而虚线**间隔边界上的点则是支持向量**。由于这些支持向量刚好在虚线间隔边界上，所以它们满足![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f98fe3cc9acb35062f8818e0a67baa14835c1163ff4a0aaa3886a317afea4f3a) （还记得我们把 functional margin 定为 1 了吗？上节中：处于方便推导和优化的目的，我们可以令![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3b5bce61760f5e8d32cf21714e81d3d1529e7bb24a129b09c306b6ab26cbb35e) =1 ），而对于所有不是支持向量的点，则显然有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3d7beeda679b2578348a253502f30b7cfe566c234a4c5254fe8250dc2727f7b2)。 

OK，到此为止，算是了解到了SVM的第一层，对于那些只关心怎么用SVM的朋友便已足够，不必再更进一层深究其更深的原理。

第二层、深入SVM

2.1、从线性可分到线性不可分

2.1.1、从原始问题到对偶问题的求解

接着考虑之前得到的目标函数：

由于求![]()![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/dbf7c729c7dbf5599075a13a8724fd02c4b5f26024cc355f8e06cd0784b77c2e)的最大值相当于求![]()![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/291f0a988fcf95432d894c395865ebd80848d20e6cd9992f478f40e77bb7776e)的最小值，所以上述目标函数等价于（w由分母变成分子，从而也有原来的max问题变为min问题，很明显，两者问题等价）：

因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用现成的[QP (Quadratic Programming)](http://en.wikipedia.org/wiki/Quadratic_programming) 优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。


此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable)  的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。


 那什么是拉格朗日对偶性呢？简单来讲，通过给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier）![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c)，定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而 只用一个函数表达式便能清楚的表达出我们的问题）：

然后令

容易验证，当某个约束条件不满足时，例如![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/134187ffe738150b8962631ebff767227b49243371fbe7dd8e35808ec6a1f54b) ，那么显然有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/cbc1173dee766e9e5c4988db92088e9532875bafe7b97e04589731e607e4a68c)（ 只要令![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/2b9ff7b11c10a0f64b297ed80c4b56870867886309dad18bef936cbee30ee368)即可）。而当所有约束条件都满足时，则最优值为 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/1d7433c7cc69f8eb631c41e27ab79a4ec9053af8695c0902c4b03aa31f68ebd5)，亦即最初要最小化的量。 


因此，在要求约束条件得到满足的情况下最小化![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/4be7e808133b515df54f86c3eae03acf26aa541fec4fb58297af1350fd13905b) ，实际上等价于直接最小化 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/d831458fc0a1cb7c88d2fb7e4856f0b678c7af58fad3d7b5053c63a8ce74113c)（当然，这里也有约束条件，就是![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/cf7af9a16700a7553ffc517b07813cabc6063f2bcd76be1d595c7f65e8a2d964)

≥ 0, i= 1, …, n ） ，因为如果约束条件没有得到满足，会等于无穷大，自然不会是我们所要求的最小值。

具体写出来，目标函数变成了： 

这里用![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b4873d508b6beb5869efe871dec6d44b0fd8e3bf506bc50e0d15c2581be063ba)表示这个问题的最优值，且和最初的问题是等价的。如果直接求解，那么一上来便得面对w和b两个参数，而![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/cf7af9a16700a7553ffc517b07813cabc6063f2bcd76be1d595c7f65e8a2d964)又是不等式约束，这个求解过程不好做。不妨把最小和最大的位置交换一下，变成：

交换以后的新问题是原始问题的对偶问题，这个新问题的最优值用![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/709bfc2ec2fec1290d8e3310e3f42963859de075832bda3310b5be1102695c93)来表示。而且有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/709bfc2ec2fec1290d8e3310e3f42963859de075832bda3310b5be1102695c93)≤ ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b4873d508b6beb5869efe871dec6d44b0fd8e3bf506bc50e0d15c2581be063ba)，在满足某些条件的情况下，这两者相等，这个时候就可以通过求解对偶问题来间接地求解原始问题。


换言之，之所以从minmax的原始问题![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b4873d508b6beb5869efe871dec6d44b0fd8e3bf506bc50e0d15c2581be063ba)，转化为 maxmin的对偶问题![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/709bfc2ec2fec1290d8e3310e3f42963859de075832bda3310b5be1102695c93)，一者因为 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/709bfc2ec2fec1290d8e3310e3f42963859de075832bda3310b5be1102695c93)是![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b4873d508b6beb5869efe871dec6d44b0fd8e3bf506bc50e0d15c2581be063ba)的近似解，二者，转化为对偶问题后，更容易求解。


下面可以先求L 对w、 b的极小，再求L 对![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c)的极大。

2.1.2、KKT条件

上文中提到“![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/709bfc2ec2fec1290d8e3310e3f42963859de075832bda3310b5be1102695c93) ≤![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b4873d508b6beb5869efe871dec6d44b0fd8e3bf506bc50e0d15c2581be063ba)在满足某些条件的情况下，两者等价”，~~这所谓的“满足某些条件”就是要满足KKT~~ ~~条件~~。 

勘误：经读者qq_28543029指出，这里的条件不应该是KKT条件，要让两者等价需满足strong duality （强对偶），而后有学者在强对偶下提出了KKT条件，且KKT条件的成立要满足constraint qualifications，而constraint qualifications之一就是Slater条件。所谓Slater 条件，即指：凸优化问题，如果存在一个点x，使得所有等式约束都成立，并且所有不等式约束都严格成立（即取严格不等号，而非等号
），则满足Slater 条件。对于此处，Slater 条件成立，所以d*≤p*可以取等号。

一般地，一个最优化数学模型能够表示成下列标准形式：

其中，f(x)是需要最小化的函数，h(x)是等式约束，g(x)是不等式约束，p和q分别为等式约束和不等式约束的数量。


同时，得明白以下两点：

• 凸优化的概念： 为一凸集， 为一凸函数。凸优化就是要找出一点 ，使得每一 满足
  。
• KKT条件的意义：它是一个非线性规划（Nonlinear Programming）问题能有最优化解法的必要和充分条件。

而KKT条件就是指上面最优化数学模型的标准形式中的最小点 x\*  必须满足下面的条件：

经过论证，我们这里的问题是满足 KKT 条件的 （首先已经满足Slater条件，再者f 和gi也都是可微的，即L对 w和b都可导），因此现在我们便转化为求解第二个问题。


也就是说，原始问题通过满足KKT条件，已经转化成了对偶问题。而求解这个对偶学习问题，分为3个步骤：首先要让L(w ，b，a) 关于 w  和 b 最小化，然后求对![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c)的极大，最后利用 SMO算法求解对偶问题中的拉格朗日乘子。

2.1.3、对偶问题求解的3个步骤

**（1）** 、首先固定*![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c)，*要让 

L 关于
w 和
b 最小化 ，我们分别对w，b求偏导数，即令
∂ L / ∂ w 和
∂ L / ∂ b 等于零（对w求导结果的解释请看本文评论下第45楼回复 ）：

将以上结果代入之前的L

：

得到：

提醒：有读者可能会问上述推导过程如何而来？说实话，其具体推导过程是比较复杂的，如下图所示：![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/85986173d13df563843063d3b9492fc4adbfe72513b965723c2f7ea662b62b4e)


  最后，得到：

如 jerrylead所说：“倒数第4步”推导到“倒数第3步”使用了线性代数的转置运算，由于ai和yi都是实数，因此转置后与自身一样。“倒数第3步”推导到“倒数第2步”使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法运算法则。最后一步是上一步的顺序调整。

L (
从上面的最后一个式子，我们可以看出，此时的拉格朗日函数只包含了一个变量，那就是 )（求出了)便能求出w，和b，由此可见，上文第1.2节提出来的核心问题：分类函数也就可以轻而易举的求出来了 ）。

**（2）** 、求对 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c) 的极大 ， 即是关于对偶问题的最优化问题。 经过上面第一个步骤的求w和b，得到的拉格朗日函数式子已经没有了变量w，b，只有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c)。从上面的式子得到： 

这样，求出了![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/cf7af9a16700a7553ffc517b07813cabc6063f2bcd76be1d595c7f65e8a2d964) ![]()，根据![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/4b1f76c740671f5aca83fb84b1fff07e10141955da48d36da414dce03efc088d)， ![]()即可求出w，然后通过![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/d65f856e09e9051f763e6535d1d035ec6d76efbcdd2b7cf66d2f08b40adda6f1)， 即可求出b，最终得出分离超平面和分类决策函数。
 **（3）**在求得L(w, b, a) 关于 w  和 b 最小化，以及对![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/988fe6087724d0f8bef4cc183a11ffd2b0e915af9800be06fd33ba3f2421596c)的极大之后，最后一步则可以利用 SMO算法求解对偶问题中的拉格朗日乘子

。

上述式子要解决的是在参数![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6193c31279e93e8eef696facebfae55cdef16c90ee96f58e0375d518c51d936e)![]()上求最大值W的问题，至于

))和)都是已知数。要了解这个SMO算法是如何推导的，请跳到下文第3.5节、SMO算法。 到目前为止，我们的 SVM 还比较弱，只能处理线性的情况，下面我们将引入核函数，进而推广到非线性分类问题。

2.1.5、线性不可分的情况

OK，为过渡到下节2.2节所介绍的核函数，让我们再来看看上述推导过程中得到的一些有趣的形式。首先就是关于我们的 hyper plane ，对于一个数据点 

x 进行分类，实际上是通过把
x 带入到算出结果然后根据其正负号来进行类别划分的。而前面的推导中我们得到

因此**分类函数**为：

这里的形式的有趣之处在于，对于新点 *x*的预测，只需要计算它与训练数据点的内积即可（ ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/8cc81633d0af8f62ac6452b08616f7319245eb5d83cf13addf9acc36b6185713)表示向量内积），这一点至关重要，是之后使用 Kernel 进行非线性推广的基本前提。此外，所谓 Supporting Vector

也在这里显示出来——事实上，所有非Supporting Vector 所对应的系数都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。

为什么非支持向量对应的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b88ea62f2c5ecac4bcbe23cded66b254f7bb19e49e07b37cc168ba07919600c5)等于零呢？直观上来理解的话，就是这些“后方”的点——正如我们之前分析过的一样，对超平面是没有影响的，由于分类完全有超平面决定，所以这些无关的点并不会参与分类问题的计算，因而也就不会产生任何影响了。


回忆一下我们2.1.1节中通过 Lagrange multiplier得到的目标函数：

注意到如果 

x i 是支持向量的话，上式中红颜色的部分是等于 0 的（因为支持向量的 functional margin 等于 1 ），而对于非支持向量来说，functional margin 会大于 1 ，因此红颜色部分是大于零的，而又是非负的，为了满足最大化，
必须等于 0 。这也就是这些非Supporting Vector 的点的局限性。

从1.5节到上述所有这些东西，便得到了一个maximum margin hyper plane classifier，这就是所谓的支持向量机（Support Vector Machine）。当然，**到目前为止，我们的 SVM 还比较弱，只能处理线性的情况**，不过，在得到了对偶dual 形式之后，通过**Kernel 推广到非线性**的情况就变成了一件非常容易的事情了( 相信，你还记得本节开头所说的：“通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题”

)。

2.2、核函数Kernel

2.2.1、特征空间的隐式映射：核函数

事实上，大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在。在上文中，我们已经了解到了SVM处理线性可分的情况，那对于非线性的数据SVM咋处理呢？对于非线性的情况，SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。


具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。如图7-7 所示，一堆数据在二维空间无法划分，从而映射到三维空间里划分：

而在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：

这里*ϕ*：X->F是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：

1. 首先使用一个非线性映射将数据变换到一个特征空间F，

   2. 然后在特征空间使用线性学习器分类。

      而由于对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：

如果有一种方式可以**在特征空间中直接计算内积〈φ(xi · φ(x)** **〉**，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，**这样直接计算法的方法称为核函数方法：**     核是一个函数K，对所有x，z(-X，满足![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/61ce2d20edc90fec0c0cf9924d51aff41f00d0cfc37825ecb2c676be02a436a2)，这里φ是从X到内积特征空间F的映射。

2.2.2、核函数：如何处理非线性数据

来看个核函数的例子。如下图所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时咱们该如何把这两类数据分开呢( 下文将会有一个相应的三维空间图)？

事实上，上图所述的这个数据集，是用两个半径不同的圆圈加上了少量的噪音生成得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用 

X 1 和
X 2 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：

注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 

Z 1 = X 1 ,
Z 2 = X 2 1 ,
Z 3 = X 2 ,
Z 4 = X 2 2 ,
Z 5 = X 1 X 2 ，那么显然，上面的方程在新的坐标系下可以写作：

关于新的坐标 

Z ，这正是一个 hyper plane 的方程！也就是说，如果我们做一个映射
ϕ :R 2 → R 5 ，将
X 按照上面的规则映射为
Z ，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。

再进一步描述 Kernel 的细节之前，不妨再来看看这个例子映射过后的直观例子。当然，你我可能无法把 5 维空间画出来，不过由于我这里生成数据的时候就是用了特殊的情形，具体来说，我这里的超平面实际的方程是这个样子（圆心在 

X 2 轴上的一个正圆）：

因此我只需要把它映射到 

Z 1 = X 2 1 ,
Z 2 = X 2 2 ,
Z 3 = X 2 这样一个三维空间中即可，下图即是映射之后的结果，将坐标轴经过适当的旋转，就可以很明显地看出，数据是可以通过一个平面来分开的( pluskid： 下面的gif 动画，先用 Matlab 画出一张张图片，再用 Imagemagick 拼贴成 )：

核函数相当于把原来的分类函数：

映射成：

而其中的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b88ea62f2c5ecac4bcbe23cded66b254f7bb19e49e07b37cc168ba07919600c5)可以通过求解如下 dual 问题而得到的：

这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射

，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上没有这么简单！其实刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到
19 维的新空间，这个数目是呈爆炸性增长的，这给
的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要 Kernel 出马了。

不妨还是从最开始的简单例子出发，设两个向量![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/c160f58185bf37762ceccd3379ce14786451ad6d95d418ac43714bc00e9ca626)和 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/75c42ad1742be3cd878d7683fb5bbeb42e3ed2a35982c670bdef230872d2356f)，而![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/751736dbaa45c7062d9f1dceb5d706076dd5c27db6b9d697c7fd1296500bc1ad)即是到前面说的五维空间的映射，因此映射过后的内积为：

    （公式说明：上面的这两个推导过程中，所说的前面的五维空间的映射，这里说的前面便是文中2.2.1节的所述的映射方式，回顾下之前的映射规则，再看那第一个推导，其实就是计算x1，x2各自的内积，然后相乘相加即可，第二个推导则是直接平方，去掉括号，也很容易推出来）


另外，我们又注意到：

二者有很多相似的地方，实际上，我们只要把某几个维度线性缩放一下，然后再加上一个常数维度，具体来说，上面这个式子的计算结果实际上和映射

之后的内积![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3c6d775523efa3e6a6fadc0d76b1f92c57585c5d8752afcf85d1337a69c5a203)的结果是相等的，那么区别在于什么地方呢？

1. 一个是映射到高维空间中，然后再根据内积的公式进行计算；
2. 而另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。

（公式说明：上面之中，最后的两个式子，第一个算式，是带内积的完全平方式，可以拆开，然后，通过凑一个得到，第二个算式，也是根据第一个算式凑出来的）


回忆刚才提到的映射的维度爆炸，在前一种方法已经无法计算的情况下，后一种方法却依旧能从容处理，甚至是无穷维度的情况也没有问题。


我们把这里**的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数** (Kernel Function) ，例如，在刚才的例子中，我们的核函数为：

核函数能**简化映射空间中的内积运算**——刚好“碰巧”的是，在我们的 **SVM 里需要计算的地方数据向量总是以内积的形式出现**的。对比刚才我们上面写出来的式子，现在我们的**分类函数**为：

其中

由如下 dual 问题计算而得：

这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的！当然，因为我们这里的例子非常简单，所以我可以手工构造出对应于 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/751736dbaa45c7062d9f1dceb5d706076dd5c27db6b9d697c7fd1296500bc1ad)的核函数出来，如果对于任意一个映射，想要构造出对应的核函数就很困难了。

2.2.3、几个核函数

通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），例如：

• 多项式核，显然刚才我们举的例子是这里多项式核的一个特例（R = 1，d = 2）。虽然比较麻烦，而且没有必要，不过这个核所对应的映射实际上是可以写出来的，该空间的维度是 ，其中
  是原始空间的维度。
• 高斯核，这个核就是最开始提到过的会将原始空间映射为无穷维空间的那个家伙。不过，如果 )选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数
  ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：
  
• 线性核，这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了( 意思是说，咱们有的时候，写代码，或写公式的时候，只要写个模板或通用表达式，然后再代入不同的核，便可以了，于此，便在形式上统一了起来，不用再分别写一个线性的，和一个非线性的)。

2.2.4、核函数的本质

上面说了这么一大堆，读者可能还是没明白核函数到底是个什么东西？我再简要概括下，即以下三点：

1. 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去(如上文2.2节最开始的那幅图所示，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的)；
   2. 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的(如上文中19维乃至无穷维的例子)。那咋办呢？
   3. 此时，核函数就隆重登场了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。

最后引用[这里](http://www.yaksis.com/posts/why-use-svm.html)的一个例子举例说明下核函数解决非线性问题的直观效果。


假设现在你是一个农场主，圈养了一批羊群，但为预防狼群袭击羊群，你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢？你很可能需要依据牛群和狼群的位置建立一个“分类器”，比较下图这几种不同的分类器，我们可以看到SVM完成了一个很完美的解决方案。

这个例子从侧面简单说明了SVM使用非线性分类器的优势，而逻辑模式以及决策树模式都是使用了直线方法。

OK，不再做过多介绍了，对核函数有进一步兴趣的，还可以看看[此文](http://www.cnblogs.com/vivounicorn/archive/2010/12/13/1904720.html) 。

2.3、使用松弛变量处理 outliers 方法

在本文第一节最开始讨论支持向量机的时候，我们就假定，数据是线性可分的，亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，在上文2.2节使用 Kernel 方法对原来的线性 SVM 进行了推广，使得非线性的的情况也能处理。虽然通过映射

将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。

例如可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier ，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。例如下图：

用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。


为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的 ~~超平面~~ 蓝色间隔边界上，而不会使得超平面发生变形了。


插播下一位读者@Copper\_PKU的理解：**“**换言之，在有松弛的情况下outline点也属于支持向量SV，同时，对于不同的支持向量，拉格朗日参数的值也不同，如此篇论文《Large Scale Machine Learning》中的下图所示：

对于远离分类平面的点值为0；对于边缘上的点值在[0, 1/L]之间，其中，L为训练数据集个数，即数据集大小；对于outline数据和内部的数据值为1/L。更多请参看本文文末参考条目第51条。 **”** 


OK，继续回到咱们的问题。我们，原来的约束条件为：

现在考虑到outlier问题，约束条件变成了：

其中![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/fe2b7d821643380973b4c9dd00148e7cb8bba54bf19c2088a76d570869f145d2)称为松弛变量 (slack variable) ，对应数据点![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/084f0cb82a17aec0187ee43b52df8c070cbc15e49f0899d4a6969d40f64b48b9)允许偏离的 functional margin 的量。当然，如果我们运行![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/413aa8abe3e670e749ee49546f995b6866dd364334d9cf2413ef6779a0fa292c)任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/413aa8abe3e670e749ee49546f995b6866dd364334d9cf2413ef6779a0fa292c)的总和也要最小：

其中

是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中
是需要优化的变量（之一），而
是一个事先确定好的常量。完整地写出来是这个样子：

用之前的方法将限制或约束条件加入到目标函数中，得到新的拉格朗日函数，如下所示：

分析方法和前面一样，转换为另一个问题之后，我们先让 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/1b40b4ee6963ab7d76d8c70ee2d3c31679b90ce1d4b80caa7d4e1f33db3eb18a)针对![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/2d01ee491c1cb5ee874fc896cf65302da36f2b10d21d8f3dd2dd25953495fddf)、

)和最小化：

将 

带回
并化简，得到和原来一样的目标函数：

不过，由于我们得到![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/d2c08e54e6059f93e6f2a4c54059c31466db9ee406c8f93a8254dcc41328840d)而又有 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b5be67f263dbfdccfbecdfb9d6a56e55c30c7877514144695ea30832c1097b71)（作为 Lagrange multiplier 的条件），因此有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/f5d1819bcf8e921d99638084b8883257d18093b5c3576329c1a3610d22805180)，所以整个 dual 问题现在写作：

把前后的结果对比一下（错误修正：图中的Dual formulation中的Minimize应为maxmize）：

可以看到唯一的区别就是现在 dual variable  ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3adafc723dc4330772a005ff01ddf56ee7dc789dce7511f364d697759556fda0) 多了一个上限

。而 Kernel 化的非线性形式也是一样的，只要把)换成即可。这样一来，一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。
行文至此，可以做个小结，不准确的说，SVM它本质上即是一个分类方法，用w^T+b定义分类函数，于是求w、b，为寻最大间隔，引出1/2||w||^2，继而引入拉格朗日因子，化为对拉格朗日乘子a的求解（求解过程中会涉及到一系列最优化或凸二次规划等问题），如此，求w.b与求a等价，而a的求解可以用一种快速学习算法SMO，至于核函数，是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。

OK，理解到这第二层，已经能满足绝大部分人一窥SVM原理的好奇心，然对于那些想在证明层面理解SVM的则还很不够，但进入第三层理解境界之前，你必须要有比较好的数理基础和逻辑证明能力，不然你会跟我一样，吃不少苦头的。

第三层、证明SVM

说实话，凡是涉及到要证明的东西.理论，便一般不是怎么好惹的东西。绝大部分时候，看懂一个东西不难，但证明一个东西则需要点数学功底，进一步，证明一个东西也不是特别难，难的是从零开始发明创造这个东西的时候，则显艰难( 因为任何时代，大部分人的研究所得都不过是基于前人的研究成果，前人所做的是开创性工作，而这往往是最艰难最有价值的，他们被称为真正的先驱。牛顿也曾说过，他不过是站在巨人的肩上。你，我则更是如此)。


正如陈希孺院士在他的著作《数理统计学简史》的第4章、最小二乘法中所讲：在科研上诸多观念的革新和突破是有着很多的不易的，或许某个定理在某个时期由某个人点破了，现在的我们看来一切都是理所当然，但在一切没有发现之前，可能许许多多的顶级学者毕其功于一役，耗尽一生，努力了几十年最终也是无功而返。


话休絮烦，要证明一个东西先要弄清楚它的根基在哪，即构成它的基础是哪些理论。OK，以下内容基本是上文中未讲到的一些定理的证明，包括其背后的逻辑、来源背景等东西，还是读书笔记。

本部分导述

• 3.1节线性学习器中，主要阐述感知机算法；
• 3.2节非线性学习器中，主要阐述mercer定理；
• 3.3节、损失函数；
• 3.4节、最小二乘法；
• 3.5节、SMO算法；
• 3.6节、简略谈谈SVM的应用；

3.1、线性学习器

3.1.1、感知机算法

这个感知机算法是1956年提出的，年代久远，依然影响着当今，当然，可以肯定的是，此算法亦非最优，后续会有更详尽阐述。不过，有一点，你必须清楚，这个算法是为了干嘛的：不断的训练试错以期寻找一个合适的超平面( 是的，就这么简单)。 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/240932398ccf73bf65cee055c04095bc6bfd29f8c82091fab00396f2255c6b70)     下面，举个例子。如下图所示，凭我们的直觉可以看出，图中的红线是最优超平面，蓝线则是根据感知机算法在不断的训练中，最终，若蓝线能通过不断的训练移动到红线位置上，则代表训练成功。

既然需要通过不断的训练以让蓝线最终成为最优分类超平面，那么，到底需要训练多少次呢？Novikoff定理告诉我们当间隔是正的时候感知机算法会在有限次数的迭代中收敛，也就是说Novikoff定理证明了感知机算法的收敛性，即能得到一个界，不至于无穷循环下去。

• Novikoff定理：如果分类超平面存在, 仅需在序列)上迭代几次，在界为的错误次数下就可以找到分类超平面，算法停止。

  这里)，为扩充间隔。根据误分次数公式可知,
  迭代次数与对应于扩充(包括偏置)权重的训练集的间隔有关。 顺便再解释下这个所谓的扩充间隔， )即为样本到分类间隔的距离，即从引出的最大分类间隔。OK，还记得上文第1.3.2节开头的内容么？如下： “

在给出几何间隔的定义之前，咱们首先来看下，如上图所示，对于一个点 

x ，令其垂直投影到超平面上的对应的为
x 0 ，由于
w 是垂直于超平面的一个向量，为样本x到分类间隔的距离，我们有

”

然后后续怎么推导出最大分类间隔请回到本文第一、二部分，此处不重复板书。     同时有一点得注意：感知机算法虽然可以通过简单迭代对线性可分数据生成正确分类的超平面，但不是最优效果，那怎样才能得到最优效果呢，就是上文中第一部分所讲的寻找最大分类间隔超平面。此外，Novikoff定理的证明请见

这里。

3.2、非线性学习器

3.2.1、Mercer定理

Mercer定理  ：如果函数K是![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/15cfabfdfd21f55cd42fc40b00f7a0fa63e4027a54d1061c96618ec588e4f0ae)上的映射（也就是从两个n维向量映射到实数域）。那么如果K是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例

，其相应的核函数矩阵是对称半正定的。 要理解这个Mercer 定理，先要了解什么是半正定矩阵，要了解什么是半正定矩阵，先得知道什么是正定矩阵（矩阵理论博大精深，关于矩阵推荐我正在看的一本《矩阵分析与应用》） 。然后这里有一个此定理的证明
，可以看下。 正如@Copper_PKU所说：核函数在SVM的分类效果中起了重要的作用，最后这里有个tutorial可以看看。

3.3 、损失函数

在本文1.0节有这么一句话“支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。”但初次看到的读者可能并不了解什么是结构化风险，什么又是经验风险。要了解这两个所谓的“风险”，还得又从监督学习说起。 


监督学习实际上就是一个经验风险或者结构风险函数的最优化问题。风险函数度量平均意义下模型预测的好坏，模型每一次预测的好坏用损失函数来度量。它从假设空间F中选择模型f作为决策函数，对于给定的输入X，由f(X)给出相应的输出Y，这个输出的预测值f(X)与真实值Y可能一致也可能不一致，用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。


常用的损失函数有以下几种（基本引用自《统计学习方法》）：

  ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/879ba5ef7cc3e8b7cc0ace017aa4d6302a73fc3af2cdca482bcb2ee92fe6b823)


如此，SVM有第二种理解，即最优化+损失最小，或如@夏粉\_百度所说“可从损失函数和优化算法角度看SVM，boosting，LR等算法，可能会有不同收获”。


OK，关于更多统计学习方法的问题，请参看[此文](http://blog.csdn.net/qll125596718/article/details/8351337)。


关于损失函数，如下文读者评论中所述：可以看看张潼的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性，优化这些损失函数得到的分类器可以看作是后验概率的“代理”。 此外，张潼还有另外一篇论文《Statistical analysis of some multi-category

large margin classification methods》，在多分类情况下margin loss的分析，这两篇对Boosting和SVM使用的损失函数分析的很透彻。

3.4 、最小二乘法

3.4.1、什么是最小二乘法？

既然本节开始之前提到了最小二乘法，那么下面引用《正态分布的前世今生》里的内容稍微简单阐述下。


我们口头中经常说：一般来说，平均来说。如平均来说，不吸烟的健康优于吸烟者，之所以要加“平均”二字，是因为凡事皆有例外，总存在某个特别的人他吸烟但由于经常锻炼所以他的健康状况可能会优于他身边不吸烟的朋友。而最小二乘法的一个最简单的例子便是算术平均。


最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。用函数表示为：

使误差「所谓误差，当然是观察值与实际真实值的差量」平方和达到最小以寻求估计值的方法，就叫做最小二乘法，用最小二乘法得到的估计，叫做最小二乘估计。当然，取平方和作为目标函数只是众多可取的方法之一。

最小二乘法的一般形式可表示为：

有效的最小二乘法是勒让德在 1805 年发表的，基本思想就是认为测量中有误差，所以所有方程的累积误差为

我们求解出导致累积误差最小的参数即可：

勒让德在论文中对最小二乘法的优良性做了几点说明：

• 最小二乘使得误差平方和最小，并在各个方程的误差之间建立了一种平衡，从而防止某一个极端误差取得支配地位
• 计算中只要求偏导后求解线性方程组，计算过程明确便捷
• 最小二乘可以导出算术平均值作为估计值

对于最后一点，从统计学的角度来看是很重要的一个性质。推理如下：假设真值为 

θ ,
x 1 , ⋯, x n 为n次测量值, 每次测量的误差为
e i = x i − θ ，按最小二乘法，误差累积为

求解![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/008a21f95d4b91d074fd4fcff7c17bd7472613f8bd88826bcc435b2bab9401e1) 使![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/22167dddd9a9b2511e750e150c39f036b6bfcbe47061da032405fc9a6315999e)达到最小，正好是算术平均

。

由于算术平均是一个历经考验的方法，而以上的推理说明，算术平均是最小二乘的一个特例，所以从另一个角度说明了最小二乘方法的优良性，使我们对最小二乘法更加有信心。


最小二乘法发表之后很快得到了大家的认可接受，并迅速的在数据分析实践中被广泛使用。不过历史上又有人把最小二乘法的发明归功于高斯，这又是怎么一回事呢。高斯在1809年也发表了最小二乘法，并且声称自己已经使用这个方法多年。高斯发明了小行星定位的数学方法，并在数据分析中使用最小二乘方法进行计算，准确的预测了谷神星的位置。


说了这么多，貌似跟本文的主题SVM没啥关系呀，别急，请让我继续阐述。本质上说，最小二乘法即是一种参数估计方法，说到参数估计，咱们得从一元线性模型说起。

3.4.2、最小二乘法的解法

什么是一元线性模型呢？ 请允许我引用[这里](http://blog.csdn.net/qll125596718/article/details/8248249)的内容，先来梳理下几个基本概念：

• 监督学习中，如果预测的变量是离散的，我们称其为分类（如决策树，支持向量机等），如果预测的变量是连续的，我们称其为回归。

  • 回归分析中，如果只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。

  • 如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。

  • 对于二维空间线性是一条直线；对于三维空间线性是一个平面，对于多维空间线性是一个超平面…

    对于一元线性回归模型, 假设从总体中获取了n组观察值（X1，Y1），（X2，Y2）， …，（Xn，Yn）。对于平面中的这n个点，可以使用无数条曲线来拟合。要求样本回归函数尽可能好地拟合这组值。综合起来看，这条直线处于样本数据的中心位置最合理。 选择最佳拟合曲线的标准可以确定为：使总的拟合误差（即总残差）达到最小。有以下三个标准可以选择：

1. 用“残差和最小”确定直线位置是一个途径。但很快发现计算“残差和”存在相互抵消的问题。

   2. 用“残差绝对值和最小”确定直线位置也是一个途径。但绝对值的计算比较麻烦。

   3. 最小二乘法的原则是以“残差平方和最小”确定直线位置。 用最小二乘法除了计算比较方便外，得到的估计量还具有优良特性。这种方法对异常值非常敏感。

      最常用的是普通最小二乘法（ Ordinary Least Square，OLS）：所选择的回归模型应该使所有观察值的残差平方和达到最小，即采用平方损失函数。 　 我们定义样本回归模型为：

其中ei为样本（Xi, Yi）的误差。     接着，定义平方损失函数Q：

则通过Q最小确定这条直线，即确定 ![]()![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/3067edb8d9ed36e1ca57f856014ecd354b0a5dd904a288b78dabb1eaa88a062e) ，以

为变量，把它们看作是Q的函数，就变成了一个求极值的问题，可以通过求导数得到。
求Q对两个待估参数的偏导数：

根据数学知识我们知道，函数的极值点为偏导为0的点。        解得：

 这就是最小二乘法的解法，就是求得平方损失函数的极值点。自此，你看到求解最小二乘法与求解SVM问题何等相似，尤其是定义损失函数，而后通过偏导求得极值。
OK，更多请参看陈希孺院士的《数理统计学简史》的第4章、最小二乘法。

3.5、SMO算法

在上文中，我们提到了求解对偶问题的序列最小最优化SMO算法，但并未提到其具体解法。首先看下最后悬而未决的问题：

等价于求解： 

1998年，Microsoft Research的John C. Platt在[论文](http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf) 《Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines》中提出针对上述问题的解法：SMO算法，它很快便成为最快的二次规划优化算法，特别是在针对线性SVM和数据稀疏时性能更优。


接下来，咱们便参考John C. Platt的[这篇](http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf)文章来看看SMO的解法是怎样的。

3.5.1、SMO算法的推导

咱们首先来定义特征到结果的输出函数：

注：这个u与我们之前定义的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6fc2f4fa6addfee6677f8235e89d11d7a7a34b8fcffda2672d628f3084d8512e)实质是一样的。


接着，重新定义下咱们原始的优化问题，权当重新回顾，如下：

求导得到：

代入![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/78e4b1eed67163cb86c21ede1b20b9338eaa5447b207bd276a944677c161c337)中，可得![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/1778be295f9ef1fe70f35cd1c96ee0cf07d7af39bfad360f153ead10c1a3e2ed)。


通过引入拉格朗日乘子转换为对偶问题后，得：

s.t：

且

注：这里得到的min函数与我们之前的max函数实质也是一样，因为把符号变下，即由min转化为max的问题，且yi也与之前的 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/72cc1277fb038576a66e861cc5ca35f366688f4172d24d6bd3015bc665cb60ba)等价，yj亦如此。

 经过加入松弛变量![]()后，模型修改为：

从而最终我们的问题变为：

下面要解决的问题是：在![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/275a0ec1b013264bc156a245b258286c32a994f96a6cfc21193b2b22e705ba7a)上求上述目标函数的最小值。为了求解这些乘子，每次从中任意抽取两个乘子![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/344706b6be0aa929a2af8996e5ed38f05da9f7f665d9bc36e1d63bd2f87a056a)和![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)，然后固定![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/344706b6be0aa929a2af8996e5ed38f05da9f7f665d9bc36e1d63bd2f87a056a)和 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)以外的其它乘子![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/7321adc2e94969d2977f326cddae9e21ddb2b820eae2691367d5fc5cebbb5ee5)，使得目标函数只是关于![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/344706b6be0aa929a2af8996e5ed38f05da9f7f665d9bc36e1d63bd2f87a056a)和

的函数。这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求解子问题，最终达到求解原问题的目的。

而原对偶问题的子问题的目标函数可以表达为：

其中 

为了解决这个子问题，首要问题便是每次如何选取![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/344706b6be0aa929a2af8996e5ed38f05da9f7f665d9bc36e1d63bd2f87a056a)和 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)。实际上，其中一个乘子是违法KKT条件最严重的，另外一个乘子则由另一个约束条件选取。


根据KKT条件可以得出目标函数中![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/cf7af9a16700a7553ffc517b07813cabc6063f2bcd76be1d595c7f65e8a2d964)取值的意义：

这里的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/cf7af9a16700a7553ffc517b07813cabc6063f2bcd76be1d595c7f65e8a2d964)还是拉格朗日乘子：  

1. 对于第1种情况，表明是正常分类，在间隔边界内部（我们知道正确分类的点 ）；

2. 对于第2种情况，表明了是支持向量，在间隔边界上；

3. 对于第3种情况，表明了是在两条间隔边界之间；

   而最优解需要满足KKT条件，即上述3个条件都得满足，以下几种情况出现将会出现不满足：

• )<=1但是<C则是不满足的，而原本
  =C

• >=1但是 >0则是不满足的，而原本
  =0

• =1但是 =0或者 =C则表明不满足的，而原本应该是0< <C

  也就是说，如果存在不满足KKT条件的)，那么需要更新这些)，这是第一个约束条件。此外，更新的同时还要受到第二个约束条件的限制，即。 因此，如果假设选择的两个乘子)和)，它们在更新之前分别是)、，更新之后分别是
  )、，那么更新前后的值需要满足以下等式才能保证和为0的约束：

其中，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/af40efb3556aa3733bec40c12f0b72e32cfd3504ee6a1c72163566d952a90b03)是常数。  
 两个因子不好同时求解，所以可先求第二个乘子![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)的解（ ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/601e9f5f2f5b37262e7e222015ab6db34abe735f04ed5c93fec7aa32306af8e6)），得到![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)的解（

)）之后，再用的解（ )）表示)的解（）。
为了求解)，得先确定的取值范围
。假设它的上下边界 分别为H和 L，那么有：

接下来，综合![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/677eedd52f8e88f2929a3a41b6b80075f60ffa5e7cc154cd02d5ab73668f7fba)和![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/62b24a516824a28db8c5cac7377e3ce739ff8e02c2c0fa29380813c7a0ce98fb)这两个约束条件，求取

的取值范围。
当y1 != y2 时，根据)可得)，所以有)， ，如下图所示：

当y1 = y2时，同样根据![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/62b24a516824a28db8c5cac7377e3ce739ff8e02c2c0fa29380813c7a0ce98fb)可得：![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/41b3a8a1f253bba1a15ba60c213e94b0fcb28da19cb2e3d489857f1ab2f12c2e)，所以有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/db3cacf3d935e6046da8e885c1e4a2d8e79ec7f6950c7eba8d27c507d0faa2f6)，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/972796267244ba5d11af64b2d2751c9a6a40bfc94e2c6e304e537c78567c9a3e) ，如下图所示：

如此，根据y1和y2异号或同号，可得出![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/601e9f5f2f5b37262e7e222015ab6db34abe735f04ed5c93fec7aa32306af8e6)的上下界分别为：

回顾下第二个约束条件![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/62b24a516824a28db8c5cac7377e3ce739ff8e02c2c0fa29380813c7a0ce98fb)，令上式两边乘以y1，可得

其中，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/70d5e82f8950f8ed5a2b717ad3ee6ed095b4dd4930da59e365f491aea92025e5)。     因此![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/344706b6be0aa929a2af8996e5ed38f05da9f7f665d9bc36e1d63bd2f87a056a)可以用 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)表示，![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/a8d04267de0647d25ae957e4381599c19f421dd5180febc01193cc4a390565b4)，从而把子问题的目标函数转换为只含

的问题：

对![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)求导，可得

化简下：

然后将![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/d9c4a4b2038358837349a903664f47f575b1e5823919dfd534f282ce894223da)、![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/b8f34f19a0ed9897b768a3894fec5a67fa355e98ad75a20ac80a53248a3e3d3b)、和

代入上式可得：

令![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/6c2e1f64cafd043e4e00c17d965cb8e8ea5f1e380bc6d1700922e61c06e1e62c)（表示预测值与真实值之差），![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/84c17879c3b3d0c9af1831c8bedb5ecaf5e72c1d8bebebff6c787bbbaecc5650)，然后上式两边同时除以![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/d0cddd6eb54afaeef00e8175773362fff698aa42e4a04399da2bd02a583e1aca)，得到一个关于单变量![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)的解：

这个解没有考虑其约束条件![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/481197c910c1f3da2693bcbd1472c2e19f4a07a4b3186c1f57162629f949da96)，即是未经剪辑时的解。     然后考虑约束![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/481197c910c1f3da2693bcbd1472c2e19f4a07a4b3186c1f57162629f949da96)可得到经过剪辑后的![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/601e9f5f2f5b37262e7e222015ab6db34abe735f04ed5c93fec7aa32306af8e6)的解析解为：

求出了后![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/601e9f5f2f5b37262e7e222015ab6db34abe735f04ed5c93fec7aa32306af8e6)，便可以求出![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/94a15b42348f9c8caf166feceaae36deec4a230136b85ba672ea6daa3b6c8c41)，得![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/a4628b9ec1c543ea1230f506a0459ebe239dc3404822c7012f02ac0181b1e62f)。     ![]()那么如何选择乘子![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/344706b6be0aa929a2af8996e5ed38f05da9f7f665d9bc36e1d63bd2f87a056a)和 ![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/311d73b99e496cb10d91e0dde59e4b9da9b68c4c716e2194c409d1a3bafe6691)呢？

• 对于，即第一个乘子，可以通过刚刚说的那3种不满足KKT的条件来找；

  • 而对于第二个乘子可以寻找满足条件 ：的乘子。

    而b在满足下述条件：

下更新b：

且每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。     最后更新所有![](https://gitee.com/songjianzaina/juejin_p4/raw/master/img/a9197547024307a90721eb634db0bc67b5b3357a15f9cb4134787b7903215ad8)，y和b，这样模型就出来了，从而即可求出咱们开头提出的分类函数：

此外，[这里](http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html)也有一篇类似的文章，大家可以参考下。

3.5.2、SMO算法的步骤

综上，总结下SMO的主要步骤，如下：

意思是，

1. 第一步选取一对))和)，选取方法使用启发式方法；

   2. 第二步，固定除)和
      ))之外的其他参数，确定W极值条件下的))，))由)表示。

      假定在某一次迭代中，需要更新， )对应的拉格朗日乘子， ，那么这个小规模的二次规划问题写为：

那么在每次迭代中，如何更新乘子呢？引用[这里](http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf)的两张PPT说明下：  

)

知道了如何更新乘子，那么选取哪些乘子进行更新呢？具体选择方法有以下两个步骤： 

1. 步骤1：先“扫描”所有乘子，把第一个违反KKT条件的作为更新对象，令为a1；

2. 步骤2：在所有不违反KKT条件的乘子中，选择使|E1 −E2|最大的a2进行更新，使得能最大限度增大目标函数的值（类似于梯度下降. 此外)，而，求出来的E代表函数ui对输入xi的预测值与真实输出类标记yi之差）。

   最后，每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。
   综上，SMO算法的 基本思想是将Vapnik在1982年提出的Chunking方法推到极致， SMO算法每次迭代只选出两个分量ai和aj进行调整，其它分量则保持固定不变，在得到解ai和aj之后，再用ai和aj改进其它分量。与通常的分解算法比较，尽管它可能需要更多的迭代次数，但每次迭代的计算量比较小，所以该算法表现出较好的快速收敛性，且不需要存储核矩阵，也没有矩阵运算。

3.5.3、SMO算法的实现

行文至此，我相信，SVM理解到了一定程度后，是的确能在脑海里从头至尾推导出相关公式的，最初分类函数，最大化分类间隔，max1/||w||，min1/2||w||^2，凸二次规划，拉格朗日函数，转化为对偶问题，SMO算法，都为寻找一个最优解，一个最优分类平面。一步步梳理下来，为什么这样那样，太多东西可以追究，最后实现。如下图所示：

至于下文中将阐述的核函数则为是为了更好的处理非线性可分的情况，而松弛变量则是为了纠正或约束少量“不安分”或脱离集体不好归类的因子。


台湾的林智仁教授写了一个封装SVM算法的[libsvm库](http://www.csie.ntu.edu.tw/~cjlin/libsvm/) ，大家可以看看，此外[这里](http://www.pami.sjtu.edu.cn/people/gpliu/document/libsvm_src.pdf)还有一份libsvm的注释文档。


除了在这篇论文《fast training of support vector machines using sequential minimal optimization》中platt给出了SMO算法的逻辑代码之外， [这里](http://blog.csdn.net/techq/article/details/6171688)也有一份SMO的实现代码，大家可以看下。

3.6、SVM的应用

或许我们已经听到过，SVM在很多诸如文本分类，图像分类，生物序列分析和生物数据挖掘，手写字符识别等领域有很多的应用，但或许你并没强烈的意识到，SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。

3.6.1、文本分类

一个文本分类系统不仅是一个自然语言处理系统，也是一个典型的模式识别系统，系统的输入是需要进行分类处理的文本，系统的输出则是与文本关联的类别。由于篇幅所限，其它更具体内容本文将不再详述。


OK，本节虽取标题为证明SVM，但聪明的读者们想必早已看出，其实本部分并无多少证明部分（特此致歉），怎么办呢？可以参阅《支持向量机导论》一书，此书精简而有趣。本节完。

读者评论

本文发表后，[微博](http://weibo.com/julyweibo)上的很多朋友给了不少意见，以下是节选的一些精彩评论：

1. “压力”陡增的评论→//@藏了个锋：我是看着July大神的博文长大的啊//@zlkysl：就是看了最后那一篇才决定自己的研究方向为SVM的。– weibo.com/1580904460/zraWk0u6u?mod=weibotime 。
   2. @张金辉：“SVM的三重境界，不得不转的一篇。其实Coursera的课堂上Andrew Ng讲过支持向量机，但显然他没有把这作为重点，加上Ng讲支持向量机的方法我一时半会难以完全消化，所以听的也是一知半解。真正开始了解支持向量机就是看的这篇“三重境界”，之后才对这个算法有了大概的概念，以至如何去使用，再到其中的原理为何，再到支持向量机的证明等。总之，这篇文章开启了我长达数月的研究支持向量机阶段，直到今日。

”–zhan.renren.com/profile/249…。
3. @孤独之守望者：”最后，推出svm的cost function 是hinge loss，然后对比其他的方法的cost function，说明其实他们的目标函数很像，那么问题是svm为什么这么popular呢？您可以再加些VC dimension跟一些error bound的数学，点一下，提供一个思路和方向”。– weibo.com/1580904460/AiohoyDwq?mod=weibotime 。
4. @夏粉_百度：“在面试时，考察SVM可考察机器学习各方面能力：目标函数,优化过程,并行方法，算法收敛性,样本复杂度，适用场景,调参经验，不过个人认为考察boosting和LR也还不错啊。此外，随着统计机器学习不断进步，SVM只被当成使用了一个替代01损失hinge研究，更通用的方法被提出，损失函数研究替代损失与贝叶斯损失关系，算法稳定性研究替代损失与推广性能关系,凸优化研究如何求解凸目标函数，SVM,boosting等算法只是这些通用方法的一个具体组建而已。
”
5. @居里猴姐：关于SVM损失函数的问题，可以看看张潼老师的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性，优化这些损失函数得到的分类器可以看作是后验概率的“代理”。此外，张潼老师还有另外一篇论文《Statistical analysis of some
multi-category large margin classification methods》，在多分类情况下margin loss的分析，这两篇对Boosting和SVM使用的损失函数分析的很透彻。
6. @夏粉_百度：SVM用了hinge损失，hinge损失不可导，不如其它替代损失方便优化并且转换概率麻烦。核函数也不太用，现在是大数据时代，样本非常大，无法想象一个n^2的核矩阵如何存储和计算。 而且，现在现在非线性一般靠深度学习了。//@Copper_PKU:请教svm在工业界的应用典型的有哪些？工业界如何选取核函数，经验的方法？svm的训练过程如何优化？
7. @Copper_PKU：July的svm tutorial 我个人觉得还可以加入和修改如下部分：(1) 对于支持向量解释，可以结合图和拉格朗日参数来表达，松弛中sv没有写出来. (2) SMO算法部分，加入Joachims论文中提到的算法，以及SMO算法选取workset的方法，包括SMO算法的收敛判断，还有之前共轭梯度求解方法，虽然是较早的算法，但是对于理解SMO算法有很好的效果。模型的优化和求解都是迭代的过程，加入历史算法增强立体感。–
weibo.com/1580904460/…。
8. //@廖临川: 之所以sgd对大训练集的效果更好，1.因为SGD优化每次迭代使用样本子集，比使用训练全集（尤其是百万数量级）要快得多；2.如果目标函数是凸的或者伪凸的，SGD几乎必然可以收敛到全局最优；否则，则收敛到局部最优；3.SGD一般不需要收敛到全局最优，只要得到足够好的解，就可以立即停止。//@Copper_PKU：sgd的核心思想：是迭代训练，每拿到一个样本就算出基于当前w(t) 的loss function，t代表训练第t次，然后进行下一w（t+1）的更新，w(t+1)=w(t)-(learning
rate) * loss function的梯度，这个类比神经网络中bp中的参数训练方法。 sample by sample就是每次仅处理一个样本 而不是一个batch。
9. //@Copper_PKU：从损失函数角度说：primal问题可以理解为正则化项+lossfunction，求解目标是在两个中间取平衡 如果强调loss function最小则会overfitting，所以有C参数。 //@研究者July：SVM还真就是在一定限定条件下，即约束条件下求目标函数的最优值问题，同时，为减少误判率，尽量让损失最小。
10. …

非常享受这种全民大讨论的年代，没有谁一定就对或一定就错，而是各自发表各自的理解见解，真棒！

参考文献及推荐阅读

1. 《支持向量机导论》， [英] Nello Cristianini / John Shawe-Taylor 著 ；
2. 支持向量机导论一书的支持网站： www.support-vector.net/ ；
3. 《数据挖掘导论》， [美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著；
4. 《数据挖掘：概念与技术》，(加)Jiawei Han;Micheline Kamber 著；
5. 《数据挖掘中的新方法：支持向量机》，邓乃扬 田英杰 著；
6. 《支持向量机–理论、算法和扩展》，邓乃扬 田英杰 著；
7. 支持向量机系列，pluskid： blog.pluskid.org/?page_id=683 ；
8. www.360doc.com/content/07/0716/23/11966_615252.shtml ；
9. 数据挖掘十大经典算法初探；
10. 《模式识别支持向量机指南》，C.J.C Burges 著；
11. 《统计学习方法》，李航著；
12. 《统计自然语言处理》，宗成庆编著，第十二章、文本分类；
13. SVM入门系列，Jasper： www.blogjava.net/zhenandaci/… ；
14. 最近邻决策和SVM数字识别的实现和比较，作者不详；
15. 斯坦福大学机器学习课程原始讲义： www.cnblogs.com/jerrylead/a… ；
16. 斯坦福机器学习课程笔记： www.cnblogs.com/jerrylead/t… ；
17. www.cnblogs.com/jerrylead/a… ；
18. SMO算法的数学推导：www.cnblogs.com/jerrylead/a… ；
19. 数据挖掘掘中所需的概率论与数理统计知识、上；
20. 关于机器学习方面的文章，可以读读： www.cnblogs.com/vivounicorn… ；
21. 数学系教材推荐：blog.sina.com.cn/s/blog_5e63…；
22. 《神经网络与机器学习(原书第三版)》，[加] Simon Haykin 著；
23. 正态分布的前世今生：t.cn/zlH3Ygc；
24. 《数理统计学简史》，陈希孺院士著；
25. 《最优化理论与算法(第2版)》，陈宝林编著；
26. A Gentle Introduction to Support Vector Machines in Biomedicine： www.nyuinformatics.org/downloads/s… ，此PPT很赞，除了对引入拉格朗日对偶变量后的凸二次规划问题的深入度不够之外，其它都挺好，配图很精彩，本文有几张图便引自此PPT中；
27. 来自卡内基梅隆大学carnegie mellon university(CMU)的讲解SVM的PPT：www.autonlab.org/tutorials/s…；
28. 发明libsvm的台湾林智仁教授06年的机器学习讲义SVM：wenku.baidu.com/link?url=PW…；
29. staff.ustc.edu.cn/~ketang/PPT…；
30. Introduction to Support Vector Machines (SVM)，By Debprakash Patnai M.E (SSA)，www.google.com.hk/url?sa=t&rc…；
31. 多人推荐过的libsvm： www.csie.ntu.edu.tw/~cjlin/libs… ；
32. 《machine learning in action》，中文版为《机器学习实战》；
33. SMO算法的提出：Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines： research.microsoft.com/en-us/um/pe…；
34. 《统计学习理论的本质》，[美] Vladimir N. Vapnik著，非常晦涩，不做过多推荐；
35. 张兆翔，机器学习第五讲之支持向量机irip.buaa.edu.cn/~zxzhang/co…；
36. VC维的理论解释：www.svms.org/vc-dimensio…，中文VC维解释xiaoxia001.iteye.com/blog/116333… ；
37. 来自NEC Labs America的Jason Weston关于SVM的讲义www.cs.columbia.edu/~kathy/cs47…；
38. 来自MIT的SVM讲义：www.mit.edu/~9.520/spri…；
39. PAC问题：www.cs.huji.ac.il/~shashua/pa…；
40. 百度张潼老师的两篇论文 ：《Statistical behavior and consistency of classification methods based on convex risk minimization》 home.olemiss.edu/~xdang/676/… ，《Statistical analysis of some multi-category large margin classification methods》；
41. jacoxu.com/?p=39 ；
42. 《矩阵分析与应用》，清华张贤达著；
43. SMO算法的实现： blog.csdn.net/techq/artic… ；
44. 常见面试之机器学习算法思想简单梳理： www.cnblogs.com/tornadomeet… ；
45. 矩阵的wikipedia页面： zh.wikipedia.org/wiki/%E7%9F%A9%E9%98%B5 ；
46. 最小二乘法及其实现：blog.csdn.net/qll12559671…；
47. 统计学习方法概论：blog.csdn.net/qll12559671…；
48. www.csdn.net/article/201…；
49. A Tutorial on Support Vector Regression：alex.smola.org/papers/2003…；SVR简明版：www.cmlab.csie.ntu.edu.tw/~cyy/learni…。
50. SVM Org ：www.support-vector-machines.org/ ；
51. R. Collobert. Large Scale Machine Learning. Université Paris VI phd thesis. 2004 ：ronan.collobert.com/pub/matos/2…；
52. Making Large-Scale SVM Learning Practical ：www.cs.cornell.edu/people/tj/p… ；
53. 文本分类与SVM：blog.csdn.net/zhzhl202/ar…；
54. Working Set Selection Using Second Order Information
    for Training Support Vector Machines ：www.csie.ntu.edu.tw/~cjlin/pape… ；
55. SVM Optimization: Inverse Dependence on Training Set Size ：icml2008.cs.helsinki.fi/papers/266.… ；
56. Large-Scale Support Vector Machines: Algorithms and Theory： cseweb.ucsd.edu/~akmenon/Re… ；
57. 凸优化的概念：cs229.stanford.edu/section/cs2… ；
58. 《凸优化》，作者: Stephen Boyd / Lieven Vandenberghe，原作名: Convex Optimization；
59. Large-scale Non-linear Classification: Algorithms and Evaluations，Zhuang Wang，讲了很多SVM算法的新进展： ijcai13.org/files/tutor… ；
60. 基于SMO算法实现SVM：www.cs.iastate.edu/~honavar/sm…；
61. copper推荐的一些SVM相关的论文（当然，其中不少论文在上面的条目中都已经提到）：c.blog.sina.com.cn/profile.php…；
62. 在线编辑Latex 公式：www.codecogs.com/latex/eqned…。

后记

OK，此文从最初2012年5月开始动笔，到后续不断的修改，创造了三个之最，即所写时间最长，所花心血最大，所改次数最多，因为我的目标是让没有任何机器学习基础的都能看懂此文，所以总是不停的改，不停的改，不想放过任何一个小的细节。再者，引用侯捷的一句话是：天下大作，必作于细。     最后，非常感谢pluskid及诸多朋友们的文章及著作，让我有机会在其基础上总结、深入。有任何问题，敬请广大读者随时不吝批评指正，感谢

。

本文PDF版

• 13年11月 25日，用 chrome浏览器打开文章，右键打印，弹出打印框，把左上角的目标更改为“另存为 PDF”，成第一个 PDF： vdisk.weibo.com/s/zrFL6OXKghu5V 。
  • 13年12月 7日，朋友吴新隆用“印象笔记”提取出博客正文，放到 office内编辑成此 PDF：vdisk.weibo.com/s/zrFL6OXKg… ，较上一版本添加了完整的书签。
  • 14年 2月18日，朋友邬书哲用Latex全部重排了本文所有公式，而且给所有公式和图片全部做了标记，Latex版PDF下载地址为： vdisk.weibo.com/s/zrFL6OXKg… 。
  • 15年1月8日，朋友陈笙再为本SVM一文弄了最新的第二个LaTeX版本，下载地址为：pan.baidu.com/s/1eQrgiOU。

本文会一直不断翻新，再者，上述 4 个PDF 的阅读体验也还不是最好的，如果有朋友制作了更好的PDF ，欢迎分享给我：[weibo.com/julyweibo](http://weibo.com/julyweibo)，谢谢。


July、二零一六年一月十七日第N次修改（N > 100）。

重大消息：我的 新书《编程之法：面试和算法心得》终于在2015年10月14日上架开卖了！京东抢购地址：item.jd.com/11786791.ht… 。京东、当当、亚马逊等各大网店均已有现货销售。新书收录了本篇SVM，且新书质量远高于博客。July、二零一五年十月二十九日。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

Table of contents

• Breaking changes: removed reinforce()
• New features
  • Unreduced losses
  • A profiler for the autograd engine
  • More functions support Higher order gradients
  • New features in Optimizers
  • New layers and nn functionality
  • New Tensor functions and Features
  • Other additions
• API changes
• Performance improvements
  • Big reduction in framework overhead (helps small models)
  • 4x to 256x faster Softmax/LogSoftmax
  • More…
• Framework Interoperability
  • DLPack Interoperability
  • Model Exporter to ONNX (ship PyTorch to Caffe2, CoreML, CNTK, MXNet, Tensorflow)
• Bug Fixes (a lot of them)

Breaking changes

Stochastic functions, i.e. Variable.reinforce() were removed because of their limited functionality and broad performance implications. The motivation for stochastic functions was to avoid book-keeping of sampled values. In practice,
users were still book-keeping in their code for various reasons. We constructed an alternative, equally effective API, but did not have a reasonable deprecation path to the new API. Hence this removal is a breaking change.

We introduce the torch.distributions package to replace Stochastic functions.

Your previous code typically looked like this:

1
2
3
4
5

复制代码probs = policy_network(state)
action = probs.multinomial()
next_state, reward = env.step(action)
action.reinforce(reward)
action.backward()

This is the new equivalent code:

1
2
3
4
5
6
7

复制代码probs = policy_network(state)
# NOTE: categorical is equivalent to what used to be called multinomial
m = torch.distributions.Categorical(probs)
action = m.sample()
next_state, reward = env.step(action)
loss = -m.log_prob(action) * reward
loss.backward()

New features

Unreduced losses

Now, Some loss functions can compute per-sample losses in a mini-batch

• By default PyTorch sums losses over the mini-batch and returns a single scalar loss. This was limiting to users.
• Now, a subset of loss functions allow specifying reduce=False to return individual losses for each sample in the mini-batch
• Example: loss = nn.CrossEntropyLoss(..., reduce=False)
• Currently supported losses: MSELoss, NLLLoss, NLLLoss2d, KLDivLoss, CrossEntropyLoss, SmoothL1Loss, L1Loss
• More loss functions will be covered in the next release

An in-built Profiler in the autograd engine

We built a low-level profiler to help you identify bottlenecks in your models

Let us start with an example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复制代码>>> x = Variable(torch.randn(1, 1), requires_grad=True)
>>> with torch.autograd.profiler.profile() as prof:
...     y = x ** 2
...     y.backward()
>>> # NOTE: some columns were removed for brevity
... print(prof)
--------------------------------  ----------  ---------
Name                               CPU time   CUDA time
-------------------------------   ----------  ---------
PowConstant                        142.036us    0.000us
N5torch8autograd9GraphRootE         63.524us    0.000us
PowConstantBackward                184.228us    0.000us
MulConstant                         50.288us    0.000us
PowConstant                         28.439us    0.000us
Mul                                 20.154us    0.000us
N5torch8autograd14AccumulateGradE   13.790us    0.000us
N5torch8autograd5CloneE              4.088us    0.000us

The profiler works for both CPU and CUDA models.
For CUDA models, you have to run your python program with a special nvprof prefix. For example:

1
2
3
4
5
6
7

复制代码nvprof --profile-from-start off -o trace_name.prof -- python <your arguments>

# in python
>>> with torch.cuda.profiler.profile():
...     model(x) # Warmup CUDA memory allocator and profiler
...     with torch.autograd.profiler.emit_nvtx():
...         model(x)

Then, you can load trace_name.prof in PyTorch and print a summary profile report.

1
2

复制代码>>> prof = torch.autograd.profiler.load_nvprof('trace_name.prof')
>>> print(prof)

Read additional documentation here

Higher order gradients

Added higher-order gradients support for the following layers

• ConvTranspose, AvgPool1d, AvgPool2d, LPPool2d, AvgPool3d, MaxPool1d, MaxPool2d, AdaptiveMaxPool, AdaptiveAvgPool, FractionalMaxPool2d, MaxUnpool1d, MaxUnpool2d, nn.Upsample, ReplicationPad2d, ReplicationPad3d, ReflectionPad2d
• PReLU, HardTanh, L1Loss, SoftSign, ELU, RReLU, Hardshrink, Softplus, SoftShrink, LogSigmoid, Softmin, GLU
• MSELoss, SmoothL1Loss, KLDivLoss, HingeEmbeddingLoss, SoftMarginLoss, MarginRankingLoss, CrossEntropyLoss
• DataParallel

Optimizers

• optim.SparseAdam: Implements a lazy version of Adam algorithm suitable for sparse tensors.
  • In this variant, only moments that show up in the gradient get updated, and only those portions of the gradient get applied to the parameters.
• Optimizers now have an add_param_group function that lets you add new parameter groups to an already constructed optimizer.

New layers and nn functionality

• Added AdpativeMaxPool3d and AdaptiveAvgPool3d

• Added LPPool1d

• F.pad now has support for:

  • ‘reflection’ and ‘replication’ padding on 1d, 2d, 3d signals (so 3D, 4D and 5D Tensors)
  • constant padding on n-d signals

• nn.Upsample now works for 1D signals (i.e. B x C x L Tensors) in nearest and linear modes.

• grid_sample now allows padding with the border value via padding_mode="border". grid_sample expects a grid in
  the range of [-1, 1], and if the values are out of these bounds, padding with the value 0.0 is applied by default. However, in a lot of cases, using the border value (i.e. the nearest valid value) helps improve accuracy
  of the overall model.

• Introducing nn.utils.parameters_to_vector and nn.utils.vector_to_parameters

  • parameters_to_vector takes net.parameters() and return a 1D vector that contains all the parameters
  • vector_to_parameters takes a vector of flattened parameters and copies the values over to a network’s parameters
  • Convenient for some reinforcement learning algorithms, such as cross-entropy method, TRPO etc., which need to pull all network parameters as one big vector, modify them, and put the modified vector back.

• Allow user to not specify certain input dimensions for AdaptivePool*d and infer them at runtime.

  • For example:

    1 2	复制代码# target output size of 10x7 m = nn.AdaptiveMaxPool2d((None, 7))

• DataParallel container on CPU is now a no-op (instead of erroring out)

New Tensor functions and features

• Introduced torch.erf and torch.erfinv that compute the error function and the inverse error function of each element in the Tensor.
• adds broadcasting support to bitwise operators
• Added Tensor.put_ and torch.take similar to numpy.take and numpy.put.
  • The take function allows you to linearly index into a tensor without viewing it as a 1D tensor
    first. The output has the same shape as the indices.
  • The put function copies value into a tensor also using linear indices.
  • Differences from numpy equivalents:
    • numpy.take has an optional axis argument, which behaves like index_select. This axis argument is not yet present.
    • numpy.put repeats the values if necessary to make them as long as indices. This behavior is not yet replicated.
• add zeros and zeros_like for sparse Tensors.
• 1-element Tensors can now be casted to Python scalars. For example: int(torch.Tensor([5])) works now.

Other additions

• Added torch.cuda.get_device_name and torch.cuda.get_device_capability that do what the names say. Example:

1
2
3
4

复制代码>>> torch.cuda.get_device_name(0)
'Quadro GP100'
>>> torch.cuda.get_device_capability(0)
(6, 0)

• If one sets torch.backends.cudnn.deterministic = True, then the CuDNN convolutions use deterministic algorithms
• torch.cuda_get_rng_state_all and torch.cuda_set_rng_state_all are introduced to let you save / load the state of the random number generator over all GPUs at once
• torch.cuda.emptyCache() frees the cached memory blocks in PyTorch’s caching allocator. This is useful when having long-running ipython notebooks while sharing the GPU with other processes.

API changes

• softmax and log_softmax now take a dim argument that specifies the dimension in which slices are taken for the softmax operation. dim allows negative dimensions as well (dim = -1 will be the last dimension)
• torch.potrf (Cholesky decomposition) is now differentiable and defined on Variable
• Remove all instances of device_id and replace it with device, to make things consistent
• torch.autograd.grad now allows you to specify inputs that are unused in the autograd graph if you use allow_unused=True
  This gets useful when using torch.autograd.grad in large graphs with lists of inputs
  / outputs
  For example:

1
2
3

复制代码x, y = Variable(...), Variable(...)
torch.autograd.grad(x * 2, [x, y]) # errors
torch.autograd.grad(x * 2, [x, y], allow_unused=True) # works

• pad_packed_sequence now allows a padding_value argument that can be used instead of zero-padding
• Dataset now has a + operator (which uses ConcatDataset). You can do something like MNIST(...) + FashionMNIST(...) for example, and you will get a concatenated dataset containing samples from
  both.
• torch.distributed.recv allows Tensors to be received from any sender (hence, src is optional). recv returns the rank of the sender.
• adds zero_() to Variable
• Variable.shape returns the size of the Tensor (now made consistent with Tensor)
• torch.version.cuda specifies the CUDA version that PyTorch was compiled with
• Add a missing function random_ for CUDA.
• torch.load and torch.save can now take a pathlib.Path object, which is a standard Python3 typed filepath object
• If you want to load a model’s state_dict into another model (for example to fine-tune a pre-trained network), load_state_dict was strict on matching the key names of the parameters. Now we provide a strict=False option to load_state_dict where it only loads in parameters where the keys match, and ignores the other parameter keys.
• added nn.functional.embedding_bag that is equivalent to nn.EmbeddingBag

Performance Improvements

• The overhead of torch functions on Variables was around 10 microseconds. This has been brought down to ~1.5 microseconds by moving most of the core autograd formulas into C++ using our ATen library. This speeds-up models that are
  very small, such as small LSTMs and other common models seen in NLP.
• softmax and log_softmax are now 4x to 256x faster on the GPU after rewriting the gpu kernels
• 2.5x to 3x performance improvement of the distributed AllReduce (gloo backend) by enabling GPUDirect
• nn.Embedding’s renorm option is much faster on the GPU. For embedding dimensions of 100k x 128 and a batch size of 1024, it is 33x faster.
• All pointwise ops now use OpenMP and get multi-core CPU benefits
• Added dedicated CUDA kernels for group convolutions where groups == nInputPlane (depthwise convolution). Speedups range from 5x to 1000x for tested layer sizes. See the benchmark table for more details as well as this table.
• Fixed optim.SGD‘s memory usage for sparse gradients (for ex. nn.Embedding(..., sparse=True)), reducing the usage on a user-provided test script by 10x.
• Optional NNPack integration for faster CPU convolutions (not part of binaries)
• Reduce overhead of broadcasting if Tensors aren’t broadcastable
• torch.nn.utils.weight_norm over the right-most dimensions is faster
• Backward of torch.norm is sped up by ~1.5x
• Improve the performance of pack_padded_sequence
• Add a single-argument version of torch.arange. For example torch.arange(10)

Framework Interoperability

DLPack Interoperability

DLPack Tensors are cross-framework Tensor formats. We now have torch.utils.to_dlpack(x) and torch.utils.from_dlpack(x) to convert between DLPack and torch Tensor formats. The conversion
has zero memory copy and hence is very efficient.

Model exporter to ONNX

ONNX is a common model interchange format that can be executed in Caffe2, CoreML, CNTK, MXNet, Tensorflow at the moment. PyTorch models that are ConvNet-like and RNN-like (static graphs) can now be shipped to the ONNX
format.

• There is a new module torch.onnx (pytorch.org/docs/0.3.0/…) which provides the API for exporting ONNX models.
• The operations supported in this release are:

+ add, sub (nonzero alpha not supported), mul, div, cat, mm, addmm, neg, tanh, sigmoid, mean, t, transpose, view, split, squeeze
+ expand (only when used before a broadcasting ONNX operator; e.g., add)
+ prelu (single weight shared among input channels not supported)
+ threshold (non-zero threshold/non-zero value not supported)
+ Conv, ConvTranspose, BatchNorm, MaxPool, RNN, Dropout, ConstantPadNd, Negate
+ elu, leaky\_relu, glu, softmax, log\_softmax, avg\_pool2d
+ unfold (experimental support with ATen-Caffe2 integration)
+ Embedding (no optional arguments supported)
+ RNN
+ FeatureDropout (training mode not supported)
+ Index (constant integer and tuple indices supported)

Usability Improvements

• More cogent error messages during indexing of Tensors / Variables
  Breaking changes
• Add proper error message for specifying dimension on a tensor with no dimensions
• better error messages for Conv*d input shape checking
• More user-friendly error messages for LongTensor indexing
• Better error messages and argument checking for Conv*d routines
• Trying to construct a Tensor from a Variable fails more appropriately
• If you are using a PyTorch binary with insufficient CUDA version, then a warning is printed to the user.
• Fixed incoherent error messages in load_state_dict
• Fix error message for type mismatches with sparse tensors

Bug fixes

torch

• Fix CUDA lazy initialization to not trigger on calls to torch.manual_seed (instead, the calls are queued and run when CUDA is initialized)

Tensor

• if x is 2D, x[[0, 3],] was needed to trigger advanced indexing. The trailing comma is no longer needed, and you can do x[[0, 3]]
• x.sort(descending=True) used to incorrectly fail for Tensors. Fixed a bug in the argument checking logic to allow this.
• Tensor constructors with numpy input: torch.DoubleTensor(np.array([0,1,2], dtype=np.float32))
  • torch will now copy the contents of the array in a storage of appropriate type.
  • If types match, it will share the underlying array (no-copy), with equivalent semantics to initializing a tensor with another tensor.
  • On CUDA, torch.cuda.FloatTensor(np.random.rand(10,2).astype(np.float32)) will now work by making a copy.
• ones_like and zeros_like now create Tensors on the same device as the original Tensor
• torch.multinomial on the CPU would reshape the input prob_dist in-place. Fixed this to make sure the prob_dist input’s shape is unchanged after the call to multinomial
• expand and expand_as allow expanding an empty Tensor to another empty Tensor
• when [..., None, ...] was given (i.e. newaxis placement in indexing was specified), PyTorch had different behavior from NumPy. This is made consistent with NumPy in all cases.
• Fix exponential distribution implementation to never sample infinity - cuRAND returns numbers in (0, 1]
• torch.HalfTensor supports numpy() and torch.from_numpy
• Add additional size checking for torch.scatter
• fix torch.tril and torch.triu on the GPU for storage-offset Tensors (would return incorrect result).
• Fix a memory leak in CUDA qr decomposition
• Fix stream-awareness issues in THCUNN kernels
• Fix kwargs parsing in torch.topk
• Fixed random_ on CPU (which previously had a max value of 2^32) for DoubleTensor and LongTensor
• Fix ZeroDivisionError: float division by zero when printing certain Tensors
• torch.gels when m > n had a truncation bug on the CPU and returned incorrect results. Fixed.
• Add a check in tensor.numpy() that checks if no positional arguments are passed
• Before a Tensor is moved to CUDA pinned memory, added a check to ensure that it is contiguous
• any and all work on empty Tensors on the cpu (previously errored out)
• Fix symeig on CUDA for large matrices. The bug is that not enough space was being allocated for the workspace, causing some undefined behavior.
• Improved the numerical stability of torch.var and torch.std by using Welford’s algorithm
• The Random Number Generator returned uniform samples with inconsistent bounds (inconsistency in cpu implementation and running into a cublas bug).
  • Now, all uniform sampled numbers will return within the bounds [0, 1), across all types and devices
• Fix torch.svd to not segfault on large CUDA Tensors (fixed an overflow error in the magma bindings)
• Allows empty index Tensor for index_select (instead of erroring out)
• Previously when eigenvector=False, symeig returns some unknown value for the eigenvectors. Now we zero them out.

sparse

• Fix bug with ‘coalesced’ calculation in sparse ‘cadd’
• Fixes .type() not converting indices tensor.
• Fixes sparse tensor coalesce on the GPU in corner cases

autograd

• Fixed crashes when calling backwards on leaf variable with requires_grad=False
• fix bug on Variable type() around non-default GPU input.
• when torch.norm returned 0.0, the gradient was NaN. We now use the subgradient at 0.0, so the gradient is 0.0.
• Fix an correctness issue with advanced indexing and higher-order gradients
• torch.prod‘s backward was failing on the GPU due to a type error, fixed.
• Advanced Indexing on Variables now allows the index to be a LongTensor backed Variable
• Variable.cuda() and Tensor.cuda() are consistent in kwargs options

optim

• torch.optim.lr_scheduler is now imported by default.

nn

• Returning a dictionary from a nn.Module’s forward function is now supported (used to throw an error)
• When register_buffer("foo", ...) is called, and self.foo already exists, then instead of silently failing, now raises a KeyError
• Fixed loading of older checkpoints of RNN/LSTM which were missing _data_ptrs attributes.
• nn.Embedding had a hard error when using the max_norm option. This is fixed now.
• when using the max_norm option, the passed-in indices are written upon (by the underlying implementation). To fix this, pass a clone of the indices to the renorm kernel.
• F.affine_grid now can take non-contiguous inputs
• EmbeddingBag can accept both 1D and 2D inputs now.
• Workaround a CuDNN bug where batch sizes greater than 131070 fail in CuDNN BatchNorm
• fix nn.init.orthogonal to correctly return orthonormal vectors when rows < cols
• if BatchNorm has only 1 value per channel in total, raise an error in training mode.
• Make cuDNN bindings respect the current cuda stream (previously raised incoherent error)
• fix grid_sample backward when gradOutput is a zero-strided Tensor
• Fix a segmentation fault when reflection padding is out of Tensor bounds.
• If LogSoftmax has only 1 element, -inf was returned. Now this correctly returns 0.0
• Fix pack_padded_sequence to accept inputs of arbitrary sizes (not just 3D inputs)
• Detect pointer aliasing in cuDNN RNN flatten_parameters and avoid that path.
• Fixed ELU higher order gradients when applied in-place
• Workaround a CuDNN RNN bug for half-precision
• Prevent numerical issues with poisson_nll_loss when log_input=False by adding a small epsilon

distributed and multi-gpu

• Allow kwargs-only inputs to DataParallel. This used to fail: n = nn.DataParallel(Net()); out = n(input=i)
• DistributedDataParallel calculates num_samples correctly in python2
• Fix the case of DistributedDataParallel when 1-GPU per process is used.
• Allow some params to be requires_grad=False in DistributedDataParallel
• Fixed DataParallel to specify GPUs that don’t include GPU-0
• DistributedDataParallel’s exit doesn’t error out anymore, the daemon flag is set.
• Fix a bug in DistributedDataParallel in the case when model has no buffers (previously raised incoherent error)
• Fix __get_state__ to be functional in DistributedDataParallel (was returning nothing)
• Fix a deadlock in the NCCL bindings when GIL and CudaFreeMutex were starving each other

Others

• model.zoo.load_url now first attempts to use the requests library if available, and then falls back to urllib
• Fix error when default_collate is passed a collection of numpy.str_

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

今天早上闹钟还没响，就被手机的震动声弄醒了，一看就是有朋友催更PyTorch 0.3了。本来也就更新一条链接的事，没想到conda的build工具竟然不能支持MSVC 2017。好吧，又可以水一篇文章了。

在conda-build没有提供MSVC 2017的支持之前，我们没有办法来制作相应的Conda包，因此只能通过whl包来进行安装。具体怎么安装呢？目前将编译好的包上传到了Github的Release页面上，国内的在百度云，需要的用户可以自己下载安装。安装的命令如下：

1
2
3
4
5
6
7
8

复制代码# 对于 Conda 的用户
conda install numpy mkl pyyaml cffi

# For Python 3.5
pip install torch-0.3.0b0.591e73e-cp35-cp35m-win_amd64.whl

# For Python 3.6
pip install torch-0.3.0b0.591e73e-cp36-cp36m-win_amd64.whl

另外，再把相应的发布日志一同搬过来吧。

Windows版本的改动:

错误修复

1. backward中的错误会导致死锁
2. DataLoader多线程时的内存泄漏
3. torch.cuda中的缩进bug

新功能

1. 添加对 CUDA 和 cuDNN 新版本的支持
2. 添加对 Ninja 和 clcache 编译器的支持

已知问题

1. 有些测试不能通过
2. 不能支持 torch.distributed（分布式）、NCCL（多卡）和 Magma
3. 不支持 3.5 及以下的版本
4. 不要把 num_worker 设置为1以上的值。有问题可以尝试调成0。另外代码入口得用以下的if语句包裹。这里稍微解释下为什么要这样，因为Windows不支持fork，多进程只能采用spawn，而如果你不用这个条件包裹，那么代码就会被再次执行一遍，这样如果不加限制，那么就会有无限多的进程了。那为什么不能把 num_worker 开的大一些呢？因为PyTorch在Windows下跨进程的数据传输方式采取了FileMapping，在传输过程中，Mapping也会占用一份内存，这样的话，如果将
   num_worker 设置为1，就要使用双倍的内存了。另外管道传递也是比较慢的，因此如果开的多了，主进程如果不能快速处理的话，会造成数据的积压，从而导致对内存无限的占用。

1

复制代码if __name__ == '__main__':

另外这两天还有个好消息是，Windows的CI已经正式在搭建中了，估计下周就能完工。以后大家可以更加方便的使用master分支进行编译了。我写的一些脚本可以帮助你们方便的进行编译。

以上，就是文章的全部内容啦，如果感觉还意犹未尽的话，可以给我的Github 主页或者项目加个watch或者star之类的（滑稽），以后说不定还会再分享一些相关的经验。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

在上一篇博客《模拟 HTTP 请求》中，我们分别介绍了两种方法来进行 HTTP 的模拟请求：HttpURLConnection 和 HttpClient ，到目前为止这两种方法都工作的很好，基本上可以实现我们需要的 GET/POST 方法的模拟。对于一个爬虫来说，能发送
HTTP 请求，能获取页面数据，能解析网页内容，这相当于已经完成 80% 的工作了。只不过对于剩下的这 20% 的工作，还得花费我们另外 80% 的时间 :-)

在这篇博客里，我们将介绍剩下 20% 的工作中最为重要的一项：如何在 Java 中使用 HTTP 代理，代理也是爬虫技术中的重要一项。你如果要大规模的爬别人网页上的内容，必然会对人家的网站造成影响，如果你太拼了，就会遭人查封。要防止别人查封我们，我们要么将自己的程序分布到大量机器上去，但是对于资金和资源有限的我们来说这是很奢侈的；要么就使用代理技术，从网上捞一批代理，免费的也好收费的也好，或者购买一批廉价的 VPS 来搭建自己的代理服务器。关于如何搭建自己的代理服务器，后面有时间的话我再写一篇关于这个话题的博客。现在有了一大批代理服务器之后，就可以使用我们这篇博客所介绍的技术了。

一、简单的 HTTP 代理

我们先从最简单的开始，网上有很多免费代理，直接上百度搜索 “免费代理” 或者 “HTTP 代理” 就能找到很多（虽然网上能找到大量的免费代理，但它们的安全性已经有很多文章讨论过了，也有专门的文章对此进行调研的，譬如这篇文章，我在这里就不多作说明，如果你的爬虫爬取的信息并没有什么特别的隐私问题，可以忽略之，如果你的爬虫涉及一些例如模拟登录之类的功能，考虑到安全性，我建议你还是不要使用网上公开的免费代理，而是搭建自己的代理服务器比较靠谱）。

1.1 HttpURLConnection 使用代理

HttpURLConnection 的 openConnection() 方法可以传入一个 Proxy 参数，如下：

OK 了，就这么简单！

不仅如此，我们注意到 Proxy 构造函数的第一个参数为枚举类型 Proxy.Type.HTTP ，那么很显然，如果将其修改为 Proxy.Type.SOCKS 即可以使用 SOCKS 代理。

1.2 HttpClient 使用代理

由于 HttpClient 非常灵活，使用 HttpClient 来连接代理有很多不同的方法。最简单的方法莫过于下面这样：

和上一篇中使用 HttpClient 发送请求的代码几乎一样，只是 httpclient.execute() 方法多加了一个参数，第一参数为 HttpHost 类型，我们这里设置成我们的代理即可。

这里要注意一点的是，虽然这里的 new HttpHost() 和上面的 new Proxy() 一样，也是可以指定协议类型的，但是遗憾的是 HttpClient 默认是不支持 SOCKS 协议的，如果我们使用下面的代码：

将会直接报协议不支持异常：

org.apache.http.conn.UnsupportedSchemeException: socks protocol is not supported

如果希望 HttpClient 支持 SOCKS 代理，可以参看这里：How
to use Socks 5 proxy with Apache HTTP Client 4? 通过 HttpClient 提供的 ConnectionSocketFactory 类来实现。

虽然使用这种方式很简单，只需要加个参数就可以了，但是其实看 HttpClient 的代码注释，如下：

可以看到第一个参数 target 并不是代理，它的真实作用是 执行请求的目标主机，这个解释有点模糊，什么叫做 执行请求的目标主机？代理算不算执行请求的目标主机呢？因为按常理来讲，执行请求的目标主机 应该是要请求 URL 对应的站点才对。如果不算的话，为什么这里将 target 设置成代理也能正常工作？这个我也不清楚，还需要进一步研究下
HttpClient 的源码来深入了解下。

除了上面介绍的这种方式（自己写的，不推荐使用）来使用代理之外，HttpClient 官网还提供了几个示例，我将其作为推荐写法记录在此。

第一种写法是使用 RequestConfig
类，如下：

第二种写法是使用 RoutePlanner
类，如下：

二、使用系统代理配置

我们在调试 HTTP 爬虫程序时，常常需要切换代理来测试，有时候直接使用系统自带的代理配置将是一种简单的方法。以前在做 .Net 项目时，程序默认使用 Internet 网络设置中配的代理，遗憾的是，我这里说的系统代理配置指的 JVM 系统，而不是操作系统，我还没找到简单的方法来让 Java 程序直接使用 Windows 系统下的代理配置。

尽管如此，系统代理使用起来还是很简单的。一般有下面两种方式可以设置 JVM 的代理配置：

2.1 System.setProperty

Java 中的 System 类不仅仅是用来给我们 System.out.println() 打印信息的，它其实还有很多静态方法和属性可以用。其中System.setProperty() 就是比较常用的一个。

可以通过下面的方式来分别设置 HTTP 代理，HTTPS 代理和 SOCKS 代理：

这里有三点要说明：

1. 系统默认先使用 HTTP/HTTPS 代理，如果既设置了 HTTP/HTTPS 代理，又设置了 SOCKS 代理，SOCKS 代理会起不到作用
2. 由于历史原因，注意 socksProxyHost 和 socksProxyPort 中间没有小数点
3. HTTP 和 HTTPS 代理可以合起来缩写，如下：

2.2 JVM 命令行参数

可以使用 System.setProperty() 方法来设置系统代理，也可以直接将这些参数通过 JVM 的命令行参数来指定。如果你使用的是 Eclipse ，可以按下面的步骤来设置：

1. 按顺序打开：Window -> Preferences -> Java -> Installed JREs -> Edit
2. 在 Default VM arguments 中填写参数： -DproxyHost=127.0.0.1 -DproxyPort=9876

2.3 使用系统代理

上面两种方法都可以设置系统，下面要怎么在程序中自动使用系统代理呢？

对于 HttpURLConnection 类来说，程序不用做任何变动，它会默认使用系统代理。但是 HttpClient 默认是不使用系统代理的，如果想让它默认使用系统代理，可以通过 SystemDefaultRoutePlanner 和 ProxySelector 来设置。示例代码如下：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

原文：MySQL Performance Tuning Tips for the Shopping Season
作者：Shree Nair
翻译：无阻我飞扬

摘要：针对购物旺季网站流量会对数据库造成的压力，作者给出了MySQL性能调优的一些技巧，这些技巧极具参考价值，通过这些调优，可以有效避免因为流量过大造成服务器宕机，从而给企业造成经济损失。以下是译文

万圣节已经过去很久了，该是把注意力集中在即将到来的假日季节的时候了。首先是感恩节，接着就是黑色星期五和网络星期一，最终在圣诞节/节礼周（从12月26日的节礼日开始，到12月31日的除夕结束为期六天或更长时间。这个词是由零售业在2000年代中期左右发明的，试图延长他们的节礼日销售）达到购物高潮。对于企业主来说，一年的这个时候标志着人们期待已久的年底获利了结。对于一些DBA来说，它会带来恐惧，不安，甚至是不眠之夜，他们要努力使系统重新上线。

值得庆幸是，情况并非如此。通过对MySQL性能变量做一些主动调整，可以使数据库服务器免受购物旺季带来的需求增加的冲击。

技巧#1：确定MySQL的最大连接数

对于MySQL的最大连接数，一次最好是发送5个请求到Web服务器。对Web服务器的5个请求中的一部分将用于CSS样式表，图像和脚本等资源。由于诸如浏览器缓存等原因，要获得准确的MySQL到Web服务器的请求比率可能很困难; 要想得到一个确切的数字，就需要分析Web服务器的日志文件。例如，可以手动访问Apache的“access_log”日志文件，也可以通过Analog或Webalizer等实用程序访问日志文件。

一旦有了对特定使用情况的准确估计，请将该比率乘以Web服务器的最大连接数。例如，如果Web服务器配置为最多为256个客户端提供服务，MySQL请求与Web请求的比率为1/8，则最好将最大数据库连接数设置为32。还要考虑留有安全余量，把这个数乘以2，得到最终的数量。只有在基础设施支持的情况下，才能尝试将数据库连接数的最大数量与Web服务器的客户端限制相匹配。在大多数情况下，最好保持接近32。

在Monyog中查看MySQL连接

在MySQL数据库中，MySQL的最大并发连接数是存储在全局变量max_connections中的。Monyog报告变量“max_connections”作为当前连接监控组中的“最大允许”指标。它还将该数字除以打开的连接数，以生成连接使用百分比：

还有一个连接历史记录监控，可以帮助计算最佳的最大并发连接数。它包括尝试，拒绝和成功连接的数量。此外，允许达到的最大指标的百分比显示为一个进度条，可以让你快速评估服务器在过去达到的最大并发连接数：

技巧#2：为临时表分配足够的内存

在某些情况下，服务器在处理语句时会创建内部临时表。临时表用于内部操作如GROUP BY和distinct，还有一些ORDER BY查询以及UNION和FROM子句（派生表）中的子查询。这些都是在内存中创建的内存表。内存中临时表的最大大小由tmp_table_size和max_heap_table_size中较小的值确定。如果临时表的大小超过这个阈值，则将其转换为磁盘上的InnoDB或MyISAM表。此外，如果查询涉及BLOB或TEXT列，而这些列不能存储在内存表中，临时表总是直接指向磁盘。

这种转换的代价很大，所以考虑增加max_heap_table_size和tmp_table_size变量的大小来帮助减少在磁盘上创建临时表的数量。请记住，这将需要大量内存，因为内存中临时表的大小是基于“最坏情况”的。例如，内存表总是使用固定长度的列，所以字符列使用VARCHAR（255）。这可以使内存中的临时表比想象的要大得多—事实上，这比查询表的总大小要大很多倍！当增加max_heap_table_size和tmp_table_sizevariables的大小时，一定要监视服务器的内存使用情况，因为内存中的临时表可能会增加达到服务器内存容量的风险。

一般来说，32M到64M是建议值，从这两个变量开始并根据需要进行调优。

在Monyog中的临时表监测

临时表的监测是许多预定义的Monyog监测之一。它提供了一些临时表使用的指标，包括：

• 允许的最大值：显示tmp_table_size服务器变量的值，它定义了在内存中创建的临时表的最大大小。与max_heap_table_size一起，这个值定义了可以在内存中创建的临时表的最大大小。如果内存临时表大于此大小，则将其存储在磁盘上。
• 内存表的最大大小：显示max_heap_table_size服务器变量的值，该值定义了显式创建的MEMORY存储引擎表的最大大小。
• 创建的临时表总数：显示created_tmp_tables服务器变量的值，它定义了在内存中创建的临时表的数量。
• 在磁盘上创建的临时表：显示created_tmp_disk_tables服务器变量的值，该变量定义了在磁盘上创建的临时表的数量。如果这个值很高，则应该考虑增加tmp_table_size和max_heap_table_size的值，以便增加创建内存临时表的数量，从而减少在磁盘上创建临时表的数量。
• 磁盘：总比率：基于created_tmp_disk_tables除以created_tmp_tables的计算值。由于tmp_table_size或max_heap_table_size不足而在磁盘上创建的临时表的百分比。Monyog将这个数字显示为一个进度条和百分比，以便快速确定有多少磁盘用于临时表，而不是内存。

趋势图可用于创建的总表，磁盘上创建的表和磁盘的总比值。这些让我们看到了它们随着时间的演变：

技巧#3：增加线程缓存大小

连接管理器线程处理服务器监听的网络接口上的客户端连接请求。连接管理器线程将每个客户端连接与专用于它的线程关联，该线程负责处理该连接的身份验证和所有请求处理。因此，线程和当前连接的客户端之间是一对一的比例。确保线程缓存足够大以容纳所有传入请求是非常重要的。

MySQL提供了许多与连接线程相关的服务器变量：

线程缓存大小由thread_cache_size系统变量决定。默认值为0（无缓存），这将导致为每个新连接设置一个线程，并在连接终止时需要处理该线程。如果希望服务器每秒接收数百个连接请求，那么应该将thread_cache_size设置的足够高，以便大多数新连接可以使用缓存线程。可以在服务器启动或运行时设置max_connections的值。

还应该监视缓存中的线程数（Threads_cached）以及创建了多少个线程，因为无法从缓存中获取线程（Threads_created）。关于后者，如果Threads_created继续以每分钟多于几个线程的增加，请考虑增加thread_cache_size的值。

使用MySQL show status命令显示MySQL的变量和状态信息。这里有几个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复制代码SHOW GLOBAL STATUS LIKE '%Threads_connected%';

+-------------------+-------+

| Variable_name     | Value |

+-------------------+-------+

| Threads_connected | 2     |

+-------------------+-------+
SHOW GLOBAL STATUS LIKE '%Threads_running%';

+-----------------+-------+

| Variable_name   | Value |

+-----------------+-------+

| Threads_running | 1     |

+-----------------+-------+

Monyog线程缓存监测

Monyog提供了一个监控线程缓存的屏幕，名为“线程”。与MySQL线程相关的服务器变量映射到以下Monyog指标：

• thread_cache_size：可以缓存的线程数。
• Threads_cached：缓存中的线程数。
• Threads_created：创建用于处理连接的线程。

Monyog线程屏幕还包括“线程缓存命中率”指标。这是一个提示线程缓存命中率的指标。如果值较低，则应该考虑增加线程缓存。在状态栏以百分比形式显示该值；它的值越接近100％越好。

如果这些指标的值等于或超过指定值，则可以将每一个指标配置为发出警告和/或严重警报。

其他相关的服务器变量

除了上述指标以外，还应该监控以下内容：

1. InnoDB缓冲池大小： InnoDB缓冲池大小在使用InnoDB的MySQL数据库中起着至关重要的作用。缓冲池同时缓存数据和索引。它的值应该尽可能的大，以确保数据库使用内存而不是硬盘驱动器进行读取操作。
2. 临时表大小： MySQL使用max_heap_table_size和tmp_table_size中较小的一个来限制内存中临时表的大小。拥有较大的值可以帮助减少在磁盘上创建临时表的数量，但也会增加服务器内存容量的风险，因为这个指标适用于每个客户端。一般来说，32M到64M是建议的值，从这两个变量开始并根据需要进行调优。
3. InnoDB日志缓冲区大小： MySQL每次写入日志文件时，它都会利用可用于处理销售数据的重要系统资源。因此，将InnoDB日志缓冲区大小设置为较大值才有意义。这样，服务器在大型事务中写入磁盘的次数就减少了，从而最大限度地减少了这些耗时的操作。64M是这个变量的一个很好的起点。

结论

虽然即便是最大的公司网站也会因宕机而遭受损失，但这种影响对于处理网上销售的中小型企业尤其关键。根据最近的一份调查报告显示，一分钟的宕机导致企业平均损失约5000美元。不要让你的业务成为那种统计数据（因为宕机造成的损失）的一部分。在假日繁忙之前，主动调优MySQL数据库服务器（S）并收获回报吧！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

自从我写完这个话题的上半部分之后，就感觉头脑中出现了许多细小的声音，久久挥之不去。它们就像是在为了一些鸡毛蒜皮的小事而相互争吵个不停。的确，有关分布式的话题就是这样，琐碎异常，而且每个人说的话听起来似乎都有道理。

今天，我们就继续探讨这个话题的后半部分。本文中，我们将从antirez反驳Martin Kleppmann的观点开始讲起，然后会涉及到Hacker News上出现的一些讨论内容，接下来我们还会讨论到基于Zookeeper和Chubby的分布式锁是怎样的，并和Redlock进行一些对比。最后，我们会提到Martin对于这一事件的总结。

还没有看过上半部分的同学，请先阅读：

• 基于Redis的分布式锁到底安全吗（上）

antirez的反驳

Martin在发表了那篇分析分布式锁的blog (How to do distributed locking)之后，该文章在Twitter和Hacker News上引发了广泛的讨论。但人们更想听到的是Redlock的作者antirez对此会发表什么样的看法。

Martin的那篇文章是在2016-02-08这一天发表的，但据Martin说，他在公开发表文章的一星期之前就把草稿发给了antirez进行review，而且他们之间通过email进行了讨论。不知道Martin有没有意料到，antirez对于此事的反应很快，就在Martin的文章发表出来的第二天，antirez就在他的博客上贴出了他对于此事的反驳文章，名字叫”Is Redlock safe?”，地址如下:

• antirez.com/news/101

这是高手之间的过招。antirez这篇文章也条例非常清晰，并且中间涉及到大量的细节。antirez认为，Martin的文章对于Redlock的批评可以概括为两个方面（与Martin文章的前后两部分对应）：

• 带有自动过期功能的分布式锁，必须提供某种fencing机制来保证对共享资源的真正的互斥保护。Redlock提供不了这样一种机制。
• Redlock构建在一个不够安全的系统模型之上。它对于系统的记时假设(timing assumption)有比较强的要求，而这些要求在现实的系统中是无法保证的。

antirez对这两方面分别进行了反驳。

首先，关于fencing机制。antirez对于Martin的这种论证方式提出了质疑：既然在锁失效的情况下已经存在一种fencing机制能继续保持资源的互斥访问了，那为什么还要使用一个分布式锁并且还要求它提供那么强的安全性保证呢？即使退一步讲，Redlock虽然提供不了Martin所讲的递增的fencing token，但利用Redlock产生的随机字符串(my_random_value)可以达到同样的效果。这个随机字符串虽然不是递增的，但却是唯一的，可以称之为unique
token。antirez举了个例子，比如，你可以用它来实现“Check and Set”操作，原话是：

When starting to work with a shared resource, we set its state to “<token>”, then we operate the read-modify-write only if the token is still the same when we write. （译文：当开始和共享资源交互的时候，我们将它的状态设置成“<token>”，然后仅在token没改变的情况下我们才执行“读取-修改-写回”操作。）

第一遍看到这个描述的时候，我个人是感觉没太看懂的。“Check and Set”应该就是我们平常听到过的CAS操作了，但它如何在这个场景下工作，antirez并没有展开说（在后面讲到Hacker News上的讨论的时候，我们还会提到）。

然后，antirez的反驳就集中在第二个方面上：关于算法在记时(timing)方面的模型假设。在我们前面分析Martin的文章时也提到过，Martin认为Redlock会失效的情况主要有三种：

• 时钟发生跳跃。
• 长时间的GC pause。
• 长时间的网络延迟。

antirez肯定意识到了这三种情况对Redlock最致命的其实是第一点：时钟发生跳跃。这种情况一旦发生，Redlock是没法正常工作的。而对于后两种情况来说，Redlock在当初设计的时候已经考虑到了，对它们引起的后果有一定的免疫力。所以，antirez接下来集中精力来说明通过恰当的运维，完全可以避免时钟发生大的跳动，而Redlock对于时钟的要求在现实系统中是完全可以满足的。

Martin在提到时钟跳跃的时候，举了两个可能造成时钟跳跃的具体例子：

• 系统管理员手动修改了时钟。
• 从NTP服务收到了一个大的时钟更新事件。

antirez反驳说：

• 手动修改时钟这种人为原因，不要那么做就是了。否则的话，如果有人手动修改Raft协议的持久化日志，那么就算是Raft协议它也没法正常工作了。
• 使用一个不会进行“跳跃”式调整系统时钟的ntpd程序（可能是通过恰当的配置），对于时钟的修改通过多次微小的调整来完成。

而Redlock对时钟的要求，并不需要完全精确，它只需要时钟差不多精确就可以了。比如，要记时5秒，但可能实际记了4.5秒，然后又记了5.5秒，有一定的误差。不过只要误差不超过一定范围，这对Redlock不会产生影响。antirez认为呢，像这样对时钟精度并不是很高的要求，在实际环境中是完全合理的。

好了，到此为止，如果你相信antirez这里关于时钟的论断，那么接下来antirez的分析就基本上顺理成章了。

关于Martin提到的能使Redlock失效的后两种情况，Martin在分析的时候恰好犯了一个错误（在本文上半部分已经提到过）。在Martin给出的那个由客户端GC
pause引发Redlock失效的例子中，这个GC pause引发的后果相当于在锁服务器和客户端之间发生了长时间的消息延迟。Redlock对于这个情况是能处理的。回想一下Redlock算法的具体过程，它使用起来的过程大体可以分成5步：

1. 获取当前时间。
2. 完成获取锁的整个过程（与N个Redis节点交互）。
3. 再次获取当前时间。
4. 把两个时间相减，计算获取锁的过程是否消耗了太长时间，导致锁已经过期了。如果没过期，
5. 客户端持有锁去访问共享资源。

在Martin举的例子中，GC pause或网络延迟，实际发生在上述第1步和第3步之间。而不管在第1步和第3步之间由于什么原因（进程停顿或网络延迟等）导致了大的延迟出现，在第4步都能被检查出来，不会让客户端拿到一个它认为有效而实际却已经过期的锁。当然，这个检查依赖系统时钟没有大的跳跃。这也就是为什么antirez在前面要对时钟条件进行辩护的原因。

有人会说，在第3步之后，仍然可能会发生延迟啊。没错，antirez承认这一点，他对此有一段很有意思的论证，原话如下：

The delay can only happen after steps 3, resulting into the lock to be considered ok while actually expired, that is, we are back at the first problem Martin identified of distributed locks where the client fails to stop working to the shared
resource before the lock validity expires. Let me tell again how this problem is common with all the distributed locks implementations, and how the token as a solution is both unrealistic and can be used with Redlock as well. （译文：延迟只能发生在第3步之后，这导致锁被认为是有效的而实际上已经过期了，也就是说，我们回到了Martin指出的第一个问题上，客户端没能够在锁的有效性过期之前完成与共享资源的交互。让我再次申明一下，这个问题对于所有的分布式锁的实现是普遍存在的，而且基于token的这种解决方案是不切实际的，但也能和Redlock一起用。）

这里antirez所说的“Martin指出的第一个问题”具体是什么呢？在本文上半部分我们提到过，Martin的文章分为两大部分，其中前半部分与Redlock没有直接关系，而是指出了任何一种带自动过期功能的分布式锁在没有提供fencing机制的前提下都有可能失效。这里antirez所说的就是指的Martin的文章的前半部分。换句话说，对于大延迟给Redlock带来的影响，恰好与Martin在文章的前半部分针对所有的分布式锁所做的分析是一致的，而这种影响不单单针对Redlock。Redlock的实现已经保证了它是和其它任何分布式锁的安全性是一样的。当然，与其它“更完美”的分布式锁相比，Redlock似乎提供不了Martin提出的那种递增的token，但antirez在前面已经分析过了，关于token的这种论证方式本身就是“不切实际”的，或者退一步讲，Redlock能提供的unique
token也能够提供完全一样的效果。

另外，关于大延迟对Redlock的影响，antirez和Martin在Twitter上有下面的对话：

antirez: @martinkl so I wonder if after my reply, we can at least agree about unbound messages delay to don’t cause any harm.

Martin: @antirez Agree about message delay between app and lock server. Delay between app and resource being accessed is still problematic.

（译文： antirez问：我想知道，在我发文回复之后，我们能否在一点上达成一致，就是大的消息延迟不会给Redlock的运行造成损害。 Martin答：对于客户端和锁服务器之间的消息延迟，我同意你的观点。但客户端和被访问资源之间的延迟还是有问题的。）

通过这段对话可以看出，对于Redlock在第4步所做的锁有效性的检查，Martin是予以肯定的。但他认为客户端和资源服务器之间的延迟还是会带来问题的。Martin在这里说的有点模糊。就像antirez前面分析的，客户端和资源服务器之间的延迟，对所有的分布式锁的实现都会带来影响，这不单单是Redlock的问题了。

以上就是antirez在blog中所说的主要内容。有一些点值得我们注意一下：

• antirez是同意大的系统时钟跳跃会造成Redlock失效的。在这一点上，他与Martin的观点的不同在于，他认为在实际系统中是可以避免大的时钟跳跃的。当然，这取决于基础设施和运维方式。
• antirez在设计Redlock的时候，是充分考虑了网络延迟和程序停顿所带来的影响的。但是，对于客户端和资源服务器之间的延迟（即发生在算法第3步之后的延迟），antirez是承认所有的分布式锁的实现，包括Redlock，是没有什么好办法来应对的。

讨论进行到这，Martin和antirez之间谁对谁错其实并不是那么重要了。只要我们能够对Redlock（或者其它分布式锁）所能提供的安全性的程度有充分的了解，那么我们就能做出自己的选择了。

Hacker News上的一些讨论

针对Martin和antirez的两篇blog，很多技术人员在Hacker News上展开了激烈的讨论。这些讨论所在地址如下：

• 针对Martin的blog的讨论：news.ycombinator.com/item?id=110…
• 针对antirez的blog的讨论：news.ycombinator.com/item?id=110…

在Hacker News上，antirez积极参与了讨论，而Martin则始终置身事外。

下面我把这些讨论中一些有意思的点拿出来与大家一起分享一下（集中在对于fencing token机制的讨论上）。

关于antirez提出的“Check and Set”操作，他在blog里并没有详加说明。果然，在Hacker News上就有人出来问了。antirez给出的答复如下：

You want to modify locked resource X. You set X.currlock = token. Then you read, do whatever you want, and when you write, you “write-if-currlock == token”. If another client did X.currlock = somethingelse, the transaction fails.

翻译一下可以这样理解：假设你要修改资源X，那么遵循下面的伪码所定义的步骤。

1. 先设置X.currlock = token。
2. 读出资源X（包括它的值和附带的X.currlock）。
3. 按照”write-if-currlock == token”的逻辑，修改资源X的值。意思是说，如果对X进行修改的时候，X.currlock仍然和当初设置进去的token相等，那么才进行修改；如果这时X.currlock已经是其它值了，那么说明有另外一方也在试图进行修改操作，那么放弃当前的修改，从而避免冲突。

随后Hacker News上一位叫viraptor的用户提出了异议，它给出了这样一个执行序列：

• A: X.currlock = Token_ID_A
• A: resource read
• A: is X.currlock still Token_ID_A? yes
• B: X.currlock = Token_ID_B
• B: resource read
• B: is X.currlock still Token_ID_B? yes
• B: resource write
• A: resource write

到了最后两步，两个客户端A和B同时进行写操作，冲突了。不过，这位用户应该是理解错了antirez给出的修改过程了。按照antirez的意思，判断X.currlock是否修改过和对资源的写操作，应该是一个原子操作。只有这样理解才能合乎逻辑，否则的话，这个过程就有严重的破绽。这也是为什么antirez之前会对fencing机制产生质疑：既然资源服务器本身都能提供互斥的原子操作了，为什么还需要一个分布式锁呢？因此，antirez认为这种fencing机制是很累赘的，他之所以还是提出了这种“Check
and Set”操作，只是为了证明在提供fencing token这一点上，Redlock也能做到。但是，这里仍然有一些不明确的地方，如果将”write-if-currlock == token”看做是原子操作的话，这个逻辑势必要在资源服务器上执行，那么第二步为什么还要“读出资源X”呢？除非这个“读出资源X”的操作也是在资源服务器上执行，它包含在“判断-写回”这个原子操作里面。而假如不这样理解的话，“读取-判断-写回”这三个操作都放在客户端执行，那么看不出它们如何才能实现原子性操作。在下面的讨论中，我们暂时忽略“读出资源X”这一步。

这个基于random token的“Check and Set”操作，如果与Martin提出的递增的fencing token对比一下的话，至少有两点不同：

• “Check and Set”对于写操作要分成两步来完成（设置token、判断-写回），而递增的fencing token机制只需要一步（带着token向资源服务器发起写请求）。
• 递增的fencing token机制能保证最终操作共享资源的顺序，那些延迟时间太长的操作就无法操作共享资源了。但是基于random token的“Check and Set”操作不会保证这个顺序，那些延迟时间太长的操作如果后到达了，它仍然有可能操作共享资源（当然是以互斥的方式）。

对于前一点不同，我们在后面的分析中会看到，如果资源服务器也是分布式的，那么使用递增的fencing token也要变成两步。

而对于后一点操作顺序上的不同，antirez认为这个顺序没有意义，关键是能互斥访问就行了。他写下了下面的话：

So the goal is, when race conditions happen, to avoid them in some way. ……Note also that when it happens that, because of delays, the clients are accessing concurrently, the lock ID has little to do with the order in which the
operations were indented to happen. （译文： 我们的目标是，当竞争条件出现的时候，能够以某种方式避免。…… 还需要注意的是，当那种竞争条件出现的时候，比如由于延迟，客户端是同时来访问的，锁的ID的大小顺序跟那些操作真正想执行的顺序，是没有什么关系的。）

这里的lock ID，跟Martin说的递增的token是一回事。

随后，antirez举了一个“将名字加入列表”的操作的例子：

• T0: Client A receives new name to add from web.
• T0: Client B is idle
• T1: Client A is experiencing pauses.
• T1: Client B receives new name to add from web.
• T2: Client A is experiencing pauses.
• T2: Client B receives a lock with ID 1
• T3: Client A receives a lock with ID 2

你看，两个客户端（其实是Web服务器）执行“添加名字”的操作，A本来是排在B前面的，但获得锁的顺序却是B排在A前面。因此，antirez说，锁的ID的大小顺序跟那些操作真正想执行的顺序，是没有什么关系的。关键是能排出一个顺序来，能互斥访问就行了。那么，至于锁的ID是递增的，还是一个random token，自然就不那么重要了。

Martin提出的fencing token机制，给人留下了无尽的疑惑。这主要是因为他对于这一机制的描述缺少太多的技术细节。从上面的讨论可以看出，antirez对于这一机制的看法是，它跟一个random token没有什么区别，而且，它需要资源服务器本身提供某种互斥机制，这几乎让分布式锁本身的存在失去了意义。围绕fencing token的问题，还有两点是比较引人注目的，Hacker News上也有人提出了相关的疑问：

• （1）关于资源服务器本身的架构细节。
• （2）资源服务器对于fencing token进行检查的实现细节，比如是否需要提供一种原子操作。

关于上述问题（1），Hacker News上有一位叫dwenzek的用户发表了下面的评论：

…… the issue around the usage of fencing tokens to reject any late usage of a lock is unclear just because the protected resource and its access are themselves unspecified. Is the resource distributed or not? If distributed, does the resource
has a mean to ensure that tokens are increasing over all the nodes? Does the resource have a mean to rollback any effects done by a client which session is interrupted by a timeout?

（译文：…… 关于使用fencing token拒绝掉延迟请求的相关议题，是不够清晰的，因为受保护的资源以及对它的访问方式本身是没有被明确定义过的。资源服务是不是分布式的呢？如果是，资源服务有没有一种方式能确保token在所有节点上递增呢？对于客户端的Session由于过期而被中断的情况，资源服务有办法将它的影响回滚吗？）

这些疑问在Hacker News上并没有人给出解答。而关于分布式的资源服务器架构如何处理fencing token，另外一名分布式系统的专家Flavio Junqueira在他的一篇blog中有所提及（我们后面会再提到）。

关于上述问题（2），Hacker News上有一位叫reza_n的用户发表了下面的疑问：

I understand how a fencing token can prevent out of order writes when 2 clients get the same lock. But what happens when those writes happen to arrive in order and you are doing a value modification? Don’t you still need to rely on some kind of
value versioning or optimistic locking? Wouldn’t this make the use of a distributed lock unnecessary?

（译文： 我理解当两个客户端同时获得锁的时候fencing token是如何防止乱序的。但是如果两个写操作恰好按序到达了，而且它们在对同一个值进行修改，那会发生什么呢？难道不会仍然是依赖某种数据版本号或者乐观锁的机制？这不会让分布式锁变得没有必要了吗？）

一位叫Terr_的Hacker News用户答：

I believe the “first” write fails, because the token being passed in is no longer “the lastest”, which indicates their lock was already released or expired.

（译文： 我认为“第一个”写请求会失败，因为它传入的token不再是“最新的”了，这意味着锁已经释放或者过期了。）

Terr_的回答到底对不对呢？这不好说，取决于资源服务器对于fencing token进行检查的实现细节。让我们来简单分析一下。

为了简单起见，我们假设有一台（先不考虑分布式的情况）通过RPC进行远程访问文件服务器，它无法提供对于文件的互斥访问（否则我们就不需要分布式锁了）。现在我们按照Martin给出的说法，加入fencing token的检查逻辑。由于Martin没有描述具体细节，我们猜测至少有两种可能。

第一种可能，我们修改了文件服务器的代码，让它能多接受一个fencing token的参数，并在进行所有处理之前加入了一个简单的判断逻辑，保证只有当前接收到的fencing token大于之前的值才允许进行后边的访问。而一旦通过了这个判断，后面的处理不变。

现在想象reza_n描述的场景，客户端1和客户端2都发生了GC pause，两个fencing token都延迟了，它们几乎同时到达了文件服务器，而且保持了顺序。那么，我们新加入的判断逻辑，应该对两个请求都会放过，而放过之后它们几乎同时在操作文件，还是冲突了。既然Martin宣称fencing token能保证分布式锁的正确性，那么上面这种可能的猜测也许是我们理解错了。

当然，还有第二种可能，就是我们对文件服务器确实做了比较大的改动，让这里判断token的逻辑和随后对文件的处理放在一个原子操作里了。这可能更接近antirez的理解。这样的话，前面reza_n描述的场景中，两个写操作都应该成功。

基于ZooKeeper的分布式锁更安全吗？

很多人（也包括Martin在内）都认为，如果你想构建一个更安全的分布式锁，那么应该使用ZooKeeper，而不是Redis。那么，为了对比的目的，让我们先暂时脱离开本文的题目，讨论一下基于ZooKeeper的分布式锁能提供绝对的安全吗？它需要fencing token机制的保护吗？

我们不得不提一下分布式专家Flavio Junqueira所写的一篇blog，题目叫“Note on fencing and distributed locks”，地址如下：

• fpj.me/2016/02/10/…

Flavio Junqueira是ZooKeeper的作者之一，他的这篇blog就写在Martin和antirez发生争论的那几天。他在文中给出了一个基于ZooKeeper构建分布式锁的描述（当然这不是唯一的方式）：

• 客户端尝试创建一个znode节点，比如/lock。那么第一个客户端就创建成功了，相当于拿到了锁；而其它的客户端会创建失败（znode已存在），获取锁失败。
• 持有锁的客户端访问共享资源完成后，将znode删掉，这样其它客户端接下来就能来获取锁了。
• znode应该被创建成ephemeral的。这是znode的一个特性，它保证如果创建znode的那个客户端崩溃了，那么相应的znode会被自动删除。这保证了锁一定会被释放。

看起来这个锁相当完美，没有Redlock过期时间的问题，而且能在需要的时候让锁自动释放。但仔细考察的话，并不尽然。

ZooKeeper是怎么检测出某个客户端已经崩溃了呢？实际上，每个客户端都与ZooKeeper的某台服务器维护着一个Session，这个Session依赖定期的心跳(heartbeat)来维持。如果ZooKeeper长时间收不到客户端的心跳（这个时间称为Sesion的过期时间），那么它就认为Session过期了，通过这个Session所创建的所有的ephemeral类型的znode节点都会被自动删除。

设想如下的执行序列：

1. 客户端1创建了znode节点/lock，获得了锁。
2. 客户端1进入了长时间的GC pause。
3. 客户端1连接到ZooKeeper的Session过期了。znode节点 /lock被自动删除。
4. 客户端2创建了znode节点/lock，从而获得了锁。
5. 客户端1从GC pause中恢复过来，它仍然认为自己持有锁。

最后，客户端1和客户端2都认为自己持有了锁，冲突了。这与之前Martin在文章中描述的由于GC pause导致的分布式锁失效的情况类似。

看起来，用ZooKeeper实现的分布式锁也不一定就是安全的。该有的问题它还是有。但是，ZooKeeper作为一个专门为分布式应用提供方案的框架，它提供了一些非常好的特性，是Redis之类的方案所没有的。像前面提到的ephemeral类型的znode自动删除的功能就是一个例子。

还有一个很有用的特性是ZooKeeper的watch机制。这个机制可以这样来使用，比如当客户端试图创建/lock的时候，发现它已经存在了，这时候创建失败，但客户端不一定就此对外宣告获取锁失败。客户端可以进入一种等待状态，等待当/lock节点被删除的时候，ZooKeeper通过watch机制通知它，这样它就可以继续完成创建操作（获取锁）。这可以让分布式锁在客户端用起来就像一个本地的锁一样：加锁失败就阻塞住，直到获取到锁为止。这样的特性Redlock就无法实现。

小结一下，基于ZooKeeper的锁和基于Redis的锁相比在实现特性上有两个不同：

• 在正常情况下，客户端可以持有锁任意长的时间，这可以确保它做完所有需要的资源访问操作之后再释放锁。这避免了基于Redis的锁对于有效时间(lock validity time)到底设置多长的两难问题。实际上，基于ZooKeeper的锁是依靠Session（心跳）来维持锁的持有状态的，而Redis不支持Sesion。
• 基于ZooKeeper的锁支持在获取锁失败之后等待锁重新释放的事件。这让客户端对锁的使用更加灵活。

顺便提一下，如上所述的基于ZooKeeper的分布式锁的实现，并不是最优的。它会引发“herd effect”（羊群效应），降低获取锁的性能。一个更好的实现参见下面链接：

• zookeeper.apache.org/doc/r3.4.9/…

我们重新回到Flavio Junqueira对于fencing token的分析。Flavio Junqueira指出，fencing token机制本质上是要求客户端在每次访问一个共享资源的时候，在执行任何操作之前，先对资源进行某种形式的“标记”(mark)操作，这个“标记”能保证持有旧的锁的客户端请求（如果延迟到达了）无法操作资源。这种标记操作可以是很多形式，fencing token是其中比较典型的一个。

随后Flavio Junqueira提到用递增的epoch number（相当于Martin的fencing token）来保护共享资源。而对于分布式的资源，为了方便讨论，假设分布式资源是一个小型的多备份的数据存储(a small replicated data store)，执行写操作的时候需要向所有节点上写数据。最简单的做标记的方式，就是在对资源进行任何操作之前，先把epoch number标记到各个资源节点上去。这样，各个节点就保证了旧的（也就是小的）epoch number无法操作数据。

当然，这里再展开讨论下去可能就涉及到了这个数据存储服务的实现细节了。比如在实际系统中，可能为了容错，只要上面讲的标记和写入操作在多数节点上完成就算成功完成了（Flavio Junqueira并没有展开去讲）。在这里我们能看到的，最重要的，是这种标记操作如何起作用的方式。这有点类似于Paxos协议（Paxos协议要求每个proposal对应一个递增的数字，执行accept请求之前先执行prepare请求）。antirez提出的random token的方式显然不符合Flavio Junqueira对于“标记”操作的定义，因为它无法区分新的token和旧的token。只有递增的数字才能确保最终收敛到最新的操作结果上。

在这个分布式数据存储服务（共享资源）的例子中，客户端在标记完成之后执行写入操作的时候，存储服务的节点需要判断epoch number是不是最新，然后确定能不能执行写入操作。如果按照上一节我们的分析思路，这里的epoch判断和接下来的写入操作，是不是在一个原子操作里呢？根据Flavio Junqueira的相关描述，我们相信，应该是原子的。那么既然资源本身可以提供原子互斥操作了，那么分布式锁还有存在的意义吗？应该说有。客户端可以利用分布式锁有效地避免冲突，等待写入机会，这对于包含多个节点的分布式资源尤其有用（当然，是出于效率的原因）。

Chubby的分布式锁是怎样做fencing的？

提到分布式锁，就不能不提Google的Chubby。

Chubby是Google内部使用的分布式锁服务，有点类似于ZooKeeper，但也存在很多差异。Chubby对外公开的资料，主要是一篇论文，叫做“The Chubby lock service for loosely-coupled distributed systems”，下载地址如下：

• research.google.com/archive/chu…

另外，YouTube上有一个的讲Chubby的talk，也很不错，播放地址：

• www.youtube.com/watch?v=PqI…

Chubby自然也考虑到了延迟造成的锁失效的问题。论文里有一段描述如下：

a process holding a lock L may issue a request R, but then fail. Another process may ac- quire L and perform some action before R arrives at its destination. If R later arrives, it may be acted on without the protection of L, and potentially on
inconsistent data.

（译文： 一个进程持有锁L，发起了请求R，但是请求失败了。另一个进程获得了锁L并在请求R到达目的方之前执行了一些动作。如果后来请求R到达了，它就有可能在没有锁L保护的情况下进行操作，带来数据不一致的潜在风险。）

这跟Martin的分析大同小异。

Chubby给出的用于解决（缓解）这一问题的机制称为sequencer，类似于fencing token机制。锁的持有者可以随时请求一个sequencer，这是一个字节串，它由三部分组成：

• 锁的名字。
• 锁的获取模式（排他锁还是共享锁）。
• lock generation number（一个64bit的单调递增数字）。作用相当于fencing token或epoch number。

客户端拿到sequencer之后，在操作资源的时候把它传给资源服务器。然后，资源服务器负责对sequencer的有效性进行检查。检查可以有两种方式：

• 调用Chubby提供的API，CheckSequencer()，将整个sequencer传进去进行检查。这个检查是为了保证客户端持有的锁在进行资源访问的时候仍然有效。
• 将客户端传来的sequencer与资源服务器当前观察到的最新的sequencer进行对比检查。可以理解为与Martin描述的对于fencing token的检查类似。

当然，如果由于兼容的原因，资源服务本身不容易修改，那么Chubby还提供了一种机制：

• lock-delay。Chubby允许客户端为持有的锁指定一个lock-delay的时间值（默认是1分钟）。当Chubby发现客户端被动失去联系的时候，并不会立即释放锁，而是会在lock-delay指定的时间内阻止其它客户端获得这个锁。这是为了在把锁分配给新的客户端之前，让之前持有锁的客户端有充分的时间把请求队列排空(draining the queue)，尽量防止出现延迟到达的未处理请求。

可见，为了应对锁失效问题，Chubby提供的三种处理方式：CheckSequencer()检查、与上次最新的sequencer对比、lock-delay，它们对于安全性的保证是从强到弱的。而且，这些处理方式本身都没有保证提供绝对的正确性(correctness)。但是，Chubby确实提供了单调递增的lock generation number，这就允许资源服务器在需要的时候，利用它提供更强的安全性保障。

关于时钟

在Martin与antirez的这场争论中，冲突最为严重的就是对于系统时钟的假设是不是合理的问题。Martin认为系统时钟难免会发生跳跃（这与分布式算法的异步模型相符），而antirez认为在实际中系统时钟可以保证不发生大的跳跃。

Martin对于这一分歧发表了如下看法（原话）：

So, fundamentally, this discussion boils down to whether it is reasonable to make timing assumptions for ensuring safety properties. I say no, Salvatore says yes — but that’s ok. Engineering discussions rarely have one right answer.

（译文： 从根本上来说，这场讨论最后归结到了一个问题上：为了确保安全性而做出的记时假设到底是否合理。我认为不合理，而antirez认为合理 —— 但是这也没关系。工程问题的讨论很少只有一个正确答案。）

那么，在实际系统中，时钟到底是否可信呢？对此， Julia
Evans专门写了一篇文章，“TIL:
clock skew exists”，总结了很多跟时钟偏移有关的实际资料，并进行了分析。这篇文章地址：

• jvns.ca/blog/2016/0…

Julia Evans在文章最后得出的结论是：

clock skew is real （时钟偏移在现实中是存在的）

Martin的事后总结

我们前面提到过，当各方的争论在激烈进行的时候，Martin几乎始终置身事外。但是Martin在这件事过去之后，把这个事件的前后经过总结成了一个很长的故事线。如果你想最全面地了解这个事件发生的前后经过，那么建议去读读Martin的这个总结：

• storify.com/martinkl/re…

在这个故事总结的最后，Martin写下了很多感性的评论：

For me, this is the most important point: I don’t care who is right or wrong in this debate — I care about learning from others’ work, so that we can avoid repeating old mistakes, and make things better in future. So much great work has already
been done for us: by standing on the shoulders of giants, we can build better software. …… By all means, test ideas by arguing them and checking whether they stand up to scrutiny by others. That’s part of the learning process.
But the goal should be to learn, not to convince others that you are right. Sometimes that just means to stop and think for a while.

（译文： 对我来说最重要的一点在于：我并不在乎在这场辩论中谁对谁错 —— 我只关心从其他人的工作中学到的东西，以便我们能够避免重蹈覆辙，并让未来更加美好。前人已经为我们创造出了许多伟大的成果：站在巨人的肩膀上，我们得以构建更棒的软件。 …… 对于任何想法，务必要详加检验，通过论证以及检查它们是否经得住别人的详细审查。那是学习过程的一部分。但目标应该是为了获得知识，而不应该是为了说服别人相信你自己是对的。有时候，那只不过意味着停下来，好好地想一想。）

关于分布式锁的这场争论，我们已经完整地做了回顾和分析。

按照锁的两种用途，如果仅是为了效率(efficiency)，那么你可以自己选择你喜欢的一种分布式锁的实现。当然，你需要清楚地知道它在安全性上有哪些不足，以及它会带来什么后果。而如果你是为了正确性(correctness)，那么请慎之又慎。在本文的讨论中，我们在分布式锁的正确性上走得最远的地方，要数对于ZooKeeper分布式锁、单调递增的epoch number以及对分布式资源进行标记的分析了。请仔细审查相关的论证。

Martin为我们留下了不少疑问，尤其是他提出的fencing token机制。他在blog中提到，会在他的新书《Designing Data-Intensive Applications》的第8章和第9章再详加论述。目前，这本书尚在预售当中。我感觉，这会是一本值得一读的书，它不同于为了出名或赚钱而出版的那种短平快的书籍。可以看出作者在这本书上投入了巨大的精力。

最后，我相信，这个讨论还远没有结束。分布式锁(Distributed Locks)和相应的fencing方案，可以作为一个长期的课题，随着我们对分布式系统的认识逐渐增加，可以再来慢慢地思考它。思考它更深层的本质，以及它在理论上的证明。

（完） 感谢：

由衷地感谢几位朋友花了宝贵的时间对本文草稿所做的review：CacheCloud的作者付磊，快手的李伟博，阿里的李波。当然，文中如果还有错漏，由我本人负责^-^。

其它精选文章：

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

复制代码                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        [基于Redis的分布式锁到底安全吗（上）](http://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=2657261514&idx=1&sn=47b1a63f065347943341910dddbb785d&chksm=84479e13b3301705ea29c86f457ad74010eba8a8a5c12a7f54bcf264a4a8c9d6adecbe32ad0b&scene=21#wechat_redirect)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            [Redis内部数据结构详解(7)——intset](http://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=2657261457&idx=1&sn=fe966f3825b81e9d50a2cf38dac9060c&chksm=84479e48b330175ea07905e791856cca5fc50694db9fd4c3485ba5dc097443e69f5ed28a34b5&scene=21#wechat_redirect)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Redis内部数据结构详解(6)——skip
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                list
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Redis内部数据结构详解(5)——
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            quicklist
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Redis内部数据结构详解(4)——zip
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            list
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Redis内部数据结构详解(3)——robj
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Redis内部数据结构详解(2)——sds
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Redis内部数据结构详解(1)——dict
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            [知识的三个层次](http://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=2657261491&idx=1&sn=cff9bcc4d4cc8c5e642309f7ac1dd5b3&chksm=84479e6ab330177c51bbf8178edc0a6f0a1d56bbeb997ab1cf07d5489336aa59748dea1b3bbc&scene=21#wechat_redirect)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    [小白的数据进阶之路](http://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=2657261434&idx=1&sn=b53c0ec13953f6a28f24abf0e6ee3629&chksm=84479ea3b33017b5dd96082ceaba9883d45b4700aabf3c3a13463ff3ca5894aaba42d4696b7f&scene=21#wechat_redirect)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            [深度学习、信息路与统计学](http://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=2657261505&idx=1&sn=32b9dc4d729679b53f71dba11ce70d25&chksm=84479e18b330170e3519a8f6bd5f9a919b9bd454da26aada2c11525c5999a23a7f74aba6e797&scene=21#wechat_redirect)

扫码或长按关注微信公众号：张铁蕾。

有时候写点技术干货，有时候写点有趣的文章。

这个公众号有点科幻。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

长久以来，OpenStack基金会一直致力于在其同名云计算基础设施项目之外拓展新的疆土，而这成为其最为核心的关注重点。考虑到这一背景，该基金会日前宣布推出Kata Containers[1]项目自然也不足为奇。

Kata Containers为全新开源项目，旨在为用户带来最出色的容器解决方案（包括速度、灵活性与可管理性等），同时提供最强大的虚拟机机制（特别是在安全性方面）。其建立在英特尔的Clear Containers技术与Hyper的runV[2]虚拟机管理程序运行时基础之上。

正如OpenStack基金会执行总监Jonathan Bryce在采访中所指出，该基金会正在努力支持更多项目，以便在云环境中运行生产工作负载。他解释称：“在OpenStack基金会，我们高度关注我们所建立的用户社区，努力解决其实际需求——这一点比OpenStack核心服务本身更为重要。”

那么，Kata Containers项目到底是什么？总结来讲，其基本思想是承认尽管拥有种种优势，但容器技术一直存在着一些基本的安全问题——这主要是因为各容器在共享虚拟机上运行时很难保证彼此之间的完全隔离。Kata Containers项目则通过为每套容器提供其专属的、高度轻量化的虚拟机与内核来解决这个问题，旨在确保各个容器或容器pod能够在真正的独立环境中运行，且具备自己的网络、I/O以及内存配额；此外，其还将通过英特尔为自家处理器构建的虚拟机化技术实现硬件层面的强制隔离。

Kata Containers项目目前集成有Kubernetes、Docker与OpenStack，暂时只能在基于x86架构的芯片上运行，且仅支持KVM作为虚拟机管理程序选项。不过，该项目未来还将逐步添加对其它架构以及虚拟机管理程序的支持能力。

截至目前，英特尔与Hyper都分别致力于构建类似的解决方案。Hyper公司COO James Kulina告诉我们，该公司已经与英特尔就此进行了长达一年的合作，且双方都认为目前是推出标准化解决方案的最佳时机。考虑到Canonical、中国移动、CoreOS、戴尔/EMC、谷歌、华为、京东、Mirantis、Suse、腾讯以及中兴等企业都已经支持这套解决方案，其中来自中国的电商平台京东甚至已经开始在其数据中心内运行Hyper的runV技术。

除了具体技术之外，看到OpenStack基金会朝着核心项目之外迈出发展步伐同样令人振奋。该基金会目前将自身描述为“开放式基础设施之家”，Kata项目的出现无疑很好地印证了这样的表述。这同时表明，OpenStack基金会将能够为这一新项目带来更多支持者。

值得强调的是，Kata容器本身是一个独立项目，拥有自己的技术治理体系与贡献者群体。OpenStack基金会将负责管理此项目，具体方式类似于Linux基金会为Cloud Foundry基金会的CNCF提供支持。

Kata Containers项目的代码目前已经发布在GitHub之上，而且与其它OpenStack项目类似，其代码遵循Apache 2许可进行授权。
相关链接：

1. http://www.katacontainers.io/
2. https://github.com/hyperhq/runv

原文链接：https://techcrunch.com/2017/12/05/intel-and-hyper-partner-with-the-openstack-foundation-to-launch-the-kata-containers-project/

基于Kubernetes的DevOps实践培训

本次培训内容包含：Kubernetes架构、安装、深入了解Kubernetes、Kubernetes高阶——设计与实现、Kubernetes落地实践、微服务、Cloud Native等，点击识别下方二维码加微信好友了解具体培训内容。

点击阅读原文链接即可报名。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

介绍

TgDao是一款基于Mybatis的编译期SQL生成器，利用注解来表达SQL，能根据你的方法签名生成对应的Mapper.xml文件。
它能减少你日常开发中大量简单SQL的编写，由于它只是生成Mapper.xml文件，因此对于复杂的查询场景，
你同样可以自己编写来完成一些工具所无法生成的SQL。

1
2
3
4
5
6
7

复制代码@Table(name = "T_User")
public class User {
    @Id("id")
    private int id;
    private String username;
    private int age;
}

上面的model定义了模型和数据库表的关系，看到下面这些方法的签名，聪明的你肯定能猜出每个方法的sql吧，这就是这个库要做的工作。

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

复制代码@DaoGen(model = User.class)
public interface UserDao {
    @Select
    @OrderBy("id desc")
    List<User> queryUser(@Condition(criterion = Criterions.EQUAL, column = "username") String name,
                         @Condition(criterion = Criterions.GREATER, attach = Attach.OR) int age,
                         @Limit int limit, @OffSet int offset);

    @Select
    List<User> queryUser2(@Condition(criterion = Criterions.GREATER, column = "age") int min,
                          @Condition(criterion = Criterions.LESS, column = "age") int max);

    @Select
    List<User> queryUser3(@Condition(criterion = Criterions.EQUAL, column = "username") String name,
                          @Condition(attach = Attach.OR, column = "id", criterion = Criterions.IN) String[] ids);

    @Insert(useGeneratedKeys = true, keyProperty = "id")
    int insert(User user);

    @BatchInsert(columns = "username,age")
    int batchInsert(List<User> users);

    @Update
    @ModelConditions({
            @ModelCondition(field = "id")
    })
    int update(User user);

    @Delete
    int delete(@Condition(criterion = Criterions.GREATER, column = "age") int min,
               @Condition(criterion = Criterions.LESS, column = "age") int max);
}

项目地址 github.com/twogoods/Tg…

文档

引入如下依赖：

1
2
3
4
5

复制代码<dependency>
  <groupId>com.github.twogoods</groupId>
  <artifactId>tgdao-core</artifactId>
  <version>0.1.3</version>
</dependency>

Table与Model关联

@Table记录数据表的名字
@Id记录主键信息
@Column映射了表字段和属性的关系，如果表字段和类属性同名，那么可以省略这个注解
@Ingore忽略这个类属性，没有哪个表字段与它关联

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复制代码@Table(name = "T_User")
public class User {
    @Id("id")
    private int id;

    private String username;
    private String password;
    private int age;

    @Column("old_address")
    private String oldAddress;
    @Column("now_address")
    private String nowAddress;

    private int state;

    @Column("created_at")
    private Timestamp createdAt;
    @Column("updated_at")
    private Timestamp updatedAt;

    @Ignore
    private String remrk;

查询

1
2
3
4
5
6

复制代码@Select
@OrderBy("id desc")
List<User> queryUser(@Condition(criterion = Criterions.EQUAL, column = "username") String name,
                    @Condition(criterion = Criterions.GREATER, attach = Attach.OR) int age,
                    @Condition(column = "id", criterion = Criterions.IN) String[] ids,
                    @Limit int limit, @OffSet int offset);

@Select

• columns:默认 select *可以配置columns("username,age")选择部分字段；
• SqlMode:有两个选择，SqlMode.SELECTIVE 和 SqlMode.COMMON，区别是selective会检查查询条件的字段是否为null来实现动态的查询,
  即<if test="name != null">username = #{name}</if>

@Condition

• criterion：查询条件，=,<,>,in等，具体见Criterions
• column：与表字段的对应，若与字段名相同可不配置
• attach：连接 and,or， 默认是and
• test：selective下的判断表达式，即<if test="username != null">里的test属性

@Limit，@OffSet为分页字段。
方法的参数不加任何注解一样会被当做查询条件，如下面两个函数效果是一样的：

1
2
3
4
5

复制代码@Select()
List<User> queryUser(Integer age);

@Select()
List<User> queryUser(@Condition(criterion = Criterions.EQUAL, column = "age") Integer age);

查询Model

上面的例子在查询条件比较多时方法参数会比较多，我们可以把查询条件封装到一个类里，使用@ModelConditions来注解查询条件，注意被@ModelConditions只能有一个参数。

1
2
3
4
5
6
7
8
9
10

复制代码@Select
@Page
@ModelConditions({
       @ModelCondition(field = "username", criterion = Criterions.EQUAL),
       @ModelCondition(field = "minAge", column = "age", criterion = Criterions.GREATER),
       @ModelCondition(field = "maxAge", column = "age", criterion = Criterions.LESS),
       @ModelCondition(field = "ids", column = "id", criterion = Criterions.IN),
       @ModelCondition(field = "idArr", column = "id", criterion = Criterions.IN, paramType = InType.ARRAY)
})
List<User> queryUser5(UserSearch userSearch);

@ModelCondition

• field:必填，查询条件中类对应的属性
• column：对应的表字段
• paramType：in 查询下才需要配置，数组为array,List为collection类型
• test：selective下的判断表达式，即<if test="username != null">里的test属性

@Page只能用在ModelConditions下的查询，并且方法参数的那个类应该有offset，limit这两个属性。

注：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复制代码@Select(columns = "username,age")
List<User> queryUser(Integer age);

@Select(columns = "username,age")
List<User> queryUser2param(Integer age, String username);

<select id="queryUser" resultMap="XXX">select username,age from T_User
    <where>
      <if test="age != null">AND age = #{age}</if>
    </where>
</select>

<select id="queryUser2param" resultMap="XXX">select username,age from T_User
    <where>
      <if test="age != null">AND age = #{age}</if>
      <if test="username != null">AND username = #{username}</if>
    </where>
</select>

两个函数生成的sql如上，@Select的属性SqlMode默认是Selective，所以两个都有条件判断，但是这里第一个函数的sql，
Mybatis不支持，执行会报错，类似no age getter in java.lang.Interger，Mybatis会把这唯一的一个参数当做对象来取里面的值。
解决方法：函数签名里强加@Param()注解，或者@Select里使用sqlMode = SqlMode.COMMON去掉生成sql里的if判断。
这个问题只会在方法只有一个参数的情况下发生，第二个函数生成的sql是ok的。

分页

查询参数里@Limit，@OffSet或查询model里@Page的分页功能都比较原始，TgDao只是一款SQL生成器而已，因此你可以使用各种插件，
或者与其他框架集成。对于分页，可以无缝与PageHelper整合。

1
2
3
4
5
6
7
8
9
10
11
12
13

复制代码@Select
List<User> queryUser2(@Condition(criterion = Criterions.GREATER, column = "age") int min,
                @Condition(criterion = Criterions.LESS, column = "age") int max);


@Test
public void testQueryUser2() throws Exception {
   PageHelper.offsetPage(1, 10);
   List<User> users = mapper.queryUser2(12, 30);
   PageInfo page = new PageInfo<>(users);
   System.out.println(page.getTotal());
   Assert.assertTrue(page.getList().size() > 0);
}

插入

1
2
3
4
5

复制代码@Insert(useGeneratedKeys = true, keyProperty = "id")//获取自增id
int insert(User user);

@BatchInsert(columns = "username,age")//插入的列
int batchInsert(List<User> users);

BatchInsert强烈建议写columns，因为生成的语句并不会过滤null字段，数据库中插入null易报错。

更新

1
2
3
4
5

复制代码@Update(columns = "username,age")//选择更新某几个列
@ModelConditions({
       @ModelCondition(field = "id")
})
int update(User user);

删除

1
2
3
4
5
6
7
8
9
10

复制代码@Delete
int delete(@Condition(criterion = Criterions.GREATER, column = "age") int min,
          @Condition(criterion = Criterions.LESS, column = "age") int max);

@Delete
@ModelConditions({
       @ModelCondition(attach = Attach.AND, field = "minAge", column = "age", criterion = Criterions.GREATER),
       @ModelCondition(attach = Attach.AND, field = "maxAge", column = "age", criterion = Criterions.LESS)
})
int delete2(UserSearch userSearch);

selective

@Select，@Count，@Update，@Delete都有selective这个属性，这个属性有两个值，分别是SqlMode.COMMON和SqlMode.SELECTIVE。
它们的区别在下面这段生成的xml里显示的很清楚，SqlMode.SELECTIVE引入了Mybatis的动态SQL能力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

复制代码  <!-- SELECTIVE -->
  <select id="queryUser" resultMap="BaseResultMap">select username,age from T_User 
    <where>
      <if test="name!=null and name!=''">AND username = #{name}</if>
      <if test="age != null">OR age = #{age}</if>
    </where>
  </select>
  
  <!-- COMMON -->
  <select id="queryUser" resultMap="BaseResultMap">select username,age from T_User 
    <where>
      AND username = #{name} OR age = #{age}
    </where>
  </select>

@Select，@Count默认的selective属性是SqlMode.SELECTIVE，这样查询语句可以充分利用Mybatis的动态SQL能力。
而@Update，@Delete默认是SqlMode.COMMON，这样做的原因是：selective模式下如果参数全是null会使得where语句里没有任何条件，
最终变成全表的更新和删除，这是一个极其危险的动作。所以@Update，@Delete慎用SqlMode.SELECTIVE模式。

@Params

在介绍这个注解时要先介绍一下Mybatis自己的@Param注解，@Param注解在方法的参数上，给参数定义了一个名字，
这样可以在xml的sql里使用这个名字来取得参数所对应的值。如下：

1
2
3

复制代码    List<User> queryUser(@Param("name") String name);
    
    <select id="queryUser">select * from T_User where username=#{name} </select>

明明参数就叫name,为什么还要@Param注解一个名字name呢？这是因为Java编译完，会丢掉参数名，以至于运行期mybatis不知道这个参数叫什么，所以需要注解一个名字。
在运行时看到mybatis报错如：Parameter 'XXX' not found. Available parameters are... 这就是没有这个注解导致的问题。
但是在Java8里我们已经可以通过给javac 添加-parameters参数来保留参数名字信息，这样mybatis会利用这个信息，这样就不需要加@Param注解了。
maven可以通过如下方式设置：

1
2
3
4
5
6
7
8
9
10

复制代码  <plugin>
      <groupId>org.apache.maven.plugins</groupId>
      <artifactId>maven-compiler-plugin</artifactId>
      <version>3.1</version>
      <configuration>
          <compilerArgs>
              <arg>-parameters</arg>
          </compilerArgs>
      </configuration>
  </plugin>

然而有一种情况-parameters也无能为力，List<User> queryUser4(List ids);当参数是collection或者数组类型时，mybatis依旧无法认出ids这个参数，只认collection和array。
而@Params注解是Mybatis自身注解@Param和-parameters外的另外一种解决方案。@Params可以注解在类和方法上，
被它注解的类和方法会在编译期自动给所有方法参数加上@Param注解，它借鉴了lombok的方式在编译期修改抽象语法树从而改变编译生成的字节码文件。

1
2
3
4
5
6

复制代码    @Select(columns = "username,age")
    @Params
    List<User> queryUser(Integer age, String username);
    
    //编译后
    List<User> queryUser(@Param("age") Integer var1, @Param("username") String var2);

更多请看example

说明

• 编译生成的XML文件与Mapper接口在同一个包下
• 只支持Java8和MySql
• 修改了源代码中方法的定义或者model里和数据表的映射关系，发现编译出来的xml却没有改变，这是增量编译的原因。生成一个xml同时需要model和mapper interface两个部分，
  如果你只修改了其中一个的代码，那么另一个未修改的代码编译器就不做处理，这样这一次编译就无法得到全部的信息，所以TgDao无法生成最新版本的xml。
  解决方法是每次mvn clean compile先清除一下编译目录，更好的方案正在寻找…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

大家或多或少听说过ThreadLocal这个词,我们创建的对象默认是所有线程可以访问的,多线程并发修改对象时就会可能出现数据不一致的问题,使用ThreadLocal创建的对象只能被当前线程访问，每个线程保存一个对象的副本,在多线程操作时是线程安全的。

ThreadLocal用法简介

比如有这样一个类:

1
2
3
4
5
6
7

复制代码public class Counter{
	private int count;
 	public Counter(int cnt) {
            this.count = cnt;
    }
	//省略setter()和getter()方法
}

我们希望多线程访问Counter对象时，各个线程各自保留一份count计数,那可以这么写:

1
2
3

复制代码ThreadLocal<Counter> threadLocal = new ThreadLocal<>();
threadLocal.set(new Counter(0));
Counter counter = threadLocal.get();

如果你不想每次调用的时候都去初始化,那可以重写ThreadLocal的initValue()方法给ThreadLocal设置一个对象的初始值,如下所示:

1
2
3
4
5
6

复制代码ThreadLocal<Counter> threadLocal = new ThreadLocal<Counter>() {
    @Override
    protected Counter initialValue() {
        return new Counter(0);
    }
};

这样每次调用threadLocal.get()的时候，会去判断当前线程是否存在Counter对象,如果不存在则调用initValue()方法初始化。

ThreadLocal实现原理

我们先来看一下ThreadLocal的get()方法，如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13

复制代码public T get() {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            return result;
        }
    }
    return setInitialValue();
}

调用get()方法时先获取到当前线程,然后通过线程获取每个线程绑定的ThreadLocalMap对象,map中的key就是ThreadLocal对象,Value就是实际我们要访问的对象，上面的例子中是Counter对象,如果Entry为空,那就调用setInitialValue()方法设置初始值。

ThreadLocalMap实现原理

从前面可以看出每个线程内部有个ThreadLocalMap,从java.lang.Thread类的源码也可以看到Thread类有个ThreadLocal.ThreadLocalMap threadLocals属性,接下来我们来分析下它的实现原理:
ThreadLocalMap和WeakHashMap实现有点类似，也是利用了WeakReference来和GC建立关联,因为ThreadLocal对象被线程对象引用，如果一个线程的生命周期比较长,那可能会出现内存泄露的问题，ThreadLocalMap借助弱引用巧妙的解决了这个问题，源码如下所示:

1
2
3
4
5
6
7
8
9
10
11

复制代码static class ThreadLocalMap {
    static class Entry extends WeakReference<ThreadLocal<?>> {
        /** The value associated with this ThreadLocal. */
        Object value;
		//这里的Entry并不是一个链表,如果出现hash碰撞,会放到数组的下一个位置
        Entry(ThreadLocal<?> k, Object v) {
            super(k);
            value = v;
        }
    }
}

从源码可以看到ThreadLocalMap的Entry继承自WeakReference,Entry中的key是一个弱引用，也就是说线程类持有了ThreadLocal对象的一个弱引用,当ThreadLocal对象没有其他强引用关联时,在GC时会把ThreadLocal对象回收掉，但是这里仅仅回收ThreadLocal对象,Entry对象和Value并没有回收,ThreadLocalMap里就可能存在很多Key为null的Entry,所以需要在调用map.getEntry()时对key为null的对象进行处理,源码如下:

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

复制代码private Entry getEntry(ThreadLocal<?> key) {
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if (e != null && e.get() == key)
        return e;
    else
		//当前位置没有找到,可能Hash碰撞了
        return getEntryAfterMiss(key, i, e);
}

private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
    Entry[] tab = table;
    int len = tab.length;

    while (e != null) {
        ThreadLocal<?> k = e.get();
        if (k == key)
			//找到了直接返回
            return e;
        if (k == null)
			//检测到有个ThreadLocal对象被回收了,这个时候去清理后面所有Key为null的Entry
            expungeStaleEntry(i);
        else
            i = nextIndex(i, len);
        e = tab[i];
    }
    return null;
}

从源码中可以看到ThreadLocalMap清理掉key为Null的Entry的时机是根据ThreadLocal对象的hashCode去获取entry时发生了hash碰撞,并且下一个entry的key为null时才去清理,因为ThreadLocalMap的Entry和普通Map的不太一样，一般的Map是一个链表数组，而它的数组每个元素就是一个Entry，如果出现Hash碰撞了就放到数组的下一个位置,因此如果get的时候发现没有碰撞可以认为当前Map中的元素还不多，一旦检测到碰撞了并且下一个entry的key被回收了,就调用expungeStaleEntry（）来释放ThreadLocal为null的那些entry,避免了内存泄露。

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

复制代码private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;

    // expunge entry at staleSlot
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;

    // Rehash until we encounter null
    Entry e;
    int i;
    for (i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        if (k == null) {
			//清理key为null的entry
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
			//hashCode发生了变化,重新放置entry
            if (h != i) {
                tab[i] = null;
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    return i;
}

总结

ThreadLocal可以保证每个线程拥有一个变量的副本，实现了线程隔离,主要利用了每个Thread有个ThreadLocalMap,ThreadLocalMap保存了该线程拥有的所有ThreadLocal对象，并利用弱引用机制避免了Map无线增大导致内存泄露的问题。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有