上一篇介绍了OAuth2协议的基本原理，以及Spring Security框架中自带的OAuth2客户端GitHub的实现细节，本篇以微信公众号网页授权登录为目的，介绍如何在原框架基础上定制开发OAuth2客户端。

一、微信公众平台OAuth2服务

先简单地介绍一下微信公众平台网页授权主要流程，具体可以参考微信公众平台的官方文档（https://developers.weixin.qq.com/doc/offiaccount/OA_Web_Apps/Wechat_webpage_authorization.html）

1.1 请求code

其服务端点为：https://open.weixin.qq.com/connect/oauth2/authorize?appid=APPID&redirect_uri=REDIRECT_URI&response_type=code&scope=SCOPE&state=STATE#wechat_redirect

参数部分说明：

• appId：必填参数，即clientId，公众号唯一标识
• redirect_uri：必填参数，同OAuth2标准协议，表示服务端生成code之后重定向会本系统的地址
• response_type：必填参数，同OAuth2标准协议，需填写"code"
• scope: 必填参数，同OAuth2标准协议，在微信公众号访问中有两个场景，一种参数值为"snsapi_login"，用于静默授权并自动重定向，只能获取到用户的openId，另一种参数值为“snsapi_userinfo”，用于弹出授权页面，供用户手动确认的场景，可以获取昵称、性别、所在地等信息
• state: 非必填参数，同OAuth2标准协议，可防止CSRF攻击，最好加上，可使用Spring Security框提供的默认实现，上一篇已提过。
• #wechat_redirect：这个fragment不能少，但也不是OAuth2标准协议的规范，官方也未作过多说明，可能是出于某种安全考虑

另外需要格外注意的是，微信公众平台会对这个授权请求的参数顺序进行校验，如果顺序不对，也会导致授权失败。

1.2 服务端重定向

服务端在收到请求后，就弹出用户授权页面，用户同意授权后（如使用静默授权则直接通过），又会重定向到redirect_uri的地址，并携带code和state参数，例如redirect_uri?code=CODE&state=STATE，客户端在收到这个请求后，获得code和state的参数值，并再次发起请求，获取access_token

1.3 获取access_token

其服务端点为：https://api.weixin.qq.com/sns/oauth2/access_token?appid=APPID&secret=SECRET&code=CODE&grant_type=authorization_code

参数部分说明：

• appId：必填参数，即clientId，公众号唯一标识
• secret：必填参数，即client_secret，可在公众平台内查看
• code：必填参数，同OAuth2标准协议，即上一步获取的code参数
• grant_type：必填参数，同OAuth2标准协议，固定值“authorization_code”

这个端点看似是用GET请求，但实测用POST请求也是可以获取到access_token。

响应数据示例如下

{
  "access_token":"ACCESS_TOKEN",
  "expires_in":7200,
  "refresh_token":"REFRESH_TOKEN",
  "openid":"OPENID",
  "scope":"SCOPE",
  "is_snapshotuser": 1,
  "unionid": "UNIONID"
}

1.4 获取用户基础信息

其服务端点为：https://api.weixin.qq.com/sns/userinfo?access_token=ACCESS_TOKEN&openid=OPENID&lang=zh_CN

参数部分说明：

• access_token：必填参数，即上一步获取到的acces_token
• openid：必填参数，即上一步获取到的openid，用户唯一标识
• lang：非必填参数，即返回数据的语言，zh_CN 简体，zh_TW 繁体，en 英语

这里没有按照标准协议的建议，将access_token放在Header中的Authorization字段，而是作为URL参数。

响应数据示例如下：

{   
  "openid": "OPENID",
  "nickname": NICKNAME,
  "sex": 1,
  "province":"PROVINCE",
  "city":"CITY",
  "country":"COUNTRY",
  "headimgurl":"https://thirdwx.qlogo.cn/mmopen/g3MonUZtNHkdmzicIlibx6iaFqAc56vxLSUfpb6n5WKSYVY0ChQKkiaJSgQ1dZuTOgvLLrhJbERQQ4eMsv84eavHiaiceqxibJxCfHe/46",
  "privilege":[ "PRIVILEGE1" "PRIVILEGE2"     ],
  "unionid": "o6_bmasdasdsad6_2sgVt7hMZOPfL"
}

1.5 差异分析

可以看到，微信公众平台提供的OAuth2授权服务没有严格遵循标准协议，所以先梳理一下哪些是需要定制的部分，综上所述，主要有以下3点：

1. 在发起授权请求时，包括：

• client-id这个参数需重命名为appid
• 请求code的参数顺序必须依次为appid，redirect_uri，response_type，scope，state
• 参数最后必须加上“#wechat_redirect”这个锚点

2. 在获取access_token时，包括：

• client-id，client-secret这两个参数需重命名为appid和secret
• 服务端响应的MediaType为text/plain，而默认HttpMessageConverter仅支持application/json
• 根据OAuth2标准协议，返回的数据字段中缺少了一个必须字段：token_type，需要自动填充进去，否则反序列化时就会报错

3. 在获取用户信息时，包括

• 需要在请求地址中拼接access_token，openid这两个参数，并指定为GET请求
• 同上，需要兼容text/plain的MediaType

二、开发实战

下面我们逐步介绍如何优雅地实现这些定制需求，这里秉持一种原则，尽量复用框架的代码，减少重复造轮所带来的成本。

2.1 准备工作

这里我们使用微信公众平台提供的测试账号进行开发（https://mp.weixin.qq.com/debug/cgi-bin/sandbox?t=sandbox/login），只要扫描即可登录使用。另外，为了方便调试，可以下载微信开发者工具模拟微信客户端环境（https://developers.weixin.qq.com/miniprogram/dev/devtools/download.html）

2.2 引入依赖

说明：本篇所使用的Spring Boot为3.3.0，对应Spring Security版本为6.3.0，但其他6.x版本也同样适用。

<properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    <spring-boot.version>3.3.0</spring-boot.version>
</properties>

<dependencyManagement>
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-dependencies</artifactId>
            <version>${spring-boot.version}</version>
            <type>pom</type>
            <scope>import</scope>
        </dependency>
    </dependencies>
</dependencyManagement>

<dependencies>
    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <scope>annotationProcessor</scope>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-security</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.security</groupId>
        <artifactId>spring-security-oauth2-client</artifactId>
    </dependency>
</dependencies>

2.3 配置客户端信息

首先在application.yml文件中配置关于微信公众平台OAuth2客户端的基础信息：

spring:
  security:
    oauth2:
      client:
        registration:
          wechat:
            client-id: *********
            client-secret: *******************
            authorization-grant-type: authorization_code
            redirect-uri: "{baseUrl}/{action}/oauth2/code/{registrationId}"
            scope: snsapi_userinfo # 该scope允许获取微信的用户信息
        provider:
          wechat:
            authorization-uri: https://open.weixin.qq.com/connect/oauth2/authorize
            token-uri: https://api.weixin.qq.com/sns/oauth2/access_token
            user-info-uri: https://api.weixin.qq.com/sns/userinfo
            user-name-attribute: nickname # 用户名对应的属性名称，即微信昵称

其次在HttpSecurity的oauth2Login DSL中，重点关注3个配置项：authorizationEndpoint，tokenEndpoint及userInfoEndpoint，分别用于定制发起授权请求，获取access_token，以及获取用户信息这3个部分的业务逻辑，下面详细介绍如何利用这些配置项将定制逻辑注入进来，当然也可以直接跳过2.4-2.6小节，2.7小节直接给出了完整的代码。

2.4 authorizationEndpoint配置

该配置项其中有一个authorizationRequestResolver的扩展点，用于配置接口OAuth2AuthorizationRequestResolver的实例，OAuth2AuthorizationRequestResolver是用来生成发起授权请求对象OAuth2AuthorizationRequest，最终用于发起授权请求的地址authorizationRequestUri就是从OAuth2AuthorizationRequest对象中获取的，其默认实现类是DefaultOAuth2AuthorizationRequestResolver，下面是其核心方法resolve，实际生成过程其实依赖OAuth2AuthorizationRequest.Builder构造器，这里预留了一个authorizationRequestCustomizer对象，可以实现对Builder对象的定制

public final class DefaultOAuth2AuthorizationRequestResolver implements OAuth2AuthorizationRequestResolver {
    ...
    private Consumer<OAuth2AuthorizationRequest.Builder> authorizationRequestCustomizer = (customizer) -> {};
    ...         
    private OAuth2AuthorizationRequest resolve(HttpServletRequest request, String registrationId,
           String redirectUriAction) {
        if (registrationId == null) {
           return null;
        }
        ClientRegistration clientRegistration = this.clientRegistrationRepository.findByRegistrationId(registrationId);
        if (clientRegistration == null) {
           throw new InvalidClientRegistrationIdException("Invalid Client Registration with Id: " + registrationId);
        }
        OAuth2AuthorizationRequest.Builder builder = getBuilder(clientRegistration);
        ...
        this.authorizationRequestCustomizer.accept(builder); // 可在此注入定制逻辑
        return builder.build();
    }
    ...
}

再看一下构造器Builder内部authorizationRequestUri的生成方法，其build方法源码如下，这里有两个扩展点，一个是parametersConsumer，一个是authorizationRequestUriFunction，前者可以用于替换参数名称，以及调整参数顺序，后者可以对UriBuilder作进一步的定制，我们可以用来添加“#wechat_redirect”。

public OAuth2AuthorizationRequest build() {
    ...
    authorizationRequest.authorizationRequestUri = StringUtils.hasText(this.authorizationRequestUri)
          ? this.authorizationRequestUri : this.buildAuthorizationRequestUri(); // 如果没有额外设置，最终构造URL的方法是buildAuthorizationRequestUri
    return authorizationRequest;
}

private String buildAuthorizationRequestUri() {
    Map<String, Object> parameters = getParameters(); 
    this.parametersConsumer.accept(parameters); // 扩展点
    MultiValueMap<String, String> queryParams = new LinkedMultiValueMap<>();
    parameters.forEach((k, v) -> queryParams.set(encodeQueryParam(k), encodeQueryParam(String.valueOf(v)))); 
    UriBuilder uriBuilder = this.uriBuilderFactory.uriString(this.authorizationUri).queryParams(queryParams);
    return this.authorizationRequestUriFunction.apply(uriBuilder).toString(); // 扩展点
}

2.5 tokenEndpoint配置

该配置项仅有一个accessTokenResponseClient的扩展点，用于配置接口OAuth2AccessTokenResponseClient的实例，它定义了获取access_token的客户端操作，其中授权码模式的实现类为DefaultAuthorizationCodeTokenResponseClient，可以看到这里有两个扩展点，一个是requestEntityConverter，可以用于调整参数，二是RestOperations，为了支持响应的MediaType，以及默认填充token_type字段，再对RestTemplate实例做进一步定制。

public final class DefaultAuthorizationCodeTokenResponseClient implements OAuth2AccessTokenResponseClient<OAuth2AuthorizationCodeGrantRequest> {
    ...
    private Converter<OAuth2AuthorizationCodeGrantRequest, RequestEntity<?>> requestEntityConverter = new ClientAuthenticationMethodValidatingRequestEntityConverter<>(
          new OAuth2AuthorizationCodeGrantRequestEntityConverter());

    private RestOperations restOperations;
    
    public DefaultAuthorizationCodeTokenResponseClient() {
        RestTemplate restTemplate = new RestTemplate(
              Arrays.asList(new FormHttpMessageConverter(), new OAuth2AccessTokenResponseHttpMessageConverter())); // 定制OAuth2AccessTokenResponseHttpMessageConverter
        restTemplate.setErrorHandler(new OAuth2ErrorResponseErrorHandler());
        this.restOperations = restTemplate;
    }

    @Override
    public OAuth2AccessTokenResponse getTokenResponse(OAuth2AuthorizationCodeGrantRequest authorizationCodeGrantRequest) {
       ...
       RequestEntity<?> request = this.requestEntityConverter.convert(authorizationCodeGrantRequest); //生成请求实体对象，利用这个converter注入定制逻辑
       ResponseEntity<OAuth2AccessTokenResponse> response = getResponse(request);
       OAuth2AccessTokenResponse tokenResponse = response.getBody();
       ...
       return tokenResponse;
    }

    private ResponseEntity<OAuth2AccessTokenResponse> getResponse(RequestEntity<?> request) {
       ...
          return this.restOperations.exchange(request, OAuth2AccessTokenResponse.class);

    }
    ...
}

2.6 userInfoEndpoint配置

该配置项有一个userService的扩展点，用于配置接口OAuth2UserService的实例，它定义了发起获取用户信息请求的客户端操作，默认实现类为DefaultOAuth2UserService，与上面类似，它也有两个扩展点，一个是requestEntityConverter，以及一个RestOperations，定制逻辑也基本类似。

public class DefaultOAuth2UserService implements OAuth2UserService<OAuth2UserRequest, OAuth2User> {
    ...
    private Converter<OAuth2UserRequest, RequestEntity<?>> requestEntityConverter = new OAuth2UserRequestEntityConverter();

    private RestOperations restOperations;

    public DefaultOAuth2UserService() {
       RestTemplate restTemplate = new RestTemplate();
       restTemplate.setErrorHandler(new OAuth2ErrorResponseErrorHandler());
       this.restOperations = restTemplate;
    }
    
    @Override
    public OAuth2User loadUser(OAuth2UserRequest userRequest) throws OAuth2AuthenticationException {
        Assert.notNull(userRequest, "userRequest cannot be null");
        String userNameAttributeName = getUserNameAttributeName(userRequest);
        RequestEntity<?> request = this.requestEntityConverter.convert(userRequest);
        ResponseEntity<Map<String, Object>> response = getResponse(userRequest, request);
        OAuth2AccessToken token = userRequest.getAccessToken();
        Map<String, Object> attributes = this.attributesConverter.convert(userRequest).convert(response.getBody());
        Collection<GrantedAuthority> authorities = getAuthorities(token, attributes);
        return new DefaultOAuth2User(authorities, attributes, userNameAttributeName);
    }
    ...
}

2.7 定制开发

下面给出完整代码，为了方便展示，下面将所有的定制实现类，都放在同一个Configuration类中，实际开发过程中，可以根据需要进行拆分调整

@Slf4j
@EnableWebSecurity
@Configuration
public class SpringSecurityConfiguration {

    @Resource
    private ClientRegistrationRepository clientRegistrationRepository;

    @Bean
    public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
        http.oauth2Login(oauth2 -> oauth2
                .authorizationEndpoint(authorization -> authorization.authorizationRequestResolver(authorizationRequestResolver(clientRegistrationRepository)))
                .tokenEndpoint(token -> token.accessTokenResponseClient(accessTokenResponseClient()))
                .userInfoEndpoint(userInfo -> userInfo.userService(userService()))
        );
        DefaultSecurityFilterChain filterChain = http.build();
        filterChain.getFilters().stream().map(Object::toString).forEach(log::info);
        return filterChain;
    }

    private OAuth2AuthorizationRequestResolver authorizationRequestResolver(ClientRegistrationRepository clientRegistrationRepository) {
        String authorizationRequestBaseUri = OAuth2AuthorizationRequestRedirectFilter.DEFAULT_AUTHORIZATION_REQUEST_BASE_URI;
        // 参考框架内默认的实例构造方法
        DefaultOAuth2AuthorizationRequestResolver resolver = new DefaultOAuth2AuthorizationRequestResolver(clientRegistrationRepository, authorizationRequestBaseUri);
        // 设置OAuth2AuthorizationRequest.builder的定制逻辑
        resolver.setAuthorizationRequestCustomizer(builder -> builder.parameters(this::parametersConsumer).authorizationRequestUri(this::authorizationRequestUriFunction));
        return resolver;
    }

    private void parametersConsumer(Map<String, Object> parameters) {
        Object clientId = parameters.get(OAuth2ParameterNames.CLIENT_ID);
        Object redirectUri = parameters.get(OAuth2ParameterNames.REDIRECT_URI);
        Object responseType = parameters.get(OAuth2ParameterNames.RESPONSE_TYPE);
        Object scope = parameters.get(OAuth2ParameterNames.SCOPE);
        Object state = parameters.get(OAuth2ParameterNames.STATE);
        // 清除掉原来所有的参数
        parameters.clear();
        // 重新调整顺序
        parameters.put("appid", clientId);// 修改clientId参数名称为appid
        parameters.put(OAuth2ParameterNames.REDIRECT_URI, redirectUri);
        parameters.put(OAuth2ParameterNames.RESPONSE_TYPE, responseType);
        parameters.put(OAuth2ParameterNames.SCOPE, scope);
        parameters.put(OAuth2ParameterNames.STATE, state);

    }

    private URI authorizationRequestUriFunction(UriBuilder builder) {
        builder.fragment("wechat_redirect");// 添加#wechat_redirect
        return builder.build();
    }
    

    private OAuth2AccessTokenResponseClient<OAuth2AuthorizationCodeGrantRequest> accessTokenResponseClient() {
        DefaultAuthorizationCodeTokenResponseClient client = new DefaultAuthorizationCodeTokenResponseClient();
        // 注入自定义WechatOAuth2AuthorizationCodeGrantRequestEntityConverter
        client.setRequestEntityConverter(new WechatOAuth2AuthorizationCodeGrantRequestEntityConverter()); 
        // 创建一个OAuth2AccessTokenResponseHttpMessageConverter对象，设置支持的MediaType为text/plain
        OAuth2AccessTokenResponseHttpMessageConverter messageConverter = new OAuth2AccessTokenResponseHttpMessageConverter();
        messageConverter.setSupportedMediaTypes(List.of(MediaType.TEXT_PLAIN)); 
        messageConverter.setAccessTokenResponseConverter(new WechatOAuth2AccessTokenResponseConverter());
        // 其他配置照搬源码
        RestTemplate restTemplate = new RestTemplate(Arrays.asList(new FormHttpMessageConverter(), messageConverter));
        restTemplate.setErrorHandler(new OAuth2ErrorResponseErrorHandler());
        client.setRestOperations(restTemplate);
        return client;
    }

    private static class WechatOAuth2AccessTokenResponseConverter implements Converter<Map<String, Object>, OAuth2AccessTokenResponse> {

        private static final DefaultMapOAuth2AccessTokenResponseConverter delegate = new DefaultMapOAuth2AccessTokenResponseConverter();
        //响应中缺少token_type字段，为避免报错默认填充，剩余部分依然委托给默认的DefaultMapOAuth2AccessTokenResponseConverter处理
        @Override
        public OAuth2AccessTokenResponse convert(Map<String, Object> source) {
            source.put(OAuth2ParameterNames.TOKEN_TYPE, OAuth2AccessToken.TokenType.BEARER.getValue()); 
            return delegate.convert(source);
        }
    }

    // 无法直接实现接口，不过可以继承OAuth2AuthorizationCodeGrantRequestEntityConverter
    private static class WechatOAuth2AuthorizationCodeGrantRequestEntityConverter extends OAuth2AuthorizationCodeGrantRequestEntityConverter {
        //参考父类的源码，依葫芦画瓢重写createParameters方法，根据微信的文档，依次添加appid，secret，grant_type，code这四个参数
        @Override
        protected MultiValueMap<String, String> createParameters(OAuth2AuthorizationCodeGrantRequest authorizationCodeGrantRequest) {
            ClientRegistration clientRegistration = authorizationCodeGrantRequest.getClientRegistration();
            OAuth2AuthorizationExchange authorizationExchange = authorizationCodeGrantRequest.getAuthorizationExchange();
            MultiValueMap<String, String> parameters = new LinkedMultiValueMap<>();
            parameters.add("appid", clientRegistration.getClientId());
            parameters.add("secret", clientRegistration.getClientSecret());
            parameters.add(OAuth2ParameterNames.GRANT_TYPE, authorizationCodeGrantRequest.getGrantType().getValue());
            parameters.add(OAuth2ParameterNames.CODE, authorizationExchange.getAuthorizationResponse().getCode());
            return parameters;
        }
    }

    private OAuth2UserService<OAuth2UserRequest, OAuth2User> userService() {
        DefaultOAuth2UserService userService = new DefaultOAuth2UserService();
        // 注入自定义的requestEntityConverter
        userService.setRequestEntityConverter(new WechatOAuth2UserRequestEntityConverter());
        // 创建一个MappingJackson2HttpMessageConverter对象，同样设置支持的MediaType为text/plain
        MappingJackson2HttpMessageConverter messageConverter = new MappingJackson2HttpMessageConverter();
        messageConverter.setSupportedMediaTypes(List.of(MediaType.TEXT_PLAIN));
        RestTemplate restTemplate = new RestTemplate(List.of(messageConverter));
        restTemplate.setErrorHandler(new OAuth2ErrorResponseErrorHandler());
        userService.setRestOperations(restTemplate);
        return userService;
    }

    private static class WechatOAuth2UserRequestEntityConverter implements Converter<OAuth2UserRequest, RequestEntity<?>> {
        // 根据微信文档，在请求地址中拼接上access_token和openid两个参数
        @Override
        public RequestEntity<?> convert(OAuth2UserRequest userRequest) {
            ClientRegistration clientRegistration = userRequest.getClientRegistration();
            URI uri = UriComponentsBuilder.fromUriString(clientRegistration.getProviderDetails().getUserInfoEndpoint().getUri())
                    .queryParam(OAuth2ParameterNames.ACCESS_TOKEN, userRequest.getAccessToken().getTokenValue())
                    .queryParam("openid", userRequest.getAdditionalParameters().get("openid"))
                    .build()
                    .toUri();
            return new RequestEntity<>(HttpMethod.GET, uri);
        }
    }
}

三、测试验证

首先为了方便测试，可以在hosts文件中将本地IP"127.0.0.1"映射为一个虚拟的域名，例如www.oauth2.com，然后在微信公众平台测试账号内设置授权回调页面域名地址，找到“网页账号”这一项，点击修改，在弹窗中输入“www.oauth2.com”，点击确认即可。

接着就可以启动程序验证效果了，测试时可以打开spring security的debug日志，在微信开发者工具内访问http://www.oauth2.com/oauth2/authorization/wechat，观察日志输出，请求被重定向到了https://open.weixin.qq.com/connect/oauth2/authorize这个地址，并且参数都按照预期设置成功。

o.s.security.web.FilterChainProxy        : Securing GET /oauth2/authorization/wechat
o.s.s.web.DefaultRedirectStrategy        : Redirecting to https://open.weixin.qq.com/connect/oauth2/authorize?appid=wx3574913d730b2837  
&redirect_uri=http://www.oauth2.com/login/oauth2/code/wechat&response_type=code&scope=snsapi_userinfo
&state=pBpqcIj_Z_A7iiApozDIBPw1IY1XFJQw1uTHhoqvGvs%3D#wechat_redirect

此时客户端会跳转到微信授权页面，如下图

点击同意后，服务端会重定向到redirect_uri的地址，即http://www.oauth2.com/login/oauth2/code/wechat，若该地址后面携带了code和state这两个参数，则表示code获取成功，另外回调地址中的state和此前发起请求时的state两个值也是一样的。

然后通过日志可以看到，接着又发起了获取access_token的请求，如果成功获取到access_token，随即就会使用acces_token再请求获取用户信息的接口，最后在得到用户数据后会创建对应的Authentication对象，并为其进行持久化操作，至此微信公众号网页授权的整个过程就完成了。

o.s.security.web.FilterChainProxy        : Securing GET /login/oauth2/code/wechat?
code=071jlkGa1xcSxH0okrFa1ERx9y0jlkGu&state=KXg4KA_6s6imMwr1Vm0DTZz7m8vn
iA2Bi4RZIjVEx2o%3D

o.s.web.client.RestTemplate              : HTTP POST https://api.weixin.qq.com/sns/oauth2/access_token
o.s.web.client.RestTemplate              : Response 200 OK

o.s.web.client.RestTemplate              : HTTP GET https://api.weixin.qq.com/sns/userinfo?
access_token=81_8wWRqWFvwAVQldmWeraiE7sNOwt7eRZJ5S5teKN2ua90TgxaCpRo97Eh
zR1Hr_3gP0eL7hpUK7zH0zYcFqZ-5Zxxs4as-6P5HJjDHiZ7Tyg&openid=***
2024-06-01T16:57:34.093+08:00 DEBUG 3965 --- [p-nio-80-exec-2] 
o.s.web.client.RestTemplate              : Response 200 OK

2024-06-01T16:57:37.730+08:00 DEBUG 3965 --- [p-nio-80-exec-2] 
w.c.HttpSessionSecurityContextRepository : Stored SecurityContextImpl 
[Authentication=OAuth2AuthenticationToken [Principal=Name: [**], Granted 
Authorities: [[OAUTH2_USER, SCOPE_snsapi_userinfo]], User Attributes: 
[{openid=***, nickname=**, sex=0, language=, city=, province=, country=, 
headimgurl=https://thirdwx.qlogo.cn/mmopen/vi_32/****, privilege=[]}], 
Credentials=[PROTECTED], Authenticated=true, 
Details=WebAuthenticationDetails [RemoteIpAddress=127.0.0.1, 
SessionId=6D5003EC4A8EF36118C02A7138CBAAAF], Granted Authorities=
[OAUTH2_USER, SCOPE_snsapi_userinfo]]] to HttpSession 
[org.apache.catalina.session.StandardSessionFacade@50161408]
2024-06-01T16:57:37.730+08:00 DEBUG 3965 --- [p-nio-80-exec-2] 
.s.o.c.w.OAuth2LoginAuthenticationFilter : Set SecurityContextHolder to 
OAuth2AuthenticationToken [Principal=Name: [**], Granted Authorities: 
[[OAUTH2_USER, SCOPE_snsapi_userinfo]], User Attributes: [{openid=***, 
nickname=**, sex=0, language=, city=, province=, country=, 
headimgurl=https://thirdwx.qlogo.cn/mmopen/vi_32/****, privilege=[]}], 
Credentials=[PROTECTED], Authenticated=true, 
Details=WebAuthenticationDetails [RemoteIpAddress=127.0.0.1, 
SessionId=6D5003EC4A8EF36118C02A7138CBAAAF], Granted Authorities=
[OAUTH2_USER, SCOPE_snsapi_userinfo]]
o.s.s.web.DefaultRedirectStrategy        : Redirecting to /

可以再写一个简单Controller，查看一下实际的Authentication对象

@RestController
public class UserController {

    @GetMapping("/user")
    public String user() {
        String username = SecurityContextHolder.getContext().getAuthentication().getName();
        return "Hello " + username;
    }
    
}

四、结束语

微信公众平台提供的OAuth2授权服务与标准协议的规范存在着诸多不同之处，但是基本框架流程都是相同的，Spring Security框架也为这些差异预留了相应的扩展点，我们在学习源码的时候，要尽量观察和思考这些扩展点的实际用途，这样可以帮助我们找到定制化开发的最佳方案。

上一篇介绍了Spring Security框架中身份认证的架构设计，本篇就OAuth2客户端登录认证的实现源码做一些分析。

一、OAuth2协议简介

OAuth2协议，英文全称Open Authorization 2.0，即开放授权协议，它本身解决的问题，就是互联网中的安全信任问题，当第三方需要访问本系统内受保护资源的时候，如何对其授权以实现合法安全的访问。

举个例子，可能在物理世界里面并不存在，只是为方便说明OAuth2的工作原理。假设有某个大型商场提供了一种无卡消费的服务，用户只要在商场的账户中充值，就可以在商场中任何一家店铺进行无卡消费，此时商家作为第三方，需要访问你的无卡账户，对于用户来说，无卡账户就是一种受保护资源，它并不能随意进行访问，那么怎么解决信任问题。

首先，能够想到的是，任何一家的店铺想要支持无卡消费，就必须在商场内进行登记注册，只有在册的店铺才被允许访问储值卡的账户；

其次，用户不应该在每家店铺消费时都提供用户名和密码，这样密码就存在泄露的风险，商场应该提供一种用户授权的交互方式，在店铺发起访问无卡账户时，用户只需要授权即可，姑且想象一下，在店铺中支付时，会从空气中弹出一个商场提供的确认授权页面，当然商场已经核对了商户的注册信息；

最后，一旦用户对该店铺进行了合法的授权，商场就给店铺发放一个交易凭证，店铺带着这个凭证就可以访问我的无卡账户；

当然，商场应当要保证这个交易凭证的发放是安全的，不能轻易泄露，否则就有盗刷的风险。

以上，OAuth2的工作原理大致如此，用户不用担心自己的密码暴露给了第三方，而又实现了受保护资源的授权访问，其中店铺被授权后得到凭证就是所谓的访问令牌，即access_token。OAuth2协议中最主要的一个部分就是如何获取accessToken，在OAuth2协议规范文档https://datatracker.ietf.org/doc/html/rfc6749中介绍了几种常用的授权模式：

• 授权码模式（Authorization Code Grant）：服务端通过重定向机制，将一次性的授权码code参数下发给客户端，客户端通过code获取accessToken和refreshToken，这种模式比较完整地体现了OAuth2协议的原则，流程较为复杂，但安全性最好，因此也是最常用的模式，广泛运用于各类互联网应用的登录认证场景，交互流程见下图
• 隐式模式（Implicit Grant）：也叫简化模式，没有重定向过程，一次授权请求就可以获得accessToken，通常用于浏览器脚本，例如在JavaScript脚本内发起授权请求，有令牌泄露的风险，安全性一般，另外也不支持refreshToken
• 资源属主密码模式（Resource Owner Password Credentials Grant）：用户需要在第三方应用中输入用户名和密码，上面提到过，这种模式有暴露密码的风险，安全性较差，在OAuth2官方推荐的最佳实践中，已经明确禁止使用这种模式，并且在Spring Security 高版本中也已经弃用
• 客户端凭证模式（Client Credentials Grant）：常用于设备或者可信任的应用本身，通过客户端凭证与OAuth2直接通信进行认证，对用户无感

OAuth2本身是一种协议，它不直接规定实现细节，下面主要就Spring Security框架内OAuth2客户端的源码作一定的分析，通过研究它默认的实现，为将来扩展对接其他OAuth2服务端做一定参考。

二、OAuth2登录认证

Spring Security集成了国外几个OAuth2认证服务商的默认实现，包括Google, GitHub, Facebook, 以及Okta，下面以Github为例，说明OAuth2登录认证（授权码模式）的整个交互过程。

2.1 OAuth2.0客户端配置

默认配置下，仅添加SecurityFilterChain的oauth2Login配置项即可，它主要的作用是向过滤器链中添加两个过滤器：即OAuth2AuthorizationRequestRedirectFilter和OAuth2LoginAuthenticationFilter（第2小节和第3小节会分别介绍这两个类的实现细节），他们分别负责处理两个端点：

• /oauth2/authorization/{client}，即OAuth2授权端点，用于向OAuth2服务端发起授权请求
• /login/oauth2/code/{client}，即OAuth2服务端重定向端点，用于在OAuth2服务端重定向回到本应用时接收code，从而利用code换取accessToken

@EnableWebSecurity
@Configuration
public class SpringSecurityConfiguration {

    @Bean
    public SecurityFilterChain securityFilterChain(HttpSecurity http) throws Exception {
        http.oauth2Login(Customizer.withDefaults());
        return http.build();
    }
}

另外在application.yaml配置文件中注册Github客户端，主要是指定client-id和client-secret这两个参数

通常，client-id和client-secret等参数都需要在Github官网注册自己的应用后，才能拿到。注册的操作流程放在文末的附录中

spring:
  security:
    oauth2:
      client:
        registration:
          github:
            client-id: *********
            client-secret: **********************

至于其他参数，例如authorization-uri，token-uri等，对于任何一个OAuth2的客户端来说都是通用的，所以都已经提前定义好了，具体可以看CommonOAuth2Provider的源码

public enum CommonOAuth2Provider {
 ...
    GITHUB {

       @Override
       public Builder getBuilder(String registrationId) {
          ClientRegistration.Builder builder = getBuilder(registrationId,
                ClientAuthenticationMethod.CLIENT_SECRET_BASIC, DEFAULT_REDIRECT_URL);
          builder.scope("read:user");
          builder.authorizationUri("https://github.com/login/oauth/authorize");
          builder.tokenUri("https://github.com/login/oauth/access_token");
          builder.userInfoUri("https://api.github.com/user");
          builder.userNameAttributeName("id");
          builder.clientName("GitHub");
          return builder;
       }
...
}

在Spring Boot中，当我们在配置文件中添加了spring.security.oauth2.client.registration相关内容时，例如上面的github配置，就会触发自动配置以完成客户端信息的注册，配置类为OAuth2ClientRegistrationRepositoryConfiguration，其中构建过程主要由OAuth2ClientPropertiesMapper这个类完成，源码如下

@Configuration(proxyBeanMethods = false)
@EnableConfigurationProperties(OAuth2ClientProperties.class)
@Conditional(ClientsConfiguredCondition.class)
class OAuth2ClientRegistrationRepositoryConfiguration {

    @Bean
    @ConditionalOnMissingBean(ClientRegistrationRepository.class)
    InMemoryClientRegistrationRepository clientRegistrationRepository(OAuth2ClientProperties properties) {
       List<ClientRegistration> registrations = new ArrayList<>(
             new OAuth2ClientPropertiesMapper(properties).asClientRegistrations().values());
       return new InMemoryClientRegistrationRepository(registrations);
    }

}

public final class OAuth2ClientPropertiesMapper {
...
    private static ClientRegistration getClientRegistration(String registrationId,
          OAuth2ClientProperties.Registration properties, Map<String, Provider> providers) {
       Builder builder = getBuilderFromIssuerIfPossible(registrationId, properties.getProvider(), providers);
       if (builder == null) {
          builder = getBuilder(registrationId, properties.getProvider(), providers);
       }
       PropertyMapper map = PropertyMapper.get().alwaysApplyingWhenNonNull();
       map.from(properties::getClientId).to(builder::clientId);
       map.from(properties::getClientSecret).to(builder::clientSecret);
       map.from(properties::getClientAuthenticationMethod)
          .as(ClientAuthenticationMethod::new)
          .to(builder::clientAuthenticationMethod);
       map.from(properties::getAuthorizationGrantType)
          .as(AuthorizationGrantType::new)
          .to(builder::authorizationGrantType);
       map.from(properties::getRedirectUri).to(builder::redirectUri);
       map.from(properties::getScope).as(StringUtils::toStringArray).to(builder::scope);
       map.from(properties::getClientName).to(builder::clientName);
       return builder.build();
    }
...    
}

OAuth2ClientPropertiesMapper#getBuilder方法会根据application.yml配置文件中配置的客户端名称，从CommonOAuth2Provider枚举类中得到对应枚举值, 即“GITHUB”，并调用其getBuilder方法返回builder对象，然后使用配置文件中的参数值进行填充，最终得到完整的客户端注册信息。

2.2 OAuth2AuthorizationRequestRedirectFilter：提交授权请求

该Filter继承自OncePerRequestFilter，用于向OAuth2协议服务端发起认证请求，核心逻辑也比较简单，其中doFilterInternal核心源码如下

@Override
protected void doFilterInternal(HttpServletRequest request, HttpServletResponse response, FilterChain filterChain)
       throws ServletException, IOException {
    try {
       OAuth2AuthorizationRequest authorizationRequest = this.authorizationRequestResolver.resolve(request);
       if (authorizationRequest != null) {
          this.sendRedirectForAuthorization(request, response, authorizationRequest);
          return;
       }
    }
    catch (Exception ex) {
       this.unsuccessfulRedirectForAuthorization(request, response, ex);
       return;
    }
    ...
}

当请求“/oauth2/authorization/{registrationId}”端点时，authorizationRequestResolver就会解析出{registrationId}对应的值，如github，然后通过registrationId查询到对应客户端的注册信息，并通过构造器OAuth2AuthorizationRequest.Builder，创建出一个OAuth2AuthorizationRequest实例，它主要作用就是生成重定向到OAuth2.0服务端获取code的地址，对于github来说，该地址为https://github.com/login/oauth/authorize?response_type=code&client_id={client_id}&scope=read:user&state={state}&redirect_uri={redirect_uri}，其中state是由客户端生成的一个随机字符串，在Spring Security框架中，使用了32位长度的Base64编码生成算法，而redirect_uri则表示期望OAuth2服务端在通过验证后重定向到本系统的地址，以便从响应中获取code之后发起认证，当然这个redirectUri需要事先注册在OAuth2服务端中，否则视为非授权的访问而拒绝。

private OAuth2AuthorizationRequest resolve(HttpServletRequest request, String registrationId, String redirectUriAction) {
    if (registrationId == null) {
       return null;
    }
    ClientRegistration clientRegistration = this.clientRegistrationRepository.findByRegistrationId(registrationId);
    if (clientRegistration == null) {
       throw new InvalidClientRegistrationIdException("Invalid Client Registration with Id: " + registrationId);
    }
    OAuth2AuthorizationRequest.Builder builder = getBuilder(clientRegistration);

    String redirectUriStr = expandRedirectUri(request, clientRegistration, redirectUriAction);

    // @formatter:off
    builder.clientId(clientRegistration.getClientId())
          .authorizationUri(clientRegistration.getProviderDetails().getAuthorizationUri())
          .redirectUri(redirectUriStr)
          .scopes(clientRegistration.getScopes())
          .state(DEFAULT_STATE_GENERATOR.generateKey());
    // @formatter:on

    this.authorizationRequestCustomizer.accept(builder);

    return builder.build();
}

而在重定向之前，为了在认证通过之后能够跳转回认证前的访问路径，需要保存当前请求的地址，在authorizationRequestRepository#saveAuthorizationRequest方法中，会将当前请求存储到session中，这样就可以在OAuth2服务端回调之后，再从session取出。

private void sendRedirectForAuthorization(HttpServletRequest request, HttpServletResponse response,
       OAuth2AuthorizationRequest authorizationRequest) throws IOException {
    if (AuthorizationGrantType.AUTHORIZATION_CODE.equals(authorizationRequest.getGrantType())) {
       this.authorizationRequestRepository.saveAuthorizationRequest(authorizationRequest, request, response);
    }
    this.authorizationRedirectStrategy.sendRedirect(request, response,
          authorizationRequest.getAuthorizationRequestUri());
}

public void saveAuthorizationRequest(OAuth2AuthorizationRequest authorizationRequest, HttpServletRequest request,
       HttpServletResponse response) {
    Assert.notNull(request, "request cannot be null");
    Assert.notNull(response, "response cannot be null");
    if (authorizationRequest == null) {
       removeAuthorizationRequest(request, response);
       return;
    }
    String state = authorizationRequest.getState();
    Assert.hasText(state, "authorizationRequest.state cannot be empty");
    request.getSession().setAttribute(this.sessionAttributeName, authorizationRequest);
}

OAuth2服务端在接受到该请求之后，如果一切正常，则会生成一个临时的code，然后连同请求参数中state一起拼接到redirect_uri的参数中，例如https://{domain}/login/oauth2/code/github?code={code}&state={state in request}，最后发起重定向，此时请求就会进入过滤器OAuth2LoginAuthenticationFilter。

2.3 OAuth2LoginAuthenticationFilter：发起认证

该过滤器继承自AbstractAuthenticationProcessingFilter，显然，它的作用主要是用于完成OAuth2的认证过程，最终生成认证对象。具体看一下attemptAuthentication方法，这里创建出来的对象稍微有点复杂，先梳理一下引用关系：

这里，OAuth2AuthorizationRequest代表了此前提交授权的请求，上文有提到，即保存在session中的请求对象，而OAuth2AuthorizationResponse代表了OAuth2服务端重定向回来的响应，其中也封装了请求时携带过去的state参数，他们构造了一个OAuth2AuthorizationExchange对象，并连同ClientRegistration一并被封装到了OAuth2LoginAuthenticationToken对象中，该对象用于在OAuth2LoginAuthenticationProvider发起认证请求时提取各种参数。

以下是源码的实现细节：

public Authentication attemptAuthentication(HttpServletRequest request, HttpServletResponse response)
       throws AuthenticationException {
    MultiValueMap<String, String> params = OAuth2AuthorizationResponseUtils.toMultiMap(request.getParameterMap());
    // ①
    if (!OAuth2AuthorizationResponseUtils.isAuthorizationResponse(params)) {
       OAuth2Error oauth2Error = new OAuth2Error(OAuth2ErrorCodes.INVALID_REQUEST);
       throw new OAuth2AuthenticationException(oauth2Error, oauth2Error.toString());
    }
    OAuth2AuthorizationRequest authorizationRequest = this.authorizationRequestRepository
       .removeAuthorizationRequest(request, response); // ②
    if (authorizationRequest == null) {
       OAuth2Error oauth2Error = new OAuth2Error(AUTHORIZATION_REQUEST_NOT_FOUND_ERROR_CODE);
       throw new OAuth2AuthenticationException(oauth2Error, oauth2Error.toString());
    }
    String registrationId = authorizationRequest.getAttribute(OAuth2ParameterNames.REGISTRATION_ID);
    ClientRegistration clientRegistration = this.clientRegistrationRepository.findByRegistrationId(registrationId);
    // ③
    if (clientRegistration == null) {
       OAuth2Error oauth2Error = new OAuth2Error(CLIENT_REGISTRATION_NOT_FOUND_ERROR_CODE,
             "Client Registration not found with Id: " + registrationId, null);
       throw new OAuth2AuthenticationException(oauth2Error, oauth2Error.toString());
    }
    // @formatter:off
    String redirectUri = UriComponentsBuilder.fromHttpUrl(UrlUtils.buildFullRequestUrl(request))
          .replaceQuery(null)
          .build()
          .toUriString();
    // @formatter:on
    OAuth2AuthorizationResponse authorizationResponse = OAuth2AuthorizationResponseUtils.convert(params,
          redirectUri);
    // ④      
    Object authenticationDetails = this.authenticationDetailsSource.buildDetails(request);
    OAuth2LoginAuthenticationToken authenticationRequest = new OAuth2LoginAuthenticationToken(clientRegistration,
          new OAuth2AuthorizationExchange(authorizationRequest, authorizationResponse));
    authenticationRequest.setDetails(authenticationDetails);
    // ⑤
    OAuth2LoginAuthenticationToken authenticationResult = (OAuth2LoginAuthenticationToken) this
       .getAuthenticationManager()
       .authenticate(authenticationRequest); // ⑥
    OAuth2AuthenticationToken oauth2Authentication = this.authenticationResultConverter
       .convert(authenticationResult); // ⑦
    Assert.notNull(oauth2Authentication, "authentication result cannot be null");
    oauth2Authentication.setDetails(authenticationDetails);
    OAuth2AuthorizedClient authorizedClient = new OAuth2AuthorizedClient(
          authenticationResult.getClientRegistration(), oauth2Authentication.getName(),
          authenticationResult.getAccessToken(), authenticationResult.getRefreshToken());
    // ⑧
    this.authorizedClientRepository.saveAuthorizedClient(authorizedClient, oauth2Authentication, request, response);
    return oauth2Authentication;
}

1. 检查URL参数是否有效，即是否包含了code和state
2. 通过authorizationRequestRepository查询认证之前存储在session中的request对象，即authorizationRequest，同时还要将其删除，以保证一个对应的code，只能被处理一次，同时如果没有查询到对应的request对象，也不会继续执行，从而也杜绝了其他伪造的重定向请求进入系统，这一步还是比较重要的，它严格约束了一个发起授权请求和接受服务端响应必须成对匹配，否则整个OAuth2授权码流程就无法执行
3. 这个request对象中保存了客户端的registrationId，因此可以通过clientRegistrationRepository查询到对应的客户端信息，即clientRegistration
4. 同时再根据code和state参数，以及当前request请求的url作为redirectUri，构造出一个OAuth2AuthorizationResponse对象，即authorizationResponse
5. 在得到clientRegistration，authorizationRequest，authorizationResponse三个实例之后，再构造出一个OAuth2LoginAuthenticationToken实例，它便是用来发起OAuth2认证的实际对象
6. OAuth2认证过程交由OAuth2LoginAuthenticationProvider执行（具体细节在下一节中介绍）
7. 认证通过后，结果返回了一个OAuth2LoginAuthenticationToken对象，这个对象主要是用于封装授权码模式的认证结果，经过转换，将其principal，authorities，和clientRegistration的RegistrationId取出，最终构造出一个标准的OAuth2认证对象，即OAuth2AuthenticationToken

2.4 OAuth2LoginAuthenticationProvider：获取AccessToken

这个Provider的作用主要包括两个部分，一是请求OAuth2服务端获取AccessToken，二是获取服务端用户信息，前者委托给了OAuth2AuthorizationCodeAuthenticationProvider来执行具体请求的逻辑，而后者则通过UserService实例请求OAuth2服务端的UserInfo相关端点，获取用户信息，最后上述AccessToken相关信息，以及用户信息被封装成OAuth2LoginAuthenticationToken认证对象返回。

public Authentication authenticate(Authentication authentication) throws AuthenticationException {
    OAuth2LoginAuthenticationToken loginAuthenticationToken = (OAuth2LoginAuthenticationToken) authentication;
    ...
    OAuth2AuthorizationCodeAuthenticationToken authorizationCodeAuthenticationToken;
    try {
       authorizationCodeAuthenticationToken = (OAuth2AuthorizationCodeAuthenticationToken) this.authorizationCodeAuthenticationProvider
          .authenticate(
                new OAuth2AuthorizationCodeAuthenticationToken(loginAuthenticationToken.getClientRegistration(),
                      loginAuthenticationToken.getAuthorizationExchange()));
    }
    catch (OAuth2AuthorizationException ex) {
       OAuth2Error oauth2Error = ex.getError();
       throw new OAuth2AuthenticationException(oauth2Error, oauth2Error.toString(), ex);
    }
    OAuth2AccessToken accessToken = authorizationCodeAuthenticationToken.getAccessToken();
    Map<String, Object> additionalParameters = authorizationCodeAuthenticationToken.getAdditionalParameters();
    OAuth2User oauth2User = this.userService.loadUser(new OAuth2UserRequest(
          loginAuthenticationToken.getClientRegistration(), accessToken, additionalParameters));
    Collection<? extends GrantedAuthority> mappedAuthorities = this.authoritiesMapper
       .mapAuthorities(oauth2User.getAuthorities());
    OAuth2LoginAuthenticationToken authenticationResult = new OAuth2LoginAuthenticationToken(
          loginAuthenticationToken.getClientRegistration(), loginAuthenticationToken.getAuthorizationExchange(),
          oauth2User, mappedAuthorities, accessToken, authorizationCodeAuthenticationToken.getRefreshToken());
    authenticationResult.setDetails(loginAuthenticationToken.getDetails());
    return authenticationResult;
}

下面再看一下OAuth2LoginAuthenticationProvider#authenticate方法的源码：

public Authentication authenticate(Authentication authentication) throws AuthenticationException {
    OAuth2AuthorizationCodeAuthenticationToken authorizationCodeAuthentication = (OAuth2AuthorizationCodeAuthenticationToken) authentication;
    OAuth2AuthorizationResponse authorizationResponse = authorizationCodeAuthentication.getAuthorizationExchange()
       .getAuthorizationResponse();
    if (authorizationResponse.statusError()) {
       throw new OAuth2AuthorizationException(authorizationResponse.getError());
    }
    OAuth2AuthorizationRequest authorizationRequest = authorizationCodeAuthentication.getAuthorizationExchange()
       .getAuthorizationRequest();
    if (!authorizationResponse.getState().equals(authorizationRequest.getState())) { // ①
       OAuth2Error oauth2Error = new OAuth2Error(INVALID_STATE_PARAMETER_ERROR_CODE);
       throw new OAuth2AuthorizationException(oauth2Error);
    }
    OAuth2AccessTokenResponse accessTokenResponse = this.accessTokenResponseClient.getTokenResponse(
          new OAuth2AuthorizationCodeGrantRequest(authorizationCodeAuthentication.getClientRegistration(),
                authorizationCodeAuthentication.getAuthorizationExchange())); // ②
    OAuth2AuthorizationCodeAuthenticationToken authenticationResult = new OAuth2AuthorizationCodeAuthenticationToken(
          authorizationCodeAuthentication.getClientRegistration(),
          authorizationCodeAuthentication.getAuthorizationExchange(), accessTokenResponse.getAccessToken(),
          accessTokenResponse.getRefreshToken(), accessTokenResponse.getAdditionalParameters());  // ③
    authenticationResult.setDetails(authorizationCodeAuthentication.getDetails());
    return authenticationResult;
}

1. authorizationRequest中包含了请求时携带的state，而authorizationResponse中包含了OAuth2服务端重定向URL中携带的state，通过两个state参数的比较，校验是否为非法的重定向地址，如果不校验state是否一致，当其他账号正常授权时重定向的地址被另一个人点击了，就可以能发生用户在毫无察觉的情况下登录其他人账号的情况，从而导致信息泄露
2. accessTokenResponseClient向OAuth2服务端发起认证请求，请求地址存储在ClientRegistration中的tokenUri，即https://github.com/login/oauth/access_token，请求体参数则包括code，redirect_uri，grant_type，另外还加入了Authorization的请求头，其属性值是用client_id和client_serect拼接后编码出来的一个字符串，用于向OAuth2服务端证明客户端的真实性
3. OAuth2服务端通过认证后就会返回AccessToken，以及创建时间，过期时间等信息，最后封装成OAuth2AuthorizationCodeAuthenticationToken认证对象返回

2.5 OAuth2UserService：访问受保护资源

上文提到，需要请求OAuth2服务端获取用户信息，用户信息是服务端保护的资源，包含了在Github中个人账号的各类属性，例如id，用户名，头像，主页地址等等，因此这里需要携带AccessToken才能访问，下面看一下具体的执行过程

public OAuth2User loadUser(OAuth2UserRequest userRequest) throws OAuth2AuthenticationException {
 ...
    String userNameAttributeName = userRequest.getClientRegistration()
       .getProviderDetails()
       .getUserInfoEndpoint()
       .getUserNameAttributeName();
    if (!StringUtils.hasText(userNameAttributeName)) {
       OAuth2Error oauth2Error = new OAuth2Error(MISSING_USER_NAME_ATTRIBUTE_ERROR_CODE,
             "Missing required \"user name\" attribute name in UserInfoEndpoint for Client Registration: "
                   + userRequest.getClientRegistration().getRegistrationId(),
             null);
       throw new OAuth2AuthenticationException(oauth2Error, oauth2Error.toString());
    }
    RequestEntity<?> request = this.requestEntityConverter.convert(userRequest); // 关键代码
    ResponseEntity<Map<String, Object>> response = getResponse(userRequest, request);
    Map<String, Object> userAttributes = response.getBody();
    Set<GrantedAuthority> authorities = new LinkedHashSet<>();
    authorities.add(new OAuth2UserAuthority(userAttributes));
    OAuth2AccessToken token = userRequest.getAccessToken();
    for (String authority : token.getScopes()) {
       authorities.add(new SimpleGrantedAuthority("SCOPE_" + authority));
    }
    return new DefaultOAuth2User(authorities, userAttributes, userNameAttributeName);
}

public RequestEntity<?> convert(OAuth2UserRequest userRequest) {
    ClientRegistration clientRegistration = userRequest.getClientRegistration();
    HttpMethod httpMethod = getHttpMethod(clientRegistration);
    HttpHeaders headers = new HttpHeaders();
    headers.setAccept(Collections.singletonList(MediaType.APPLICATION_JSON));
    URI uri = UriComponentsBuilder
       .fromUriString(clientRegistration.getProviderDetails().getUserInfoEndpoint().getUri())
       .build()
       .toUri();

    RequestEntity<?> request;
    if (HttpMethod.POST.equals(httpMethod)) {
       headers.setContentType(DEFAULT_CONTENT_TYPE);
       MultiValueMap<String, String> formParameters = new LinkedMultiValueMap<>();
       formParameters.add(OAuth2ParameterNames.ACCESS_TOKEN, userRequest.getAccessToken().getTokenValue());
       request = new RequestEntity<>(formParameters, headers, httpMethod, uri);
    }
    else {
       headers.setBearerAuth(userRequest.getAccessToken().getTokenValue());
       request = new RequestEntity<>(headers, httpMethod, uri);
    }

    return request;
}

其中生成请求对象的关键代码在OAuth2UserRequestEntityConverter#convert方法中：

• 用户信息的端点同样也是由clientRegistration提供，即https://api.github.com/user
• accessToken作为参数，如果是GET方法，则被置于Header中的"Authorization"属性中，并按照规范添加"Bearer "的前缀，如果是POST，则被放在请求表单参数"access_token"中，此处为GET方法有关

更多访问受保护资源的方法，将在下一篇文章中介绍。

三、附录

3.1 在Github中注册一个新的OAuth2客户端

注册地址为https://github.com/settings/developers，点击右上方“new OAuth App”，就会跳转到注册页面

3.2 填写表单

其中，必填项包括“应用名称”，“主页地址”，“授权回调地址”即上文提到的redirect_uri参数，最后点击“Register Application”即可完成客户端注册

3.3 查看客户端信息

注册完成之后就可以进入客户端信息页面，此时client-id已经生成好了，还需要生成一串client-secret，点击“Generate a new client secret”即可生成，此时务必复制并保存该字符串，后面就无法再次查看了，只能再生成一个新的。

至此，客户端基本信息就注册完成了。

3.4 官方文档

如有其他问题，也可以参考其官方文档

https://docs.github.com/zh/apps/oauth-apps/building-oauth-apps/authorizing-oauth-apps

“Authentication(认证)”是spring security框架中最重要的功能之一，所谓认证，就是对当前访问系统的用户给予一个合法的身份标识，用户只有通过认证后才可以进入系统，在物理世界中，有点类似“拿工卡刷门禁”的场景。身份认证在市面上有很多种的实现协议，最常见的就是用户名密码的认证方式，另外还有OAuth2.0，CAS（Central Authentication Service），SAML等，其中OAuth2.0是一种我们比较熟悉的认证协议，例如微信，支付宝提供的第三方登录。回到身份认证的原本需求：

• 首先系统要提供对应的认证服务，即需要判断用户提交的凭证是否正确，凭证是一个比较宽泛的概念，密码只是其中一种，还包括短信验证码，指纹等，一切可以证明“你是你”的材料都可以是凭证
• 在用户认证成功后，系统还要记录这些认证信息，并返回客户端一个令牌，对于后续的请求，通过这个令牌就可以校验是否经过认证，若已经完成过认证，那么应该取出当时认证的信息，包括用户名，权限等，然后继续执行后续的业务逻辑，若没有认证信息，则拒绝访问。这样才能对受保护的系统资源起到作用。根据上面的描述，很自然地，我们想到定义一个controller的API接口来提供认证服务，然后定义一个“切面”来校验认证信息，这种方式可以方便地拦截到系统内各个资源的访问请求，不仅可以灵活配置，也不会侵入业务代码。到此，我们对认证的架构有了一个初步的构想，先画一个简单的草稿

这里所谓的“令牌”，“凭证”，“认证信息”，“受保护资源”都是抽象的概念，并不特指某一种实现，“切面”也不是Spring的AOP，只表示在执行校验逻辑时，不与受保护资源相耦合，它应该是独立运作的模块。下面具体看一下spring security中的认证架构设计，对比上图，学习一下spring security是如何实践的。

二、架构设计

spring security利用了SecurityFilterChain的过滤器中实现了校验逻辑，另外为了实现各种认证协议，spring security也内置了很多种认证实现类，供开发者直接使用，不过这里提供两种方式，一种也是利用SecurityFilterChain的过滤器来实现认证服务，当然也可以实现自定义的Controller来暴露API接口。明确了这两点之后，我们再给出spring security完整的认证架构，图中均以SecurityFilterChain的过滤器实现认证和校验的逻辑，这是比较常见惯用的方法。                

可以参考官方文档 https://docs.spring.io/spring-security/reference/servlet/authentication/architecture.html，不过官方文档的结构组织比较散，这里我们再做一次整合，看起来更直观一些

首先介绍一下相关的接口和类：

接口

• Authentication：顶层接口，用于保存身份认证信息，主要包括3个部分：用户标识（principal，通常为用户名），凭证（credentials，通常为密码），权限信息（authorities，通常为该用户所拥有的角色）
• SecurityContext：顶层接口，直译为安全上下文，内部只定义了getAuthentication和setAuthentication两个方法，概括地说，SecurityContext相当于用于装载Authentication对象的容器，在整个SecurityFilterChain中，为不同的认证机制操作Authentication对象时提供服务。
• AuthenticationManager: 顶层接口，定义了“认证“方法，签名如下：

Authentication authenticate(Authentication authentication) throws AuthenticationException;

• AuthenticationProvider:  顶层接口，同样也定义了一个签名相同的“认证”方法，不同于AuthenticationManager的认证方法，这个才是各种认证协议的具体实现，它通常接受一个未认证的Authentication对象的参数，该对象仅包含了principal和credentials的信息，在经过认证后，会把authorities填充进来，并将状态设置为已认证。在spring security中内置了很多实现类，例如OAuth2LoginAuthenticationProvider，用于实现OAuth2.0认证协议等。当然我们也可以根据需要自定义其实现。
• SecurityContextRepository：顶层接口，定义了保存和加载SecuriyContext对象的方法，常用的实现有HttpSessionSecurityContextRepository，即通过request的会话对象session，存取SecurityContext的实例。
• SecurityContextHolderStrategy：顶层接口，定义了在当前请求的线程中，获取和设置SecurityContext对象等方法，在5.8版本之后，新增了两个get/set“延迟（Deferred）”接口，主要是使用了Supplier函数式接口实现的惰性计算，不过只是性能上的考量，本质上都是用于维护SecurityContext对象的方法

类

• SecurityContextHolder：它是spring security认证模型中最为常用的一个工具类，它采用策略模式封装了SecurityContextHolderStrategy接口实现，默认的策略实现为ThreadLocalSecurityContextHolderStrategy，其底层使用了ThreadLocal实现对SecurityContext对象的存取逻辑，这样可以保证在一次请求的同一个线程中，方便地获取SecurityContext对象。
• ProviderManager: AuthenticationManager的实现类，它内部维护了一个List成员变量，在实现AuthenticationManager#authenticate方法时，其实是遍历这个List列表，依次判断是否支持当前Authentication对象（如OAuth2LoginAuthenticationProvider支持OAuth2LoginAuthenticationToken），如果支持，则调用AuthenticationProvider#authenticate方法，完成认证过程。

从图中可以看到，整个认证流程主要围绕以下3个Filter：

1. SecurityContextHolderFilter：它在整个SecurityFilterChain中具有较高的优先级，因为当一个请求进入SecurityFilterChain的时候，需要从SecurityContextRepository加载SecurityContext实例①，并调用SecurityContextHolder对应的set方法进行保存②，以便后续其他地方获取这个SecurityContext实例，如上文所述，通常会保存在ThreadLocal中
2. AuthorizationFilter：如果该请求没有被认证过，那么在当前的SecurityContext对象中是没有Authentication实例的，这时在执行AuthorizationFilter的逻辑时就会发生异常，AuthorizationFilter主要是用来判断请求访问受保护资源时，是否符合授权条件，而为了获取用户的授权信息，先通过SecurityContext得到Authentication认证信息①，这时如果获取到Authentication实例为空，就表示该请求并没有认证过，那么就会抛出一个AuthenticationCredentialsNotFoundException的异常②，这个异常会被ExceptionTranslationFilter捕获，通常情况下，异常处理方式就是跳转到到登录页面③，让用户完成登录的操作。
3. AbstractAuthenticationProcessingFilter：它定义了一个比较通用的认证“模板”方法。当用户发起登录请求时，AbstractAuthenticationProcessingFilter配置的RequestMatcher就匹配到这次请求的url，默认执行认证的是UsernamePasswordAuthenticationFilter，它匹配的请求端点是"/login"，此时它从request请求参数中获取用户名和密码，并封装成UsernamePasswordAuthenticationToken①，然后交给ProviderManager#authenticate方法对其认证②，在认证通过之后，我们将AuthenticationProvider返回的Authentication对象③，此时SecurityContextHolderStrategy会创建出一个空载的SecurityContext实例④，并传入上述Authentication⑤，然后调用SecurityContextHolderStrategy的保存方法⑤，最后通过SecurityContextRepository进行持久化⑦，可以参考以下的样板代码，对于各类认证实现，基本上大同小异。

try {
    Authentication authenticationToken = createAuthentication() // // 例如创建UsernamePasswordAuthenticationToken,OAuth2AuthorizationCodeAuthenticationToken等等，将待认证的信息封装起来，
    Authentication authResult = this.authenticationManager.authenticate(someAuthenticationToken); // 交给ProviderManager进行认证，通常由实际的AuthenticationProvider实现类完成具体的认证逻辑，并将认证结果返回
    SecurityContext context = this.securityContextRepository.createEmptyContext(); // 创建一个空载的SecurityContext实例
    context.setAuthentication(authResult); // 传入经过认证的Authentication对象
    this.securityContextHolderStrategy.setContext(context); // 存储SecurityContextHolder中，方便同一个线程执行过程中的其他地方获取
    this.securityContextRepository.saveContext(context, request, response); // 进行持久化，方便下次请求访问时，可以获取对应SecurityContext，实现登录态的保持
    this.successHandler.onAuthenticationSuccess(request, response, authResult); // 认证成功后的流程，例如跳转到系统首页等
} catch (AuthenticationException ex) {
    // Authentication failed
    this.securityContextHolderStrategy.clearContext(); // 认证失败时，清空SecurityContext
    this.failureHandler.onAuthenticationFailure(request, response, failed); // 认证失败后的流程，例如提示错误信息等
}

说明：spring security对用户名和密码的认证提供了默认实现DaoAuthenticationProvider，但由于默认实现限制比较多，一般在实际的生产活动中不会采用，通常会继承AbstractUserDetailsAuthenticationProvider来定制开发，或者参考它的源码自定义实现AuthenticationProvider接口。

三、总结

最后，我们对spring security整个认证架构中的认证流程和存取校验流程，再做一个总结：

• 认证流程：AuthenticationManager为这个系统所支持的所有认证协议，统一提供authenticate方法，比如支持用户名密码登录，也支持短信验证码，第三方授权登录等，不论哪种认证请求，最终都交由这个方法执行，其实现类ProviderManager则高度封装了认证过程，其中具体的AuthenticationProvider实现维护在List列表中，通过遍历使得不同的认证协议进入不同的认证实现类，然后都返回Authentication对象，Authentication定义了一个认证信息应该必须包含的信息，包括用户标识principal，凭证credentials，权限authorities，因此我们也可以实现自定义的AuthenticationProvider，并注册到ProviderManager中，然后再实现自定义的认证Filter和Authentication，这样就完成了整合。
• 存取校验流程：在得到认证后的Authentication对象，需要解决的是如何获取这个Authentication对象，以判断该请求是否已经通过认证，这里就引入另一个重要的类SecurityContext，它相当于一个用于装载Authentication对象的容器，首先依赖SecurityContextRepository从持久化的介质（例如session）中加载出来SecurityContext对象，其次通过SecurityContextHolder内部策略类方便快速地读写SecurityContext对象，这里很容易就想到使用ThreadLocal来实现同一个请求的线程中存取操作，spring security也是这么做的，最终在得到SecurityContext后，可以通过其内部的Authentication对象判断是否已认证。

可见，上述两个核心流程基本围绕着Authentication和SecurityContext这两个接口来建设，前者对外提供认证服务，我们可以进行深度的定制开发，包括Authentication，Filter，AuthenticationProvider都可以自定义实现，并整合进入SecurityFilterChain，后者对内提供存取服务，通常情况下我们也不会对存取流程进行改造，对于绝大多数场景，只需要利用SecurityContextHolder这个工具类读写SecurityContext对象，这基本上已经足够了。这样的设计，在最大程度上固化了存取校验的逻辑，不会因为认证机制和结果的不同，而改变存取校验的逻辑。

上一篇主要介绍了Spring Secuirty中的过滤器链SecurityFilterChain是如何配置的，那么在配置完成之后，SecurityFilterChain是如何在应用程序中调用各个Filter，从而起到安全防护的作用，本文主要围绕SecurityFilterChain的工作原理做详细的介绍。

一、Filter背景知识

因为Spring Security底层依赖Servlet的过滤器技术，所以先简单地回顾一下相关背景知识。

过滤器Filter是Servlet的标准组件，自Servlet 2.3版本引入，主要作用是在Servlet实例接受到请求之前，以及返回响应之后，这两个方向上进行动态拦截，这样就可以与Servlet主业务逻辑解耦，从而实现灵活性和可扩展性，利用这个特性可以实现很多功能，例如身份认证，统一编码，数据加密解密，审计日志等等。

Filter接口定义了3个方法：doFilter，init和destory，其中doFilter就是请求进入过滤器时需要执行的逻辑，伪代码实现如下

public class ExampleFilter implements Filter {
    …
    public void doFilter(ServletRequest request, ServletResponse response,
                            FilterChain chain) throws IOException, ServletException {
        doSomething();
        chain.doFilter(request,response);    
    }
    …
}

其中FilterChain中维护了一个所有已注册的过滤器数组，它组成了真正的“过滤器链”，下面是FilterChain的实现类ApplicationFilterChain的部分源码：当请求到达Servlet容器时，就会创建出一个FilterChain实例，然后调用FilterChain#doFilter方法，这时会从数组中取出下一个过滤器，并调用Filter#doFilter方法，在方法末尾又会将请求继续交由FilterChain处理，如此往复，从而实现职责链模式的调用方式。

private void internalDoFilter(ServletRequest request, ServletResponse response)
        throws IOException, ServletException {

    // Call the next filter if there is one
    if (pos < n) {
        ApplicationFilterConfig filterConfig = filters[pos++];
        try {
            Filter filter = filterConfig.getFilter();
            ...
            if (Globals.IS_SECURITY_ENABLED) {
               // ...
            } else {
                filter.doFilter(request, response, this);
            }
        } catch (...) {
          ...
        }
        return;
    }

    // We fell off the end of the chain -- call the servlet instance
    try {
        ...
        // Use potentially wrapped request from this point
        if ((request instanceof HttpServletRequest) && (response instanceof HttpServletResponse) &&
                Globals.IS_SECURITY_ENABLED) {
           ...
        } else {
            servlet.service(request, response);
        }
    } catch (...) {
       ...
    } finally {
       ...
    }
}

Filter实例可以在web.xml中注册，同时设置URL映射逻辑，当URL符合设置的规则时，便会进入该Filter，举个例子，在Spring Boot问世之前开发一个普通的Spring MVC应用时，经常会配置一个CharacterEncodingFilter，用于统一请求和响应的编码，以避免一些中文乱码的问题

<filter>
    <filter-name>characterEncodingFilter</filter-name>
    <filter-class>org.springframework.web.filter.CharacterEncodingFilter</filter-class>
    <init-param>
        <param-name>encoding</param-name>
        <param-value>UTF-8</param-value>
    </init-param>
    <init-param>
        <param-name>forceEncoding</param-name>
        <param-value>true</param-value>
    </init-param>
</filter>
<filter-mapping>
    <filter-name>characterEncodingFilter</filter-name>
    <url-pattern>/*</url-pattern> <!-- 相当于拦截所有请求 -->
</filter-mapping>

二、SecurityFilterChain的必要性

再回到SecurityFilterChain，先来思考一个问题：基于上面所介绍的Filter，我们自然会想到，定义一系列与安全相关的Filter，例如我们在上一篇提到的那些包括认证，鉴权等在内的Filter，然后只要把他们一个个注册到FilterChain中，就可以实现各种安全特性，看起来也并不需要Spring Security提供的SecuriyFilterChain，也正因如此，初学者经常会有一个疑问，就是明明加一个Filter就可以解决的事，为什么搞得这么复杂？那么SecurityFilterChain的必要性是什么？我们一层一层逐步说明这个问题：

1. 首先要解决的是如何在Filter中获取Spring容器中Bean对象，因为在Servlet容器中启动时，各个Filter的实例便会初始化并完成注册，此时Spring Bean对象还没有完成整个加载过程，不能直接注入，不过很容易想到，可以用一个“虚拟”的Filter在Servlet容器启动时先完成注册，然后在执行doFilter时，再获取对应的Spring Bean作为实际的Filter实例，执行具体的doFilter逻辑，这是一个典型的委派模式，Spring Security为此提供了一个名为DelegatingFilterProxy的类，下文再作详细介绍。
2. 解决了Spring Bean容器与Servlet Filter整合的问题之后，我们是否可以将每一个Filter都通过DelegatingFilterProxy的模式添加到FilterChain中？试想一下，如果每个Spring Security的Filter都分别创建一个独立的委派类，那么通过ApplicationContext查找bean的代码就会反复出现，这在很大程度上违背了依赖注入的原则，也极大了增加了维护成本和开发成本，为了解决这个问题，在上述DelegateFilterProxy基础上，Spring Security又引入了一个代理类FilterChainProxy，它可以看作是Spring Security Filter的统一入口，此时，从Servlet的FIlterChain角度来看，整个Spring Security只定义了一个Filter，即DelegatingFilterProxy，而执行doFilter时则委派给了FilterChainProxy，这样就可以利用这个入口简化很多工作，例如官方文档中提到，可以在调试Spring Security功能时，将断点设置在这个入口，方便我们跟踪定位问题等等
3. FilterChainProxy作为统一收口，同时也起到了打通SecurityFilterChain的桥梁作用，在调用doFilter方法时，实际上都交给某个SecurityFilterChain实例执行，到这里请求才算是进入了我们使用HttpSecurity配置的各个Filter，而在执行SecurityFilterChain的前后位置，又可以统一添加一些处理，例如添加Spring Security的防火墙HttpFirewall，用以防范某些特定类型的攻击
4. 最后还有一点，Servlet Filter本身也存在一定的局限性，例如映射配置不够灵活，只能根据URL进行匹配，而SecurityFilterChain通过RequestMatcher接口实现了不同匹配逻辑及组合，大大丰富了匹配规则映射的能力

综上所述，通过DelegatingFilterProxy->FilterChainProxy->SecurityFilterChain这样的三层结构关系，使得SecurityFilterChain中的各个Filter被当成了一个整体，置于Servlet FilterChain之中，又能和其他的Filter独立开，不论我们如何配置SecurityFilterChain，都不会引起Servlet FilterChain的变更，这样的设计很好地遵循了开放封闭原则，即对Servlet Filter的修改是保持封闭的，而对Spring Security Filter的配置和扩展是保持开放的。

其实，我们在很多Spring的框架中，都可以见到这种设计，本质上来说，即通过添加一个中间层来达到解耦的目的，我们应该深入地理解这种设计，并学以致用。

三、SecuriyFilterChain的工作原理

讨论完SecurityFilterChain必要性，再来介绍SecurityFilterChain的工作原理就会变得比较好理解了：

1. 注册DelegatingFilterProxy：

在非Spring Boot环境可以通过web.xml进行注册，配置如下：

<filter>
    <filter-name>springSecurityFilterChain</filter-name>
    <filter-class>org.springframework.web.filter.DelegatingFilterProxy</filter-class>
</filter>

<filter-mapping>
    <filter-name>springSecurityFilterChain</filter-name>
    <url-pattern>/*</url-pattern>
</filter-mapping>

而在Spring Boot环境下，则是通过RegistrationBean的方式注册Servlet组件，具体实现类为DelegatingFilterProxyRegistrationBean，它由SecurityFilterAutoConfiguration配置类创建出来，并在Servlet容器启动的时候完成Filter的注册。完成注册后，当Servlet容器启动时，FilterChain就包含了DelegatingFilterProxy这个Filter。

2. 委派FilterChainProxy：

上文提到在执行DelegatingFilterProxy的doFilter方法时，实际上都是交给FilterChainProxy来执行，它是由Spring容器托管的bean对象，通过下面WebSecurityConfiguration配置类源码可以看到，其中定义了一个名称为“springSecurityFilterChain”的Bean，而其中webSecurity#build方法返回的就是FilerChainProxy的实例，其构建过程和上一篇介绍的HttpSecurity类似，这里就不再展开。

@Bean(name = AbstractSecurityWebApplicationInitializer.DEFAULT_FILTER_NAME) // "springSecurityFilterChain"
public Filter springSecurityFilterChain() throws Exception {
    ...
    return this.webSecurity.build();
}

委派过程比较简单，下面是DelegatingFilterProxy#doFilter方法的源码（可以忽略并发控制的代码），当请求进入doFilter之后，首先调用initDelegate方法，这里利用Spring的ApplicationContext#getBean方法获取名为“springSecurityFilterChain“的bean对象，即FilterChainProxy，然后调用其doFilter方法，这样就完成了委派调用。

public void doFilter(ServletRequest request, ServletResponse response, FilterChain filterChain)
       throws ServletException, IOException {

    // Lazily initialize the delegate if necessary.
    Filter delegateToUse = this.delegate;
    if (delegateToUse == null) {
       synchronized (this.delegateMonitor) {
          delegateToUse = this.delegate;
          if (delegateToUse == null) {
             WebApplicationContext wac = findWebApplicationContext();
             if (wac == null) {
                throw new IllegalStateException("No WebApplicationContext found: " +
                      "no ContextLoaderListener or DispatcherServlet registered?");
             }
             delegateToUse = initDelegate(wac);
          }
          this.delegate = delegateToUse;
       }
    }

    // Let the delegate perform the actual doFilter operation.
    invokeDelegate(delegateToUse, request, response, filterChain);
}

protected Filter initDelegate(WebApplicationContext wac) throws ServletException {
    String targetBeanName = getTargetBeanName(); // "springSecurityFilterChain"
    Assert.state(targetBeanName != null, "No target bean name set");
    Filter delegate = wac.getBean(targetBeanName, Filter.class);
    if (isTargetFilterLifecycle()) {
       delegate.init(getFilterConfig());
    }
    return delegate;
}

protected void invokeDelegate(
       Filter delegate, ServletRequest request, ServletResponse response, FilterChain filterChain)
       throws ServletException, IOException {

    delegate.doFilter(request, response, filterChain);
}

3. 执行SecurityFilterChain的过滤器链：

严格来说，最终执行doFilter的并不是SecuritFilterChain，FilterChainProxy内部维护了一个SecurityFilterChain的List列表，在调用doFilter方法时，会根据SecurityFilterChain#match方法匹配的结果决定选择某一个SecurityFilterChain，然后取出该SecurityFilterChain所有的Filter，用其构造一个VirtualFilterChain，这才是实际意义上过滤器链执行的入口。

private void doFilterInternal(ServletRequest request, ServletResponse response, FilterChain chain)
       throws IOException, ServletException {
    FirewalledRequest firewallRequest = this.firewall.getFirewalledRequest((HttpServletRequest) request);
    HttpServletResponse firewallResponse = this.firewall.getFirewalledResponse((HttpServletResponse) response);
    List<Filter> filters = getFilters(firewallRequest); // 重点关注这个方法，获取到某个SecurityFilterChain的所有Filter
    if (filters == null || filters.size() == 0) {
        ...
       firewallRequest.reset();
       this.filterChainDecorator.decorate(chain).doFilter(firewallRequest, firewallResponse);
       return;
    }
     ...
    FilterChain reset = (req, res) -> {
          ...
       // Deactivate path stripping as we exit the security filter chain
       firewallRequest.reset();
       chain.doFilter(req, res);
    };
    // 装饰器模式，实际上返回了VirtualFilterChain的实例
    this.filterChainDecorator.decorate(reset, filters).doFilter(firewallRequest, firewallResponse);
}

private List<Filter> getFilters(HttpServletRequest request) {
    int count = 0;
    for (SecurityFilterChain chain : this.filterChains) {
         ...
       if (chain.matches(request)) {
          return chain.getFilters();
       }
    }
    return null;
}


public FilterChain decorate(FilterChain original, List<Filter> filters) {
    return new VirtualFilterChain(original, filters);
}

VirtualFilterChain的实现也并不复杂，其doFilter方法源码如下，原理和Servlet的FilterChain的实现类ApplicationFilterChain基本类似，不过当所有Filter都执行完之后，它会交给originalChain继续执行，即回到Servlet的FilterChain。上文提到，如果要打断点debug，这里是一个比较好的位置，可以看到Spring Security中定义各个Filter执行的过程。

@Override
public void doFilter(ServletRequest request, ServletResponse response) throws IOException, ServletException {
    if (this.currentPosition == this.size) {
       this.originalChain.doFilter(request, response);
       return;
    }
    this.currentPosition++;
    Filter nextFilter = this.additionalFilters.get(this.currentPosition - 1);
    if (logger.isTraceEnabled()) {
       String name = nextFilter.getClass().getSimpleName();
       logger.trace(LogMessage.format("Invoking %s (%d/%d)", name, this.currentPosition, this.size));
    }
    nextFilter.doFilter(request, response, this);
}

最后，再结合Spring Security官方文档的图示，可以更好地理解整个执行流程

Spring Security框架看似比较复杂，但说到底，框架中的各种安全功能，基本上也就是一个个Filter(javax.servlet.Filter)组成的所谓“过滤器链”实现的，这些Filter以职责链的设计模式组织起来，环环相扣，不过在刚接触Spring Security框架时不必盯着每个Filter着重去研究，我们首要的目的是学会如何对Spring Security进行配置，很多人，特别是新手，在看过官方文档中配置示例代码（如下所示）之后，在没有足够背景知识的情况下，都会对这个http.build()方法感到莫名的困惑，想要定制开发也不知从何下手，本文主要对整个Spring Security配置过程做一定的剖析，希望可以对学习Spring Sercurity框架的同学所有帮助。

版本说明：下文所贴出的各段源码均源自6.2.3版本，但其实5.7以上的各个版本，跟配置相关的代码基本相同，变动不算太大

@Bean
public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
    http
            .authorizeHttpRequests(authorize -> authorize
                    .anyRequest().authenticated()
            )
            .formLogin(withDefaults())
            .httpBasic(withDefaults());
    return http.build();
}

概况地说，HttpSecurity的配置过程，主要就是向这个SecurityFilterChian中添加不同功能的Filter对象，为了方便后文理解，首先来看一下其中涉及的几个重要的接口和类（关系如下图）接口

• SecurityBuilder：顶层接口，定义了抽象的泛型构造器方法——build()
• SecurityConfigurer：顶层接口，用来定义配置类的通用方法，每个Filter都是由特定的SecurityConfigurer的实现类构建出来并添加到FilterChain中的
• SecurityFilterChain：顶层接口，即过滤器链，定义了获取List的方法，以及matches，用于判断某个请求是否满足进链的条件
• HttpSecurityBuilder：继承SecurityBuilder，定义了构建SecurityFilterChain过程中的各种辅助方法，如添加Filter到SecurityFilterChain，获取SecurityConfigurer配置实现类等类
• AbstractSecurityBuilder：顶层的抽象父类，它没有实现build具体的逻辑，实际交由doBuild方法实现，只是用CAS对doBuild过程进行了并发控制
• AbstractConfiguredSecurityBuilder：继承了AbstractSecurityBuilder，它内部维护了一个SecurityConfigurer的列表，实现了doBuild方法，确立了整个构建的流程
• HttpSecurity 作为final实现类，它主要面向开发者，我们在开发过程中就是用它提供的一系列的配置入口，方便开发者对SecurityFilterChain中不同的Filter进行定制，包括添加自定义的Filter，关闭某些Filter，或扩展原来Filter的能力等等

二、基本流程

接下来，重点分析一下AbstractConfiguredSecurityBuilder类，整个构建过程围绕doBuild方法，主要分为：

1. 初始化，包括beforeInit和init方法，其中beforeInit是扩展用的钩子方法，默认实现为空
2. 配置，包括beforeConfigure和configure方法，其中beforeConfigure是扩展用的钩子方法，默认实现为空
3. 构造，即performBuild方法，具体由HttpSecurity实现，主要是对Filter进行排序，并最终返回DefaultSecurityFilterChain的实例

而在AbstractConfiguredSecurityBuilder中维护了一个Map<Class,List<SecurityConfigure>>对象，用于缓存各种SecurityConfigure的实现类，当调用init和configure时，实际上就会遍历这个Map所有configurer，依次调用对应方法，通常就是在configure方法中，将Filter加入到FilterChain中（下文详述）

protected final O doBuild() throws Exception {
    synchronized (this.configurers) {
       this.buildState = BuildState.INITIALIZING;
       beforeInit();
       init();
       this.buildState = BuildState.CONFIGURING;
       beforeConfigure();
       configure();
       this.buildState = BuildState.BUILDING;
       O result = performBuild();
       this.buildState = BuildState.BUILT;
       return result;
    }
}
 
 private void configure() throws Exception {
    Collection<SecurityConfigurer<O, B>> configurers = getConfigurers();
    for (SecurityConfigurer<O, B> configurer : configurers) {
       configurer.configure((B) this);
    }
}

那么，这些SecurityConfigure实例则是如何添加上述的Map中的？可以在HttpSecurityConfiguration找到相关的实现，源码如下

@Bean(HTTPSECURITY_BEAN_NAME)
@Scope("prototype")
HttpSecurity httpSecurity() throws Exception {
    LazyPasswordEncoder passwordEncoder = new LazyPasswordEncoder(this.context);
    AuthenticationManagerBuilder authenticationBuilder = new DefaultPasswordEncoderAuthenticationManagerBuilder(
          this.objectPostProcessor, passwordEncoder);
    authenticationBuilder.parentAuthenticationManager(authenticationManager());
    authenticationBuilder.authenticationEventPublisher(getAuthenticationEventPublisher());
    HttpSecurity http = new HttpSecurity(this.objectPostProcessor, authenticationBuilder, createSharedObjects());
    WebAsyncManagerIntegrationFilter webAsyncManagerIntegrationFilter = new WebAsyncManagerIntegrationFilter();
    webAsyncManagerIntegrationFilter.setSecurityContextHolderStrategy(this.securityContextHolderStrategy);
    // @formatter:off
    http
       .csrf(withDefaults())
       .addFilter(webAsyncManagerIntegrationFilter)
       .exceptionHandling(withDefaults())
       .headers(withDefaults())
       .sessionManagement(withDefaults())
       .securityContext(withDefaults())
       .requestCache(withDefaults())
       .anonymous(withDefaults())
       .servletApi(withDefaults())
       .apply(new DefaultLoginPageConfigurer<>());
    http.logout(withDefaults());
    // @formatter:on
    applyCorsIfAvailable(http);
    applyDefaultConfigurers(http);
    return http;
}

可以看到在构造过程中（那段很长链式配置），已经帮我们添加了若干SecurityConfgurer实例，因此我们在使用配置SecurityFilterChain时，仅需要很少的配置就可以得到一个完整的具备基本功能的SecurityFilterChain，当然我们也可以利用这些配置项做很多定制开发。事实上，HttpSecurity大约提供了24个Filter相关的Configurer配置方法，其中11个Filter是默认加载的，整理成表格：

如果我们不对HttpSecurity做任何改动的话，默认得到的SecurityFilterChain是如下这样的，先了解大概，后续还针对部分重要的filter做深入分析。

org.springframework.security.web.session.DisableEncodeUrlFilter
org.springframework.security.web.context.request.async.WebAsyncManagerIntegrationFilter
org.springframework.security.web.context.SecurityContextHolderFilter
org.springframework.security.web.header.HeaderWriterFilter
org.springframework.web.filter.CorsFilter
org.springframework.security.web.csrf.CsrfFilter
org.springframework.security.web.authentication.logout.LogoutFilter
org.springframework.security.web.savedrequest.RequestCacheAwareFilter
org.springframework.security.web.servletapi.SecurityContextHolderAwareRequestFilter
org.springframework.security.web.authentication.AnonymousAuthenticationFilter
org.springframework.security.web.access.ExceptionTranslationFilter

三、SecurityConfigurer举例

这里还是以Spring Security官方文档中配置的示例代码为例，配置代码只需几行，比较优雅，这种设计是值得学习的，尽量让复杂的配置逻辑封装起来，让开发者在使用时，只需要关注业务逻辑即可

@Bean
public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
    http
            .authorizeHttpRequests(authorize -> authorize
                    .anyRequest().authenticated()
            )
            .formLogin(withDefaults())
            .httpBasic(withDefaults());
    return http.build();
}

Spring Security提供了两种方式进行配置，一种就是示例代码中，即利用lambda表达式实现配置逻辑，这是5.5版本引入的，在这之前是使用无参的方法获取配置对象 ，然后进行链式的配置，如上述示例代码可以改写为

@Bean
public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
    http.
            authorizeHttpRequests().anyRequest().authenticated()
            .and().formLogin()
            .and().httpBasic();
    return http.build();

}

以authorizeHttpRequests为例看一下源码实现，可以看到两种方式大同小异，只是使用了Customer函数式接口进行了封装

@Deprecated(since = "6.1", forRemoval = true)
public AuthorizeHttpRequestsConfigurer<HttpSecurity>.AuthorizationManagerRequestMatcherRegistry authorizeHttpRequests()
       throws Exception {
    ApplicationContext context = getContext();
    return getOrApply(new AuthorizeHttpRequestsConfigurer<>(context)).getRegistry();
}

public HttpSecurity authorizeHttpRequests(
       Customizer<AuthorizeHttpRequestsConfigurer<HttpSecurity>.AuthorizationManagerRequestMatcherRegistry> authorizeHttpRequestsCustomizer)
       throws Exception {
    ApplicationContext context = getContext();
    authorizeHttpRequestsCustomizer
       .customize(getOrApply(new AuthorizeHttpRequestsConfigurer<>(context)).getRegistry());
    return HttpSecurity.this;
}

其中getOrApply方法，用于获取到Configurer的具体实例（上文中提到过在AbstractConfiguredSecurityBuilder中维护了一个Configurers的Map，这些Configurer实例便是从这个Map获取的）

不过第二种写法，根据源码的注释，应该会在Spring Security 7版本里面移除，所以还是要适应这种Customizer参数的配置方法。

上面authorizeHttpRequests方法返回的是AuthorizeHttpRequestsConfigurer类中的AuthorizationManagerRequestMatcherRegistry对象，可以先看一下AuthorizeHttpRequestsConfigurer中的configure方法

public void configure(H http) {
    AuthorizationManager<HttpServletRequest> authorizationManager = this.registry.createAuthorizationManager();
    AuthorizationFilter authorizationFilter = new AuthorizationFilter(authorizationManager);
    authorizationFilter.setAuthorizationEventPublisher(this.publisher);
    authorizationFilter.setShouldFilterAllDispatcherTypes(this.registry.shouldFilterAllDispatcherTypes);
    authorizationFilter.setSecurityContextHolderStrategy(getSecurityContextHolderStrategy());
    http.addFilter(postProcess(authorizationFilter));
}

这里创建了一个AuthorizationFilter，并添加到HttpSecurity的List中，而AuthorizationManagerRequestMatcherRegistry则又是一个构造器模式实现的配置类，主要功能就是配置一些权限拦截的具体逻辑，如哪些地址需要什么角色访问等，这里就不展开了。

再看一下formLogin的例子

public HttpSecurity formLogin(Customizer<FormLoginConfigurer<HttpSecurity>> formLoginCustomizer) throws Exception {
    formLoginCustomizer.customize(getOrApply(new FormLoginConfigurer<>()));
    return HttpSecurity.this;
}

formLogin方法实际上创建FormLoginConfigurer的示例，该类主要用于创建UsernamePasswordAuthenticationFilter，即默认的用户名密码认证的过滤器。

其中的configure方法由父类AbstractAuthenticationFilterConfigurer实现，源码如下，虽然这个方法有点长，但基本是围绕配置UsernamePasswordAuthenticationFilter实例而展开（this.authFilter就是UsernamePasswordAuthenticationFilter的实例，它在FormLoginConfigurer的构造函数中创建出来），主要就是创建用户认证所用到的一些基本组件，例如AuthenticationManager用于封装不同的用户认证方式（如用户名密码），AuthenticationSuccessHandler用于封装认证成功后执行的操作，AuthenticationFailureHandler用于封装认证失败后执行的操作等等

@Override
public void configure(B http) throws Exception {
    PortMapper portMapper = http.getSharedObject(PortMapper.class);
    if (portMapper != null) {
       this.authenticationEntryPoint.setPortMapper(portMapper);
    }
    RequestCache requestCache = http.getSharedObject(RequestCache.class);
    if (requestCache != null) {
       this.defaultSuccessHandler.setRequestCache(requestCache);
    }
    this.authFilter.setAuthenticationManager(http.getSharedObject(AuthenticationManager.class));
    this.authFilter.setAuthenticationSuccessHandler(this.successHandler);
    this.authFilter.setAuthenticationFailureHandler(this.failureHandler);
    if (this.authenticationDetailsSource != null) {
       this.authFilter.setAuthenticationDetailsSource(this.authenticationDetailsSource);
    }
    SessionAuthenticationStrategy sessionAuthenticationStrategy = http
       .getSharedObject(SessionAuthenticationStrategy.class);
    if (sessionAuthenticationStrategy != null) {
       this.authFilter.setSessionAuthenticationStrategy(sessionAuthenticationStrategy);
    }
    RememberMeServices rememberMeServices = http.getSharedObject(RememberMeServices.class);
    if (rememberMeServices != null) {
       this.authFilter.setRememberMeServices(rememberMeServices);
    }
    SecurityContextConfigurer securityContextConfigurer = http.getConfigurer(SecurityContextConfigurer.class);
    if (securityContextConfigurer != null && securityContextConfigurer.isRequireExplicitSave()) {
       SecurityContextRepository securityContextRepository = securityContextConfigurer
          .getSecurityContextRepository();
       this.authFilter.setSecurityContextRepository(securityContextRepository);
    }
    this.authFilter.setSecurityContextHolderStrategy(getSecurityContextHolderStrategy());
    F filter = postProcess(this.authFilter);
    http.addFilter(filter);
}

通过上面两个源码示例，可以看到配置Filter的过程其实并不复杂，当我们在研究Spring Security不同过滤器功能时，可以参考源码中configure的配置过程，分析它们有哪些配置项，这些配置点主要能提供什么样能力的等，从而打开思路，快速实现不同的定制需求。

四、总结

最后做一个简单的总结，如图所示：

1. 从HttpSercurityConfiguration定义HttpSecurity的Bean对象开始，便向HttpSecurity中添加了若干SecurityConfigurer对象，另外我们可以在自定义的配置类中对其进行一些定制调整
2. 然后当调用HttpSecurity#Build()方法时，就会将取得所有SecurityConfigurer进行遍历，依次调用对应的init和configurer方法，而在configurer方法中，创建出各种功能的Filter实例，并添加到List列表中
3. 最后通过performBuild方法，将List进行排序，并创建出DefaultSecurityFilterChian至此整个过滤器链的构建就完成了。

最近遇到了一些字符匹配的需求，进而仔细地看了CharMatcher的源码，发现还是有点东西值得回味，例如它为我们提供了如何在多种字符类型场景下提高灵活性从而满足不同匹配需求的优秀示范。下面就对CharMatcher类的结构，设计模式，以及几个算法做一些粗浅的分析。

一、关于源码中的彩蛋

CharMatcher类中，开头部分有一张宠物小精灵“小火龙”的字符画，就像本文的封面图一样，一开始不解为何要放一只“小火龙”在这里，后来看到其英文名Charmander才明白过来。好吧，谐音梗……略冷。

二、类的结构和关系

下图是CharMatcher的类关系图，图中蓝色的是abstract类，红色的是final类

首先CharMatcher修饰为abstract，其中只有一个abstract方法matches，即判断给定字符是否匹配，以及一些其他的常用操作（它们的功能从方法名可以得知，这里就不一一介绍了，下文会选其中的一些做分析），此外还有三个用于组合的方法：negate、or、and。

public abstract boolean matches(char c);

public int indexIn(CharSequence sequence) // 查找匹配字符首次出现的索引位置

public int countIn(CharSequence sequence) // 对匹配的字符计数

public String retainFrom(CharSequence sequence) // 抽取匹配的字符

public CharMatcher negate() // 取反

public CharMatcher and(CharMatcher other) // 与

public CharMatcher or(CharMatcher other) // 或

...

如上图所示，CharMatcher类有很多的子类，一部分是直接继承于父类，一部分是继承于FastMatcher，另外还有继承于Negated和RangeMatcher。子类通过实现matches方法或重写其他父类的方法，从而提供了各种不同的具体操作，如Is（判断是否为某一个字符），Digit（判断是否为数字字符），Ascii（判断是否为ASCII字符）等。
再来说说其中一个比较重要的子类——FastMatcher，它和CharMatcher的主要区别在于，FastMatcher取消了父类中相对复杂的precomputed方法，其注释写道，这个方法可以得到一个处理速度更快的实例，但是执行该方法本身需要花费一定时间，所以只有在需要频繁调用的情况下，这样做才比较划算。
至于这个方法的奥秘在于，它使用BitSet作为存储字符的数据结构，然后遍历所有的字符（Character.MIN_VALUE~Character.MAX_VALUE），根据matches方法放入这个BitSet中，最后根据这个BitSet中1的数量生成其他类型的CharMatcher实例，包括None，Is，IsEither，SmallCharMatcher（一个单独的子类）以及BitSetMatcher，这样就避免了频繁调用过程中，（特别是复杂组合的情况）执行不必要实例化操作，而是直接归约到某一个类的实例上。
而上述那5个类正是继承于FasterMatcher（或NamedFasterMatcher）。

三、设计模式

上一节说到CharMatcher提供很多子类，为了较好地管理和使用这些类，CharMatcher对外提供了基于内部类的静态工厂方法或者单例模式来获得某个实例，举例来说：

• 静态工厂方法

public static CharMatcher is(final char match) {
    return new Is(match);
}

private static final class Is extends FastMatcher {
    
    private final char match;

    Is(char match) {
      this.match = match;
    }
    ...
  }

使用静态工厂方法的好处，这点在《Effective Java》一书中有详细的介绍

• 单例模式

public static CharMatcher ascii() {
    return Ascii.INSTANCE;
}

private static final class Ascii extends NamedFastMatcher {

    static final Ascii INSTANCE = new Ascii();

    Ascii() {
      super("CharMatcher.ascii()");
    }
    ...
}

这样我们就可以很方便地获得一个实例，并对相应的字符类型做处理，比如抽取字符串中所有的数字

CharMatcher.inRange('0', '9').retainFrom("abc12d34ef");
// 当然也可以用Digit类，不过最近的版本已经被标记为Deprecated
// 区别在于Digit类处理了字符0到9的各种unicode码，不过大多数情况还是处理ASCII数字，所以建议使用inRange
CharMatcher.digit().retainFrom("abc12d34ef")；
// 1234

当然也可以通过negate/or/and产生一些复杂的组合:

CharMatcher.inRange('0','9').or(CharMatcher.is('d')).retainFrom("abc12d34ef");
// 12d34

另外还有一个ForPredicate的子类，它接收Predicate对象作为参数，然后用Predicate的apply方法来实现matches方法，这样就用lamda表达式创建一些实例了，例如：

CharMatcher.inRange('0', '9').or(CharMatcher.is('d'))
                .or(CharMatcher.forPredicate(c -> c <= 'b' || c > 'e')).retainFrom("abc12d34ef");
// ab12d34f

四、算法分析

• collapseFrom方法，如代码注释所示，把一个字符串中匹配到的(连续)部分替换为给定的字符，

//CharMatcher.anyOf("eko").collapseFrom("bookkeeper", '-') returns "b-p-r"
public String collapseFrom(CharSequence sequence, char replacement) {
    // This implementation avoids unnecessary allocation.
    int len = sequence.length();
    for (int i = 0; i < len; i++) {
      char c = sequence.charAt(i);
      if (matches(c)) {
        if (c == replacement && (i == len - 1 || !matches(sequence.charAt(i + 1)))) {
          // a no-op replacement
          i++;
        } else {
          StringBuilder builder = new StringBuilder(len).append(sequence, 0, i).append(replacement);
          return finishCollapseFrom(sequence, i + 1, len, replacement, builder, true);
        }
      }
    }
    // no replacement needed
    return sequence.toString();
}
  
private String finishCollapseFrom(
      CharSequence sequence,
      int start,
      int end,
      char replacement,
      StringBuilder builder,
      boolean inMatchingGroup) {
    for (int i = start; i < end; i++) {
      char c = sequence.charAt(i);
      if (matches(c)) {
        if (!inMatchingGroup) {
          builder.append(replacement);
          inMatchingGroup = true;
        }
      } else {
        builder.append(c);
        inMatchingGroup = false;
      }
    }
    return builder.toString();
} 

事实上，CharMatcher里面的算法基本上都和这个差不多程度。

正如注释部分所述，这个算法没有分配不必要的空间。遍历过程中当发现当前字符满足匹配条件，这时再做一次判断，如果当前字符本身就是所需要替换的字符replacement，那么这种情况是不需要进行替换操作（感觉可以直接用一个if(c != replacement)换掉else，并不需要i++的操作），否则将i之前的字符拼上replacement形成一个“半成品”传入finishCollapseFrom，在该方法中利用了一个布尔值inMatchingGroup来控制是否需要拼接replacement，当发现满足匹配条件时，再检查inMatchingGroup是否为false，它表示上一轮拼接的不是replacement，以保证返回的结果中不会出现两个以上连续的replacement。

• Whitespace.matches 即判断该字符是否为空白字符，包括空格，换行等

static final class Whitespace extends NamedFastMatcher {

    static final String TABLE =
        "\u2002\u3000\r\u0085\u200A\u2005\u2000\u3000"
            + "\u2029\u000B\u3000\u2008\u2003\u205F\u3000\u1680"
            + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
            + "\u3000\u2004\u3000\u3000\u2028\n\u2007\u3000";
    static final int MULTIPLIER = 1682554634;
    static final int SHIFT = Integer.numberOfLeadingZeros(TABLE.length() - 1);

    static final Whitespace INSTANCE = new Whitespace();

    @Override
    public boolean matches(char c) {
      return TABLE.charAt((MULTIPLIER * c) >>> SHIFT) == c;
    }
}

这个算法本身很简单，即TABLE字符串中是否存在同样的字符c，巧妙的是它的定位方式。
先说明Integer.numberOfLeadingZeros这个方法返回的是该int变量二进制开头部分连续的零的个数。TABLE的长度为32，故SHIFT的值为27，也就是说，通过字符c和某一个乘子的乘积（超出int范围之后取低32位）向右移动27位得到的数值，即为TABLE的下标索引，例如字符'\u2002'其值为8194，它和1682554634的乘积再右移27位得到0，而TABLE第0个字符就是'\u2002'，则判定相等，字符'\u3000'的值为12288，应用相同算法得到26，TABLE第26个字符也是'\u3000'，同样判定相等。由此可以看出，1682554634这个魔数和TABLE是刻意设计成这样的。但是源码中没有解释如何生成，在GitHub上倒是也有人这么问过，Guava owner回复说道：他们确实有一个生成器，但是由于一些依赖的原因，并没有开源出来。其实如果不考虑性能，我们可以用最简单的暴力法生成乘子和TABLE，代码如下：

    @Test
    public void test() {
        // 去掉table中重复的字符
        String WHITE = "\u2002\r\u0085\u200A\u2005\u2000"
                + "\u2029\u000B\u2008\u2003\u205F\u1680"
                + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
                + "\u2004\u2028\n\u2007\u3000";

        char[] chars = WHITE.toCharArray();
        char filler = chars[chars.length - 1];
        char[] table = new char[32];

        int shift = Integer.numberOfLeadingZeros(WHITE.length());

        for (int i = 0; i <= Integer.MAX_VALUE; i++) {
            Arrays.fill(table, filler);//先用最后一个字符填充整个table
            boolean conflict = false;
            for (char c : chars) {
                int index = (i * c) >>> shift;
                //如果当前字符为填充字符，则覆盖填充字符，否则跳过
                if (table[index] != filler) { 
                    conflict = true;
                    continue;
                }
                table[index] = c;
            }
            if (conflict)
                continue;
            System.out.println("MULTIPLIER: " + i);
            System.out.println("TABLE:" + new String(table));
        }
    }

上面可以得到多种MULTIPLIER和TABLE的结果。当然，反推过程比较简单粗暴，一定有更优雅更高效的实现方式。不过这里想要表达的是，它本身是一个简单的查找算法，通常的复杂度为O(logn)，这里巧妙通过映射函数，将字符映射为字符串下标索引，使得时间复杂度为O(1)，不得不佩服Guava开发者们追求极致的精神。

• removeFrom方法，即在给定字符串中，删除其匹配的部分

// CharMatcher.is('a').removeFrom("bazaar") returns "bzr"
public String removeFrom(CharSequence sequence) {
    String string = sequence.toString();
    int pos = indexIn(string);
    if (pos == -1) {
      return string;
    }

    char[] chars = string.toCharArray();
    int spread = 1;

    // This unusual loop comes from extensive benchmarking
    OUT:
    while (true) {
      pos++;
      while (true) {
        if (pos == chars.length) {
          break OUT;
        }
        if (matches(chars[pos])) {
          break;
        }
        chars[pos - spread] = chars[pos];
        pos++;
      }
      spread++;
    }
    return new String(chars, 0, pos - spread);
  }

比较诡异的是，它使用了两层while循环，以及break [lable]的语法（这种用法并不多见，可以理解为goto语句的改良形式，可以方便地跳出多层循环）,不过在内层循环时同样也做了pos++的操作，本质上还是O(n)的时间复杂度，算法思想是char数组的位移操作，每次匹配到一个字符时，spread就自增，其他情况则每个数组元素向前移动，具体来说，spread的作用相当于对匹配到的字符进行计数，匹配到1个元素，pos指向的元素及其之后的元素向前移动1步以覆盖掉上一轮命中的字符，匹配到2个元素，pos执行的元素及其之后的元素向前移动2步，以覆盖上一次移动留下的空位和上一轮命中的字符，依次类推。最终利用String的构造函数（第二个参数是offset，即初始的偏移位置，第三个参数count，即所需长度）返回正确的字符串。
做个对比，我们以Apache commons lang3中的StringUtils作为比较对象，其对应的实现基于Matcher(java.util.regex)的replaceAll方法，亦即将匹配的字符替换为空字符串，整个遍历的过程中重复调用了find()方法，该方法查找当前字符串中匹配的字符，它每次都需要从头进行搜索，因此时间复杂度为O(n^2)，这样就比较费时了。

五、其他

在CharMatcher罗列多种字符的不同Unicode码，如果你在其他的工作场景下需要用的这些unicode，可以参考一下CharMatcher。

• 数字字符

private static final String ZEROES =
        "0\u0660\u06f0\u07c0\u0966\u09e6\u0a66\u0ae6\u0b66\u0be6\u0c66\u0ce6\u0d66\u0de6"
            + "\u0e50\u0ed0\u0f20\u1040\u1090\u17e0\u1810\u1946\u19d0\u1a80\u1a90\u1b50\u1bb0"
            + "\u1c40\u1c50\ua620\ua8d0\ua900\ua9d0\ua9f0\uaa50\uabf0\uff10";

如果要获得其他数字的unicode，就直接对应加上对应的数值

• 空白字符

static final String TABLE =
        "\u2002\u3000\r\u0085\u200A\u2005\u2000\u3000"
            + "\u2029\u000B\u3000\u2008\u2003\u205F\u3000\u1680"
            + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
            + "\u3000\u2004\u3000\u3000\u2028\n\u2007\u3000";

• 不可见字符

private static final String RANGE_STARTS =
        "\u0000\u007f\u00ad\u0600\u061c\u06dd\u070f\u08e2\u1680\u180e\u2000\u2028\u205f\u2066"
            + "\u3000\ud800\ufeff\ufff9";
private static final String RANGE_ENDS = // inclusive ends
        "\u0020\u00a0\u00ad\u0605\u061c\u06dd\u070f\u08e2\u1680\u180e\u200f\u202f\u2064\u206f"
            + "\u3000\uf8ff\ufeff\ufffb";

• 单字节长度字符

"\u0000\u05be\u05d0\u05f3\u0600\u0750\u0e00\u1e00\u2100\ufb50\ufe70\uff61"
"\u04f9\u05be\u05ea\u05f4\u06ff\u077f\u0e7f\u20af\u213a\ufdff\ufeff\uffdc"

中文字符就是双字节长度

微信公众号发布的文章和一般门户网站的新闻文本类型有所不同，通常不能用现有的文本分类器直接对这些文章进行分类，不过文本分类的原理是相通的，本文以微信公众号文章为对象，介绍朴素贝叶斯分类器的实现过程。

文本分类的科学原理和数学证明在网上有很多，这里就不做赘述，本文尽量使用通熟易懂的表述方式，简明扼要地梳理一下文本分类器的各个知识点。

参考了一下Github，发现少有Java 8风格的实现，所以这里的实现尽量利用Java 8的特性，相比之前优势有很多，例如stream在统计聚合等运算上比较方便，代码不仅简洁，而且更加语义化，另外在多线程并行控制上也省去不少的工作。

本项目的地址：https://github.com/fullstackyang/article-classifier

一、文本分类器的概述

文本分类器可以看作是一个预测函数，在给定的文本时，在预定的类别集合中，判断该文本最可能属于哪个类。

这里需要注意两个问题：

1. 在文本中含有比较多的标点符号和停用词（的，是，了等），直接使用整段文本处理肯定会产生很多不必要的计算，而且计算量也非常大，因此需要把给定的文本有效地进行表示，也就是选择一系列的特征词来代表这篇文本，这些特征词既可以比较好地反应所属文本的内容，又可以对不同文本有比较好的区分能力。
2. 在进行文本表示之后，如何对这些特征词进行预测，这就是分类器的算法设计问题了，比较常见的模型有朴素贝叶斯，基于支持向量机（SVM），K-近邻（KNN），决策树等分类算法。这里我们选择简单易懂的朴素贝叶斯算法。在机器学习中，朴素贝叶斯建模属于有监督学习，因此需要收集大量的文本作为训练语料，并标注分类结果

综上，实现一个分类器通常分为以下几个步骤：

1. 收集并处理训练语料，以及最后测试用的测试语料
2. 在训练集上进行特征选择，得到一系列的特征项（词），这些特征项组成了所谓的特征空间
3. 为了表示某个特征项在不同文档中的重要程度，计算该特征项的权重，常用的计算方法有TF-IDF，本文采用的是“经典”朴素贝叶斯模型，这里不考虑特征项的权重（当然，一定要做也可以）
4. 训练模型，对于朴素贝叶斯模型来说，主要的是计算每个特征项在不同类别中的条件概率，这点下面再做解释。
5. 预测文本，模型训练完成之后可以保存到文件中，在预测时直接读入模型的数据进行计算。

二、准备训练语料

这里需要的语料就是微信公众号的文章，我们可以抓取搜狗微信搜索网站(http://weixin.sogou.com/)首页上已经分类好的文章，直接采用其分类结果，这样也省去了标注的工作。至于如何开发爬虫去抓取文章，这里就不再讨论了。

“热门”这类别下的文章不具有一般性，因此不把它当作一个类别。剔除“热门”类别之后，最终我们抓取了30410篇文章，总共20个类别，每个类别的文章数并不均衡，其中最多 的是“养生堂”类别，有2569篇文章，最少的是“军事”类别，有654篇，大体符合微信上文章的分布情况。在保存时，我们保留了文章的标题，公众号名称，文章正文。

三、特征选择

如前文所述，特征选择的目的是降低特征空间的维度，避免维度灾难。简单地说，假设我们选择了2万个特征词，也就是说计算机通过学习，得到了一张有2万个词的“单词表”，以后它遇到的所有文本可以够用这张单词表中的词去表示其内容大意。这些特征词针对不同的类别有一定的区分能力，举例来说，“歼击机”可能来自“军事”，“越位”可能来自“体育”，“涨停”可能来自“财经”等等，而通常中文词汇量要比这个数字大得多，一本常见的汉语词典收录的词条数可达数十万。

常见的特征选择方法有两个，信息增益法和卡方检验法。

3.1 信息增益

信息增益法的衡量标准是，这个特征项可以为分类系统带来多少信息量，所谓的信息增益就是该特征项包含的能够帮预测类别的信息量，这里所说的信息量可以用熵来衡量，计算信息增益时还需要引入条件熵的概念，公式如下

可能有些见到公式就头大的小伙伴不太友好，不过这个公式虽然看起来有点复杂，其实在计算中还是比较简单的，解释一下：

P(Cj)：Cj类文档在整个语料中出现的概率；

P(ti)：语料中包含特征项ti的文档的概率，取反就是不包含特征项ti的文档的概率；

P(Cj|ti)：文档包含特征项ti且属于Cj类的条件概率，取反就是文档不包含特征项ti且属于Cj类的条件概率

上面几个概率值，都可以比较方便地从训练语料上统计得到。若还有不明白的小伙伴，推荐阅读这篇博客：文本分类入门（十一）特征选择方法之信息增益

3.2 卡方检验

卡方检验，基于χ2统计量(CHI)来衡量特征项ti和类别Cj之间的相关联程度，CHI统计值越高，该特征项与该类的相关性越大，如果两者相互独立，则CHI统计值接近零。计算时需要根据一张相依表（contingency table），公式也比较简单：

3.3 算法实现

不论何种方式都需要对每个特征项进行估算，然后根据所得的数值进行筛选，通常可以设定一个阈值，低于阈值的特征项可以直接从特征空间中移除，另外也可以按照数值从高到低排序，并指定选择前N个。这里我们采用后者，总共截取前2万个特征项。

特征选择实现类的代码如下，其中，不同特征选择方法需实现Strategy接口，以获得不同方法计算得到的估值，这里在截取特征项时为了避免不必要的麻烦，剔除了字符串长度为1的词。

Doc对象表示一篇文档，其中包含了该文档的所属分类，以及分词结果（已经滤掉了停用词等），即Term集合；

Term对象主要包含3个字段，词本身的字符串，词性（用于过滤），词频TF；

Feature表示特征项，一个特征项对应一个Term对象，还包含两个hashmap，一个用来统计不同类别下该特征项出现的文档数量（categoryDocCounter），另一个用来统计不同类别下该特征项出现的频度（categoryTermCounter）（对应朴素贝叶斯两种不同模型，下文详述）

统计时引入FeatureCounter对象，使用stream的reduce方法进行归约。主要的思想就是把每一个文档中的Term集合，映射为Term和Feature的键值对，然后再和已有的Map进行合并，合并时如果遇到相同的Term，则调用Feature的Merge方法，该方法会将双方term的词频，以及categoryDocCounter和categoryTermCounter中的统计结果进行累加。最终将所有文档全部统计完成返回Feature集合。

@AllArgsConstructor
public class FeatureSelection {

    interface Strategy {
        Feature estimate(Feature feature);
    }

    private final Strategy strategy;
    private final static int FEATURE_SIZE = 20000;

    public List<Feature> select(List<Doc> docs) {
        return createFeatureSpace(docs.stream())
                .stream()
                .map(strategy::estimate)
                .filter(f -> f.getTerm().getWord().length() > 1)
                .sorted(comparing(Feature::getScore).reversed())
                .limit(FEATURE_SIZE)
                .collect(toList());
    }

    private Collection<Feature> createFeatureSpace(Stream<Doc> docs) {

        @AllArgsConstructor
        class FeatureCounter {
            private final Map<Term, Feature> featureMap;

            private FeatureCounter accumulate(Doc doc) {
                Map<Term, Feature> temp = doc.getTerms().parallelStream()
                        .map(t -> new Feature(t, doc.getCategory()))
                        .collect(toMap(Feature::getTerm, Function.identity()));
                if (!featureMap.isEmpty())
                    featureMap.values().forEach(f -> temp.merge(f.getTerm(), f, Feature::merge));
                return new FeatureCounter(temp);
            }

            private FeatureCounter combine(FeatureCounter featureCounter) {
                Map<Term, Feature> temp = Maps.newHashMap(featureMap);
                featureCounter.featureMap.values().forEach(f -> temp.merge(f.getTerm(), f, Feature::merge));
                return new FeatureCounter(temp);
            }
        }

        FeatureCounter counter = docs.parallel()
                .reduce(new FeatureCounter(Maps.newHashMap()),
                        FeatureCounter::accumulate,
                        FeatureCounter::combine);
        return counter.featureMap.values();
    }
}
public class Feature {
...
    public Feature merge(Feature feature) {
        if (this.term.equals(feature.getTerm())) {
            this.term.setTf(this.term.getTf() + feature.getTerm().getTf());
            feature.getCategoryDocCounter()
                    .forEach((k, v) -> categoryDocCounter.merge(k, v, (oldValue, newValue) -> oldValue + newValue));
            feature.getCategoryTermCounter()
                    .forEach((k, v) -> categoryTermCounter.merge(k, v, (oldValue, newValue) -> oldValue + newValue));
        }
        return this;
    }
}

信息增益实现如下，在计算条件熵时，利用了stream的collect方法，将包含和不包含特征项的两种情况用一个hashmap分开再进行归约。

@AllArgsConstructor
public class IGStrategy implements FeatureSelection.Strategy {

    private final Collection<Category> categories;

    private final int total;

    public Feature estimate(Feature feature) {
        double totalEntropy = calcTotalEntropy();
        double conditionalEntrogy = calcConditionEntropy(feature);
        feature.setScore(totalEntropy - conditionalEntrogy);
        return feature;
    }

    private double calcTotalEntropy() {
        return Calculator.entropy(categories.stream().map(c -> (double) c.getDocCount() / total).collect(toList()));
    }

    private double calcConditionEntropy(Feature feature) {
        int featureCount = feature.getFeatureCount();
        double Pfeature = (double) featureCount / total;

        Map<Boolean, List<Double>> Pcondition = categories.parallelStream().collect(() -> new HashMap<Boolean, List<Double>>() {{
                    put(true, Lists.newArrayList());
                    put(false, Lists.newArrayList());
                }}, (map, category) -> {
                    int countDocWithFeature = feature.getDocCountByCategory(category);
                    //出现该特征词且属于类别key的文档数量/出现该特征词的文档总数量
                    map.get(true).add((double) countDocWithFeature / featureCount);
                    //未出现该特征词且属于类别key的文档数量/未出现该特征词的文档总数量
                    map.get(false).add((double) (category.getDocCount() - countDocWithFeature) / (total - featureCount));
                },
                (map1, map2) -> {
                    map1.get(true).addAll(map2.get(true));
                    map1.get(false).addAll(map2.get(false));
                }
        );
        return Calculator.conditionalEntrogy(Pfeature, Pcondition.get(true), Pcondition.get(false));
    }
}

卡方检验实现如下，每个特征项要在每个类别上分别计算CHI值，最终保留其最大值

@AllArgsConstructor
public class ChiSquaredStrategy implements Strategy {

    private final Collection<Category> categories;

    private final int total;

    @Override
    public Feature estimate(Feature feature) {

        class ContingencyTable {
            private final int A, B, C, D;

            private ContingencyTable(Feature feature, Category category) {
                A = feature.getDocCountByCategory(category);
                B = feature.getFeatureCount() - A;
                C = category.getDocCount() - A;
                D = total - A - B - C;
            }
        }

        Double chisquared = categories.stream()
                .map(c -> new ContingencyTable(feature, c))
                .map(ct -> Calculator.chisquare(ct.A, ct.B, ct.C, ct.D))
                .max(Comparator.comparingDouble(Double::valueOf)).get();
        feature.setScore(chisquared);
        return feature;
    }
}

四、朴素贝叶斯模型

4.1 原理简介

朴素贝叶斯模型之所以称之“朴素”，是因为其假设特征之间是相互独立的，在文本分类中，也就是说，一篇文档中出现的词都是相互独立，彼此没有关联，显然文档中出现的词都是有逻辑性的，这种假设在现实中几乎是不成立的，但是这种假设却大大简化了计算，根据贝叶斯公式，文档Doc属于类别Ci的概率为：

举例来说，假设有一篇文章，内容为“王者荣耀：两款传说品质皮肤将优化，李白最新模型海报爆料”，经过特征选择，文档可以表示为Doc=(王者荣耀，传说，品质，皮肤，优化，李白，最新，模型，海报，爆料)，那么在预测时需要计算P(王者荣耀，传说，品质，皮肤，优化，李白，最新，模型，海报，爆料|Ci)，这样一个条件概率是不可计算的，因为第一个特征取值为“王者荣耀”，第二个特征取值“传说”……第十个特征取值“爆料”的文档很可能为没有，那么概率就为零，而基于朴素贝叶斯的假设，这个条件概率可以转化为：

P(王者荣耀，传说，品质，皮肤，优化，李白，最新，模型，海报，爆料|Ci)=P(王者荣耀|Ci)P(传说|Ci)……P(爆料|Ci)

于是我们就可以统计这些特征词在每个类别中出现的概率了，在这个例子中，游戏类别中“王者荣耀”这个特征项会频繁出现，因此P(王者荣耀|游戏)的条件概率要明显高于其他类别，这就是朴素贝叶斯模型的朴素之处，粗鲁的聪明。

4.2 多项式模型与伯努利模型

在具体实现中，朴素贝叶斯又可以分为两种模型，多项式模型（Multinomial）和伯努利模型（Bernoulli），另外还有高斯模型，主要用于处理连续型变量，在文本分类中不讨论。

多项式模型和伯努利模型的区别在于对词频的考察，在多项式模型中文档中特征项的频度是参与计算的，这对于长文本来说是比较公平的，例如上面的例子，“王者荣耀”在游戏类的文档中频度会比较高，而伯努利模型中，所有特征词都均等地对待，只要出现就记为1，未出现就记为0，两者公式如下：

在多项式模型计算公式中，TF(ti,Doc)是文档Doc中特征ti出现的频度，TF(ti,Ci)就表示类别Ci中特征ti出现的频度，|V|表示特征空间的大小，也就是特征选择之后，不同（即去掉重复之后）的特征项的总个数，而P(Ci)可以用类别Ci中特征词的总数/所有特征词的总数，所有特征词的总数也就是所有特征词的词频之和。

至于分子和分母都加上一定的常量，这是为了防止数据稀疏而产生结果为零的现象，这种操作称为拉普拉斯平滑，至于背后的原理，推荐阅读这篇博客：贝叶斯统计观点下的拉普拉斯平滑

4.3 算法实现

这里使用了枚举类来封装两个模型，并实现了分类器NaiveBayesClassifier和训练器NaiveBayesLearner中的两个接口，其中Pprior和Pcondition是训练器所需的方法，前者用来计算先验概率，后者用来计算不同特征项在不同类别下的条件概率；getConditionProbability是分类器所需的方法，NaiveBayesKnowledgeBase对象是模型数据的容器，它的getPconditionByWord方法就是用于查询不同特征词在不同类别下的条件概率

public enum NaiveBayesModels implements NaiveBayesClassifier.Model, NaiveBayesLearner.Model {
    Bernoulli {
        @Override
        public double Pprior(int total, Category category) {
            int Nc = category.getDocCount();
            return Math.log((double) Nc / total);
        }

        @Override
        public double Pcondition(Feature feature, Category category, double smoothing) {
            int Ncf = feature.getDocCountByCategory(category);
            int Nc = category.getDocCount();
            return Math.log((double) (1 + Ncf) / (Nc + smoothing));
        }

        @Override
        public List<Double> getConditionProbability(String category, List<Term> terms, final NaiveBayesKnowledgeBase knowledgeBase) {
            return terms.stream().map(term -> knowledgeBase.getPconditionByWord(category, term.getWord())).collect(toList());
        }
    },
    Multinomial {
        @Override
        public double Pprior(int total, Category category) {
            int Nt = category.getTermCount();
            return Math.log((double) Nt / total);
        }

        @Override
        public double Pcondition(Feature feature, Category category, double smoothing) {
            int Ntf = feature.getTermCountByCategory(category);
            int Nt = category.getTermCount();
            return Math.log((double) (1 + Ntf) / (Nt + smoothing));
        }

        @Override
        public List<Double> getConditionProbability(String category, List<Term> terms, final NaiveBayesKnowledgeBase knowledgeBase) {
            return terms.stream().map(term -> term.getTf() * knowledgeBase.getPconditionByWord(category, term.getWord())).collect(toList());
        }
    };
}

五、训练模型

根据朴素贝叶斯模型的定义，训练模型的过程就是计算每个类的先验概率，以及每个特征项在不同类别下的条件概率，NaiveBayesKnowledgeBase对象将训练器在训练时得到的结果都保存起来，训练完成时写入文件，启动分类时从文件中读入数据交由分类器使用，那么在分类时就可以直接参与到计算过程中。

训练器的实现如下：

public class NaiveBayesLearner {
    ……
    ……
    public NaiveBayesLearner statistics() {
        log.info("开始统计...");
        this.total = total();
        log.info("total : " + total);
        this.categorySet = trainSet.getCategorySet();
        featureSet.forEach(f -> f.getCategoryTermCounter().forEach((category, count) -> category.setTermCount(category.getTermCount() + count)));
        return this;
    }

    public NaiveBayesKnowledgeBase build() {
        this.knowledgeBase.setCategories(createCategorySummaries(categorySet));
        this.knowledgeBase.setFeatures(createFeatureSummaries(featureSet, categorySet));
        return knowledgeBase;
    }

    private Map<String, NaiveBayesKnowledgeBase.FeatureSummary> createFeatureSummaries(final Set<Feature> featureSet, final Set<Category> categorySet) {
        return featureSet.parallelStream()
                .map(f -> knowledgeBase.createFeatureSummary(f, getPconditions(f, categorySet)))
                .collect(toMap(NaiveBayesKnowledgeBase.FeatureSummary::getWord, Function.identity()));
    }

    private Map<String, Double> createCategorySummaries(final Set<Category> categorySet) {
        return categorySet.stream().collect(toMap(Category::getName, c -> model.Pprior(total, c)));
    }

    private Map<String, Double> getPconditions(final Feature feature, final Set<Category> categorySet) {
        final double smoothing = smoothing();
        return categorySet.stream()
                .collect(toMap(Category::getName, c -> model.Pcondition(feature, c, smoothing)));
    }

    private int total() {
        if (model == Multinomial)
            return featureSet.parallelStream().map(Feature::getTerm).mapToInt(Term::getTf).sum();//总词频数
        else if (model == Bernoulli)
            return trainSet.getTotalDoc();//总文档数
        return 0;
    }

    private double smoothing() {
        if (model == Multinomial)
            return this.featureSet.size();
        else if (model == Bernoulli)
            return 2.0;
        return 0.0;
    }

    public static void main(String[] args) {
        TrainSet trainSet = new TrainSet(System.getProperty("user.dir") + "/trainset/");

        log.info("特征选择开始...");
        FeatureSelection featureSelection = new FeatureSelection(new ChiSquaredStrategy(trainSet.getCategorySet(), trainSet.getTotalDoc()));
        List<Feature> features = featureSelection.select(trainSet.getDocs());
        log.info("特征选择完成,特征数:[" + features.size() + "]");

        NaiveBayesModels model = NaiveBayesModels.Multinomial;
        NaiveBayesLearner learner = new NaiveBayesLearner(model, trainSet, Sets.newHashSet(features));
        learner.statistics().build().write(model.getModelPath());
        log.info("模型文件写入完成,路径:" + model.getModelPath());
    }
}

在main函数中执行整个训练过程，首先执行特征选择，这里使用卡方检验法，然后将得到特征空间，朴素贝叶斯模型（多项式模型），以及训练集TrainSet对象作为参数，初始化训练器，接着训练器开始进行统计的工作，事实上有一部分的统计工作，在初始化训练集对象时，就已经完成了，例如总文档数，每个类别下的文档数等，这些可以直接拿过来使用，最终将数据都装载到NaiveBayesKnowledgeBase对象当中去，并写入文件，格式为第一行是不同类别的先验概率，余下每一行对应一个特征项，每一列对应不同类别的条件概率值。

六、测试模型

分类器预测过程就相对于比较简单了，通过NaiveBayesKnowledgeBase读入数据，然后将指定的文本进行分词，匹配特征项，然后计算在不同类别下的后验概率，返回取得最大值对应的那个类别。

public class NaiveBayesClassifier {
    ……
    private final Model model;

    private final NaiveBayesKnowledgeBase knowledgeBase;

    public NaiveBayesClassifier(Model model) {
        this.model = model;
        this.knowledgeBase = new NaiveBayesKnowledgeBase(model.getModelPath());
    }

    public String predict(String content) {
        Set<String> allFeatures = knowledgeBase.getFeatures().keySet();
        List<Term> terms = NLPTools.instance().segment(content).stream()
                .filter(t -> allFeatures.contains(t.getWord())).distinct().collect(toList());

        @AllArgsConstructor
        class Result {
            final String category;
            final double probability;
        }

        Result result = knowledgeBase.getCategories().keySet().stream()
                .map(c -> new Result(c, Calculator.Ppost(knowledgeBase.getCategoryProbability(c),
                        model.getConditionProbability(c, terms, knowledgeBase))))
                .max(Comparator.comparingDouble(r -> r.probability)).get();
        return result.category;
    }
}

在实际测试时，我们又单独抓取了搜狗微信搜索网站上的文章，按照100篇一组，一共30组进行分类的测试，最终结果每一组的准确率均在90%以上，最高达98%，效果良好。当然正规的评测需要同时评估准确率和召回率，这里就偷懒不做了。

另外还需要说明一点的是，由于训练集是来源于搜狗微信搜索网站的文章，类别仅限于这20个，这不足以覆盖所有微信公众号文章的类别，因此在测试其他来源的微信文章准确率一定会有所影响。当然如果有更加丰富的微信文章训练集的话，也可以利用这个模型重新训练，那么效果也会越来越好。

七、参考文献与引用

1. 宗成庆. 统计自然语言处理[M]. 清华大学出版社, 2013.
2. T.M.Mitchell. 机器学习[M]. 机械工业出版社, 2003.
3. 吴军. 数学之美[M]. 人民邮电出版社, 2012.
4. Raoul-Gabriel Urma, Mario Fusco, Alan Mycroft. Java 8 实战[M]. 人民邮电出版社, 2016.
5. Ansj中文分词器，https://github.com/NLPchina/ansj_seg
6. HanLP中文分词器，https://github.com/hankcs/HanLP

一、背景知识

在网上已经有很多关于布隆过滤器的介绍了，这里就不再赘述，下面简单地提炼几个要点：

1. 布隆过滤器是用来判断一个元素是否出现在给定集合中的重要工具，具有快速，比哈希表更节省空间等优点，而缺点在于有一定的误识别率（false-positive，假阳性），亦即，它可能会把不是集合内的元素判定为存在于集合内，不过这样的概率相当小，在大部分的生产环境中是可以接受的；
2. 其原理比较简单，如下图所示，S集合中有n个元素，利用k个哈希函数，将S中的每个元素映射到一个长度为m的位（bit）数组B中不同的位置上，这些位置上的二进制数均置为1，如果待检测的元素经过这k个哈希函数的映射后，发现其k个位置上的二进制数不全是1，那么这个元素一定不在集合S中，反之，该元素可能是S中的某一个元素（参考1）；
3. 综上描述，那么到底需要多少个哈希函数，以及创建长度为多少的bit数组比较合适，为了估算出k和m的值，在构造一个布隆过滤器时，需要传入两个参数，即可以接受的误判率fpp和元素总个数n（不一定完全精确）。至于参数估计的方法，有兴趣的同学可以参考维基英文页面，下面直接给出公式：
4. 哈希函数的要求尽量满足平均分布，这样既降低误判发生的概率，又可以充分利用bit数组的空间；
5. 根据论文《Less Hashing, Same Performance: Building a Better Bloom Filter》提出的一个技巧，可以用2个哈希函数来模拟k个哈希函数，即gi(x) = h1(x) + ih2(x) ，其中0<=i<=k-1；
6. 在吴军博士的《数学之美》一书中展示了不同情况下的误判率，例如，假定一个元素用16位比特，8个哈希函数，那么假阳性的概率是万分之五，这已经相当小了。

首先我们来了解一下一些已经有相应实现的开源类库，如Google的Guava类库，Twitter的Algebird类库，和ScalaNLP breeze等等，其中Guava 11.0版本中增加了BloomFilter类，它使用了Funnel和Sink的设计，增强了泛化的能力，使其可以支持任何数据类型，其利用murmur3 hash来做哈希映射函数，不过它底层并没有使用传统的java.util.BitSet来做bit数组，而是用long型数组进行了重新封装，大部分操作均基于位的运算，因此能达到一个非常好的性能；Algebird是基于Scala开发的类库，其实现的布隆过滤器仅支持字符串作为元素类型，同样也采用了Murmur hash3，底层则是采用一种叫“EWAHCompressedBitmap”的数据结构，它专门为内存占用而优化，适合稀疏数据的场景，是一种可以替代BitSet的实现，不过缺点是随机访问的性能比较差；breeze是ScalaNLP下的核心类库，包括线性代数，数值计算和优化，是一个强大的机器学习工具，它实现的布隆过滤器没有使用通用的Murmur hash3算法，而是直接使用了对象的hash值，bit数组则是采用了BitSet，但是和Scala的通病一样，当编译成Java代码时分配了过多的对象，这会在内存占用上带来额外的开销。

下面我们就Guava类库中实现布隆过滤器的源码作详细分析，最后出于灵活性和解耦等因素的考虑，我们想要把布隆过滤器从JVM中拿出来，于是利用了Redis自带的Bitmaps作为底层的bit数组进行重构，另外随着插入的元素越来越多，当实际数量远远大于创建时设置的预计数量时，布隆过滤器的误判率会越来越高，因此在重构的过程中增加了自动扩容的特性，最后通过测试验证其正确性。

二、布隆过滤器在Guava中的实现

Guava中，布隆过滤器的实现主要涉及到2个类，BloomFilter和BloomFilterStrategies，首先来看一下BloomFilter：

 /** The bit set of the BloomFilter (not necessarily power of 2!) */
  private final BitArray bits;

  /** Number of hashes per element */
  private final int numHashFunctions;

  /** The funnel to translate Ts to bytes */
  private final Funnel<? super T> funnel;

  /**
   * The strategy we employ to map an element T to {@code numHashFunctions} bit indexes.
   */
  private final Strategy strategy;

这是它的4个成员变量

• BitArrays是定义在BloomFilterStrategies中的内部类，封装了布隆过滤器底层bit数组的操作，后文详述；
• numHashFunctions表示哈希函数的个数，即上文提到的k；
• Funnel，这是Guava中定义的一个接口，它和PrimitiveSink配套使用，主要是把任意类型的数据转化成Java基本数据类型（primitive value，如char，byte，int……），默认用java.nio.ByteBuffer实现，最终均转化为byte数组；
• Strategy是定义在BloomFilter类内部的接口，代码如下，有3个方法，put（插入元素），mightContain（判定元素是否存在）和ordinal方法（可以理解为枚举类中那个默认方法）

interface Strategy extends java.io.Serializable {

    /**
     * Sets {@code numHashFunctions} bits of the given bit array, by hashing a user element.
     *
     * <p>Returns whether any bits changed as a result of this operation.
     */
    <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);

    /**
     * Queries {@code numHashFunctions} bits of the given bit array, by hashing a user element;
     * returns {@code true} if and only if all selected bits are set.
     */
    <T> boolean mightContain(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);

    /**
     * Identifier used to encode this strategy, when marshalled as part of a BloomFilter. Only
     * values in the [-128, 127] range are valid for the compact serial form. Non-negative values
     * are reserved for enums defined in BloomFilterStrategies; negative values are reserved for any
     * custom, stateful strategy we may define (e.g. any kind of strategy that would depend on user
     * input).
     */
    int ordinal();
  }

对于创建布隆过滤器，BloomFilter并没有公有的构造函数，只有一个私有构造函数，而对外它提供了5个重载的create方法，在缺省情况下误判率设定为3%，采用BloomFilterStrategies.MURMUR128_MITZ_64的实现。其中4个create方法最终都调用了同一个create方法，由它来负责调用私有构造函数，其源码如下：

static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    checkNotNull(funnel);
    checkArgument(
        expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
    checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
    checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
    checkNotNull(strategy);

    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    /*
     * TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
     * is proportional to -log(p), but there is not much of a point after all, e.g.
     * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
     */
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

在create中接受了4个参数，funnel（输入的数据），expectedInsertions（预计插入的元素总数），fpp（期望误判率），strategy（实现Strategy的实例），然后它计算了bit数组的长度以及哈希函数的个数（公式参考前文），最后用numBits创建了BitArray，并调用了构造函数完成赋值操作。

static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
      p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
  }

static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
  }

接着再来看一下BloomFilterStrategies类，首先它是实现了BloomFilter.Strategy 接口的一个枚举类，其次它有两个2枚举值，MURMUR128_MITZ_32和MURMUR128_MITZ_64，分别对应了32位哈希映射函数，和64位哈希映射函数，后者使用了murmur3 hash生成的所有128位，具有更大的空间，不过原理是相通的，我们选择默认的MURMUR128_MITZ_64来分析：

MURMUR128_MITZ_64() {
    @Override
    public <T> boolean put(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
      long bitSize = bits.bitSize();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);

      boolean bitsChanged = false;
      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
        combinedHash += hash2;
      }
      return bitsChanged;
    }

    @Override
    public <T> boolean mightContain(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
      long bitSize = bits.bitSize();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);

      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
          return false;
        }
        combinedHash += hash2;
      }
      return true;
    }

抽象来看，put是写，mightContain是读，两个方法的代码有一点相似，都是先利用murmur3 hash对输入的funnel计算得到128位的字节数组，然后高低分别取8个字节（64位）创建2个long型整数hash1，hash2作为哈希值。循环体内采用了2个函数模拟其他函数的思想，即上文提到的gi(x) = h1(x) + ih2(x) ，这相当于每次累加hash2，然后通过基于bitSize取模的方式在bit数组中索引。

这里之所以要和Long.MAX_VALUE进行按位与的操作，是因为在除数和被除数符号不一致的情况下计算所得的结果是有差别的，在程序语言里，“%”准确来说是取余运算（C，C++和Java均如此，python是取模），如-5%3=-2，而取模的数学定义是x mod y=x-y[x/y]（向下取整），所以-5 mod 3= -5-3*(-2)=1，因此当哈希值为负数的时候，其取余的结果为负（bitSize始终为正数），这样就不方便在bit数组中取值，因此通过Long.MAX_VALUE(二进制为0111…1111)，直接将开头的符号位去掉，从而转变为正数。当然也可以取绝对值，在另一个MURMUR128_MITZ_32的实现中就是这么做的。

在put方法中，先是将索引位置上的二进制置为1，然后用bitsChanged记录插入结果，如果返回true表明没有重复插入成功，而mightContain方法则是将索引位置上的数值取出，并判断是否为0，只要其中出现一个0，那么立即判断为不存在。

最后再说一下底层bit数组的实现，主要代码如下：

 static final class BitArray {
    final long[] data;
    long bitCount;

    BitArray(long bits) {
      this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
    }

    // Used by serialization
    BitArray(long[] data) {
      checkArgument(data.length > 0, "data length is zero!");
      this.data = data;
      long bitCount = 0;
      for (long value : data) {
        bitCount += Long.bitCount(value);
      }
      this.bitCount = bitCount;
    }

    /** Returns true if the bit changed value. */
    boolean set(long index) {
      if (!get(index)) {
        data[(int) (index >>> 6)] |= (1L << index);
        bitCount++;
        return true;
      }
      return false;
    }

    boolean get(long index) {
      return (data[(int) (index >>> 6)] & (1L << index)) != 0;
    }

    /** Number of bits */
    long bitSize() {
      return (long) data.length * Long.SIZE;
    }
...
}

之前也提到了Guava没有使用java.util.BitSet，而是封装了一个long型的数组，另外还有一个long型整数，用来统计数组中已经占用（置为1）的数量，在第一个构造函数中，它把传入的long型整数按长度64分段（例如129分为3段），段数作为数组的长度，你可以想象成由若干个64位数组拼接成一个超长的数组，它的长度就是64乘以段数，即bitSize，在第二个构造函数中利用Long.bitCount方法来统计对应二进制编码中的1个数，这个方法在JDK1.5中就有了，其算法设计得非常精妙，有精力的同学可以自行研究。

另外两个重要的方法是set和get，在get方法中，参考put和mightContain方法，传入的参数index是经过bitSize取模的，因此一定能落在这个超长数组的范围之内，为了获取index对应索引位置上的值，首先将其无符号右移6位，并且强制转换成int型，这相当于除以64向下取整的操作，也就是换算成段数，得到该段上的数值之后，又将1左移index位，最后进行按位与的操作，如果结果等于0，那么返回false，从而在mightContain中判断为不存在。在set方法中，首先调用了get方法判断是否已经存在，如果不存在，则用同样的逻辑取出data数组中对应索引位置的数值，然后按位或并赋值回去。

到这里，对Guava中布隆过滤器的实现就基本讨论完了，简单总结一下：

1. BloomFilter类的作用在于接收输入，利用公式完成对参数的估算，最后初始化Strategy接口的实例；
2. BloomFilterStrategies是一个枚举类，具有两个实现了Strategy接口的成员，分别为MURMUR128_MITZ_32和MURMUR128_MITZ_64，另外封装了long型的数组作为布隆过滤器底层的bit数组，其中在get和set方法中完成核心的位运算。

三、利用Redis Bitmaps进行重构

通过上面的分析，主要算法和逻辑的部分大体都是一样的，真正需要重构的部分是底层位数组的实现，在Guava中是封装了一个long型的数组，而对于redis来说，本身自带了Bitmaps的“数据结构”（本质上还是一个字符串），已经提供了位操作的接口，因此重构本身并不复杂，相对比较复杂的是，之前提到的实现自动扩容特性。

这里实现自动扩容的思想是，在redis中记录一个自增的游标cursor，如果当前key对应的Bitmaps已经达到饱和状态，则cursor自增，同时用其生成一个新的key，并创建规模同等的Bitmaps。然后在get的时候，需要判断该元素是否存在于任意一个Bitmaps中。于是整个的逻辑就变成，一个元素在每个Bitmaps中都不存在时，才能插入当前cursor对应key的Bitmaps中。

下面是代码的实现部分。

首先，为了简化redis的操作，定义了2个函数式接口，分别执行单条命令和pipeline，另外还实现了一个简单的工具类

@FunctionalInterface
public interface JedisExecutor<T> {
    T execute(Jedis jedis);
}

@FunctionalInterface
public interface PipelineExecutor {
    void load(Pipeline pipeline);
}

public class JedisUtils {

    private static final GenericObjectPoolConfig poolConfig = new GenericObjectPoolConfig();

    private JedisPool jedisPool;

    public JedisUtils() {
        jedisPool = new JedisPool(poolConfig, "localhost", 6379);
    }

    public <T> T execute(JedisExecutor<T> jedisExecutor) {
        try (Jedis jedis = jedisPool.getResource()) {
            return jedisExecutor.execute(jedis);
        }
    }

    public List<Object> pipeline(List<PipelineExecutor> pipelineExecutors) {
        try (Jedis jedis = jedisPool.getResource()) {
            Pipeline pipeline = jedis.pipelined();
            for (PipelineExecutor executor : pipelineExecutors)
                executor.load(pipeline);
            return pipeline.syncAndReturnAll();
        }
    }
}

其次在Strategy中，对put和mightContain作了一点修改，其中被注释的部分是Guava中的实现。为了简化，这里我们只接受String对象。

这里先把所有的随机函数对应的索引位置收集到一个数组中，然后交由底层的RedisBitmaps处理get或set，具体过程后面会详细说明。

bits.ensureCapacityInternal()方法，即表示自动扩容，这个函数名是从ArrayList中搬过来的。

    @Override
    public boolean put(String string, int numHashFunctions, RedisBitmaps bits) {
        long bitSize = bits.bitSize();
        byte[] bytes = Hashing.murmur3_128().hashString(string, Charsets.UTF_8).asBytes();
        long hash1 = lowerEight(bytes);
        long hash2 = upperEight(bytes);

        boolean bitsChanged = false;
        long combinedHash = hash1;
//        for (int i = 0; i < numHashFunctions; i++) {
//            bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
//            combinedHash += hash2;
//        }
        long[] offsets = new long[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            offsets[i] = (combinedHash & Long.MAX_VALUE) % bitSize;
            combinedHash += hash2;
        }
        bitsChanged = bits.set(offsets);
        bits.ensureCapacityInternal();//自动扩容
        return bitsChanged;
    }

    @Override
    public boolean mightContain(String object, int numHashFunctions, RedisBitmaps bits) {
        long bitSize = bits.bitSize();
        byte[] bytes = Hashing.murmur3_128().hashString(object, Charsets.UTF_8).asBytes();
        long hash1 = lowerEight(bytes);
        long hash2 = upperEight(bytes);
        long combinedHash = hash1;
//        for (int i = 0; i < numHashFunctions; i++) {
//            if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
//                return false;
//            }
//            combinedHash += hash2;
//        }
//        return true;
        long[] offsets = new long[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            offsets[i] = (combinedHash & Long.MAX_VALUE) % bitSize;
            combinedHash += hash2;
        }
        return bits.get(offsets);
    }

最后，也是最重要的RedisBitmaps，其中bitSize用了Guava布隆过滤器中计算Long型数组长度的方法，得到bitSize之后使用setbit命令初始化一个全部为0的位数组。get(long offset)和set(long offset)，这两个与Guava布隆过滤器中的逻辑类似，这里就不再赘述了，而get(long[] offsets)方法中，所有的offset要与每一个cursor对应的Bitmaps进行判断，若全部命中，那么这个元素就可能存在于该Bitmaps，反之若不能完全命中，则表示该元素不存在于任何一个Bitmaps，所以当满足这个条件，在set(long[] offsets)方法中，就可以插入到当前key的Bitmaps中了。

在ensureCapacityInternal方法，判断需要扩容的条件是bitCount*2>bitSize，bitCount表示一个Bitmaps中“1”出现的个数，也就是当“1”出现的个数超过总数的一半时，进行扩容操作——首先使用incr命令对cursor自增，然后使用新的key创建一个新的Bitmaps。

class RedisBitmaps {

    private static final String BASE_KEY = "bloomfilter";
    private static final String CURSOR = "cursor";

    private JedisUtils jedisUtils;
    private long bitSize;

    RedisBitmaps(long bits) {
        this.jedisUtils = new JedisUtils();
        this.bitSize = LongMath.divide(bits, 64, RoundingMode.CEILING) * Long.SIZE;//位数组的长度，相当于n个long的长度
        if (bitCount() == 0) {
            jedisUtils.execute((jedis -> jedis.setbit(currentKey(), bitSize - 1, false)));
        }
    }

   boolean get(long[] offsets) {
        for (long i = 0; i < cursor() + 1; i++) {
            final long cursor = i;
            //只要有一个cursor对应的bitmap中，offsets全部命中，则表示可能存在
            boolean match = Arrays.stream(offsets).boxed()
                    .map(offset -> jedisUtils.execute(jedis -> jedis.getbit(genkey(cursor), offset)))
                    .allMatch(b -> (Boolean) b);
            if (match)
                return true;
        }
        return false;
    }

    boolean get(final long offset) {
        return jedisUtils.execute(jedis -> jedis.getbit(currentKey(), offset));
    }

    boolean set(long[] offsets) {
        if (cursor() > 0 && get(offsets)) {
            return false;
        }
        boolean bitsChanged = false;
        for (long offset : offsets)
            bitsChanged |= set(offset);
        return bitsChanged;
    }

    boolean set(long offset) {
        if (!get(offset)) {
            jedisUtils.execute(jedis -> jedis.setbit(currentKey(), offset, true));
            return true;
        }
        return false;
    }

    long bitCount() {
        return jedisUtils.execute(jedis -> jedis.bitcount(currentKey()));
    }

    long bitSize() {
        return this.bitSize;
    }

    private String currentKey() {
        return genkey(cursor());
    }

    private String genkey(long cursor) {
        return BASE_KEY + "-" + cursor;
    }

    private Long cursor() {
        String cursor = jedisUtils.execute(jedis -> jedis.get(CURSOR));
        return cursor == null ? 0 : Longs.tryParse(cursor);
    }

    void ensureCapacityInternal() {
        if (bitCount() * 2 > bitSize())
            grow();
    }

    void grow() {
        Long cursor = jedisUtils.execute(jedis -> jedis.incr(CURSOR));
        jedisUtils.execute((jedis -> jedis.setbit(genkey(cursor), bitSize - 1, false)));
    }

    void reset() {
        String[] keys = LongStream.range(0, cursor() + 1).boxed().map(this::genkey).toArray(String[]::new);
        jedisUtils.execute(jedis -> jedis.del(keys));
        jedisUtils.execute(jedis -> jedis.set(CURSOR, "0"));
        jedisUtils.execute(jedis -> jedis.setbit(currentKey(), bitSize - 1, false));
    }

    private PipelineExecutor apply(PipelineExecutor executor) {
        return executor;
    }
}

下面我们做一个单元测试来验证其正确性。

如果我们插入的数量等于原预计总数，RedisBloomFilter扩容了1次，而两个布隆过滤器的结果一致，都为false,true,false。

如果插入的数量为原预计总数的3倍，RedisBloomFilter扩容了3次，并且仍判断正确，而Guava布隆过滤器则在判断str3时出现误判。

public class TestRedisBloomFilter {

    private static final int TOTAL = 10000;
    private static final double FPP = 0.0005;

    @Test
    public void test() {
        RedisBloomFilter redisBloomFilter = RedisBloomFilter.create(TOTAL, FPP);
        redisBloomFilter.resetBitmap();
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), TOTAL, FPP);

        IntStream.range(0, /* 3* */TOTAL).boxed()
                .map(i -> Hashing.md5().hashInt(i).toString())
                .collect(toList()).forEach(s -> {
            redisBloomFilter.put(s);
            bloomFilter.put(s);
        });

        String str1 = Hashing.md5().hashInt(99999).toString();
        String str2 = Hashing.md5().hashInt(9999).toString();
        String str3 = "abcdefghijklmnopqrstuvwxyz123456";
        System.out.println(redisBloomFilter.mightContain(str1) + ":" + bloomFilter.mightContain(str1));
        System.out.println(redisBloomFilter.mightContain(str2) + ":" + bloomFilter.mightContain(str2));
        System.out.println(redisBloomFilter.mightContain(str3) + ":" + bloomFilter.mightContain(str3));
    }
}
>>
grow bloomfilter-1
false:false
true:true
false:false
>>
grow bloomfilter-1
grow bloomfilter-2
grow bloomfilter-3
false:false
true:true
false:true

综上，本文利用了Guava布隆过滤器的思想，并结合Redis中的Bitmaps等特性实现了支持动态扩容的布隆过滤器，它将布隆过滤器底层的位数据装载到了Redis数据库中，这样的好处在于可以部署在更复杂的多应用或分布式系统中，还可以利用Redis完成持久化，定时过期等功能。

四、参考文献

1. 吴军. 数学之美[M]. 人民邮电出版社, 2012.
2. Kirsch A, Mitzenmacher M. Less hashing, same performance: building a better bloom filter[C]//ESA. 2006, 6: 456-467.
3. Bloom Filters for the Perplexed, https://sagi.io/2017/07/bloom-filters-for-the-perplexed/
4. Google Guava, https://github.com/google/guava

在使用HttpClient进行抓取一些网页的时候，经常会保留从服务器端发回的Cookie信息，以便发起需要这些Cookie的请求。大多数情况下，我们使用内置的cookie策略，便能够方便直接地获取这些cookie。

下面的一小段代码，就是访问http://www.baidu.com，并获取对应的cookie：

    @Test
    public void getCookie(){
        CloseableHttpClient httpClient = HttpClients.createDefault();
        HttpGet get=new HttpGet("http://www.baidu.com");
        HttpClientContext context = HttpClientContext.create();
        try {
            CloseableHttpResponse response = httpClient.execute(get, context);
            try{
                System.out.println(">>>>>>headers:");
                Arrays.stream(response.getAllHeaders()).forEach(System.out::println);
                System.out.println(">>>>>>cookies:");
                context.getCookieStore().getCookies().forEach(System.out::println);
            }
            finally {
                response.close();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            try {
                httpClient.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

打印结果

>>>>>>headers:
Server: bfe/1.0.8.18
Date: Tue, 12 Sep 2017 06:19:06 GMT
Content-Type: text/html
Last-Modified: Mon, 23 Jan 2017 13:28:24 GMT
Transfer-Encoding: chunked
Connection: Keep-Alive
Cache-Control: private, no-cache, no-store, proxy-revalidate, no-transform
Pragma: no-cache
Set-Cookie: BDORZ=27315; max-age=86400; domain=.baidu.com; path=/
>>>>>>cookies:
[version: 0][name: BDORZ][value: 27315][domain: baidu.com][path: /][expiry: null]

但是也有一些网站返回的cookie并不一定完全符合规范，例如下面这个例子，从打印出的header中可以看到，这个cookie中的Expires属性是时间戳形式，并不符合标准的时间格式，因此，httpclient对于cookie的处理失效，最终无法获取到cookie，并且发出了一条警告信息：“Invalid ‘expires’ attribute: 1505204523”。

九月 12, 2017 2:22:04 下午 org.apache.http.client.protocol.ResponseProcessCookies processCookies
警告: Invalid cookie header: "Set-Cookie: yd_cookie=90236a64-8650-494b332a285dbd886e5981965fc4a93f023d; Expires=1505204523; Path=/; HttpOnly". Invalid 'expires' attribute: 1505204523
>>>>>>headers:
Date: Tue, 12 Sep 2017 06:22:03 GMT
Content-Type: text/html
Connection: keep-alive
Set-Cookie: yd_cookie=90236a64-8650-494b332a285dbd886e5981965fc4a93f023d; Expires=1505204523; Path=/; HttpOnly
Cache-Control: no-cache, no-store
Server: WAF/2.4-12.1
>>>>>>cookies:

虽然我们可以使用header的数据，重新构造一个cookie出来，也有很多人确实也是这么做的，但这种方法不够优雅，那么如何解决这个问题？网上相关的资料又很少，所以就只能先从官方文档入手。
在官方文档3.4小节custom cookie policy中讲到允许自定义的cookie策略，自定义的方法是实现CookieSpec接口，并通过创建CookieSpecProvider的实现，来完成在httpclient中的初始化和注册策略实例的工作。好了，关键的线索在于CookieSpec接口，我们来看一下它的源码：

public interface CookieSpec {
……
    /**
      * Parse the {@code "Set-Cookie"} Header into an array of Cookies.
      *
      * <p>This method will not perform the validation of the resultant
      * {@link Cookie}s</p>
      *
      * @see #validate
      *
      * @param header the {@code Set-Cookie} received from the server
      * @param origin details of the cookie origin
      * @return an array of {@code Cookie}s parsed from the header
      * @throws MalformedCookieException if an exception occurs during parsing
      */
    List<Cookie> parse(Header header, CookieOrigin origin) throws MalformedCookieException;
……

}

在源码中我们发现了一个parse方法，从注释中可以知道，正是这个方法，将Set-Cookie的header信息解析为Cookie对象，自然地再看一下在httplcient中的默认实现DefaultCookieSpec，限于篇幅，源码就不贴了。在默认的实现中，DefaultCookieSpec主要的工作是判断header中Cookie规范的类型，然后再调用具体的某一个实现。像上述这种Cookie，最终是交由NetscapeDraftSpec的实例来做解析，而在NetscapeDraftSpec的源码中，定义了对应expires时间格式为“EEE, dd-MMM-yy HH:mm:ss z”

public class NetscapeDraftSpec extends CookieSpecBase {

    protected static final String EXPIRES_PATTERN = "EEE, dd-MMM-yy HH:mm:ss z";

    /** Default constructor */
    public NetscapeDraftSpec(final String[] datepatterns) {
        super(new BasicPathHandler(),
                new NetscapeDomainHandler(),
                new BasicSecureHandler(),
                new BasicCommentHandler(),
                new BasicExpiresHandler(
                        datepatterns != null ? datepatterns.clone() : new String[]{EXPIRES_PATTERN}));
    }

    NetscapeDraftSpec(final CommonCookieAttributeHandler... handlers) {
        super(handlers);
    }

    public NetscapeDraftSpec() {
        this((String[]) null);
    }
……
}

到这里已经比较清楚了，我们只需要将Cookie中expires的时间转换为正确的格式，然后再送入默认的解析器就可以了。

解决方法：

1. 自定义一个CookieSpec类，继承DefaultCookieSpec
2. 重写parser方法
3. 将Cookie中的expires转换为正确的时间格式
4. 调用默认的解析方法

实现如下：

public class TestHttpClient {
    
    String url = sth;

    class MyCookieSpec extends DefaultCookieSpec {
        @Override
        public List<Cookie> parse(Header header, CookieOrigin cookieOrigin) throws MalformedCookieException {
            String value = header.getValue();
            String prefix = "Expires=";
            if (value.contains(prefix)) {
                String expires = value.substring(value.indexOf(prefix) + prefix.length());
                expires = expires.substring(0, expires.indexOf(";"));
                String date = DateUtils.formatDate(new Date(Long.parseLong(expires) * 1000L),"EEE, dd-MMM-yy HH:mm:ss z");
                value = value.replaceAll(prefix + "\\d{10};", prefix + date + ";");
            }
            header = new BasicHeader(header.getName(), value);
            return super.parse(header, cookieOrigin);
        }
    }

    @Test
    public void getCookie() {

        CloseableHttpClient httpClient = HttpClients.createDefault();

        Registry<CookieSpecProvider> cookieSpecProviderRegistry = RegistryBuilder.<CookieSpecProvider>create()
                .register("myCookieSpec", context -> new MyCookieSpec()).build();//注册自定义CookieSpec

        HttpClientContext context = HttpClientContext.create();
        context.setCookieSpecRegistry(cookieSpecProviderRegistry);

        HttpGet get = new HttpGet(url);
        get.setConfig(RequestConfig.custom().setCookieSpec("myCookieSpec").build());

        try {
            CloseableHttpResponse response = httpClient.execute(get, context);
            try{
                System.out.println(">>>>>>headers:");
                Arrays.stream(response.getAllHeaders()).forEach(System.out::println);
                System.out.println(">>>>>>cookies:");
                context.getCookieStore().getCookies().forEach(System.out::println);
            }
            finally {
                response.close();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            try {
                httpClient.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

再次运行，便可顺利地打印出正确的结果，完美！

>>>>>>headers:
Date: Tue, 12 Sep 2017 07:24:10 GMT
Content-Type: text/html
Connection: keep-alive
Set-Cookie: yd_cookie=9f521fc5-0248-4ab3ee650ca50b1c7abb1cd2526b830e620f; Expires=1505208250; Path=/; HttpOnly
Cache-Control: no-cache, no-store
Server: WAF/2.4-12.1
>>>>>>cookies:
[version: 0][name: yd_cookie][value: 9f521fc5-0248-4ab3ee650ca50b1c7abb1cd2526b830e620f][domain: www.sth.com][path: /][expiry: Tue Sep 12 17:24:10 CST 2017]

一、Tomcat部署的场景分析

通常，我们对tomcat部署需求可以分为几种：单实例单应用，单实例多应用，多实例单应用，多实例多应用。

对于第一种场景，如果不要求周期性地维护tomcat版本，一般的做法是把打好的war包丢到webapps目录下，然后执行startup.sh脚本，并且可以在浏览器里访问就行了。

对于第二种场景，是把多个应用程序的war包放在同一个tomcat的webapps目录，这样一来，关闭和启动tomcat会影响所有项目。

对于第三种场景，各个tomcat都运行同一个应用程序，对应地需要修改不同的监听端口，这种方式通常会和apache httpd或者nginx整合使用，做一些负载均衡的处理。

对于第四种场景相当于第一种场景的复数形式，除了修改不同的监听端口，没有本质区别。

一般来说，多实例部署tomcat，可以充分利用系统资源，不过这种方式，也有几个方面需要考虑：

• 多实例tomcat的更新维护，例如对tomcat进行升级等操作，我们需要考虑如何能“优雅”地对所有实例进行升级
• 尽量不要影响应用程序，在更新tomcat时，一不小心就把conf目录等全部覆盖，所以尽量要把配置文件和安装目录隔离
• 对于单应用来说，如果将war包分别置于各个tomcat的webapps目录，那么在发布新版本的war时，可能会出现某个实例更新失败，导致用户在访问时可能会访问到不同版本的web app，因此，比较好的方式就是所有tomcat实例都统一指向同一个应用程序

本文重点阐述多实例应用的部署方案，但是为了解决上述几个问题，我们需要先来了解一下tomcat的一些基本情况

二、基本要点

2.1 分离目录

首先来看一下tomcat的目录结构，一个刚解压出来的tomcat打包文件应该有以下几个目录

• CATALINA_HOME：即指向Tomcat安装路径的系统变量
• CATALINA_BASE：即指向活跃配置路径的系统变量
  通过设置这两个变量，就可以将tomcat的安装目录和工作目录分离，从而实现tomcat多实例的部署。

Tomcat官方文档指出，CATALINA_HOME路径的路径下只需要包含bin和lib目录，这也就是支持tomcat软件运行的目录，而CATALINA_BASE设置的路径可以包括上述所有目录，不过其中bin和lib目录并不是必需的，缺省时会使用CATALINA_HOME中的bin和conf。如此，我们就可以使用一个tomcat安装目录部署多个tomcat实例，这样的好处在于方便升级，就可以在不影响tomcat实例的前提下，替换掉CATALINA_HOME指定的tomcat安装目录。

2.2 修改server.xml

这里不详细分析server.xml中每一个配置项，网上也有很多这方面的文档。下面主要说明监听端口和Host的配置内容。

在server.xml中配置了四个监听端口，分别是：

• Server Port：该端口用于监听关闭tomcat的shutdown命令，默认为8005
• Connector Port：该端口用于监听HTTP的请求，默认为8080
• AJP Port：该端口用于监听AJP（ Apache JServ Protocol ）协议上的请求，通常用于整合Apache Server等其他HTTP服务器，默认为8009
• Redirect Port：重定向端口，出现在Connector配置中，如果该Connector仅支持非SSL的普通http请求，那么该端口会把https的请求转发到这个Redirect Port指定的端口，默认为8443

可见，如果不是使用AJP协议连接tomcat，只需要保证多实例中的Server Port和Connect Port不同即可。

再来说Host配置，Host就是所谓的虚拟主机，对应包含了一个或者多个web应用程序，默认的Host配置如下

<Host name="localhost"  appBase="webapps" unpackWARs="true" autoDeploy="true">

其中：

• name： 虚拟主机的名称，一台主机表示了完全限定的域名或IP地址，默认为localhost，同时也是唯一的host，进入tomcat的所有http请求都会映射到该主机上
• appBase：web应用程序目录的路径，可以是CATALINA_HOME的相对路径，也可以写成绝对路径，默认情况下为$CATALINA_HOME/webapps
• unpackWARs： 表示是否自动解压war包
• autoDeploy：所谓的热部署，即在tomcat正在运行的情况下，如果有新的war加入，则会立即执行部署操作
• 另外再介绍一个Host中的属性—deployOnStartup：表示tomcat启动时是否自动部署appBase目录下所有的Web应用程序，默认为true。这个属性和autoDeploy会产生两次部署的“副作用”：一次是tomcat启动时就开始部署，第二次就是autoDeploy引起的热部署。因此最好将autoDeploy置为false

在部署多实例单应用的时候，默认的$CATALINA/webapps会因为tomcat安装目录升级产生不必要的麻烦，我们考虑将appBase的目录统一到另外的路径下。

最后再说明一下Context的配置，它出现在Host配置内，一个Context的配置就代表了一个web应用程序，如果配置多应用程序，就需要在Host下配置多个Context，一个简单的Context配置如下

<Context path="/some" docBase="someapp.war" >

其中:

• path：表示访问入口，例如，path=”/abc”，则访问localhost:8080/abc时，就可以访问该Context对应的应用程序。如果path=””，则直接用localhost:8080就可以访问
• docBase：表示应用程序的解包目录或者war文件路径，是Host的appBase配置目录的相对路径，也可以是直接写成绝对路径，但是不要将appBase的值，作为docBase配置路径的前缀，例如appBase=”somedir”，docBase=”somedir-someapp.war”，这样的配置会导致部署错误
  通过配置Host的appBase和Context的docBase两个属性，可以将应用程序的文件和tomcat相关的目录进行分离，这样webapps目录也就没有作用了。

最终我们可以得到多实例单应用部署方案的整体框架：

三、方案实施

现在假设我们有一台已经配置好Java环境的服务器：

# export JAVA_HOME=/application/jdk
# export PATH=$JAVA_HOME/bin:$JAVA_HOME/jre/bin:$PATH
# export CLASSPATH=.$CLASSPATH:$JAVA_HOME/lib:$JAVA_HOME/jre/lib:$JAVA_HOME/lib/tools.jar

# java -version
java version "1.8.0_101"
Java(TM) SE Runtime Environment (build 1.8.0_101-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.101-b13, mixed mode)

另外假设一个完好的可以运行的web应用程序已经打包成some.war，放在/data/www目录下，其中包含一个简单的index.jsp

<html>
<body>
<h2>Hello World!</h2>
</body>
</html>

3.1 下载并解压tomcat

# cd /usr/local
# wget -q http://mirrors.cnnic.cn/apache/tomcat/tomcat-7/v7.0.72/bin/apache-tomcat-7.0.72.tar.gz
# tar zxf apache-tomcat-7.0.72.tar.gz
# ls apache-tomcat-7.0.72
bin  conf  lib  LICENSE  logs  NOTICE  RELEASE-NOTES  RUNNING.txt  temp  webapps  work

3.2 配置tomcat多实例

可以用一小段脚本来完成批量创建的工作

for ((i=1;i<=3;i++))
do
    mkdir /application/tomcat7-$i/{work,temp,conf,logs} -p
    cp -a /application/tomcat7-$i/application/tomcat7-$i && \
    sed -i 22s@8005@80${i}5@ /application/tomcat7-$i/conf/server.xml // 修改tomcat关闭端口
    sed -i 71s@8080@808${i}@ /application/tomcat7-$i/conf/server.xml // 修改Http监听端口
    sed -i 93s@8009@80${i}9@ /application/tomcat7-$i/conf/server.xml // 修改AJP端口
    sed -i '125s@appBase="webapps"@appBase="/data/www"@' /application/tomcat7-$i/conf/server.xml //统一web应用程序的路径
    sed -i '126s@autoDeploy="true"@autoDeploy="false"@' /application/tomcat7-$i/conf/server.xml //关闭自动部署
    sed -i '126a <Context path="" docBase="/data/www/some.war" />' /application/tomcat7-$i/conf/server.xml //配置Context信息，指向some.war的路径
done

3.3 创建启停脚本

#!/bin/sh

CUR_DIR=`dirname $BASH_SOURCE`
export JAVA_HOME="/application/jdk"
export CATALINA_BASE=`readlink -f $CUR_DIR`
export CATALINA_HOME="/usr/local/apache-tomcat-7.0.72"

case $1 in
 start)
 [ -f $CATALINA_HOME/bin/startup.sh ] && $CATALINA_HOME/bin/startup.sh
 ;;
 stop)
 [ -f $CATALINA_HOME/bin/shutdown.sh ] && $CATALINA_HOME/bin/shutdown.sh
 ;;
 restart)
 [ -f $CATALINA_HOME/bin/shutdown.sh ] && $CATALINA_HOME/bin/shutdown.sh && \
 [ -f $CATALINA_HOME/bin/startup.sh ] && $CATALINA_HOME/bin/startup.sh
 ;;
 *)
 echo "usage : $0 { start | stop | restart }"
 return 1;
 ;;
esac

return 0

把该脚本放在tomcat7-1，tomcat7-2和tomcat7-3目录下

现在我们的目录结构如下

# ls tomcat7-1 tomcat7-2 tomcat7-3 
tomcat7-1:
conf  logs  temp  tomcat.sh  work

tomcat7-2:
conf  logs  temp  tomcat.sh  work

tomcat7-3:
conf  logs  temp  tomcat.sh  work

3.4 启动tomcats

# cd /application
# . tomcat7-1/tomcat.sh start 
# . tomcat7-2/tomcat.sh start
# . tomcat7-3/tomcat.sh start

# netstat -tunlp
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address               Foreign Address             State       PID/Program name   
tcp        0      0 0.0.0.0:22                  0.0.0.0:*                   LISTEN      25757/sshd                
tcp        0      0 :::8029                     :::*                        LISTEN      21225/java          
tcp        0      0 ::ffff:127.0.0.1:8035       :::*                        LISTEN      21186/java          
tcp        0      0 :::8039                     :::*                        LISTEN      21186/java          
tcp        0      0 ::ffff:127.0.0.1:8015       :::*                        LISTEN      21002/java          
tcp        0      0 :::8081                     :::*                        LISTEN      21002/java          
tcp        0      0 :::8082                     :::*                        LISTEN      21225/java          
tcp        0      0 :::8083                     :::*                        LISTEN      21186/java          
tcp        0      0 :::8019                     :::*                        LISTEN      21002/java          
tcp        0      0 :::22                       :::*                        LISTEN      25757/sshd          
tcp        0      0 ::ffff:127.0.0.1:8025       :::*                        LISTEN      21225/java

可以看到8081，8082，8083等其他端口都已经启动，现在可以使用curl命令进行访问

# curl localhost:8081
<html>
<body>
<h2>Hello World!</h2>
</body>
</html>

# curl localhost:8082
<html>
<body>
<h2>Hello World!</h2>
</body>
</html>

# curl localhost:8083
<html>
<body>
<h2>Hello World!</h2>
</body>
</html>

完成！

四、参考文献

• (美)布里泰恩, (美)达尔文, 吴豪. Tomcat权威指南[M]. 中国电力出版社, 2009.
• tomcat官方文档：https://tomcat.apache.org/tomcat-7.0-doc/RUNNING.txt

一、引言

作为一名IT从业者，不仅要有扎实的知识储备，出色的业务能力，还需要具备一定的软实力。软实力体现在具体事务的处理能力，包括沟通，协作，团队领导，问题的解决方案等，这些能力在关键时刻比硬性的技术水平更能体现一名工程师的价值，它决定了IT职业生涯的高度和视野。

而本文所分享的绘图能力，与其说是软实力，不妨说是基本功。无论从事的是开发、运维、通信，甚至产品经理，交互设计、运营这些有交集的岗位，都会在工作中用到。因为在计算机的世界里，大多数场景都是抽象的，当我们在描述他们的时候，一定是通过其实现原理和机制，抽象出一个行为逻辑，最后再具象到一张图。想象一下，当我们在浏览器中输入了一个地址，在敲击回车之后，所发生的一切是多么地复杂，如果能拍成电影，那么可以取名叫《一个数据包的奇幻漂流》。如果你能够以具象的画面来表述一个计算机世界中发生的一个场景，那很好，说明你的思路清晰，对原理的理解非常透彻，然后你要做的工作就像导演创作分镜一样，将它们体现在画纸上。

这是一种所谓抽象思维的能力，最好的锻炼方式之一便是画图。很多时候，我们会觉得说不清楚，一旦你发现说不清楚，那么我们就可以用画图来说明，这些图包含了你想要表达的思想或者逻辑，而不是一个画得非常逼真的主机箱。因此，在工作学习中，养成画图的习惯，把复杂模糊的文字描述转换成一张清晰直白的图，不仅可以降低许多沟通的成本，还可以锻炼个人的抽象思维能力。

下图（重新绘制）取自Jesse James Garrett 的《用户体验的要素：以用户为中心的Web设计》一书中的用户体验模型，可以说整本书就是围绕这张图展开论述的，是很多产品经理的入门经典书籍。从2000年3月初次发布到网上以来，Jesse所绘制的这个模型已经被下载了2万多次。事实上，用户体验是一种非常抽象的东西，所谓大师就是具备这样的能力，将极为抽象的思想，投射到一个简单的二维空间上，表现为具象的图表，从而形成具有逻辑的信息，这就是真正意义上的深入浅出。

那么很多人会问，说了这么多，用什么工具画图比较好等等，这里要说明的是，本文所要分享的内容，并不局限于某一种画图的工具和技巧，工具本身没有什么高低之差，差别在于是否具备抽象思维的能力，在于绘图的操作是否规范高效，在于是否理解事务的机理，关注这些才能够提升绘图能力，而不是陷入工具之争，这没有任何意义，即便是最普通的windows画图板，一样可以画图，无非图标不够漂亮，但我们并不在乎这些，对于IT从业者来说，并不需要视觉上艺术上的美感，而是这张图背后承载的信息。

下面要介绍的基本是各个绘图软件都相通的功能特性，使用这些功能可以提升我们绘图的效率，另外还提出了一些绘图的规范建议，供大家参考，毕竟这不是一份绘图软件的说明书。希望大家能够了解绘图的思想，而不是工具本身的使用。

二、ProcessOn简介

本文所使用的是在线绘图工具——ProcessOn，这是一个方便易用、免费高效的在线作图工具，运用它可以免费制作多种图。

之所以会使用这个工具，主要有几个原因：

• 一是因为它是一个在线的工具，自然也就有了跨平台的特性。作为一个IT从业者，很多情况下会穿梭在Windows，Linux，Mac OS这些操作系统之间工作，而常用的绘图软件，通常只能运行在Windows，当然Linux和Mac OS也有非常不错的绘图软件，但终究无法实现移动办公。而作为在线工具，也就屏蔽了因为不同操作系统带来的麻烦，你可以方便地在家中MacBook中使用它打开公司下班前画的一张半成品图，继续完成，然后明天上班就可以直接给领导作汇报了。
• 二是因为其在线存储，这也很重要，可以避免一些悲剧的发生，例如赶了一晚上的图，突然断电，蓝屏什么的，然而并没有保存，不得不满腹怨气地重画。
• 三是因为它操作简单，它基本吸取了visio之类常用绘图软件的操作特点，因此对于有绘图经验的用户，学习成本几乎为零。
• 四是因为结合网络社交的特性，不同图表的作者可以轻松地在平台分享各自作品，用户也可以方便地对公开的作品进行搜索，同时还支持多人协作的功能，适合团队内部协同工作

当然，这个工具也不是十全十美的，毕竟是2015年才上线提供服务，产品还存在或大或小的不稳定因素，如丢失数据（据其他网友反馈存在这样的情况，不过笔者在实际使用中未遇到过），菜单功能卡住，图标相对比较少等，不过这些问题也还在可忍受的范围之内。作为国内免费的在线绘图工具，可以做到这般实为不易。

三、操作技巧

对于ProcessOn登录注册等其他操作，这里不过多介绍（说多了就像软文），下面介绍一些常用的操作技巧，这些技巧通常也适用于visio等其他绘图软件，大家可以自行对应。可以说，这些技巧相当于绘图效率的催化剂，可以让我们实际的绘图工作提升效率，并且完成的图又不失美观和专业。

对于已经掌握这些技巧的读者可以跳过本节

3.1 平均分布

在很多场景下，我们会画一排，或者一串矩形之类的元素，但是由于手动拖拽的随意性，导致这些元素的间距不尽相同，这时我们可以使用图形分布的功能，将这些元素调整为相等间距，这样在元素比较多的情况下，可以保持整幅图的整洁。

操作时，选中对应的元素，然后选择屏幕顶部的工具栏中的“排列”，并选择“图形分布”->“垂直平均分布”

对应有两种分布：

• 水平平均分布，即水平方向上，使多个元素以相等的间距进行排列
• 垂直平均分布，即垂直方向上，使多个元素以相等的间距进行排列

3.2 元素对齐

大多数绘图软件中，在拖动一个元素的时候，会自动地出现一些对齐线，方便用户将元素对齐到特定的位置，但是一旦元素比较多，拖动的操作就有点杯水车薪了，事实上，我们可以使用对齐的功能快速地进行元素对齐，如下图：

我们可以将需要对齐元素选中，然后右键（或者点击屏幕顶部的工具栏中的“排列”），并选择“图形对齐”->“居中对齐”

这些对齐方式，可以从字面意思理解：

• 左对齐，即选中的所有元素，向处于屏幕最左侧的元素对齐
• 居中对齐：即选中的所有元素，根据屏幕最左侧和最右侧的位置计算得到中线，并向该中线对齐
• 右对齐，即选中的所有元素，向处于屏幕最右侧的元素对齐
• 顶端对齐：即选中的所有元素，向处于屏幕最上方的元素对齐
• 垂直居中对齐：即选中的所有元素，根据处于屏幕最上方和最下方的位置计算得到中线，并向该中线对齐
• 底端对齐：即选中的所有元素，向处于屏幕最下方的元素对齐

3.3 大小控制

有时候，我们在框内会标注上一些文字，由于标注的文字长短一步，就出现框本身的宽度不一致，为了保持整齐，通常就会将这些元素宽度（或高度）保持统一，一般操作就是手动地逐个调整方框大小，或者选中之后统一调整高宽的数值，当然也可以使用批量操作的方式

选中对应的元素，然后选择屏幕顶部的工具栏中的“排列”，并选择“匹配大小”->“宽度”

说明：不论是调整高度还是宽度，都是调整为所选元素中高度最大或宽度最大的数值

3.4 Z轴排列

这里所谓“Z轴”的概念，是从CSS中的“z-index”属性借鉴过来的，亦即垂直屏幕向外的方向。

在多个元素进行组合的时候，通常会涉及到前后遮挡的问题，这时候需要用到z轴排列，如下图中的圆环，其中就是由三个圆层叠而成，其中橙色的圆在最底层，红色的圆在中间，白色的圆在最顶层。

默认情况下，元素的z轴值是根据创建的先后顺序决定大小的，越是后创建的元素，其Z轴的数值越大，也就是能遮挡在它之前创建的元素。

绘制该图形时，首先需要选中这3个圆，然后使用“居中对齐”和“垂直居中对齐”，使其成为同心圆，如果此时，橙圆遮挡住了其他两个圆，则点击橙圆，并选择屏幕顶部的工具栏中的“排列”，然后点击“置于底层”，于是橙圆就会被推到最底层，接着可以选中红圆，先同样的操作将它置于底层，然后点击“上移一层”，这样红圆就会叠在橙圆之上，如果此时白圆仍然没有出现在最顶层，可以选中它，点击“置于顶层”，这样就完成了

3.5 分组

分组这个功能在复杂元素组成的图形中，非常实用，它相当于将某几个元素封装成为一个组件，以整体的方式进行拖拽，旋转，连线等操作，并且可以有效地防止意外拖动而打乱布局之类的误操作。

下图是表示负载均衡结构的一个简单拓扑图，图中load balancer 节点和web server的节点，是由3个元素组成：“主机”，“图标”和“圆角矩形”。通常我们会把这个三个元素进行组合，然后再连接线等其他操作，这样一旦这个拓扑图趋于复杂，而又需要做调整的时候，就可以方便地选中相关的节点，不至于元素漏选或错选而导致整个布局失败。

3.6 框内文字对齐

在很多框图中，为了表示一个集合的概念，通常会在表示父元素的框内标注上集合的名字，下图所示的是spring框架内核容器的组成。一般情况下，父元素内的标注文字会使用“顶端对齐”的方式，而子元素则是居中，这也是框内文字默认的对齐方式。

操作时，先选中元素，然后打开屏幕上方工具栏中的“对齐”菜单，就可以选择相应的对齐方式。

3.7 快捷键

点击屏幕顶部的工具栏中的“帮助”，我们可以查看Processon目前支持的快捷键
其中，除了Ctrl+C，Ctrl+V，Ctrl+A等常用的快捷键，我们会经常使用Ctrl+D，该快捷键相当于按了一次Ctrl+C，再按一次Ctrl+V，也就是复制和粘贴一键完成，在复制多个元素的时候非常实用，效率提升一倍。
另外组合功能Ctrl+G，插入文本T，插入连线L，置于顶层Ctrl+]，置于底层Ctrl+[，按住Ctrl约束比例调整大小也是使用率极高的快捷键。
我们在实践过程，一定要多使用快捷键来提升操作效率，不要在对齐排列，调整大小，拖拽布局等操作上浪费过多的时间。

3.8 综合案例

下面介绍一个综合案例，我们将运用上述技巧，绘制Linux中的awk数据处理模型示意图，如下图所示。了解awk命令的人都知道，awk是以行为单位处理数据的，并且可以按照指定的分隔符，将数据切割成多列，其中RS为行分隔符，FS为列，$+数字表示取列。

• 绘制表示行的横向矩形
  首先创建5个矩形，使用复用快捷键Ctrl+D，然后全选完成对齐操作，接着将最下方的矩形，拖动到合适的位置，最后使用“垂直平均分布”功能，完成。
  
• 绘制表示列的垂直矩形
  
• 将行置于列之上，使用“置于底层”的功能，这里最好将列的各个矩形进行分组。这样，如果觉得布局不是特别合适，就可以比较方便地重新进行水平分布。

• 最后完成：
  • 标注文字说明，尽量使用Ctrl+D进行元素的复用
  • 调整行矩形的透明度
  • 列矩形中的文字使用“顶端对齐”即可

另外，我们在生成相同元素的时候，尽量先手动地配置大小，并且这个大小是你记得住的，然后使用Ctrl+D进行复用，那么当某一个元素被误拖拽而导致大小发生了变化之后，就可以迅速地调整回来，另外，如果在后期还想添加一个相同元素，那么也可以直接配置对应的大小。简言之，配置元素的大小，使用一个你可以记住的数值，从而提高工作效率。

4.2 字体

先来介绍一些关于字体的背景知识：

• 通常，字体可以分为衬线体和无衬线体，熟悉CSS的同学一定知道设置字体时有san-serif属性，san-serif即无衬线体，词根serif即衬线的意思。所谓的衬线，就是在每个字符的边缘部分有一定的描边修饰。举例来说，中文字体中的“宋体”，英文字体中的“Times New Roma”就是典型的衬线体，而中文字体中的“黑体”，英文字体中的“Arial”就是典型的无衬线体。
  
• 按照字符的宽度，还可以将字体分为等宽字体和非等宽字体，顾名思义，等宽字体也就是每个字符的宽度都相同。在IT领域，一般都倾向于使用等宽字体，例如微软开发的Consolas字体就是典型的等宽字体，它被使用在windows的控制台中，新版本eclipse默认也使用该字体（旧版本默认的是Courier New字体）。从下面的对比中，可以很清楚地看到等宽字体和非等宽字体的差别。
  
  一般来说，由于衬线体具有笔画上的修饰，使得感官上字符之间有一定的连续性，这样对于大段的文字就比较方便横向阅读，这也就是我们的课本，报纸等读物使用宋体进行印刷的原因之一，而无衬线体更符合现代美学从简的观念，也比较适合作为标语来印刷，例如挂着的大红横幅通常就是用黑体来印刷的。

我们在绘图的过程中，并不需要大段的文字，因此建议尽量使用同一种无衬线体，并且除了标题部分等进行特殊大小处理的字体，其他元素的文字都统一字号。在processon提供的字体中，笔者建议统一使用“微软雅黑”字体，字号大小为14px，并且加粗。这样可以使得导出的图片，粘贴在word等文档中时显得比较和谐。

如果我们要在图中引入代码或配置文件等专业性的内容，则尽量使用等宽字体，以保证内容排版的整齐性，这里建议使用Lucida Console，因为它既是等宽字体，又是无衬线字体。

4.3 配色

毕竟笔者不是学设计或美术出身，谈不上专业角度的美学配色方案，这里就引用网络上一篇关于中国街头广告牌设计的文章，以此借鉴对颜色的运用方法

绘图中使用颜色的时候，建议不要过于追求高饱和度和鲜艳的色彩，而是采用低纯度和充分的留白。这一点，processon的调色板也给出非常好的示范。

• 一个方块，除了包含文字和足够留白，就可以应该保持在最小的尺寸，而不应该毫无逻辑地扩大，建议四个方向上的留白大约保持在5px左右；
• 元素之间连线，除了在连续上标注足够的文字，就应该保持的在最短的长度；
• 相邻的元素之间，也应该保持在最小的间隔之内，不应该过大，大约在5px-20px之间；
• 整体比例保持在最小，不应该留有大面积的空白，但也不应过于拥挤，留有适当空间，可以让整体具有呼吸属性，不会让人觉得“密不透风”；

五、实战

因为IT细分领域内有着非常多的专业图表，但笔者知识边界有限，所以下面着重介绍两种通用性比较高的图：基本流程图和系统拓扑图

5.1 基本流程图

有关流程图的概念，最早是在软件工程中接触到的程序流程图，早期，流程图目的就是描述程序的执行过程，一直以来就是软件设计的重要工具，随着使用者增多，流程图的概念也不再限制于软件设计，只要涉及有关流程的任何场景，我们都可以用流程图来表示。

这里所谓的基本流程图，是相对于其他流程图来说的。这里简单介绍一下泳道图，下图所示，泳道图包含了流程中每一个步骤对应的相关单位，其中单位可以是部门，也可以是职位等，泳道图可以很好地表现了一个流程中不同的职能分工，以及协作的逻辑关系，是项目管理者制定项目计划的常用工具。

5.1.1 常用符号

下面整理了基本流程图常用的符号图示，掌握以下10个足够应付99%的流程图，其中最常用也就是第一行的符号：

• 开始和结束用圆弧矩形表示
• 处理过程用矩形表示
• 分支判断用菱形表示
• 元素之间用带箭头的线连接

5.1.2 基本结构

了解了常用符号之后，就可以画出流程图中的三个基本结构，即顺序结构，分支结构和循环结构：

• 顺序结构：也是最简单的结构，即按照事务的顺序依次执行
• 分支结构：流程中会进行条件的判断，根据不同的判断结果采取不同的处理，例如启动服务时，先检查pid文件是否存在，如果不存在，则启动服务，否则报错
• 循环结构：当条件不被满足时，重复执行同一个（或几个）处理，例如常会被用于遍历数组等操作

5.1.3 流程图案例

下面我们以“超市购物”为案例，综合运用一下上述3个基本结构。

如图，其中购物是一个循环结构，如果购物清单上的物品还没有买全，则继续购买物品，否则就可以去收银台结算了，而支付环节就是一个分支结构，如果现金足够的话，就选择用现金支付，否则就使用手机的APP支付。

5.2 系统拓扑图

这里分享的系统拓扑图，主要是指集群架构图，对于其他拓扑图，从绘图的角度来说，本质上是一样的，可以融会贯通。

下面还是以一个案例来分享一些笔者浅薄的经验，如图，这是一个经典的中小规模web集群架构（参考自《跟老男孩学Linux运维：web集群实战》），包括负载均衡，web服务，数据库主从复制，读写分离，网络文件系统，文件备份，批量管理，yum仓库等诸多单元。

5.2.1 方案规划

首先在新建一张空白画纸之前，我们应该对当前这个系统架构有充分了解，不论你是否已经实现了这个架构，都至少有一个方案规划，方案描述了这个系统应该要完成的哪些功能，以及为了完成这些功能，需要提供哪些基础的服务等，另外还应当包含服务器规划表，用来说明为了完成这个系统，至少需要哪些服务器，这些服务器提供哪些服务等信息。

5.2.2 模块分割

在确定方案之后，就可以对系统中的各个模块进行分割，这个过程与软件设计的模块设计比较相似，先确定功能模块，先不管这个功能模块如何实现，只要确定他在系统架构中的位置和作用，以及提供服务的方式，数据的流向等。这些确定之后，整个系统的框架就设计完成了。如图，我们抽象出了几个模块：负载均衡，web服务，数据库，文件存储，以及管理五个模块。这些模块就可以实现一个基本的web服务解决方案了。

• 负载均衡可以由nginx，lvs或者硬件等实现；
• web服务根据开发语言的特性实现不同web容器，如apache+tomcat，nginx+php等；
• 数据库的实现就更多了，传统的关系型数据库和NoSQL数据库产品，甚至还可以实现利用redis，memcached等实现缓存；
• 文件存储，可以通过GlusterFS等各种分布式文件系统实现；
• 管理模块的功能比较多，例如安装，部署，监控等，对应有多种实现方式，这里就一一列举了；

但不管如何实现，以后即便模块内部进行调整，大的框架仍然不变。因此在绘图时，框架的确定尤为重要，也是我们着手绘制架构图的关键一步。

5.2.3 节点设计

接下来，就可以设计模块内部的实现了，我们可以通过各类的图标绘制不同服务的节点。processon提供的图标并没有MS visio中的丰富，但也足够使用了。

笔者的做法是，使用“服务器”图标+“功能”图标+圆角矩形组合成一个节点（如上面3.5小节中看到的那个图）。之所以要用圆角矩形进行包裹，一方面为了方便输入文字标注，更重要的一点是在架构比较复杂，连接线比较多的情况下，矩形的边可以连接更多的线，而如果直接连接服务器的图标，会显得非常杂乱，有时候也会遮挡文字标注。

绘制各个节点时，尽量使用Ctrl+D进行复用。对于“功能”图标，由于默认的图标比较大，在调整大小时可以按住Ctrl键进行拖拽的操作，这样可以保持图标的大小比例，就不会失真了。

5.2.4 连线调整

当我们需要将每个节点连接起来的时候，务必记得对节点进行分组操作，不然一旦置于大框架之内，再想选择这个节点，或者再次添加连线操作就非常麻烦。比较遗憾的是processon的分组功能比较单薄，当我们将一个分组作为一个元素与其他的元素再次分组时，原来的分组就会撤销掉，也就是说分组不具有嵌套的特性，这和MS visio不太一样，所以在分组操作时，最好的方式就是单个节点分组。

分组之后，节点中的三个元素就作为一个整体，此时再与其他节点进行相连，连接时也务必连接到对方的边上，这样在拖动时就可以跟着一起动。针对重要节点连线，需要进行一定的文字标注，说明其意义。

5.2.5 整体调整

这里就需要应用最小化原则进行调整。在设计节点的时候，为了能够包含各个节点，通常会把大框调整到比较大的尺寸，不至于影响节点的拖拽，而当模块内部完成之后，就要将整幅图的比例调整到合适的大小，去掉无意义的空白，使得布局趋于紧凑合理。

然后去掉框架之间的连线，将提供服务的节点和使用服务的节点直接相连，由于管理中的节点与其他节点都需要连接，如果画线就显得比较凌乱，并且连线的意义不大，故而省去。

最后再加上一些修饰，以及外部的调用情况，就完成了整个系统架构图。

六、总结

本文主要分享了以下几点

• 介绍了绘图作为IT从业人员软实力的重要性，以及绘图在日常工作中的重要作用
• 绘图工具processon中各个功能特性和使用技巧，主要有分布，对齐，z轴排列，快捷键等
• 提出了一些绘图的规范建议，包括大小，字体，颜色，最小化原则，均是体现在细节上，不过，这些细节最终会影响到整体的质感
• 流程图和系统拓扑图的绘制要领和经验。
• 绘图是抽象思维能力的培养方式之一
• 流程图的常用符号，基本结构，以及实战运用
• 以web集群架构为案例介绍了绘制系统拓扑图的步骤
• 一点微薄的经验分享，希望可以帮助到那些不习惯画图，或者想画好图却在画图各种操作上耗费过多精力的小伙伴们。

七、参考资料

• Jesse James Garrett. 用户体验的要素:以用户为中心的Web设计. 机械工业出版社, 2007.
• 麦克韦德. 超越平凡的平面设计 版式设计原理与应用. 人民邮电出版社, 2010.
• 大象公社. 中国的招牌为什么这么丑. http://weibo.com/ttarticle/p/show?id=2309403993629365534797, 2016.
• 张海藩. 软件工程导论[M]. 清华大学出版社, 2003.
• 老男孩. 跟老男孩学Linux运维:Web集群实战. 机械工业出版社, 2016.

零、铺垫

在介绍B树之前，先来看另一棵神奇的树——二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若右子树不空，则右字数上所有节点的值均大于它的根节点的值
• 它的左、右子树也分别为二叉排序数（递归定义）
  

从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree），所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）

一、B树的起源

B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……

二、B树长啥样

还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。

总的来说，m阶B树满足以下条件：

• 每个节点至多可以拥有m棵子树
• 根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)。
• 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)
• 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针
• 从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空
  B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。

例如查询图中字母表中的K

1. 从根节点P开始，K的位置在P之前，进入左侧指针
2. 左子树中，依次比较C、F、J、M，发现K在J和M之间
3. 沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值

三、Plus版——B+树

作为B树的加强版，B+树与B树的差异在于

• 有n棵子树的节点含有n个关键字（也有认为是n-1个关键字）
• 所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接
• 非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字
  

四、MySQL是如何使用B树的

说明：事实上，在MySQL数据库中，诸多存储引擎使用的是B+树，即便其名字看上去是BTREE。

4.1 innodb的索引机制

先以innodb存储引擎为例，说明innodb引擎是如何利用B+树建立索引的

首先创建一张表：zodiac，并插入一些数据

CREATE TABLE `zodiac` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` char(4) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `index_name` (`name`)
); 

insert zodiac(id,name) values(1,'鼠');
insert zodiac(id,name) values(2,'牛');
insert zodiac(id,name) values(3,'虎');
insert zodiac(id,name) values(4,'兔');
insert zodiac(id,name) values(5,'龙');
insert zodiac(id,name) values(6,'蛇');
insert zodiac(id,name) values(7,'马');
insert zodiac(id,name) values(8,'羊');
insert zodiac(id,name) values(9,'猴');
insert zodiac(id,name) values(10,'鸡');
insert zodiac(id,name) values(11,'狗');
insert zodiac(id,name) values(12,'猪');

对于innodb来说，只有一个数据文件，这个数据文件本身就是用B+树形式组织，B+树每个节点的关键字就是表的主键，因此innode的数据文件本身就是主索引文件，如下图所示，主索引中的叶子页（leaf page）包含了数据记录，但非叶子节点只包含了主键，术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起，因此这种索引被称为聚簇索引，或聚集索引。这种索引方式，可以提高数据访问的速度，因为索引和数据是保存在同一棵B树之中，从聚簇索引中获取数据通常比在非聚簇索引中要来得快。

所以可以说，innodb的数据文件是依靠主键组织起来的，这也就是为什么innodb引擎下创建的表，必须指定主键的原因，如果没有显式指定主键，innodb引擎仍然会对该表隐式地定义一个主键作为聚簇索引。

同样innodb的辅助索引，如下图所示，假设这些字符是按照生肖的顺序排列的（其实我也不知道具体怎么实现，不要在意这些细节，就是举个例子），其叶子节点中也包含了记录的主键，因此innodb引擎在查询辅助索引的时候会查询两次，首先通过辅助索引得到主键值，然后再查询主索引，略微有点啰嗦。。。

4.2 MyISAM的索引机制

MyISAM引擎同样也使用B+树组织索引，如下图所示，假设我们的数据不是按照之前的顺序插入的，而是按照图中的是顺序插入表，可以看到MyISAM引擎下，B+树叶子节点中包含的是数据记录的地址（可以简单理解为“行号”），而MyISAM的辅助索引在结构上和主索引没有本质的区别，同样其叶子节点也包含了数据记录的地址，稍微不同的是辅助索引的关键字是允许重复

五、简单对比

1. Innodb辅助索引的叶子节点存储的不是地址，而是主键值，这样的策略减少了当出现行移动或者数据页分裂时辅助索引的维护工作，虽然使用主键值当作指针会让辅助索引占用更多空间，但好处是，Innodb在移动行时无需更新辅助索引中的主键值，而MyISAM需要调整其叶子节点中的地址
2. innodb引擎下，数据记录是保存在B+树的叶子节点（大小相当于磁盘上的页）上，当插入新的数据时，如果主键的值是有序的，它会把每一条记录都存储在上一条记录的后面，但是如果主键使用的是无序的数值，例如UUID，这样在插入数据时Innodb无法简单地把新的数据插入到最后，而是需要为这条数据寻找合适的位置，这就额外增加了工作，这就是innodb引擎写入性能要略差于MyISAM的原因之一

Innodb和MyISAM索引的抽象图

六、参考文献

Bayer, R.; McCreight, E. (1972), “Organization and Maintenance of Large Ordered Indexes” (PDF), Acta Informatica, 1 (3): 173–189
http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf

严蔚敏, 吴伟民. 数据结构: C 语言版[M]. 清华大学出版社有限公司, 2002.
http://cs.ecust.edu.cn/snwei/studypc/jsjdl/data/sjjgc.pdf

Schwartz B, Zaitsev P, Tkachenko V. High performance MySQL: Optimization, backups, and replication[M]. ” O’Reilly Media, Inc.”, 2012.

一、mysqldump –master-data参数介绍

MySQL主从复制原理图

按照mysql最经典的部署主从复制的方式，必须要经过锁表，再导出全备数据，最后再解锁的步骤，这样的操作略显繁琐

事实上mysqldump命令中提供了一个比较方便的参数，即–master-data
下面内容来自官方手册：

It causes the dump output to include a CHANGE MASTER TO statement that indicates the binary log coordinates (file name and position) of the dumped server. These are the master server coordinates from which the slave should start replicating after you load the dump file into the slave.

也就是说，这个参数会当前binlog文件名和位置一并输出到文件，这就方便我们在从库上恢复数据时，不用再人工核对binlog坐标，同时dump数据时还会打开全局的读锁（相当于–lock-all-tables，-x），可以说–master-data参数就是为了部署从库而设计的

二、操作过程

1. 确认主库开启binlog功能，并保证server-id各不相同

2. mysqldump命令对主库的数据进行全备

# mysqldump -uroot -p -A -B --events --master-data=1|gzip >/server/backup/mysql_bak_master_data_$(date +%F).sql.gz

3.将备份文件迁移到从库服务器

4.从库执行change master to…命令

mysql> change master to
> master_host='172.16.1.52',
> master_port=3306,
> master_user='rep',
> master_password='password';

说明：change master 命令需要在下面的恢复数据步骤之前执行，否则由master-data=1产生的change master语句写入master.info的内容会被手动执行change master后修改，亦即，先恢复数据时，master.info命令写入binlog的坐标，接着再手动执行change master to配置主库地址，账号等信息时，就会把master.info的内容覆盖掉，从而丢失了binlog坐标信息

5.从库上恢复数据

# cd /server/backup
# gzip -d mysql_bak_master_data_2016-08-04.sql.gz
# mysql -uroot -p </server/backup/mysql_bak_master_data_2016-08-04.sql
# cat /data/3308/data/master.info 
18
mysql-bin.000003
2503
172.16.1.52
rep
password
3306
60
0





0
1800.000

0

6. 从库启动复制

# mysql -uroot -p -e "start slave;"
# mysql -uroot -p -e "show slave status \G;"
*************************** 1. row ***************************
 Slave_IO_State: Waiting for master to send event
 Master_Host: 172.16.1.52
 Master_User: rep
 Master_Port: 3306
 Connect_Retry: 60
 Master_Log_File: mysql-bin.000003
 Read_Master_Log_Pos: 2503
 Relay_Log_File: relay-bin.000002
 Relay_Log_Pos: 253
 Relay_Master_Log_File: mysql-bin.000003
 Slave_IO_Running: Yes
 Slave_SQL_Running: Yes
……
 Seconds_Behind_Master: 0
……

说明：如果start slave启动复制失败，则使用reset slave all命令清空所有的从库连接参数，然后再按照上述步骤执行一次即可

一、场景概述

1. MySQL数据库每日零点自动全备
2. 某天上午10点，小明莫名其妙地drop了一个数据库
3. 我们需要通过全备的数据文件，以及增量的binlog文件进行数据恢复

二、主要思想

1. 利用全备的sql文件中记录的CHANGE MASTER语句，binlog文件及其位置点信息，找出binlog文件增量的部分
2. 用mysqlbinlog命令将上述的binlog文件导出为sql文件，并剔除其中的drop语句
3. 通过全备文件和增量binlog文件的导出sql文件，就可以恢复到完整的数据

三、过程示意图

四、操作过程

1. 模拟数据

CREATE TABLE `student` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` char(20) NOT NULL,
  `age` tinyint(2) NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `index_name` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8 

mysql> insert student values(1,'zhangsan',20); 
mysql> insert student values(2,'lisi',21); 
mysql> insert student values(3,'wangwu',22);

2. 全备命令

# mysqldump -uroot -p -B -F -R -x --master-data=2 test|gzip >/server/backup/test_$(date +%F).sql.gz

参数说明：
-B 指定数据库
-F 刷新日志
-R 备份存储过程等
-x 锁表
--master-data 在备份语句里添加CHANGE MASTER语句以及binlog文件及位置点信息

3. 继续插入数据

mysql> insert student values(6,'xiaoming',20);
 
mysql> insert student values(6,'xiaohong',20); 

此时误操作，删除了test数据库
mysql> drop database test;

此时，全备之后到误操作时刻之间，用户写入的数据在binlog中，需要恢复出来

4. 查看全备之后新增的binlog文件

# cd /server/backup/
# ls
test_2016-08-02.sql.gz
# gzip -d test_2016-08-02.sql.gz 
# grep CHANGE test_2016-08-02.sql 
-- CHANGE MASTER TO MASTER_LOG_FILE='mysql-bin.000003', MASTER_LOG_POS=107;

这是全备时刻的binlog文件位置，即mysql-bin.000003的107行，因此在该文件之前的binlog文件中的数据都已经包含在这个全备的sql文件中了

5. 移动binlog文件，并读取sql，剔除其中的drop语句

# cp /data/3306/mysql-bin.000003 /server/backup/
# mysqlbinlog -d test mysql-bin.000003 >003bin.sql
# 用vim编辑文件，剔除drop语句

在恢复全备数据之前必须将该binlog文件移出，否则恢复过程中，会继续写入语句到binlog，最终导致增量恢复数据部分变得比较混乱

6. 恢复数据

# mysql -uroot -p <test_2016-08-02.sql 
# mysql -uroot -p -e "select * from test.student;"
+----+----------+-----+
| id | name     | age |
+----+----------+-----+
|  1 | zhangsan |  20 |
|  2 | lisi     |  21 |
|  3 | wangwu   |  22 |
+----+----------+-----+
//此时恢复了全备时刻的数据
//然后使用003bin.sql文件恢复全备时刻到删除数据库之间，新增的数据
# mysql -uroot -p test<003bin.sql <-需要指定恢复的数据库
# mysql -uroot -p -e "select * from test.student;"
+----+----------+-----+
| id | name     | age |
+----+----------+-----+
|  1 | zhangsan |  20 |
|  2 | lisi     |  20 |
|  3 | wangwu   |  20 |
|  4 | xiaoming |  20 | 
|  5 | xiaohong |  20 |
+----+----------+-----+
完成

五、小结

• 适合人为SQL语句造成的误操作或者没有主从复制等的热备情况宕机时的修复
• 恢复条件要全备和增量的所有数据
• 恢复时建议对外停止更新，即禁止更新数据库
• 先恢复全量，然后把全备时刻点以后的增量日志，按顺序恢复成SQL文件，然后把文件中有问题的SQL语句删除（也可通过时间和位置点），再恢复到数据库