• <xmp id="c6cca"><table id="c6cca"></table>
  • <bdo id="c6cca"><noscript id="c6cca"></noscript></bdo>
  • 騰訊企業郵箱-注冊-申請-升級-購買-續費-開通-報價等服務。全國服務熱線:400-889-0304
    遼寧行業動態 遼寧更新日志 遼寧熱門問題

    遼寧騰訊云實現時序搜索引擎:日志檢索性能提升 40 倍

    2022-08-26 18:58:32 15034

    作者:zlinzlin,騰訊云專家工程師

    引言

    騰訊云日志服務 CLS 團隊聯合北京大學軟件工程國家工程研究中心、Tencent ES Oteam,在傳統搜索引擎的基礎上,引入了時序概念,實現了時序搜索引擎。該時序搜索引擎已經提交了 6 項相關專利申請,同時,該研究成果《TencentCLS: The Cloud Log Service with High Query Performances》已經被數據庫頂會 VLDB 2022 接收,將于 2022 年 9 月份澳大利亞悉尼舉行的 VLDB 學術會議上發布。

    在海量日志檢索性能方面,時序搜索引擎相對傳統搜索引擎取得了近 40 倍的提升;騰訊云日志服務 CLS 也因此實現了在海量日志檢索領域,對類似 ELK 等業界主流日志產品大幅的性能優勢。本文將大家詳細解密專利背后的硬核技術。

    業務背景

    CLS 日志服務是騰訊云推出的專業日志服務,采用了 Lucene 來支持海量日志數據的檢索、分析處理。Lucene 是 Apache 軟件基金會的開源項目,是當前主流的日志數據處理工具;但 Lucene 主要是為通用搜索而打造的,在搜索過程中并不能有效利用日志數據的特點;因此,多家公司基于性能考慮,放棄 Lucene 改為自研日志搜索引擎,如國內某專業日志處理公司,在幾年前放棄了 Lucene 轉而自研專用搜索引擎,宣稱其搜索性能比 Lucene 提升了 1 倍。

    為了進一步提高 CLS 的日志檢索和分析能力,滿足多種業務場景的檢索分析需求。CLS 團隊在 Lucene 的基礎上,實現了日志數據專用的時序搜索引擎。相對傳統搜索引擎,時序搜索引擎在正序檢索、逆序檢索、直方圖檢索方面,分別取得了 38 倍、24 倍、7.6 倍的性能提升。論文相關實驗數據如下:

    (表中 O0、O1、O2、O3 分別代表我們設計的 4 項優化技術方案)

    正序檢索:

    圖片

    逆序檢索:

    圖片

    直方圖檢索:

    圖片

    而在離線測試中,時序搜索引擎的性能比原生 Lucene 提升了 50 倍,響應速度提升了 5 倍;上述相關功能已經在 CLS 上全量應用,在最消耗性能的冷數據場景,測試結果顯示各類核心操作的響應速度均有 10 倍+提升。

    圖片

    接下來將為大家詳細介紹時序搜索引擎基本原理,以及在實現時序搜索引擎過程中我們對 Lucene 所做的一些技術上的改造。

    主要包括:

    • 技術背景:日志搜索在 Lucene 中的實現原理及其難點
      • 一個典型的日志搜索案例
      • 日志搜索在 Lucene 中的實現
      • 日志搜索中的難題:高基維范圍檢索問題
    • 解決方案:基于時序索引的搜索方案

    • 測試與對比

      • 性能測試:時序搜索引擎與原生 Lucene 性能對比

      • 競品對比:CLS 與友商日志服務性能對比

    技術背景:日志搜索在 Lucene 中的實現原理及其難點

    時序數據是指帶有時間戳屬性的數據。日志數據是一個典型的時序數據,每一條日志都帶有一個時間戳,并且每一次對日志的檢索都會指定時間范圍。

    【注*】在監控系統中,通常時序數據是指每個時間點只有一種屬性值,在日志系統中,我們不做這個要求,也就是說,同一個時間點,可以有多條不同的日志。

    一個典型的日志搜索案例

    一個典型的日志包含時間戳,日志文本,日志屬性,比如:

    [2021-09-28 10:10:39T1234] [ip=192.168.1.1] XXXXXXXX

    其中 xxxx 代表日志文本。

    一個典型的日志系統會對日志的時間,屬性,以及文本信息建立索引。

    比如上面的日志會分別對這些信息建立索引:

    • timestamp=2021-09-28 10:10:39T1234
    • ip=192.168.1.1
    • 分詞后的文本信息

    在這種日志中,一個典型的查詢都會指定時間范圍如下:

    Select * from xxxx_index where ip = xxxx and timestmap >= 2021-09-28xxxx and timestmap<= 2021-09-29xxxx;

    日志搜索在 Lucene 中的實現

    Lucene 非常擅長文本搜索,但是不是很擅長數字類型搜索,尤其不擅長高基維數字類型的范圍搜索;非常不幸的是,日志數據的時間戳恰恰是這種高基維數據,而且對日志的搜索,通常都需要指定時間戳范圍。

    這里先定義一下什么叫高基維 (high-cardinality) 數據。high-cardinality,從字面上理解,即對于某個字段,不同值的數量非常多。比如以毫秒為單位的時間戳,一天之內就有 24*60*60*1000 種不同的值。

    Lucene 索引結構

    在搜索系統中,每一條日志都會被指定一個唯一的編號,比如有 1000 條數據,就會給每條日志分別指定 0,1,2,3,4,......,999 做為他們的編號,這個編號叫 docid。

    在建立索引時,會給每一個值都建立一個倒排索引,用來指定這個值在哪些文檔中出現過。

    關于倒排索引,可以參考:https://segmentfault.com/a/1190000037658997

    在日志場景的時間戳索引里面,我們可以認為會建立起一系列時間戳為 key,value 為一個 docid list 的倒排表:

    timestamp->[docid1,docid2],這里的[docid1,docid2]列表,稱為 postinglist,通常情況下,它是按 docid 從小到大排序的。

    舉個例子,2021-09-28 10:10:39T1234->[1,5]

    表示 doc id 為 1 和 5 的日志使用了“2021-09-28 10:10:39T1234”這個時間戳。

    Lucene 搜索算法

    搜索引擎靠大量這種結構來加速搜索,只要你指定一個時間戳,它就可以馬上從倒排表里面取出 posting list,直接響應你的搜索請求。

    在很多場景的搜索應用里面,這種設計非常高效,因為從一堆有序的 timestamp 里面找到指定的 timestamp 的 postinglist,普通搜索操作的算法復雜度只有 o(log(n))。

    日志搜索中的高基維范圍檢索難題

    對于日志數據中的時間戳范圍檢索,這種倒排的設計就沒有太大幫助了。核心原因在于傳統的搜索應用只會涉及到有限數量的倒排項,但是時間戳檢索屬于高基維范圍檢索,可能涉及億萬級索引項,比如:

    指定時間搜索范圍:timestmap > 2021-09-28:00:00T00000 and timestmap< 2021-09-29:00:00T000000

    這個時間范圍是一天,假設時間單位是毫秒,而且每一毫秒都有數據,可能涉及的索引項數量是:24*60*60*1000=8640 萬個;也就是說,要完成這個搜索,需要掃描 8640 萬個索引項中的每一個。如果時間單位是微秒,這個數量級還需要繼續放大 1000 倍。

    高基維范圍搜索的算法復雜度是 o(n),其中 n 是索引項的數量,也就是基數。

    舉一個直觀的例子,在一個 100 億條日志的索引中,目前觀測到這個索引項的數據量大概在 30G 左右,如果用 100MB/s 的速度去讀的話,光加載這些索引數據就需要 300 秒。當然,Lucene 也做了一些優化,采用 BKD 樹而不是直接倒排,不過本質上并沒有改變這些問題。

    Lucene 還提供了一些快速過濾的優化,在特定的場景下可以避免掃描這些索引數據,業務上取得了很好的效果。不過基礎這么差,我們總有機會踩到沒有被優化覆蓋到的坑的時候,更何況很多優化也只是半桶水的效果,比如把原來的 30s,優化成了 15s。

    因此我們需要從根源上解決問題,尋找具有更低算法復雜度的搜索方案。


    解決方案:基于時序索引的搜索引擎

    首先,在大方向上,我們改變了數據的組織方式,通過對日志按照時間戳排序來加快對時間范圍的搜索。在原來的索引中,日志的時間戳是無序的,對于指定時間范圍的檢索需要處理大量的時間戳索引項(幾十萬到上億),我們通過時間戳有序化將時間范圍檢索簡化為只需要對時間范圍的端點進行處理(處理的時間戳索引項從幾十萬/上億降低為 2 個)。如下圖所示:

    圖片圖片

    其次,在方案落地實現上,我們針對原系統中對時間戳有序化支持不夠友好的實現進行了深入研究,并提出 3 項針對性的改造方案,使得時間戳有序方案能夠在原系統中落地,并達到預期的檢索速度:

    二分搜索帶來的磁盤訪問離散化問題

    在原系統實現中,對于有序時間戳的檢索是通過在有序的列存中的二分查找來定位。簡單的二分查找對內存數據非常高效,但是對磁盤數據卻很容易造成散點訪問;這個問題的解決方案是通過引入二級索引來減少對磁盤的訪問(磁盤訪問從數十次降低為 3 次)。

    圖片圖片

    單向迭代器導致逆序訪問需要遍歷所有數據問題

    原系統底層實現的所有迭代器都只支持單向迭代。在逆序檢索的場景下,數據按時間戳排序導致所有逆序數據都在隊列尾部,原系統現有實現只能遍歷所有數據才能到達尾部。這個問題的解決方案是在單向迭代器的基礎上通過逆向二分檢索算法來實現對尾部數據的快速迭代(迭代次數從數萬/數十萬次降低為幾十次),該算法將尾部迭代的算法復雜度從原來的 o(n) 降低為 o(logn * logn)。

    圖片圖片

    大量回表查詢導致 histogram 響應慢問題

    對于日志應用中最常見的針對時間范圍的直方圖計算(histogram),原系統采用對每條命中的日志回表查詢時間戳的方式來實現,這種方式帶來大量的(幾萬/幾十萬或更多)回表操作,因此性能較慢。解決方案是只需要通過分桶的邊界確定桶中日志 ID 范圍(幾次索引訪問取代數萬/數十萬次回表操作),分桶內部的點直接通過跟邊界比較來確定所屬分桶。更進一步,在查詢分桶邊界日志 ID 時,我們也采用了上述介紹的二級索引來進一步降低對磁盤的訪問。

    圖片圖片

    測試與對比

    性能測試:與原生 Lucene 性能對比

    我們進行了線下原型測試(800 萬數據量級):在 100 并發的場景下,新算法的響應速度提高了 50 倍(1.059 秒 vs 56.9 秒);在確保響應速度低于 1s 的前提下,新算法的并發能力提高了 20 倍(90+ vs 4),下面是詳細測試數據:

    圖片

    上述測試只考慮數據的只讀測試;同時我們也利用線上數據進行了測試,線上數據測試過程中也伴隨著大量的寫入操作,由于寫入操作在大規模分布式查詢中容易由于 IO 抖動造成長尾,這種長尾對優化后的系統影響尤其大,因此,我們也順便優化了 IO,避免這種長尾抖動。

    (注:由于長尾會造成 2-3s 的抖動,原生 Lucene 索引查詢耗時 10s+,2-3s 的抖動影響不大,優化后的索引只需要數百毫秒,2-3s 抖動造成結果嚴重失真,因此需要先進行 IO 優化)

    測試結果表明,在所有操作的耗時上面,CLS 時序索引均比原生 Lucene 索引快了 10 倍以上。詳細測試結果如下:

    圖片

    友商對比:CLS 與友商日志服務性能對比

    某云的日志服務同樣基于 Lucene,因此,我們也跟該友商的日志服務性能做了對比。(以下對比均為 10 億數據場景)

    圖片

    說明 1:分鐘及以上且數據基本有序的場景,高頻使用場景中,友商和騰訊 CLS 相差不大,其他場景雖然不常用,但是對于利用日志來調研線上復雜問題也是必不可少的。


    說明 2:友商在秒級排序的場景,在數據量比較大的情況下,會出現檢索結果不準確,在檢索頁面會明確提示客戶“結果不準確”。

    友商在大部分場景性能/功能嚴重落后的根源在于他們只對分鐘級的時間來建立索引,從而避免時間戳高基檢索帶來的性能開銷問題:

    1. 友商支持分鐘級索引,因此一天的數據只會有 24*60=1440 個索引項;

    2. CLS 支持微秒級索引,因此一天的數據理論上存在 24*60*60*1000=86,400,000,000=860 億個索引項;

      (注:CLS 在新索引上線前采用毫秒級時間戳,在新索引上線后改為采用微秒級時間戳)-->

    CLS 通過自研時序索引來支持高基時間戳檢索問題,因此獲得性能上的大幅提升。


    總結

    對于 CLS 團隊即將發布在 VLDB 的相關論文,VLDB 評委們評價如下:

    1、相對 Lucene 來說,這篇論文的方案帶來了超過一個數量級的查詢性能提升。

    2、在 telemetry 數據這一重要的云服務領域,針對海量數據和嚴重傾斜的日志寫入和查詢,作者們用非常清晰和簡潔的方式展示了他們在這一領域的發現和解決方案。普通讀者也能通過論文輕松理解這些發現的價值和可應用性。

    3、雖然時序索引對于數據庫行業來說不是一個新的概念,論文的作者們找到了一個非常好的應用場景,并且大幅提升了這種應用場景下常用查詢的效率,因此也能帶動相關云服務質量的有效提升。

    4、對現有的文本搜索引擎來說,這是一個非常好的用戶案例,對于類似 Lucene 的搜索引擎來說,這些方案可以帶來范圍查詢、 time-based 查詢、直方圖查詢的性能提升。

    5、大規模日志的實時分析對工業界來說是一個重要的問題,很多讀者都會對這篇論文所提供的騰訊的解決方案感興趣。


    6、實驗效果數據非常清晰地證明了論文中所提到改進方案的有效性。

    未來,CLS 將持續打磨日志服務細節,不斷精進監控告警及數據分析加工能力,幫助用戶在日志運維、運營、合規審計等業務方面實現跨越式發展,為線上服務的高可用性保駕護航,造福更多運維團隊、運營團隊與開發團隊。

    聯系我們
    全國特價400-889-0304
    在線QQ1833102442
    聯系郵箱
    kf@tjwlt.com
    聯系地址

    天津、北京、上海、廣州、濟南

    一阵快速的冲刺
  • <xmp id="c6cca"><table id="c6cca"></table>
  • <bdo id="c6cca"><noscript id="c6cca"></noscript></bdo>