从事图像搜索一年的技术总结

原创
2013/12/30 13:58
阅读数 1.6K

<p>又到年底了,马上要进入2014年了,写这篇博客对今年做个技术总结。我是从2013年年初跳槽到这家从事图像搜索的公司,也进入了一个陌生的图像搜索领域。我对图像搜索的认识非常浅薄,但我会从工作中遇到的难题和解决思路来总结一下这一年我对图像搜索的认识和收获。我本身是不懂图片算法,所以主要是从工程的角度来看待图像搜索(为了不泄露公司的技术和架构,我尽量不谈技术细节,或者会很粗略地谈一下)。</p> <p>公司提供的图像搜索服务主要是有两类:一类是同款比价、另一类是以图搜图。那么为了支持着两类服务,需要三类数据:图像特征和标签、图像相似信息和图像特征分类信息。图像搜索引擎就是先通过离线计算,从商品图片中计算出这三种类型的数据,然后构建倒排索引文件和正排数据,推送给线上索引节点,提供图像搜索服务。那么我主要从离线计算和线上索引服务两个角度来进行总结。</p> <p>个人认为图像搜索相对于文本搜索从工程的角度有两点区别:</p> <p>1、图像搜索的数据离线计算是cpu和内存密集。</p> <p>2、图像搜索的倒排索引存储的是图像特征的二进制数据。</p> <p>基于以上两点,在文本搜索通用的开源框架和技术在图像搜索中难以使用(或者说只能用其中一部分),如lucene、hadoop、storm等等。所以在过去的一年里,我们根据图像搜索的一些特点,进行痛苦地、工程量浩大的重复自造轮子,由于各方面的原因,最终也没有取得一个好的效果。</p> <h2>离线计算</h2> <p>相比于线上索引服务,图片数据的离线计算更加复杂。就目前而言,离线计算需要完成需要三种类型的图像数据的计算:特征和标签、图像相似信息和图像分类信息。每一种类型的图像数据所用到的技术和所属的计算框架都不尽相同。</p> <p>我把计算这些数据所用到的技术和框架列在下面这个表里,<font color="#800000"><b>“流式的迭代计算”是</b><b>本人杜撰出来的</b><b>,因为这个东西跟preger</b><b>之类的图计算可能有点不一样,当然也可以用图计算来实现,大牛们看了不要笑话,我实在是找不到合适的词语,因为这类计算本身是一个迭代的过程,但需要支持增量(数据源是从mq</b><b>中过来,是流式的数据),spark</b><b>是不适用于这种场景。</b></font></p> <p><a href="http://static.oschina.net/uploads/img/201312/30135848_HkNG.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135849_nCuZ.png" width="651" height="112" /></a> </p> <p>从功能上来说,离线计算需要支持业务和算法的需求,比如增加一个新的图片特征,更新算法库,或者要重算某一个类目的数据之类的需求,不同的需求所需要的数据和流程都是不同的,那么我们需要将各种类型的数据都持久化存储,那么每一种类型的数据都要考虑全量和增量计算,另外图像相似和分类数据都是要求全量和增量数据之间不能重叠。如果再考虑到系统的扩展性、稳定性和容错等等,就需要将整个离线计算做成一个较为自动化的分布式系统,那么这将是一个复杂的工作。</p> <h3>我们目前实现全量和增量的思路</h3> <p>在实现图搜引擎的离线数据计算的全量和增量时,采用的思路如下:</p> <p>我们通过一个单调递增的时间戳来实现了一个时间轴,将数据按时间戳的大小顺序在数据库中进行排列,如下图所示,可以通过时间轴来区分全量和增量的数据,保证增量和全量数据不重叠。</p> <p><a href="http://static.oschina.net/uploads/img/201312/30135849_pW9A.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135849_AjTK.png" width="322" height="286" /></a> </p> <p>在这种思路下,离线计算的整体如下图所示,因为相似信息和分类信息的计算都要求增量和全量的数据不发生重叠,所以在存储各种类型的数据时,都需要建立这么一种时间轴的机制,来支持全量和增量计算的需求。</p> <p><a href="http://static.oschina.net/uploads/img/201312/30135849_uXHG.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135849_mE8w.png" width="409" height="215" /></a> </p> <h3>离线计算的现状、难题和我们的尝试</h3> <p>当前公司的数据(几亿图片数据)、离线处理集群规模和线上索引服务节点规模都比较小,所以目前离线计算的各个子系统遍布纯手工操作和单点,勉强可以支持公司的业务。</p> <p>我们尝试去实现一个分布式系统来代替当前系统,我们的尝试和难题如下:</p> <p>1、<b>实现用于计算不同数据类型的分布式计算框架。</b>由于图片计算是CPU和内存密集的,没有现成的满足我们业务需求的开源框架(hadoop处理图片数据比较无力,spark也不满足我们的应用场景),我们的尝试如下:</p> <p>A. 自行开发了一个简单的批处理系统(c++开发的),用于图像特征标签的全量数据,并应用在一个APP(一个小的图像搜索服务)的离线数据计算中。</p> <p>B. 模仿storm的思路,开发了一个简单的流式计算框架(c++开发),完成开发但没有应用在具体的场景中。</p> <p>C. 重构了同款引擎(用于计算图像相似信息),提升了数倍的性能,已经上线使用。</p> <p>2、<b>将各个子系统的计算框架放到同一个集群中统一运维、管理和监控,并实现统一调度,提升整个集群的资源利用率。</b>我们尝试了用mesos来干这个事情,为什么要选择mesos,主要是考虑到mesos的框架较为简单并支持资源隔离(cgroup),而且是使用C++语言开发的(我们的各个子系统都是C++开发的)。个人认为像hadoop yarn虽然也支持用cgroup实现资源隔离,java应用程序的进程与操作系统和cgroup之间还隔了一层虚拟机,效果要大打折扣。限于人手、资源和时间,我们只是将图像的全量计算接入到mesos中进行尝试。</p> <p>3、<b>将数据、各个计算框架和流程进行统一和自动化,形成一个完整的分布式系统。</b>由于各中类型数据的计算都有自己的约束条件,比如相似信息计算必须保证增量数据和全量数据是不能重叠;图像分类信息的计算就需要一个全局表用于数据过滤等等。为了支持业务和算法需求,需要存储各种类型的数据,并同时考虑全量和增量等等。我们尝试分析和设计了这么一套分布式系统,由于人手、时间等等各方面的原因没有去具体实践。</p> <p>4、在当前的思路下,缺乏一个单调递增、可靠、分布式的时钟服务或者计数服务,导致了我们目前的系统充满了单点和人工介入。并且我们在存储数据时,实现时间轴的方式比较笨拙,在计算全量数据和增量数据时对数据库进行随机读写操作,数据库存在读写瓶颈。</p> <h2>线上索引服务</h2> <p>在搜索引擎中,索引可以按行或者按列进行切分。</p> <p><b>按行切分:</b>当倒排链的数目太大,无法放在一台机器上,索引采用行切分,将倒排链存储在不同的节点上。</p> <p><b>按列切分:</b>将一个倒排链切分成多个分片,一次检索需要所有索引分片的节点参与,然后归并所有索引节点的查询结果,可以提升性能。</p> <p>在图像搜索中,由于对图像特征进行分类算法的原因,倒排表中的倒排链数目是有限的,而且图片特征的匹配算法非常消耗CPU,所以尽量采用按照列的方向进行切分,将每一次查询的性能开销分布到尽量多的机器上。</p> <h5>当前的架构和缺陷:</h5> <h3>当前的架构</h3> <p>1、<b>线上索引采用推的模式</b>(推模式是个人杜撰喊的不一定专业,是指离线完成倒排索引的构建,然后通过网络将倒排索引文件推送到线上索引节点;相对应的,拉模式是指离线完成倒排索引构建后,存储在分布式文件系统中,线上索引节点主动地从文件系统中拉取倒排文件)。</p> <p>2、<b>索引分片按列的方向进行切分。</b></p> <p>3、<b>全量和增量分开(读写分离)</b>,一组倒排索引的增量单独由单独的一台机器来负责。如下图所示。</p> <p><a href="http://static.oschina.net/uploads/img/201312/30135849_3VG6.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135850_7QVj.png" width="451" height="101" /></a> </p> <p>4、<b>采用开源的kv</b><b>存储引擎和SSD</b><b>硬盘来实现倒排索引文件的线上存储和高效读写</b>。</p> <h3>当前架构的缺陷</h3> <p>1、线上索引构建采用推的模式,需要更多的人工介入,容错性很差(比如节点挂断后重启,就会永久性地错过了部分增量数据,除非是重做)。</p> <p>2、缺乏对索引分片的管理(目前是采用配置文件的方式进行分片和定向地往某些索引节点上推送),索引节点的负载均衡只是简单的采用轮询的方式,一组索引节点中的一个索引节点挂断就会导致整组索引节点都不能提供服务。</p> <p>3、整个线上的索引服务器存在多个单点,容错性较差。</p> <p>4、采用全量和增量读写分离,由一个单独的节点负责增量更新,但增量节点存在IO瓶颈。索引节点使用开源的KV数据库在SSD硬盘中存储倒排索引,增量节点在进行增量写时,会导致读请求的延时。</p> <h3>新架构</h3> <p><b>我们考虑过解决以上缺陷的新架构(没有实施,停留在理论的层面),新架构如下所示:</b></p> <p>1、增加一个管理索引分片的中心管理节点,建立一个全局的增量和全量的索引分片视图和全局的索引节点视图,由这个管理节点来进行自动化配置索引分片、容错和负载均衡。</p> <p>2、索引构建采用拉的方式。将离线构建好的全量和增量的倒排文件存储在HDFS上,然后通知管理节点,由管理节点指定具体的的索引节点来拉取属于自己的全量和增量分片更新。</p> <p>3、合并部分存在单点问题的服务器节点的功能。合并之后,只剩merge节点和match节点,merge节点负责接收图片和计算图像特征,然后根据中心管理节点的全局索引分片和索引节点视图来选择索引节点处理查询,最后合并查询的结构返回给前端。Match节点负责查询倒排索引,并进行图像特征匹配计算,向merge节点返回匹配结果。</p> <p>4、重新设计增量机制来解决增量问题。这个问题在后续我们会详细讨论。</p> <p><a href="http://static.oschina.net/uploads/img/201312/30135850_gkJB.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135850_1GpJ.png" width="402" height="382" /></a> </p> <p>新架构如上图所示,中心管理节点需要维护全量和增量的倒排文件、全量和增量的倒排索引分片、索引存放策略(如几台机器,多少内存多少CPU等等),以及服务器节点的运行状态和现有索引分片的信息。</p> <p><b>新的线上索引服务的增量机制:</b></p> <p>抛弃全量和增量读写分离的方式,将增量均摊分布到各个索引节点上,使用中心管理节点来对每一台索引节点收到的增量数据进行负载均衡。如下图所示:</p> <p><a href="http://static.oschina.net/uploads/img/201312/30135850_qSLc.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135850_HdFD.png" width="398" height="257" /></a> </p> <p>新的索引节点如下图所示,抛弃采用开源kv数据库,采用两组件的LSM-Tree的思想,根据倒排索引文件的特点,开发一个存储引擎。0组件是内存,存放新增的增量更新和读缓存,以及SSD中的倒排文件的索引。1组件是SSD硬盘中,合并后的倒排索引文件。定期地将组建0中的倒排链与组建1中的倒排链进行合并,实行精细化控制,将写操作带来的IO开销进行均摊,将写操作对读操作的性能影响减少到最小。</p> <p><a href="http://static.oschina.net/uploads/img/201312/30135850_AfZF.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201312/30135851_elyq.png" width="372" height="162" /></a> </p> <p>&#160;</p> <p>作者zy,QQ105789990</p>

展开阅读全文
打赏
1
2 收藏
分享
加载中
谈吐鱼博主
mesos的push方式其实对于秒级的应用也很不合适
2014/01/05 20:10
回复
举报
谈吐鱼博主
哈哈,有空私下交流
2014/01/05 20:06
回复
举报
沙发,我来看看哈
YARN实际上是一个资源调度器,就资源调度来说,隔一个虚拟机对新性能影响应该不会很大。对于实施应用,尤其是秒级的应用,YARN有一个的问题是,采用了pull模型,所有资源都需要NM通过心跳从RM上获取,这个 对于低延时任务来说是很不合适的。
LSM-Tree最麻烦的地方就是节点的拆分和合并,我看杨兄描述的内容HBase貌似都比较合适的。
hadoop为什么会对处理图片数据很无力呢?是在哪些地方不合适呢?杨兄可否详细谈谈?
2014/01/05 19:56
回复
举报
更多评论
打赏
3 评论
2 收藏
1
分享
返回顶部
顶部