微信号:XJJ267

介绍:虽然名字叫西加加语言,但主要聊聊搜索引擎,推荐系统,广告技术,系统架构和算法都会说,也会说很基础的语言问题,当然,也会随便扯,欢迎订阅

分布式搜索引擎设计

2016-05-19 19:44 吳YH堅


提示:本文较长,看完需要时间,来首歌:)



1.前言



分布式,高可用,和机器学习一样,最近几年被提及得最多的名词,听名字多牛逼,来,我们一步一步来击破前两个名词,今天我们首先来说说分布式。


我个人感受,分布式和高可用是随着最近这些年阿里的双11活动火起来的,放眼全球,好像没有哪个公司的系统会在瞬间承接这么大的流量,并且还是绝对不能出错的交易流量,所以阿里确实积累了全球最丰富的高可用和分布式的经验,再加上各种技术大会一分享,这两个词就变成一个互联网公司技术系统的标配了。


可能很多人并不是很理解分布式和高可用,我们简单来说一下。


  • 分布式的理论在上个世纪就已经比较成熟了,只是一直没有实际可用的环境来验证,直到google的出现,分布式就是单机已经无法处理了,把服务拆分成多个服务,组成一个分布式的服务来完成之前单个服务的功能。

  • 高可用其实是一直在IT行业中存在的,最典型的就是异地灾备系统了,这就是一个标准的高可用系统。


好,前面的概念说完了,进入主题,如何来设计一个分布式系统呢?本篇没有高深的理论,仅会使用几个计算机编程的最基本概念,来一步一步阐述如何设计一个分布式系统,我们还是会以搜索引擎为例,毕竟搜索服务是一个标准的分布式场景。


再次提示,请耐心读完本篇,请耐心


2.代码的底层是什么



不是说分布式么,怎么说到代码底层了,别急,慢慢来。


代码是由数据结构和算法组成的,是用来处理数据的,而数据结构和算法组合起来是什么?是函数,所以,代码就是函数,而且有函数式编程,并且从数学上也证明了纯函数式编程也能完成所有的算法。


代码做的事情就是给一个数据作为函数的输入,然后通过函数,给出一个数据作为输出,在这个过程中可能需要存储一些数据到外部存储器中供以后使用


3.服务是什么



由多个代码片段(函数)组合起来,在加上一个外部的存储数据,就形成了一个服务,如果一个代码片段(函数)可以抽象成y=f(x),那么其实服务我们抽象成这样子y= f(g(h(u(x))),也就是各个代码片段(函数)的组合


所有的服务,最后都可以抽象成下面的样子



右边那个不是代表数据库,是代表外部的存储数据,你可以仔细想一想,是不是你写的所有的服务器端程序,或者所有的程序,都可以抽象成上面这个图的样子?如果不行,不好意思,那是你想象力不够。


好,我们以搜索引擎为例来说一下,上面的y= f(g(h(u(x)))对应出来以后


  • 如果是数据检索过程的话,x就是输入的query,y就是输出的结果集,u函数表示query分析,简单说也就是分词啦,h就是倒排索引检索,g就是结果集求交集并集,f就是排序。

  • 如果是数据更新过程的话,x就是新增的那个文档,y就是更新是否成功,u函数就是分词,h就是更新内存倒排,g就是写磁盘。


所以说,一个服务,必定可以拆分成一个一个子服务,子服务还可以继续拆,拆到最后必定变成一个函数,而如果把一个或者一组函数拆出去单独变成一个服务的话,那这个服务就变成一个分布式的服务了,用时下比较流行的说法就是微服务。


4.为什么要分布式



为什么要分布式,也就是什么情况下需要分布式。


首先我们要搞清楚两个概念,分布式和集群


比如上面说的搜索服务,我们是一个单机版的搜索引擎,性能不错,每次返回数据的时间大约在10ms左右,但是由于请求量非常巨大,QPS单机已经扛不住了,于是我们把这个单机版的变成一个像下图这样的结构,前面用一个nginx做负载均衡,后面挂N多搜索服务,这不叫分布式,这是集群。




只有当我们发现由于排序算法变复杂了,或者数据量增多了,每次返回数据的时间由10ms变成500ms了,这个时候只能把服务给拆成多个服务才能满足业务需求了,这才叫分布式


所以说,一般情况下,集群就已经够用了,需要进行分布式的服务其实并不多,而且集群基本上都是高可用的,风险也小,所以除非迫不得已,没有必要为了分布式而分布式,这叫过度设计,单机其实挺好的,简单易维护,抗造高可用。


5.如何进行分布式设计



好,假如我们的搜索引擎数据量和请求时间都已经达到极限了,必须要进行分布式了,如何来做呢?一般一个服务要进行分布式的设计,会从两个方面进行。


  • 一是服务的功能分布式,对应到代码也就是把一个1000行的函数变成两个500行的函数。

  • 二是数据的分布式,就是数据已经太多了,单节点已经放不下了,或者单节点处理这么多数据能力已经不够了,那也得进行分布式,数据分布式其实大家见得多了,分库分表就是一种数据分布式。


正好,搜索引擎的分布式这两个方面都可以涉及到,检索的时候需要对功能进行分布式,而索引本身需要对数据进行分布式,我们一个一个来说。


6.服务功能的分布式拆分



一个标准的检索过程大致分成以下几个部分:query分析,数据检索,结果集合并,排序。如下图表示的这样




如果我们直接把这个服务分成上面四个单独的服务,完成服务的分布式,行不行呢?可以,但并不好,因为设计一个分布式的服务还是有一些东西需要考虑的,对于分布式的服务,一般需要注意以下三个关键点。


6.1 尽量减少网络开销



一个分布式服务,应该尽量的减少网络通讯上的开销,分布式的初衷是将计算能力分布到多个节点上而提高整体的响应时间,如果在网络通讯上花费了很多的开销,反而会使响应时间增长而违背了设计的初衷。


上面几个模块中,数据检索,结果集合并,排序这几个模块的数据流都是搜索的结果集,一般都非常巨大,这么大量的数据在网络间传来传去,速度能快就出鬼了,所以拆分的话,也是将query分析拆出去变成一个单独的服务,拆出去以后,它满足网络开销少这个条件,他的输入就是用户的query(比如姚明有多高),也就是一个url吧,输出是一个改写好的query(姚明/身高),也就是个url吧,网络传递上开销很小。


6.2 各个子服务应该是无状态的



如果是分布式服务中的一个子服务,它应该尽量设计成无状态的,放到编程语言上来说就是说这个服务应该是一个纯函数的服务,一个输入只会有一个输出,不会因为不同的状态产生不同的输出,这样主要是为了方便调用,调用服务的时候不需要去考虑状态。如果一定需要状态的话(比如用户的会话状态session),对于分布式服务,一般会将状态单独存储在某个位置(比如redis中),需要的时候去取就行了,服务本身并不保存这个状态。


我们的query分析服务完美满足这个条件,他是无状态的,query分析是个纯算法的东西什么输入就有一个什么输出。


6.3 每个子服务都应该是可横向扩展的



虽然上面我们说了集群和分布式的区别,但是分布式的系统一般都得能满足集群的部署,如果每个子服务能满足无状态的话,那么横向扩展就没什么问题了,因为无状态,所以对外来说每台机器都是一样的,调用谁结果都一样,自然就能横向扩展了。


我们再看我们的query分析服务和主搜索服务,两个都是无状态的,都能横向扩展,那么这个搜索引擎通过一系列的功能拆解以后,将会变成这个样子



如果你设计一个分布式系统按照上面三条准则进行模块的拆分的话,那么至少方向上不会有太大的问题,系统耦合性也会比较低,如果每个子系统都能做到以上三点的话,基本上会是一个比较好的分布式系统。


这里再说一下,对于搜索服务来说,我这里只是为了阐述功能的分布式设计,把query分析给拆出去了,如果我们的query分析就是个分词的话,也完全没有必要拆分了,但如果是一个复杂的自然语言处理算法的话,还是可以拆出去的。另外,把排序单独拆开作为一个服务的,确实不多见,或者说我没见过吧,所以搜索引擎的功能拆解,基本上就是这样了,再拆就影响性能了。


现在很多人开口就是各种技术栈,各种开源组件,各种搭配组成一个看似牛逼的分布式系统,请问,对于RestfulAPI+ZooKeeper+HDFS+KafkaMQ+Nginx+Dubbo+Mysql+Docker+...这种架构的分布式系统,不管他是干什么的系统,你见了除了懵逼难道还有第二种表情么?你的系统就那么牛逼,需要把这些技术全都用上???


所以,一个好的分布式系统,同样适用于一个系统架构吧,关键点不在你用了多少新技术,而在于对模块的拆分对不对。


7. 数据的分布式拆分



服务已经进行了拆分,已经算是一个分布式系统了,但是随着搜索引擎的数据越来越多,单机的性能也会达到一个极限,比如五亿条数据,单机基本上比较难抗住了(如果你硬要上一台1T内存,100T硬盘,64CPU的机器,那是你任性),所以这时候的分布式就是需要进行数据层面的分布式设计了。


7.1 搜索引擎索引分片



对服务的分布式拆分还是比较容易的,把服务和数据一锅端到另外的节点就行了,但你要对数据进行分布式拆分,就没那么容易了,这就需要具体场景具体分析了。


先简单介绍一下搜索引擎的数据拆分,对于搜索引擎来说,外部数据比较简单,就是一条一条的文档,数据拆分相对还是比较简单的,一般我们可以选一个字段做hash,将数据hash到各个节点中,也就是经常听到的索引分片了,只要字段选得好,hash函数也选的好,基本上每个节点的数据是比较平均的,那么这么一拆解下来,这个搜索引擎就变成下图这个样子了,红框中每一个节点都有一部分的索引内容,把每部分的内容合并起来就是整个结果集了。




上面的拆分有个致命的弱点,满足不了们上面说的个子服务都应该是可横向扩展的,因为在我们加分片机器的时候,我们无法保证相同分片机器的数据一致性,就像下图,如何保证A1和A2,A3数据的一致性。



这就是数据的拆分和服务的拆分的本质区别,要考虑的地方也不一样,服务说白了就是一堆函数,不会变化,拆到哪里都是一样的,横向扩展完全没问题,而数据是会变的,如何拆分数据不是数据分布式的重点,数据拆分需要解决的最重要的问题就是:如何保证各个相同节点的数据强一致性。这也是所有的分布式系统需要的最重要的问题,才会为了这个出现那么多一致性的理论。


7.2 Log



看上去很简单吧,索引分片技术直观有效,数据库的分库分表这种拆分也很简单有效,但并不是每个服务的数据拆分都可以这么简单的,所以如何分片不是我要说的重点,如果不是那么能直观分片的数据如何进行分布式的拆分?


我们先不说那么多一致性理论,比如Paxos这种高大上的算法。我们从最最基础的说起。


如果你看到这了还没有关闭这篇文章,那么我告诉你,前面所有的都是开胃菜,我们终于见到了这篇文章的主角了,那就是Log


我们再回到这张图




右边的外部数据有两种情况

  1. 完全是静态数据,从始至终不会变化,那么这种情况随便怎么拆都好说

  2. 完全是动态数据,会经常变化,那么这种情况就要请主角出场了


7.2.1 Log是什么



我们说的Log不是我们服务的日志,日志是用来记录服务的一些信息的,主要用来进行错误排查的,是给人看的,而我们这里说的Log是给机器看的。


Log是什么,一条Log是一个带时间戳的消息,这里的消息可以任何东西,比如数据变化啊,某个事件啊,甚至是某个函数操作,任何东西都可以是Log的消息。大家熟悉的数据库的binlog,就是一种Log形式,记录的是数据的变化。


下图就是一个标准的Log,首先他带有时间戳(或者表示时间序列的ID),然后是Log的消息本身,所有Log是按时间一条一条排序好的,结构非常简单,虽然Log简单,但是Log记录了整个系统最关键的东西,那就是这个系统在某个时刻干了什么




7.2.2 Log有什么用



Log最重要的功能就是重放。A节点进行了一系列的操作,产生了5条Log,输出了一个结果R,那么将这5条Log输入到B节点,B节点最后也将输出结果R,这就是重放。


因为我们的显示世界是个时域系统,任何状态都是由一个事件和一个时间产生出来的,而Log这种简单的数据结构恰好完美的记录了时间和事件,那么任何状态都可以用Log还原出来。


7.2.3 Log怎么用



Log虽然简单而又异常强大,但很多时候我们只需要使用很少的功能就能完成很重要的事情,比如我们的搜索引擎,Log只需要记录一个序号,一个操作类型,一条消息就行了,像下面的结构


1 .  更新数据  .  id=MMM,name=XXX,content=XXX

2 .  更新数据  .  id=NNN,name=YYY,content=ZZZ

3 .  新建字段  .  fieldname=title,fieldtype=string

4 .  删除数据  .  id=MMM


这样,同样功能的节点通过Log就可以保证数据的一致性,不止搜索引擎,MySql数据库,Redis等的主从同步也是这么做的,一条简单的Log就达到了数据一致性的要求。


7.2.4 再把Log展开一点



Log既然这么牛逼,为什么说来说去还只是个数据复制呢?有别的高大上点的应用么?


首先,Log记录了系统在整个时间周期中每次的状态变更,他是可重放的。

  • 因为Log有上述特性,数据复制过程中即便从节点挂了,重启以后根据上次的Log的编号也能重放并同步数据


其次,我们可以把任何结构化的数据(比如数据库表,搜索索引,KV数据库)异构成Log这种标准的数据存储格式,并且最重要的是可以通过Log这种结构再次重建任何结构化数据。

  • 因为Log有上述特性,所以Log可以用来作为系统解耦的中间结构,现在那么多消息队列,哪个系统没有用消息队列,你以为是啥?就是Log啊,Kafka就是个高级的Log服务


7.3 回到索引分片



好了,扯了一段Log,我们回到索引分片来,有了Log以后,我们想怎么加机器就能怎么加机器了,反正通过Log可以保证各个相同节点的数据一致性,上面那个带问号的图通过Log就解决了。




8.节点间通讯



最后说一说节点间的通讯,这不是本篇重点,捎带说一下,后一篇会说这个,一般很多分布式系统使用RPC这种远程调用再加上一种序列化算法来节省带宽来进行节点间通讯,简单的话,用http也行,这里就不展开了。



9.部署



最后,我们画个分布式的最终图,搜索服务拆分成分布式了以后就是这样子了。



注意啊,这是个可用的分布式搜索引擎,只有我们第二篇出来了以后才能变成一个高可用的分布式搜索引擎:)


10.总结



好了,说了这么多了,已经没体力总结了,不知道你看完没有,这只是第一部分,分布式的部分,后面还有一篇高可用的,还没写呢,欢迎继续阅读,如果你觉得还不错,欢迎转发和赞赏:)






欢迎关注我的公众号,主要聊聊搜索,推荐,广告技术,还有瞎扯。。文章会在这里首先发出来:)扫描或者搜索微信号XJJ267或者搜索中文西加加语言就行


 
西加加语言 更多文章 用Golang写一个搜索引擎(0x02) 用Golang写一个搜索引擎(0x03) 用Golang写一个搜索引擎 (0x04) 用Golang写一个搜索引擎(0x05) 用Golang写一个搜索引擎(0x06)
猜您喜欢 [ISUX转译]拥抱手势驱动的界面设计 Windows Azure 开发训练营5月22日成都站相关资料 制定混合云规划必须考虑的四步骤 Hello, World of Programming Languages 无线开发,如何兼顾页面的体验与灵活性?