网站建设7个主要流程图,有好看图片的软件网站模板,wordpress 设置数据库,济南公司做网站的价格背景 在线广告是互联网行业常见的商业变现方式。从工程角度看#xff0c;广告索引的结构和实现方式直接决定了整个系统的服务性能。本文以美团的搜索广告系统为蓝本#xff0c;与读者一起探讨广告系统的工程奥秘。 领域问题 广告索引需具备以下基本特性#xff1a; 层次化的… 背景 在线广告是互联网行业常见的商业变现方式。从工程角度看广告索引的结构和实现方式直接决定了整个系统的服务性能。本文以美团的搜索广告系统为蓝本与读者一起探讨广告系统的工程奥秘。 领域问题 广告索引需具备以下基本特性 层次化的索引结构。实时化的索引更新。层次投放模型 一般地广告系统可抽象为如下投放模型并实现检索、过滤等处理逻辑。 该层次结构的上下层之间是一对多的关系。一个广告主通常创建若干个推广计划每个计划对应一个较长周期的KPI比如一个月的预算和投放地域。一个推广计划中的多个推广单元分别用于更精细的投放控制比如一次点击的最高出价、每日预算、定向条件等。广告创意是广告曝光使用的素材根据业务特点它可以从属于广告主或推广计划层级。 实时更新机制 层次结构可以更准确、更及时地反应广告主的投放控制需求。投放模型的每一层都会定义若干字段用于实现各类投放控制。广告系统的大部分字段需要支持实时更新比如审核状态、预算上下线状态等。例如当一个推广单元由可投放状态变为暂停状态时若该变更没有在索引中及时生效就会造成大量的无效投放。 业界调研 目前生产化的开源索引系统大部分为通用搜索引擎设计基本无法同时满足上述条件。 Apache Lucene 全文检索、支持动态脚本实现为一个Library。支持实时索引但不支持层次结构。Sphinx 全文检索实现为一个完整的Binary二次开发难度大。支持实时索引但不支持层次结构。因此广告业界要么基于开源方案进行定制要么从头开发自己的闭源系统。在经过再三考虑成本收益后我们决定自行设计广告系统的索引系统。 索引设计 工程实践重点关注稳定性、扩展性、高性能等指标。 设计分解 设计阶段可分解为以下子需求。 实时索引 广告场景的更新流涉及索引字段和各类属性的实时更新。特别是与上下线状态相关的属性字段需要在若干毫秒内完成更新对实时性有较高要求。 用于召回条件的索引字段其更新可以滞后一些如在几秒钟之内完成更新。采用分而治之的策略可极大降低系统复杂度。 属性字段的更新直接修改正排表的字段值可以保证毫秒级完成。索引字段的更新涉及更新流实时计算、倒排索引等的处理过程只需保证秒级完成。此外通过定期切换全量索引并追加增量索引由索引快照确保数据的正确性。 层次结构 投放模型的主要实体是广告主Advertiser、推广计划Campaign、广告组Adgroup、创意Creative等。其中 广告主和推广计划定义用于控制广告投放的各类状态字段。广告组描述广告相关属性例如竞价关键词、最高出价等。创意与广告的呈现、点击等相关的字段如标题、创意地址、点击地址等。一般地广告检索、排序等均基于广告组粒度广告的倒排索引也是建立在广告组层面。借鉴关系数据库的概念可以把广告组作为正排主表即一个Adgroup是一个doc并对其建立倒排索引把广告主、推广计划等作为辅表。主表与辅表之间通过外键关联。 通过查询条件从倒排索引中查找相关docID列表。对每个docID可从主表获取相关字段信息。使用外键字段分别获取对应辅表的字段信息。检索流程中实现对各类字段值的同步过滤。 可靠高效 广告索引结构相对稳定且与具体业务场景耦合较弱为避免Java虚拟机由于动态内存管理和垃圾回收机制带来的性能抖动最终采用C11作为开发语言。虽然Java可使用堆外内存但是堆外堆内的数据拷贝对高并发访问仍是较大开销。项目严格遵循《Google C Style》大幅降低了编程门槛。 在“读多写少”的业务场景需要优先保证“读”的性能。检索是内存查找过程属于计算密集型服务为保证CPU的高并发一般设计为无锁结构。可采用“一写多读”和延迟删除等技术确保系统高效稳定运转。此外巧妙利用数组结构也进一步优化了读取性能。 灵活扩展 正排表、主辅表间的关系等是相对稳定的而表内的字段类型需要支持扩展比如用户自定义数据类型。甚至倒排表类型也需要支持扩展例如地理位置索引、关键词索引、携带负载信息的倒排索引等。通过继承接口实现更多的定制化功能。 逻辑结构 从功能角度索引由Table和Index两部分组成。如上图所示Index实现由Term到主表docID的转换Table实现正排数据的存储并通过docID实现主表与辅表的关联。 分层架构 索引库分为三层 接口层以API方式对外提供索引的构建、更新、检索、过滤等功能。能力层实现基于倒排表和正排表的索引功能是系统的核心。存储层索引数据的内存布局和到文件的持久化存储。索引实现 本节将自底向上从存储层开始逐一描述各层的设计细节和挑战点。 存储层 存储层负责内存分配以及数据的持久化可使用mmap实现到虚拟内存空间的映射由操作系统实现内存与文件的同步。此外mmap也便于外部工具访问或校验数据的正确性。 将存储层抽象为分配器Allocator。针对不同的内存使用场景如对内存连续性的要求、内存是否需要回收等可定制实现不同的分配器。 以下均为基于mmap的各类分配器这里的“内存”是指调用进程的虚拟地址空间。实际的代码逻辑还涉及复杂的Metadata管理下文并未提及。 简单的分配策略 LinearAllocator 分配连续地址空间的内存即一整块大内存当空间需要扩展时会采用新的mmap文件映射并延迟卸载旧的文件映射。新映射会导致页表重新装载大块内存映射会导致由物理内存装载带来的性能抖动。一般用于空间需求相对固定的场景如HashMap的bucket数组。SegmentAllocator 为解决LinearAllocator在扩展时的性能抖动问题可将内存区分段存储即每次扩展只涉及一段保证性能稳定。分段导致内存空间不连续但一般应用场景如倒排索引的存储很适合此法。默认的段大小为64MB。集约的分配策略 频繁的增加、删除、修改等数据操作将导致大量的外部碎片。采用压缩操作可以使占用的内存更紧凑但带来的对象移动成本却很难在性能和复杂度之间找到平衡点。在工程实践中借鉴Linux物理内存的分配策略自主实现了更适于业务场景的多个分配器。 PageAllocator 页的大小为4KB使用伙伴系统Buddy System的思想实现页的分配和回收。页的分配基于SegmentAllocator即先分段再分页。在此简要阐述伙伴分配器的处理过程为有效管理空闲块每一级order持有一个空闲块的FreeList。设定最大级别order4即从order0开始由低到高每级order块内页数分别为1、2、4、8、16等。分配时先找满足条件的最小块若找不到则在上一级查找更大的块并将该块分为两个“伙伴”其中一个分配使用另一个置于低一级的FreeList。 下图呈现了分配一个页大小的内存块前后的状态变化分配前分配器由order0开始查找FreeList直到order4才找到空闲块。 将该空闲块分为页数为8的2个伙伴使用前一半并将后一半挂载到order3的FreeList逐级重复此过程直到返回所需的内存块并将页数为1的空闲块挂在到order0的FreeList。 当块释放时会及时查看其伙伴是否空闲并尽可能将两个空闲伙伴合并为更大的空闲块。这是分配过程的逆过程不再赘述。 虽然PageAllocator有效地避免了外部碎片却无法解决内部碎片的问题。为解决这类小对象的分配问题实现了对象缓存分配器SlabAllocator。 SlabAllocator 基于PageAllocator分配对象缓存slab大小以页为单位。空闲对象按内存大小定义为多个SlabManager每个SlabManager持有一个PartialFreeList用于放置含有空闲对象的slab。对象的内存分配过程即从对应的PartialFreeList获取含有空闲对象的slab并从该slab分配对象。反之释放过程为分配的逆过程。 综上实时索引存储结合了PageAllocator和SlabAllocator有效地解决了内存管理的外部碎片和内部碎片问题可确保系统高效稳定地长期运行。 能力层 能力层实现了正排表、倒排表等基础的存储能力并支持索引能力的灵活扩展。 正向索引 也称为正排索引Forward Index即通过主键Key检索到文档Doc内容以下简称正排表或Table。不同于搜索引擎的正排表数据结构Table也可以单独用于NoSQL场景类似于Kyoto Cabinet的哈希表。 Table不仅提供按主键的增加、删除、修改、查询等操作也配合倒排表实现检索、过滤、读取等功能。作为核心数据结构Table必须支持频繁的字段读取和各类型的正排过滤需要高效和紧凑的实现。 为支持按docID的随机访问把Table设计为一个大数组结构data区。每个doc是数组的一个元素且长度固定。变长字段存储在扩展区ext区仅在doc中存储其在扩展区的偏移量和长度。与大部分搜索引擎的列存储不同将data区按行存储这样可针对业务场景尽可能利用CPU与内存之间的缓存来提高访问效率。 此外针对NoSQL场景可通过HashMap实现主键到docID的映射idx文件这样就可支持主键到文档的随机访问。由于倒排索引的docID列表可以直接访问正排表因此倒排检索并不会使用该idx。 反向索引 也称作倒排索引Inverted Index即通过关键词Keyword检索到文档内容。为支持复杂的业务场景如遍历索引表时的算法粗排逻辑在此抽象了索引器接口Indexer。 具体的Indexer仅需实现各接口方法并将该类型注册到IndexerFactory可通过工厂的NewIndexer方法获取Indexer实例类图如下 当前实现了三种常用的索引器 NoPayloadIndexer最简单的倒排索引倒排表为单纯的docID列表。DefaultPayloadIndexer除docID外倒排表还存储keyword在每个doc的负载信息。针对业务场景可存储POI在每个Node粒度的静态质量分或最高出价。这样在访问正排表之前就可完成一定的倒排优选过滤。GEOHashIndexer即基于地理位置的Hash索引。上述索引器的设计思路类似仅阐述其共性的两个特征 词典文件term存储关键词、签名哈希、posting文件的偏移量和长度等。与Lucene采用的前缀压缩的树结构不同在此实现为哈希表虽然空间有所浪费但可保证稳定的访问性能。倒排表文件posting存储docID列表、Payload等信息。检索操作是顺序扫描倒排列表并在扫描过程中做一些基于Payload的过滤或倒排链间的布尔运算如何充分利用高速缓存实现高性能的索引读取是设计和实现需要考虑的重要因素。在此基于segmentAllocator实现分段的内存分配达到了效率和复杂度之间的微妙平衡。 出于业务考虑没有采用Lucene的Skip list结构因为广告场景的doc数量没有搜索引擎多且通常为单个倒排列表的操作。此外若后续doc数量增长过快且索引变更频繁可考虑对倒排列表的元素构建B树结构实现倒排元素的快速定位和修改。 接口层 接口层通过API与外界交互并屏蔽内部的处理细节其核心功能是提供检索和更新服务。 配置文件 配置文件用于描述整套索引的Schema包括Metadata、Table、Index的定义格式和内容如下 可见Index是构建在Table中的但不是必选项Table中各个字段的定义是Schema的核心。当Schema变化时如增加字段、增加索引等需要重新构建索引。篇幅有限此处不展开定义的细节。 检索接口 检索由查找和过滤组成前者产出查找到的docID集合后者逐个对doc做各类基础过滤和业务过滤。 Search返回正排过滤后的ResultSet内部组合了对DoSearch和DoFilter的调用。DoSearch查询doc返回原始的ResultSet但并未对结果进行正排过滤。DoFilter对DoSearch返回的ResultSet做正排过滤。一般仅需调用Search就可实现全部功能DoSearch和DoFilter可用于实现更复杂的业务逻辑。 以下为检索的语法描述 /{table}/{indexer|keyfield}?queryxxxxxxfilterxxxxx 第一部分为路径用于指定表和索引。第二部分为参数多个参数由分隔与URI参数格式一致支持query、filter、Payload_filter、index_filter等。 由query参数定义对倒排索引的检索规则。目前仅支持单类型索引的检索可通过index_filter实现组合索引的检索。可支持AND、OR、NOT等布尔运算如下所示 query(AB|C|D)!E 查询语法树基于Bison生成代码。针对业务场景常用的多个term求docID并集操作通过修改Bison文法规则消除了用于存储相邻两个term的doc合并结果的临时存储直接将前一个term的doc并入当前结果集。该优化极大地减少了临时对象开销。 由filter参数定义各类正排表字段值过滤多个键值对由“;”分割支持单值字段的关系运算和多值字段的集合运算。 由Payload_filter参数定义Payload索引的过滤目前仅支持单值字段的关系运算多个键值对由“;”分割。 详细的过滤语法如下 此外由index_filter参数定义的索引过滤将直接操作倒排链。由于构造检索数据结构比正排过滤更复杂此参数仅适用于召回的docList特别长但通过索引过滤的docList很短的场景。 结果集 结果集ResultSet的实现参考了java.sql.ResultSet接口。通过cursor遍历结果集采用inline函数频繁调用的开销。 实现为C模板类主要接口定义如下 Next移动cursor到下一个doc成功返回true否则返回false。若已经是集合的最后一条记录则返回false。GetValue读取单值字段的值字段类型由泛型参数T指定。如果获取失败返回默认值def_value。GetMultiValue读取多值字段的值返回指向值数组的指针数组大小由size参数返回。读取失败返回nullsize等于0。更新接口 更新包括对doc的增加、修改、删除等操作。参数类型Document表示一条doc记录内容为待更新的doc的字段内容key为字段名value为对应的字段值。操作成功返回0失败返回非0可通过GetErrorString接口获取错误信息。 增加接口Add将新的doc添加到Table和Index中。修改接口Update修改已存在的doc内容涉及Table和Index的变更。删除接口Delete删除已存在的doc涉及从Table和Index删除数据。更新服务对接实时更新流实现真正的广告实时索引。 更新系统 除以上描述的索引实现机制生产系统还需要打通在线投放引擎与商家端、预算控制、反作弊等的更新流。 挑战与目标 数据更新系统的主要工作是将原始多个维度的信息进行聚合、平铺、计算后最终输出线上检索引擎需要的维度和内容。 业务场景导致上游触发可能极不规律。为避免更新流出现的抖动必须对实时更新的吞吐量做优化留出充足的性能余量来应对触发的尖峰。此外更新系统涉及多对多的维度转换保持计算、更新触发等逻辑的可维护性是系统面临的主要挑战。 吞吐设计 虽然更新系统需要大量的计算资源但由于需要对几十种外部数据源进行查询因此仍属于IO密集型应用。优化外部数据源访问机制是吞吐量优化的主要目标。 在此采取经典的批量化方法即集群内部对于可以批量查询的一类数据源全部收拢到一类特定的worker上来处理。在短时间内worker聚合数据源并逐次返回给各个需要数据的数据流。处理一种数据源的worker可以有多个根据同类型的查询汇集到同一个worker批量查询后返回。在这个划分后就可以做一系列的逻辑优化来提升吞吐量。 分层抽象 除生成商家端的投放模型数据更新系统还需处理针对各种业务场景的过滤以及广告呈现的各类专属信息。业务变更可能涉及多个数据源的逻辑调整只有简洁清晰的分成抽象才能应对业务迭代的复杂度。 工程实践中将外部数据源抽象为统一的Schema既做到了数据源对业务逻辑透明也可借助编译器和类型系统来实现完整的校验将更多问题提前到编译期解决。 将数据定义为表Table、记录Record、字段Field、值Value等抽象类型并将其定义为Scala Path Dependent Type方便编译器对程序内部的逻辑进行校验。 可复用设计 多对多维度的计算场景中每个字段的处理函数DFP应该尽可能地简单、可复用。例如每个输出字段DF的DFP只描述需要的源数据字段SF和该字段计算逻辑并不描述所需的SF(1)到SF(n)之间的查询或路由关系。 此外DFP也不与最终输出的层级绑定。层级绑定在定义输出消息包含的字段时完成即定义消息的时候需要定义这个消息的主键在哪一个层级上同时绑定一系列的DFP到消息上。 这样DFP只需单纯地描述字段内容的生成逻辑。如果业务场景需要将同一个DF平铺到不同层级只要在该层级的输出消息上引用同一个DFP即可。 触发机制 更新系统需要接收数据源的状态变动判断是否触发更新并需要更新哪些索引字段、最终生成更新消息。 为实现数据源变动的自动触发机制需要描述以下信息 数据间的关联关系实现描述关联关系的语法即在描述外部数据源的同时就描述关联关系后续字段查询时的路由将由框架处理。DFP依赖的SF信息仅对单子段处理的简单DFP可通过配置化方式将依赖的SF固化在编译期对多种数据源的复杂DFP可通过源码分析来获取该DFP依赖的SF无需用户维护依赖关系。生产实践 早期的搜索广告是基于自然搜索的系统架构建的随着业务的发展需要根据广告特点进行系统改造。新的广告索引实现了纯粹的实时更新和层次化结构已经在美团搜索广告上线。该架构也适用于各类非搜索的业务场景。 系统架构 作为整个系统的核心基于实时索引构建的广告检索过滤服务RS承担了广告检索和各类业务过滤功能。日常的业务迭代均可通过升级索引配置完成。 此外为提升系统的吞吐量多个模块已实现服务端异步化。 性能优化 以下为监控系统的性能曲线索引中的doc数量为百万级别时延的单位是毫秒。 后续规划 为便于实时索引与其他生产系统的结合除进一步的性能优化和功能扩展外我们还计划完成多项功能支持。 JNI 通过JNI将Table作为单独的NoSQL为Java提供本地缓存。如广告系统的实时预估模块可使用Table存储模型使用的广告特征。 SQL 提供SQL语法提供简单的SQL支持进一步降低使用门槛。提供JDBC进一步简化Java的调用。 参考资料 Apache Lucene http://lucene.apache.org/Sphinx http://sphinxsearch.com/“Understanding the Linux Virtual Memory Manager” https://www.kernel.org/doc/gorman/html/understand/Kyoto Cabinet http://fallabs.com/kyotocabinet/GNU Bison https://www.gnu.org/software/bison/作者简介 仓魁广告平台搜索广告引擎组架构师主导实时广告索引系统的设计与实现。擅长C、Java等多种编程语言对异步化系统、后台服务调优等有深入研究。晓晖广告平台搜索广告引擎组核心开发负责实时更新流的设计与实现。在广告平台率先尝试Scala语言并将其用于大规模工程实践。刘铮广告平台搜索广告引擎组负责人具有多年互联网后台开发经验曾领导多次系统重构。蔡平广告平台搜索广告引擎组点评侧负责人全面负责点评侧系统的架构和优化。招聘信息 有志于从事Linux后台开发对计算广告、高性能计算、分布式系统等有兴趣的朋友请通过邮箱与我们联系。联系邮箱liuzheng04meituan.com 。
