然后分别加入 ‘dog’，‘fish’，‘cat’三个对象，这时的布隆过滤器的内容如下：
然后加入‘bird’对象，布隆过滤器的内容并没有改变，因为‘bird’和‘fish’恰好拥有相同的哈希。
最后我们检查一堆对象（’dog’, ‘fish’, ‘cat’, ‘bird’, ‘duck’, ’emu’）是不是已经被索引了。结果发现‘duck’返回True，2而‘emu’返回False。因为‘duck’的哈希恰好和‘dog’是一样的。
主要分割
主要分割使用空格来分词，实际的分词逻辑中，还会有其它的分隔符。例如Splunk的缺省分割符包括以下这些，用户也可以定义自己的分割符。
] < >( ) { } | ! ; , ‘ ” * s & ? + %21 %26 %2526 %3B %7C %20 %2B %3D — %2520 %5D %5B %3A %0A %2C %28 %29
def minor_segments(s):"""Perform minor segmentingonastring. Thisislike major segmenting, except it also captures from the start of theinputtoeachbreak."""minor_breaks ='_.'last= -1results =set()foridx, ch in enumerate(s):ifch in minor_breaks:segment = s[last+1:idx]results.add(segment)segment = s[:idx]results.add(segment)last= idxsegment = s[last+1:]results.add(segment)results.add(s)returnresults
次要分割
次要分割和主要分割的逻辑类似，只是还会把从开始部分到当前分割的结果加入。例如“1.2.3.4”的次要分割会有1，2，3，4，1.2，1.2.3
defsegments(event):"""Simple wrapper around major_segments / minor_segments"""results = set()formajorinmajor_segments(event):forminorinminor_segments(major):results.add(minor)returnresults
分词的逻辑就是对文本先进行主要分割，对每一个主要分割在进行次要分割。然后把所有分出来的词返回。
我们看看这段 code是如何运行的：
for term in segments('src_ip =1.2.3.4'):print termsrc1.21.2.3.4src_ip311.2.3ip2=4
搜索
好了，有个分词和布隆过滤器这两个利器的支撑后，我们就可以来实现搜索的功能了。
上代码：
classSplunk(object):def__init__(self):self.bf = Bloomfilter(64)self.terms = {}# Dictionary of term to set of eventsself.events = []defadd_event(self, event):"""Adds an event to this object"""# Generate a unique ID for the event, and save itevent_id = len(self.events)self.events.append(event)# Add each term to the bloomfilter, and track the event by each termforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term] = set()self.terms[term].add(event_id)defsearch(self, term):"""Search for a single term, and yield all the events that contain it"""# In Splunk this runs in O(1), and is likely to be in filesystem cache (memory)ifnotself.bf.might_contain(term):return# In Splunk this probably runs in O(log N) where N is the number of terms in the tsidxiftermnotinself.terms:returnforevent_idinsorted(self.terms[term]):yieldself.events[event_id]
Splunk代表一个拥有搜索功能的索引集合每一个集合中包含一个布隆过滤器，一个倒排词表（字典），和一个存储所有事件的数组当一个事件被加入到索引的时候，会做以下的逻辑为每一个事件生成一个unqie id，这里就是序号对事件进行分词，把每一个词加入到倒排词表，也就是每一个词对应的事件的id的映射结构，注意，一个词可能对应多个事件，所以倒排表的的值是一个Set。倒排表是绝大部分搜索引擎的核心功能。当一个词被搜索的时候，会做以下的逻辑检查布隆过滤器，如果为假，直接返回检查词表，如果被搜索单词不在词表中，直接返回在倒排表中找到所有对应的事件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 = {}# Dictionary of term to set of eventsself.events = []defadd_event(self, event):"""Adds an event to this object"""# Generate a unique ID for the event, and save itevent_id = len(self.events)self.events.append(event)# Add each term to the bloomfilter, and track the event by each termforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term] = set()self.terms[term].add(event_id)defsearch_all(self, terms):"""Search for an AND of all terms"""# Start with the universe of all events...results = set(range(len(self.events)))forterminterms:# If a term isn't present at all then we can stop lookingifnotself.bf.might_contain(term):returniftermnotinself.terms:return# Drop events that don't match from our resultsresults = results.intersection(self.terms[term])forevent_idinsorted(results):yieldself.events[event_id]defsearch_any(self, terms):"""Search for an OR of all terms"""results = set()forterminterms:# If a term isn't present, we skip it, but don't stopifnotself.bf.might_contain(term):continueiftermnotinself.terms:continue# Add these events to our resultsresults = results.union(self.terms[term])forevent_idinsorted(results):yieldself.events[event_id]
利用Python集合的intersection和union操作，可以很方便的支持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
总结
以上的代码只是为了说明大数据搜索的基本原理，包括布隆过滤器，分词和倒排表。如果大家真的想要利用这代码来实现真正的搜索功能，还差的太远。所有的内容来自于Splunk Conf2017。大家如果有兴趣可以去看网上的视频。
进群：125240963 即可获取源码！
网友评论