当我对遇到的问题找一个解决方案的时候，我遇到了BKD树这个难题。从来没有听过吗？这种情况可能不只是你自己。从google上搜索”bkd tree”，通常会把你引导到original research paper和Lucene中用来解决一些空间搜索的patch 网页，然后就没有其他的了。实际上，在写这篇文章的时候，google的第2篇文章推过来的是wikipedia上与这个比较相似名称的 K-D-B Tree。BKD树太冷门了，google都以为你是想找其他的。

BKD树作为一个这么伟大的发明，google这样对待它，这是相当不幸的。

BKD树是用来搜索多维数据的一种树。多维数据可以是物理空间中的一些点，也可以是一个很大调色板上的一些点。BKD树相当善于做其他数的工作。相比和BKD同类型的树，BKD树通常比K-D-B树以及更简单的 R-Trees更快，更节省空间。

本篇文章不是一个对BKD树简单的罗列或者详细描述的wikipedia。我尝试用大白话来讲解BKD树是怎么运作的，有哪些特性。

最近2年，整个开源搜索引擎领域，发展迅速，版本迭代很快。 Lucene最近两年从4.0版本已经发布到最新的7.5.0版本，Solr和Elasticsearch也不断跟进升级。Lucene作为核心包，互联网上或者是书籍上关于它的介绍和分析都比较陈旧了，很多都是基于Lucene3.x来。是时候，从底层来分析下最新的Lucene发展情况了。

本文，依Lucene 7.5.0（当时最新）版本描述。

Lucene索引文件的表现

Lucene索引在硬盘上的表现就是一系列的文件，后缀名不同，下面是一个样例：

通常，看到这些文件，我们就想打开看看，发现根本无法直接查看。这里存的到底是什么，都有什么作用。很多时候是一脸的懵。为了更好的理解这些文件，下面将一步步进行细致的分析。

前言

由于倒排索引的特殊性，在lucene搜索引擎里，一切都是面向字符的，因此数字、日期等类型是如何快速查找、区间匹配、排序的呢？下面将揭开Lucene数字类型处理的神秘面纱。

数值类型特点

排序

以[123，123456，222]这3个数字为例，它们是按字母序排列的，但是先后顺序显然不是我们想要的。我们期待的排序结果是[123，222，123456]。

搜索引擎为什么能查询速度那么快？

核心是在于如何快速的依据查询词快速的查找到所有的相关文档，这也是倒排索引（Inverted Index）的核心思想。那么如何设计一个快速的(常量，或者1)定位词典的数据结构就显得尤其重要。简单来说，我们可以采用HashMap， TRIE， Binary Search Tree， Tenary Search Tree等各种数据结构来实现。

那么开源的搜索引擎包Lucene是怎么来设计的呢？Lucene采用了一种称为FST（Finite State Transducer）的结构来构建词典，这个结构保证了时间和空间复杂度的均衡，是Lucene的核心功能之一。

关于FST（Finite State Transducer）

FST类似一种TRIE树。

使用FSM(Finite State Machines)作为数据结构

FSM(Finite State Machines)有限状态机: 表示有限个状态（State）集合以及这些状态之间转移和动作的数学模型。其中一个状态被标记为开始状态，0个或更多的状态被标记为final状态。
一个FSM同一时间只处于1个状态。FSM很通用，可以用来表示多种处理过程，下面的FSM描述了《小猫咪的一天》。

其中“睡觉”或者“吃饭”代表的是状态,而“提供食物”或者“东西移动”则代表了转移。图中这个FSM是对小猫活动的一个抽象（这里并没有刻意写开始状态或者final状态），小猫咪不能同时的即处于“玩耍”又处于“睡觉”状态，并且从一个状态到下一个状态的转换只有一个输入。“睡觉”状态并不知道是从什么状态转换过来的，可能是“玩耍”，也可能是”猫砂窝”。

如果《小猫咪的一天》这个FSM接收以下的输入:

• 提供食物
• 有大声音
• 安静
• 消化食物

那么我们会明确的知道，小猫咪会这样依次变化状态： 睡觉->吃饭->躲藏->吃饭->猫砂窝.

如何DUMP出堆栈

手动dump

1

jmap -dump:format=b,file=<dumpfile.hprof> <pid>

JVM参数自动dump

1
2

-XX:+HeapDumpOnOutOfMemoryError
-XX:HeapDumpPath=${heap.dump.path}

下载并调整MAT(Eclipse Memory Analyze Tool)

下载地址： https://www.eclipse.org/mat/downloads.php

依据不同的操作系统下载响应版本。

微服务下的API设计原则

目的：
规范团队乃至公司的API设计。
主要参考： Github API

1. 为了安全，请使用HTTPS

与API设计无关、为了安全请使用HTTPS。公网API,强制使用HTTPS。内网API可酌情选择。

2. API 地址和版本

在 url 中指定 API 的版本是个很好地做法。
如果 API 变化比较大，可以把API设计为子域名，比如 https://api.ke.com/v3；
也可以简单地把版本放在路径中，比如 https://ke.com/api/v1。
不建议放入Header，不直观。

3. schema请使用JSON

对于响应返回的格式，JSON 因为它的可读性、紧凑性以及多种语言支持等优点，成为了 HTTP API 最常用的返回格式。因此，最好采用JSON作为返回内容的格式。

不推荐其他格式，如果必须使用，比如 xml，应该在请求头部 Accept 中指定。
对于不支持的格式，服务端需要返回正确的 status code，并给出详细的说明。

前言：

spring-data-redis使得Spring项目可以快速简单的通过RedisTemplate来操作Redis。而spring-boot-starter-data-redis更是让redis集成更加的方便。

SpringBoot如何与Redis集成，作为cache

application.yml里如下配置：

1
2
3
4
5
6
7
8
9
10
11

spring:
  redis:
    host: 127.0.0.1
    	port: 6379
    	database: 0
    	timeout: 1000
    	pool:
      		max-idle: 200
      		min-idle: 0
      		max-active: 200
      		max-wait: 1000

spring boot可以自动组装相关配置，注意其中使用到了jedis pool，用于提升性能，非必须。
通过以下的annotation加入方法名上，可以无侵入的使用cache。

• @Cacheable 缓存
• @CachePut 设置缓存
• @CacheEvict 失效或更新缓存
• @Caching 组合操作

以上annotation不做详细展开。

使用RESTFul接口

RESTFul接口作为一个通行的标准，当然是优先使用的。项目都是基于Spring的，因此采用的是Spring MVC.

解决接口联调的苦难

作为一个技术人员，写文档是一大令人头疼的事情。况且即使把文档写好了，也可能导致在以后的修修补补中，导致不一致的情况。
因此，考虑采用文档自动生成的方式。最终选用了Swagger来自动为Spring MVC生成文档。

• swagger-maven-plugin
• swagger-ui

项目中遇到的一些教训

• 提前制定接口，方便联调
• 提前规划返回接口类型，统一字段名称。

Spring MVC本身对Restful支持非常好。它的@RequestMapping、@RequestParam、@PathVariable、@ResponseBody注解很好的支持了REST。18.2 Creating RESTful services

1. @RequestMapping

Spring uses the @RequestMapping method annotation to define the URI Template for the request. 类似于struts的action-mapping。 可以指定POST或者GET。

2. @PathVariable

The @PathVariable method parameter annotation is used to indicate that a method parameter should be bound to the value of a URI template variable. 用于抽取URL中的信息作为参数。（注意，不包括请求字符串，那是@RequestParam做的事情。）

1
2
3
4

@RequestMapping("/owners/{ownerId}", method=RequestMethod.GET)
public String findOwner(@PathVariable String ownerId, Model model) {
        // ...
}

如果变量名与pathVariable名不一致，那么需要指定：

1
2
3
4

@RequestMapping("/owners/{ownerId}", method=RequestMethod.GET)
public String findOwner(@PathVariable("ownerId") String theOwner, Model model) {
    // implementation omitted
}

Tip

method parameters that are decorated with the @PathVariable annotation can be of any simple type such as int, long, Date… Spring automatically converts to the appropriate type and throws a TypeMismatchException if the type is not correct.

最近常有数据库和网络设备升级和搬迁等事情，而各个应用都是基于数据库连接池做的，大部分都是基于C3P0，数据库或网络状况的变动都会导致客户端连接池中的connection失效，如何剔除这些blocked connection就和C3P0的各个配置息息相关。

C3P0容错和自动重连与以下配置参数有关：

breakAfterAcquireFailure ：true表示pool向数据库请求连接失败后标记整个pool为block并close，就算后端数据库恢复正常也不进行重连，客户端对pool的请求都拒绝掉。false表示不会标记 pool为block，新的请求都会尝试去数据库请求connection。默认为false。因此，如果想让数据库和网络故障恢复之后，pool能继续请求正常资源必须把此项配置设为false