搜索是大数据领域的普遍需求。Splunk和ELK分别是非开源领域和开源领域的佼佼者。本文用很少的Python代码实现了一个基本的数据搜索功能，试图让大家了解大数据搜索的基本原理。布隆过滤器（BloomFilter）第一步是实现布隆过滤器。Bloomfilter是大数据领域常用的一种算法，其目的是过滤掉那些不是目标的元素。换句话说，如果要搜索的词在我的数据中不存在，那么它可以很快返回目标不存在。让我们看看以下布隆过滤器的代码：classBloomfilter(object):"""ABloomfilterisaprobabilisticdata-structurethattradesspaceforaccuracywhendeterminingifavalueisinaset.Itcantellyouifavaluewaspossiblyadded,orifitwasdefinitelynotadded,butitcan'ttellyouforcertainthatitwasadded."""def__init__(self,size):"""SetuptheBFwiththeappropriatesize"""self.values=[False]*sizeself.size=sizedefhash_value(self,value):"""HashthevalueprovidedandscaleittofittheBFsize"""returnhash(value)%self.sizedefadd_value(self,value):"""AddavaluetotheBF"""h=self.hash_value(value)self.values[h]=Truedefmight_contain(self,value):"""检查该值是否在BF中"""h=self.hash_value(value)returnself.values[h]defprint_contents(self):"""Dump出BF的内容以供调试""printself.values的基本数据结构是一个数组（实际上是位图，用1/0记录数据是否存在），初始化没有任何内容，所以都设置为False。在实际使用中，为了保证效率，数组的长度很大。使用哈希算法判断数据应该存在于哪一位，即数组的索引当一个数据被加入布隆过滤器时，计算它的哈希值，然后将对应的位置设置为True当检查一个数据是否已经存在时当它存在或已经被索引时，只要检查对应哈希值所在位的True/Fasle即可。可以看到这里如果布隆过滤器返回False，那么数据一定没有被索引。但是，如果返回True，则不能说数据一定已经被索引了。在搜索过程中使用布隆过滤器，可以让很多不可靠的搜索提前返回，提高效率。让我们看看这段代码是如何工作的：bf=Bloomfilter(10)bf.add_value('dog')bf.add_value('fish')bf.add_value('cat')bf.print_contents()bf.add_value('bird')bf.print_contents()#Note:contentsareunchangedafteraddingbird-itcollidesfortermin['dog','fish','cat','bird','duck','emu']:print'{}:{}{}'.format(术语，bf.hash_value（术语），bf.might_contain（术语））结果：[假，假，假，假，真，真，假，假，假，真][假，假，假，假，真，True,False,False,False,True]dog:5Truefish:4Truecat:9Truebird:9Trueduck:5Truemu:8False先创建一个容量为10的Bloomfilter然后分别添加'dog'和'fish','cat'三个对象，此时bloomfilter的内容如下：然后添加'bird'对象，bloomfilter的内容没有改变，因为'bird'和'fish'刚好有相同的hash。***我们检查一堆对象（“狗”、“鱼”、“猫”、“鸟”、“鸭子”、“鸸鹋”）是否已经被索引。事实证明，“duck”返回True，2而“emu”返回False。因为'duck'的哈希恰好与'dog'相同。分词下一步是实现分词。分词的目的就是把我们的文本数据分割成最小的可以搜索到的单位，也就是词。这里我们主要关注英文，因为中文分词涉及到自然语言处理，比较复杂，而英文基本只需要用到标点符号，并返回找到的所有内容的集合。此实现中的中断是单个字符，但在Splunk中它们可以是多个字符。使用集是因为顺序无关紧要，而重复则不好。"""major_breaks=''last=-1results=set()#enumerate()willgiveus(0,s[0]),(1,s[1]),...foridx,chinenumerate(s):ifchinmajor_breaks:segment=s[last+1:idx]results.add(segment)last=idx#Thelastcharactermaynotbeabreaksoalwayscapture#thelastsegment(whichmayendupbeing"",butyolo)段=s[last+1:]results.add(segment)returnresults主分词主分词使用空格来分词。在实际的分词逻辑中，还会有其他的分隔符。例如，Splunk默认的分隔符包括如下，用户也可以定义自己的分隔符。]<>(){}|！;,'”*\n\r\s\t&?+%21%26%2526%3B%7C%20%2B%3D—%2520%5D%5B%3A%0A%2C%28%29defminor_segments(s):"""对字符串执行次要分段。这类似于主要分段，除了它还从输入到每个中断的开始捕获。""“minor_breaks='_.'last=-1results=set()foridx,chinenumerate(s):ifchinegminor:break[last+1:idx]results.add(segment)segment=s[:idx]results.add(segment)last=idxsegment=s[last+1:]results.add(segment)results.add(s)returnresultsMinorsplitminorsplit的逻辑和mainsplit类似，只是将结果从开始到当前拆分将被添加。例如，“1.2.3.4”的次要拆分将有1,2,3,4,1.2,1.2.3defsegments(event):"""Simplewrapperaroundmajor_segments/minor_segments"""results=set()formajorinmajor_segments(event):forminorinminor_segments(major):results.add(minor)returnresults分词的逻辑是先对文本进行大分词，对于每一个大分词都是在进行一次小分词。然后返回所有拆分的单词。让我们看看这段代码是如何工作的：forterminsegments('src_ip=1.2.3.4'):printtermsrc1.21.2.3.4src_ip311.2.3ip2=4搜索完成了，有了分词和Bloomfilter支持之后，我们就可以实现了搜索功能。上面的代码：classSplunk(object):def__init__(self):self.bf=Bloomfilter(64)self.terms={}#Dictionaryoftermtosetofeventsself.events=[]defadd_event(self,event):"""Addsaneventtothisobject"""#GenerateauniqueIDfortheevent,andsaveitevent_id=len(self.events)self.events.append(event)#Addeachtermtothebloomfilter,andtracktheeventbyeachtermforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term]=set()self.terms[term].add(event_id)defsearch(self,term):"""Searchforasingleterm,andyieldalltheeventstthatcontainit"""#InSplunkthisrunsinO(1),andislikelytobeinfilesystemcache(memory)ifnotself.bf.might_contain(term):return#InSplunkthisprobablyhensofsthatcontainit(logNts)哪里.terms:returnforevent_idinsorted(self.terms[term]):yieldself.events[event_id]Splunk代表一个具有搜索功能的索引集合。每个集合包含一个布隆过滤器，一个倒置词汇表（字典），以及一个存储所有事件的数组当一个事件被添加到索引中时，会为每个事件产生如下逻辑一个unqieid，这里是序号对事件进行切分，将每个词加入到倒排词表中，即每个词对应的事件id的映射结构。注意，一个词可能对应多个事件，所以inverted表的值是一个SetInvertedlist是大多数搜索引擎的核心功能。当搜索到一个词时，Bloomfilter将检查以下逻辑。如果为假，则直接返回检查词汇表。如果查找的词不在词汇表中，则直接返回，在倒排列表中查找所有对应的事件。id，然后返回事件的内容。我们运行一下看看：s=Splunk()s.add_event('src_ip=1.2.3.4')s.add_event('src_ip=5.6.7.8')s.add_event('dst_ip=1.2.3.4')foreventins.search('1.2.3.4'):printeventprint'-'foreventins.search('src_ip'):printeventprint'-'foreventins.search('ip'):printeventsrc_ip=1.2.3.4dst_ip=1.2.3.4-src_ip=1.2.3.4src_ip=5.6.7.8-src_ip=1.2.3.4src_ip=5.6.7.8dst_ip=1.2.3.4是不是很神奇！更复杂的搜索更进一步，在搜索过程中，我们想用And和Or来实现更复杂的搜索逻辑。上代码：classSplunkM(object):def__init__(self):self.bf=Bloomfilter(64)self.terms={}#Dictionaryoftermtosetofeventsself.events=[]defadd_event(self,event):"""Addsaneventtothisobject"""#GenerateauniqueIDfortheevent,andsaveitevent_id=len(self.events)self.events.append(event)#Addeachtermtothebloomfilter,andtracktheeventbyeachtermforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term]=set()self.terms[term].add(event_id)defsearch_all(self,terms):"""SearchforanANDofallterms"""#Startwiththeuniverseofallevents...results=set(range(len(self.events)))forterminterms:#Ifatermisn'tpresentaallthenwecanstoplookingifnotself.bf.might_contain(term):returniftermnotinself.terms:return#Dropeventsthatdon'tmatchfromourresultsresults=results.intersection(self.terms[term])forevent_idinsorted(results):yieldself.events[event_id]defsearch_any(self,terms):"""SearchforanORofallterms"""results=set()forterminterms:#Ifatermisn'tpresent,weskipit,butdon’tstopifnotself.bf.might_contain(term):continueiftermnotinself.terms:continue#Addtheseeventstoourresultsresults=results.union(self.terms[term])forevent_idinsorted(继续results):yieldself.events[event_id]利用Python集合的交集和并集运算，可以轻松支持And（交集）和Or（组合）运算。运行结果如下：s=SplunkM()s.add_event('src_ip=1.2.3.4')s.add_event('src_ip=5.6.7.8')s.add_event('dst_ip=1.2.3.4')foreventins.search_all(['src_ip','5.6']):printeventprint'-'foreventins.search_any(['src_ip','dst_ip']):printeventsrc_ip=5.6.7.8-src_ip=1.2.3.4src_ip=5.6.7.8dst_ip=1.2.3.4
