申艳超-博客

搜索引擎、分布式、高性能、NLP、ElasticSearch、Solr

0%

当我对遇到的问题找一个解决方案的时候,我遇到了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树是怎么运作的,有哪些特性。

Read more »

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

本文,依Lucene 7.5.0(当时最新)版本描述。

Lucene索引文件的表现

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

lucene 索引文件

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

Read more »

前言

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

数值类型特点

排序

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

Read more »

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

核心是在于如何快速的依据查询词快速的查找到所有的相关文档,这也是倒排索引(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 小猫咪的一天

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

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

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

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

Read more »

微服务下的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,并给出详细的说明。

Read more »

前言:

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不做详细展开。

Read more »

使用RESTFul接口

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

解决接口联调的苦难

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

  • swagger-maven-plugin
  • swagger-ui

项目中遇到的一些教训

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

springmvc

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.

Read more »

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

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

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

Read more »