广告投放engine设计(1)

前文提到， 广告投放engine的低延迟需求， 一般来说，我们都是要求一个广告在100ms内返回结果的，如果时间再长，就会影响到效果。怎么才能做到低延迟呢，这是一个很严肃的问题。 首先我们先谈一下广告投放系统中的engine设计。engine可以理解为一个普适的减小查询延时的基础系统，对广告业务来说，我们只需要先设计一个engine，然后将广告投放业务逻辑包装在engine外，就完成了一个广告投放系统的设计。形如：

管理系统是面向广告主的界面，广告主将他们的广告要求通过管理系统持久化到数据库中，然后通过信息格式转换，换算成便于高效查询的数据格式。广告投放engine加载上这种高校查询的数据格式后，就可以接受广告请求了。

本文聚焦于广告头饭engine的设计。为了高效，engine就不应该做太多复杂的计算，也不应该有太多的磁盘访问（我们知道磁盘访问是很慢的），或者压根就没有磁盘访问，数据全部放到内存中。到底是只放内存还是内存只放热点数据，这就需要看广告业务需求了。 如果业务是面向品牌广告的，只放到内存是更好的选择，因为品牌广告的数据量本身并不多。而且这些广告一般都是4A广告公司操刀的，仅仅是creative的创作可能就要花好几月，所以这种类型的广告数据量不会很多。，如果是面向中小企业，甚至个体户的（比如百度搜索广告这种，卖搜索词的），因为个体户，中小企业数量巨大，产生的数据量也就很多了，单台服务器在内存里面能够存储的数据量完全满足不了这种需求，就必须存储到磁盘了，当然热点数据肯定还是会在内存中有一份cache的。

解决了存储数据的地方的问题，使用哪种数据结构来存储数据呢？我们知道，数据结构的性能优劣势相对于需求来说的，很难找到一种读写都很棒的数据结构。针对广告业务来说，一般来说，特点是读多写少。广告主将广告book完以后，只需要静静的等着开报表就好了，没有必要来来回回时时刻刻的去更改自己的广告。一般我们会使用倒排索引这种搜索引擎技术来解决广告投放问题。一方面，广告的选择就是一种多维度的文档搜索，另一方面，选择出来的广告，需要进行再次排序，排序的依据是广告的价值（ecpm)或者其他能标识广告饥渴程度的指标。简单来说，就是谁出的钱多，谁的广告就先投出来。发现了吗，和百度是不是很像！有钱的吃肉，没钱的汤都没有。

什么是倒排索引，举例来说，一本书都有目录吧，一般是根据章节来组织目录的。倒排索引呢，是按照书的内容里面的关键词来建立索引的，和字典类似。 比如你要查一本小说里面一个叫张三的相关情节，那么索引就形如：

张三 -> 1. page1, line 100; 2. page 2, line 20;......
王五 -> 1. page22, line 44; 2. page 39, line 400;......
......

睁眼，我们搜索的速度就快多了。 只要现在倒排索引字典中找到张三，那么就能很快找到书中出现张三的地方。 至于怎么找到张三吗？ 一种是按照主人公名字进行排序。在计算机技术里面，算hash值是一种更加简单高效的做法。

不对啊， 如果我们查询的维度不仅仅是一个名字呢？这种情况下，怎么弄呢？这个时候就需我们把每一个维度取得的postion list进行聚合了。聚合说来简单，其实也复杂。比如广告请求里面有地理位置维度为北京，年龄维度为在18周岁的目标用户，我们要找到满足这两个维度的所有的广告主订单。可能你会说我可以把数据放到mysql里面，一个简单的sql就解决问题。但是当广告订单数量超过几千万，mysql的性能也许也满足不了我们的需求。这个时候，我们可以采用skip list这种结构来进行快速的合并。skip list细节在此不表。

当然，我们现在建立的只是简单的不能再简单的模型， 实际上我们面对的问题比这个还要复杂很多。我们先构建这个最简单的，然后一步一步优化它。

目前我们使用hash算法来进行匹配postion list的。 一般来说这种做法是十分高效简单的。 但是针对于geo等场景，我们的确是需要进行一些额外的思考。 在geo场景中， geo的范围是可大的小，而且是可以包含的。 比如北京市就包含了朝阳区，东城区，西城区，海淀区等。 如果我们有一个广告订单说要把广告投放到北京市，那么我们就认为不论是朝阳区还是海淀区来的广告请求，都应该符合广告选择的条件。 我们有三种设计方式， 一种就是把投放到北京的订单id加入到朝阳，海淀的这种最细粒度的geo维度上。 另一种我们把广告投放到北京上面去， 然后在ad select的过程中考虑投放到北京这个维度的和最细粒度区域。 最后就是在根据关键字找positing list前， 维护一个trie tree， 这样当进行startWith类型的查找的时候， 把所有符合前缀条件的posting list合并为一个posting list。

我们知道，ads 投放系统肯定不是单机的，肯定是有很多的ads服务器提供线上服务的。我们怎么把我们的数据传输给这么多台机器呢。 一种做法是每台ads服务器都定期扫描数据库数据，根据数据在内存中创建倒排索引，这种方式难免会对数据库数据造成压力，并且每台ads服务器都在进行同样的逻辑操作并不是很高效。这时候，我们就需要有一个组件将数据库内容转换为ads能够使用的倒排索引。这就涉及到倒排索引的传输和存储。 我们需要定义一个进行倒排索引文件的生成的文件格式。这个文件生成以后只是可读的，所以不需要再文件中预留空洞来保证新增的写。 因此我们采取紧凑型的文件格式。这个文件怎么定义呢？

目前版本的我暂且定义为这样：