分類
發燒車訊

用隊列實現棧,用棧實現隊列,聽起來有點繞,都搞懂了就掌握了精髓!

目錄

  • 一、背景
  • 二、概念
    • 2.1 棧
    • 2.2 隊列
  • 三、棧和隊列的相互實現
    • 3.1 用隊列實現棧
    • 3.2 用棧實現隊列
  • 四、總結

一、背景

棧和隊列是數據結構中最常用到的兩種結構,有非常廣泛的運用,該篇文章將通過動畫的手段,展示棧和隊列相互實現的底層原理,讓我們真正搞懂棧和隊列的特性。

二、概念

2.1 棧

棧[Stack]:是一種限定僅在表尾進行插入和刪除操作的線性表;即後進先出(LIFO-last in first out),最後插入的元素最先出來

  • 入棧(push)
  • 出棧 (pop)
2.2 隊列

 隊列[Queue]:是一種限定僅在表頭進行刪除操作,僅在表尾進行插入操作的線性表;即先進先出(FIFO-first in first out):最先插入的元素最先出來。

  • 入隊(enqueue)
  • 出隊(dequeue)

三、棧和隊列的相互實現

3.1 用隊列實現棧
  • 模擬入棧的實現原理
    — 棧的特性是新加入的元素出現在棧頂,保證後進先出。
    — 隊列的特性為新加入的元素出現在隊尾,隊列的隊尾元素最後出隊。
    按以上兩個前提,我們可以讓隊頭至隊尾前的其它所有元素依次出隊再入隊,直至在隊尾新加入的元素被移到隊頭,也即實現了讓新壓入的元素保留在棧頂

  • 模擬出棧的實現原理
    — 由於在入棧時保證隊列中新加入隊尾的元素被移到了隊頭,出棧只需彈出隊頭元素即可。

  • 完整代碼實現

/**
 * 用隊列模擬實現棧
 *
 * @author zhuhuix
 * @date 2020-06-09
 */
public class QueueImplStack {

    // 定義隊列
    private Queue<Integer> queue;

    public QueueImplStack() {
        queue = new LinkedList();
    }

    // 入棧--在隊尾加入元素后,讓其他元素按順序出隊再入隊,保持新加入的元素永遠在隊頭
    public void push(Integer e) {
        queue.offer(e);
        int size = queue.size();
        int i = 0;
        while (i < size - 1) {
            queue.offer(queue.poll());
            i++;
        }
    }

    // 出棧--將隊尾前的其它所有元素出隊再入隊,直至隊尾元素移到隊頭
    public Integer pop() {
        return queue.poll();
    }

    // 查看棧頂元素--即隊頭元素
    public Integer peek() {
        return queue.peek();
    }

    // 是否為空
    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        QueueImplStack stack = new QueueImplStack();
        stack.push(1);
        System.out.println(stack.peek());
        stack.push(2);
        System.out.println(stack.peek());
        stack.push(3);
        System.out.println(stack.peek());
        System.out.println("=============");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());

    }
}

3.2 用棧實現隊列
  • 模擬入隊的實現原理
    — 隊列的特性最新入隊的元素需排在隊尾,最先入隊的元素排在隊頭,按隊頭到隊尾的順序依次出隊。
    — 對應到棧的數據結構上,也即需將新加入的元素保留在棧頂,保證先進先出。
    按以上兩個前提,需在存放數據的棧的基礎上再增加一個輔助棧,在每次入隊時,先將存放數據的棧彈入輔助棧,再把需加入的新元素壓入數據棧底,最後把輔助棧中的元素彈出依次壓入數據棧,這樣保證了新加入的元素,沉在棧底。

    模擬出隊的實現原理
    — 由於在入隊時,通過數據棧與輔助棧的交換,實現了后加入的元素沉在棧底,先進入的元素保留在棧頂,直接通過出棧彈出即可。

    • 完整代碼實現
/**
 * 用棧模擬實現隊列
 *
 * @author zhuhuix
 * @date 2020-06-09
 */
public class StackImplQueue {
    // 數據棧
    private Stack<Integer> stack;
    // 輔助棧
    private Stack<Integer> aux;

    StackImplQueue() {
        stack = new Stack<>();
        aux = new Stack<>();
    }

    // 入隊--通過數據棧與輔助棧相互交換,保證新加入的元素沉在數據棧底
    public void enqueue(Integer e) {
        while (!stack.isEmpty()) {
            aux.push(stack.pop());
        }
        stack.push(e);
        while(!aux.isEmpty()){
            stack.push(aux.pop());
        }

    }

    // 出隊--彈出數據棧元素
    public Integer dequeue(){
        return stack.pop();
    }

    // 查看隊頭元素
    public Integer peek(){
        return stack.peek();
    }

    // 是否為空
    public boolean isEmpty(){
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        StackImplQueue queue = new StackImplQueue();
        queue.enqueue(1);
        System.out.println(queue.peek());
        queue.enqueue(2);
        System.out.println(queue.peek());
        queue.enqueue(3);
        System.out.println(queue.peek());
        System.out.println("=============");
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());

    }
}

四、總結

通過以上棧和隊列相互交叉的實踐,我們對棧和隊列的重大特性有了深入了解:

  • 棧和隊列都是線性連續結構,增加和刪除元素不會影響破此連續性
  • 棧通過棧頂的操作實現元素的增加與刪除,也即只能在一端進行操作
  • 隊列通過隊尾增加元素,隊頭刪除元素,也即可以在兩端操作

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

網頁設計最專業,超強功能平台可客製化

※別再煩惱如何寫文案,掌握八大原則!

分類
發燒車訊

香港環署縱容 回收亂龍

摘錄自2020年6月22日東方日報香港報導

歷時一年多的反送中條例加上疫情衝擊,雖然近日稍為平息,卻凸顯出香港政府環保政策漏洞。回收玻璃瓶行業開始恢復,但卻屢發越區搶收違規行為,環境保護署袖手旁觀。

政府按港九新界地區批出三份玻璃管理合約,由兩個承辦商承辦免市場壟斷,然而近期九龍區接連發生跨區「插旗」收瓶,更有承辦商司機越區偷瓶事件,負責監管的環保署卻沒介入糾正,使得分區收瓶制度名存實亡。

另外,廢棄塑膠回收業在沒有管理規劃下,近期大批回收店關門,令大批廢棄塑膠沒人要。有地方議員批評,署方監管不力,默許發生打擊對手的行為,長遠恐怕出現市場壟斷惡果,窒礙本地環保業發展。

公害污染
污染治理
國際新聞
香港
回收
玻璃回收
廢棄物

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計最專業,超強功能平台可客製化

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家公司費用怎麼算?

分類
發燒車訊

英醫學權威警告政界 小心出現第二波疫情

摘錄自2020年6月24日中央廣播電台報導

路透社今天(24日)報導,資深醫界人士警告英國各政黨,當地俗稱武漢肺炎的2019年冠狀病毒疾病(COVID-19)疫情可能升溫,而且第二波疫情有實質風險。

這些醫學界人士在一封寫給英國政界領袖的公開信中說:「雖然這場疫情未來在英國的情勢難以預估,現有證據顯示,當地爆發疫情的可能性愈來愈大,而第二波(疫情)有實質風險。」

在「英國醫學期刊」(British Medical Journal, BMJ)上簽署這封公開信的人士,包含英國皇家外科醫學院(Royal College of Surgeons)院長奧德森(Derek Alderson)、皇家內科醫學院(Royal College of Physicians)院長戈達(Andrew Goddard),以及皇家緊急醫藥大學院長韓德森(Katherine Henderson)。

他們表示:「遏止病毒必備的許多基礎要素已準備就緒,但重大的挑戰依然存在。」

生活環境
國際新聞
英國
武漢肺炎
疫情
新冠肺炎疫情
公共衛生

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※超省錢租車方案

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

※推薦台中搬家公司優質服務,可到府估價

分類
發燒車訊

封城後空氣污染大減 增印度德里太陽能產電量達 8%

摘錄自2020年6月24日立場新聞報導

武漢肺炎(COVID-19)下,幾乎全球國家都史無前例封城停擺,經濟發展停滯,但卻拯救了無數生命免受感染,也間接令空氣污染大幅減輕,造成意料不到的連鎖效應。最新刊於 Joule 的研究指,空氣污染減輕,令更多陽光直達太陽能電池板,增加了電力產量。

由德國基爾亥姆霍茲可再生能源研究所物理學家 Ian Marius Peters 領導的團隊,分析了疫情期間印度德里的太陽能發電量變化。團隊在疫情前已在多個城市研究霧霾和空氣污染如何阻擋陽光到達地面,以及其對太陽能電池板輸出的影響。

團隊以全天太陽輻射計(pyranometer)測量指定太陽光波長的輻射強度,並使用過去的研究數據,計算了德里到達地面的日照量變化。印度德里是全世界其中一個污染最嚴重的城市,團隊發現,與 2017 年至 2019 年同一段時間數據相比,德里 3 月 24 日封城後,空氣污染量下跌 45%–50% ,而3月下旬德里太陽能電池板接收到的陽光量增加了約 8% , 4 月則增加了 6% ,團隊推斷,污染減少是更多陽光照射電池板的主要原因。

公害污染
空氣污染
污染治理
國際新聞
印度德里
太陽能
COVID-19

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※回頭車貨運收費標準

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

分類
發燒車訊

這台後驅SUV只要5萬多,而且還是大廠出品

實際動力表現來看,這副發動機的低扭會略有不足,在2000轉時感覺動力並不是很充沛,上到3000轉以後動力會有所改善。不過,這種小排量發動機最大的問題就是後勁不足,上到100km/h之後就很難有什麼作為。底盤表現幻速S2的前懸架使用麥弗遜式獨立懸架,而後懸架為五連桿式非獨立懸架。

各個級別的SUV市場早已進入百家爭鳴的狀態,小型SUV市場更是如此,各路廠商都會使出渾身解數想搶佔這個市場,北汽也不例外。它們旗下的幻速S2可以說是一款重要產品,下面編者我就給大家分析一下幻速S2。

之所以要寫幻速S2是因為熱門的小型SUV大家已聽了不少,而幻速S2這種中規中矩的產品大家可能了解較少,但銷量並不能很好地反應出其真實產品力,因此編者我想給大家好好科普一下。

北汽銀翔-北汽幻速S2

指導價:5.18-6.08萬

外觀設計

幻速S2的車身尺寸為4250*1730*1735mm,軸距為2560mm。從前臉看,引擎蓋上由兩側向中間匯聚的凹線讓前臉有個很好的中心感。兩側向側面上揚的大燈組,看起來有一點點關二哥的威武感。

側面來看,車身顯得較為緊湊,門把手上方的腰線讓側面不至於過於單調。不過,輪胎的尺寸略微偏小。

後方來看,備胎外漏的設計野性十足,地台的高度較低,容易裝卸貨物。整個尾部給人一種方正厚實的感覺。

內飾設計

中控台的設計相當平庸也符合這個價位應有的水平,不過布局還是比較整齊,上手難度不高。擋把上的烤黑鋼琴漆帶來一絲亮點。

動力總成

幻速S2搭載了1.5L自然吸氣發動機+5擋手動變速箱,最大輸出113馬力和150牛米。實際動力表現來看,這副發動機的低扭會略有不足,在2000轉時感覺動力並不是很充沛,上到3000轉以後動力會有所改善。不過,這種小排量發動機最大的問題就是後勁不足,上到100km/h之後就很難有什麼作為。

底盤表現

幻速S2的前懸架使用麥弗遜式獨立懸架,而後懸架為五連桿式非獨立懸架。具體表現來看,幻速S2的底盤會偏硬一些,對震動的過濾並不是很到位,尤其面對連續震動會有點應付不過來。

乘坐空間

SUV在空間表現中會有一定的優勢,幻速S2也不例外。身高175cm的體驗者坐於後排,能有兩拳左右的腿部空間和4指左右的頭部空間,這個表現還是不錯的。

由於幻速S2是一款后驅車,所以它的後排中央拱起有點高,對乘坐有點影響,同時後排中央也缺乏頭枕,看來對後排中央的乘客並不友好。

油耗與保養費用

多位車主反映的幻速S2百公里綜合油耗為8.3L,對於它這個級別的產品來說,還是有一點點偏高。

保養費用方面,幻速S2的6萬公里總保養費用為4914元,其中更換機油機濾的價格為220元,這個價錢還是比較實惠的。

配置分析

幻速S2總共有8個車型可以買,但是只有4個版本,每個版本都有國四和國五的車型,這點要注意。

經過分析,我推薦買指導價為5.78萬的手動舒適型,這也是次低配的車型。因為它雖然比最低配貴了5000元,但是多了副駕駛安全氣囊、車頂行李架、倒車雷達、后視鏡電動調節和后雨刷。這堆配置之中,我覺得最重要的是副駕駛安全氣囊,這也是給家人朋友的一個保障。

編者總結:

幻速S2是小型SUV中少有的后驅車型,所以它的操控性會好一點,前輪胎的磨損也不會那麼快。如果你有一個后驅夢,而預算又正好卡在這個區間,何不買台幻速S2。本站聲明:網站內容來源於http://www.auto6s.com/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

網頁設計最專業,超強功能平台可客製化

※別再煩惱如何寫文案,掌握八大原則!

分類
發燒車訊

Spring Boot 教程 – Elasticsearch

1. Elasticsearch簡介

Elasticsearch是一個基於Lucene的搜索服務器。它提供了一個分佈式多用戶能力的全文搜索引擎,基於RESTful web接口。Elasticsearch是用Java語言開發的,並作為Apache許可條款下的開放源碼發布,是一種流行的企業級搜索引擎。Elasticsearch用於雲計算中,能夠達到實時搜索,穩定,可靠,快速,安裝使用方便。官方客戶端在Java、.NET(C#)、PHP、Python、Apache Groovy、Ruby和許多其他語言中都是可用的。根據DB-Engines的排名显示,Elasticsearch是最受歡迎的企業搜索引擎,其次是Apache Solr,也是基於Lucene。以後再給大家詳細介紹solr。

它能很方便的使大量數據具有搜索、分析和探索的能力。充分利用Elasticsearch的水平伸縮性,能使數據在生產環境變得更有價值。Elasticsearch 的實現原理主要分為以下幾個步驟,首先用戶將數據提交到Elasticsearch 數據庫中,再通過分詞控制器去將對應的語句分詞,將其權重和分詞結果一併存入數據,當用戶搜索數據時候,再根據權重將結果排名,打分,再將返回結果呈現給用戶。

Elasticsearch可以用於搜索各種文檔。它提供可擴展的搜索,具有接近實時的搜索,並支持多租戶。”Elasticsearch是分佈式的,這意味着索引可以被分成分片,每個分片可以有0個或多個副本。每個節點託管一個或多個分片,並充當協調器將操作委託給正確的分片。再平衡和路由是自動完成的。“相關數據通常存儲在同一個索引中,該索引由一個或多個主分片和零個或多個複製分片組成。一旦創建了索引,就不能更改主分片的數量。

Elasticsearch使用Lucene,並試圖通過JSON和Java API提供其所有特性。它支持facetting和percolating,如果新文檔與註冊查詢匹配,這對於通知非常有用。另一個特性稱為“網關”,處理索引的長期持久性;例如,在服務器崩潰的情況下,可以從網關恢復索引。Elasticsearch支持實時GET請求,適合作為NoSQL數據存儲,但缺少分佈式事務。

2. Elasticsearch深入了解

2.1 Elasticsearch的底層實現

  • 2.1.1 lucene

    Es是一個比較複雜的搜索服務器,本身也是使用Java語言編寫的,在上面的簡介中,說明了ES是一個基於lucene的搜索服務器,lucene是什麼呢?Lucene是apache軟件基金會4 jakarta項目組的一個子項目,是一個開放源代碼的全文檢索引擎工具包,但它不是一個完整的全文檢索引擎,而是一個全文檢索引擎的架構,提供了完整的查詢引擎和索引引擎,部分文本分析引擎。lucene也是使用Java語言編寫的,Java天下第一!

    Lucene是一套用於全文檢索和搜尋的開源程式庫,由Apache軟件基金會支持和提供。Lucene提供了一個簡單卻強大的應用程式接口,能夠做全文索引和搜尋。在Java開發環境里Lucene是一個成熟的免費開源工具。就其本身而言,Lucene是當前以及最近幾年最受歡迎的免費Java信息檢索程序庫。至於lucene到底是怎麼實現的,牛牛們可能要自己去百度或者谷歌一下啦。

  • 2.1.2 Elasticsearch的基本概念

    1. 集群(Cluster):就是多台ES服務器在一起構成搜索服務器,現在很多應用基本上都有集群的概念,提高性能,讓應用具有高可用性,一台服務器掛掉,可以很快有另一台ES服務器補上。

    2. 節點(Node):節點就是集群中的某一台ES服務器就稱為一個節點。

    3. 索引庫(Index Indices):就是ES服務器上的某一個索引,相當於Mysql數據庫中的數據庫的概念,一個節點可以有很多個索引庫。

    4. 文檔類型(Type):這個概念就相當於Mysql數據庫中表的概念,一個索引庫可以有很多個文檔類型,但是這個概念現在慢慢淡化了,因為在ES中一個索引庫直接存數據文檔就挺好的,這個概念現在來說有點多餘了,所以ES官方也在淡化這個概念,在ES8中,這個概念將會徹底的消失。

    5. 文檔(Doc):文檔就相當於Mysql是數據庫中某個表的一條數據記錄,現在ES已經到7.7版本了,我們也就忽略type這個概念,直接在索引庫中存文檔即可。另外需要說一下,我們一般把數據文檔存到Es服務器的某個索引庫的這個動作稱之為索引

      最後還有兩個比較重要的概念,但是可能不是那麼直觀的可以感受得到:

      分片(Shards)和副本(Replicas)

      索引可能會存儲大量數據,這些數據可能超過單個節點的硬件限制。例如,十億個文檔的單個索引佔用了1TB的磁盤空間,可能不適合單個節點的磁盤,或者可能太慢而無法單獨滿足來自單個節點的搜索請求。

      為了解決此問題,Elasticsearch提供了將索引細分為多個碎片的功能。創建索引時,只需定義所需的分片數量即可。每個分片本身就是一個功能齊全且獨立的“索引”,可以託管在群集中的任何節點上。

      分片很重要,主要有兩個原因:

      • 它允許您水平分割/縮放內容量
      • 它允許您跨碎片(可能在多個節點上)分佈和并行化操作,從而提高性能/吞吐量

      分片如何分佈以及其文檔如何聚合回到搜索請求中的機制由Elasticsearch完全管理,並且對您作為用戶是透明的。

      在隨時可能發生故障的網絡/雲環境中,非常有用,強烈建議您使用故障轉移機制,以防碎片/節點因某種原因脫機或消失。為此,Elasticsearch允許您將索引分片的一個或多個副本製作為所謂的副本分片(簡稱副本)。

      複製很重要,主要有兩個原因:

      • 如果分片/節點發生故障,它可提供高可用性。因此,重要的是要注意,副本碎片永遠不會與從其複製原始/主要碎片的節點分配在同一節點上。
      • 由於可以在所有副本上并行執行搜索,因此它可以擴展搜索量/吞吐量。

      總而言之,每個索引可以分為多個碎片。索引也可以複製零(表示沒有副本)或多次。複製后,每個索引將具有主碎片(從中進行複製的原始碎片)和副本碎片(主碎片的副本)。可以在創建索引時為每個索引定義分片和副本的數量。創建索引后,您可以隨時動態更改副本數,但不能事後更改分片數。

      默認情況下,Elasticsearch中的每個索引分配有5個主碎片和1個副本,這意味着如果集群中至少有兩個節點,則索引將具有5個主碎片和另外5個副本碎片(1個完整副本),總共每個索引10個碎片。

  • 2.1.3 Elasticsearch的索引原理

    Es作為一個全文檢索服務器,那麼它在搜索方面肯定很在行啦!那它是怎麼做到的呢?

    Es官方有這麼一句話:一切設計都是為了提高搜索的性能!

    Es能夠快速的搜索出我們需要的內容,靠的就是倒排索引的思想,或者說是一種設計!

    在沒有使用倒排索引的情況下,正常思路是根據搜索關鍵字去查找相應的內容,但是使用了倒排索引之後,ES會先將文檔的所有內容拆分成多個詞條,創建一個包含所有不重複詞條的排序列表,然後列出每個詞條出現在哪個文檔。

    例如,假設我們有兩個文檔,每個文檔的 content 域包含如下內容:

    ​ Doc_1:The quick brown fox jumped over the lazy dog

    ​ Doc_2:Quick brown foxes leap over lazy dogs in summer

    ES首先會將這兩個文檔拆分成多個單獨的詞,或者叫做詞條,然後為所有的詞條創建一個排序列表,並記錄每個詞條出現的文檔的信息。就像下面這樣:

    Term      Doc_1  Doc_2
    -------------------------
    Quick   |       |  X                        /*
    The     |   X   |								Term就是詞條,比如第一個Term就是Quick關鍵字,在Doc_1中不存
    brown   |   X   |  X							在,在Doc_2中存在,其他的以此類推。
    dog     |   X   |							*/
    dogs    |       |  X
    fox     |   X   |
    foxes   |       |  X
    in      |       |  X
    jumped  |   X   |
    lazy    |   X   |  X
    leap    |       |  X
    over    |   X   |  X
    quick   |   X   |
    summer  |       |  X
    the     |   X   |
    ------------------------
    

    現在,如果我們想搜索 quickbrown這兩個關鍵字,我們只需要查找包含每個詞條的文檔,就相當於我們查詢的時候,是通過這個索引表找到文檔,在通過文檔去找文檔內容中的搜索關鍵字,與傳統的通過關鍵字去找內容是不同的。

    倒排索引到底是個怎麼實現的,怎麼個思想,我在這裏就不一一說明了,大家可以看下官方的詳細介紹:倒排索引的原理

    還有es官方的一系列的說明也都可以了解一下:什麼是Elasticsearch?

2.2 Elasticsearch的安裝

本演示項目ES版本為7.0.0版本,其他版本的ES的maven依賴與其他的jar包關係請自行查閱官方文檔,保證不衝突。

  • Windows

    Es服務器的安裝很簡單,Windows版本特別的簡單,直接去官網下載,運行 bin/elasticsearch 或者bin\elasticsearch.bat

  • Linux(CentOS7)

    首先我們去官網下載ES的tar.gz包,然後自建一個文件夾放好,然後解壓tar.zg壓縮包:

    tar -xvf elasticsearch-7.0.0.tar.gz
    

    然後進入到bin目錄下:

    cd elasticsearch-7.0.0/bin
    

    然後運行elasticsearch:

    ./elasticsearch
    

    這個時候肯定會報錯的,因為沒有進行配置,所以我們先對es進行一些簡單的配置,保證能單機運行,進入elasticsearch-7.7.0/config目錄,對es的核心配置文件進行編輯:

    vim elasticsearch.yml
    

    進入到了elasticsearch.yml文件的編輯頁面:

    首先我們配置集群名稱,集群名稱自己取一個喜歡的名字就好:

    接下來配置節點名稱,就是在這個集群中,這個es服務器的名稱:

    接下來配置一些必要的參數:

    bootstrap.memory_lock: 是否鎖住內存,避免交換(swapped)帶來的性能損失,默認值是: false。

    bootstrap.system_call_filter: 是否支持過濾掉系統調用。elasticsearch 5.2以後引入的功能,在bootstrap的時候check是否支持seccomp。

    配置network為所有人都可以訪問,因為我們一般是使用ssh連接工具在其他的電腦上操作Linux系統,所以我們需要配置一下:

    到這裏就配置完成了,但是當你重新去運行.elasticsearch的可執行文件的時候,依然會報錯。

    報錯信息中可能包含以下幾個錯誤:

    • max file descriptors [4096] for elasticsearch process is too low, increase to at least [65536]

      原因:無法創建本地文件問題,用戶最大可創建文件數太小。

      解決方法:切換到root賬戶下,進入Linux系統文件夾,編輯limits.conf文件:

      vim /etc/security/limits.conf
      

      在文件的末尾加上:

      *                soft    nofile          65536
      *                hard    nofile          65536
      *                soft    nproc           4096
      *                hard    nproc           4096
      
    • max virtual memory areas vm.max_map_count [65530] is too low, increase to at least [262144]

      原因:最大虛擬內存太小,需要修改系統變量的最大值。

      解決方法:切換到root賬戶下,進入Linux系統文件夾,編輯sysctl.conf文件:

      vim /etc/sysctl.conf
      

      在文件的末尾加上:

      vm.max_map_count=262144
      
    • max number of threads [1024] for user [es] likely too low, increase to at least [2048]

      原因:無法創建本地線程問題,用戶最大可創建線程數太小。

      解決方法:如果你是CentOS6及以下系統,編輯的文件是90-nproc.conf這個文件,如果你和我一樣使用的是CentOS7的話,編輯的文件是20-nproc.conf文件,其實這兩個文件是一樣的,只是在不同CentOS系統中名稱不一樣而已。

      CentOS7使用這個命令:

      vim /etc/security/limits.d/20-nproc.conf
      

      CentOS6使用這個命令:

      vim /etc/security/limits.d/90-nproc.conf
      

      只需要在文件中加上以下配置:

      *          soft    nproc     4096
      

      這個配置的意思是說賦予其他用戶的可創建本地線程數為4096。在這個文件中本來就有一個配置,意思是說賦予root賬戶創建線程數不受限制。我們就把上面的配置加在本來存在的配置的下面一行就可以了。

      如果是CentOS7的使用者,還需要配置另一個文件,否則這個最大線程數是不會生效的。CentOS 7 使用systemd替換了SysV,Systemd目的是要取代Unix時代以來一直在使用的init系統,兼容SysV和LSB的啟動腳本,而且夠在進程啟動過程中更有效地引導加載服務。在/etc/systemd目錄下有一個系統的默認管理配置,這裡有登陸、日誌、服務、系統等。所以CentOS7的使用者還需要配置下面這個文件:

      vim /etc/systemd/system.conf
      

      對其中的選項進行配置,在文件的末尾加上:

      DefaultLimitNOFILE=65536
      DefaultLimitNPROC=4096
      

    上面的所以錯誤解決完畢之後,我們再運行.elasticsearch可執行文件,es才可以啟動成功。

2.3 Elasticsearch的使用

首先給大家介紹一個谷歌瀏覽器插件,這個插件是用來可視化展示es的索引庫數據的,這個插件叫做ElasticVue,個人感覺挺好用的,展示也比較方便,給大家截個圖看看:

大家可以使用這個建立索引庫,然後調用es官方的es專用的語法操作es服務器進行CRUD操作,但是此處我只介紹Java語言如何調用es服務器API,廢話不多說,我們直接開始下一步。

  • 2.3.1 引入依賴

    搭建工程的過程我就不演示了,直接上pom.xml依賴文件。

    pom.xml

    <!--springboot父工程-->
        <parent>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-parent</artifactId>
            <version>2.2.2.RELEASE</version>
            <relativePath/> <!-- lookup parent from repository -->
        </parent>
    
        <dependencies>
            <!--springboot-web組件-->
            <dependency>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-starter-web</artifactId>
                <version>2.2.2.RELEASE</version>
            </dependency>
            <!--elasticsearch-rest-client組件-->
            <dependency>
                <groupId>org.elasticsearch.client</groupId>
                <artifactId>elasticsearch-rest-client</artifactId>
                <version>7.7.0</version>
            </dependency>
            <!--elasticsearch-rest-high-level-client組件-->
            <dependency>
                <groupId>org.elasticsearch.client</groupId>
                <artifactId>elasticsearch-rest-high-level-client</artifactId>
                <version>7.7.0</version>
            </dependency>
            <!--elasticsearch組件-->
            <dependency>
                <groupId>org.elasticsearch</groupId>
                <artifactId>elasticsearch</artifactId>
                <version>7.7.0</version>
            </dependency>
            <!--mybatis整合springboot組件-->
            <dependency>
                <groupId>org.mybatis.spring.boot</groupId>
                <artifactId>mybatis-spring-boot-starter</artifactId>
                <version>2.1.0</version>
            </dependency>
            <!--mysql數據庫連接驅動-->
            <dependency>
                <groupId>mysql</groupId>
                <artifactId>mysql-connector-java</artifactId>
                <version>8.0.18</version>
            </dependency>
            <!--lombok組件-->
            <dependency>
                <groupId>org.projectlombok</groupId>
                <artifactId>lombok</artifactId>
                <version>1.18.10</version>
            </dependency>
            <!--json組件gson-->
            <dependency>
                <groupId>com.google.code.gson</groupId>
                <artifactId>gson</artifactId>
                <version>2.8.5</version>
            </dependency>
            <!--springboot-test組件-->
            <dependency>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-test</artifactId>
            </dependency>
            <!--單元測試junit組件-->
            <dependency>
                <groupId>junit</groupId>
                <artifactId>junit</artifactId>
                <version>4.12</version>
                <scope>test</scope>
            </dependency>
            <!--spring-test組件-->
            <dependency>
                <groupId>org.springframework</groupId>
                <artifactId>spring-test</artifactId>
                <version>5.2.2.RELEASE</version>
                <scope>test</scope>
            </dependency>
        </dependencies>
    
        <build>
            <!--springboot的maven插件-->
            <plugins>
                <plugin>
                    <groupId>org.springframework.boot</groupId>
                    <artifactId>spring-boot-maven-plugin</artifactId>
                </plugin>
                <plugin>
                    <groupId>org.apache.maven.plugins</groupId>
                    <artifactId>maven-compiler-plugin</artifactId>
                    <configuration>
                        <compilerArgs>
                            <arg>-parameters</arg>
                        </compilerArgs>
                    </configuration>
                </plugin>
            </plugins>
        </build>
    
  • 2.3.2 Elasticsearch的配置類和Gson配置類和應用配置文件

    application.yml

    butterflytri:
      databaseurl-port: 127.0.0.1:3306 # 數據庫端口
      database-name: student_db # 數據庫名
      host: 192.168.129.100:9200 # es服務端
    server:
      port: 8080 # 應用端口
      servlet:
        context-path: /butterflytri # 應用映射
    spring:
      application:
        name: mybatis # 應用名稱
      datasource:
        url: jdbc:mysql://${butterflytri.databaseurl-port}/${butterflytri.database-name}?useUnicode=true&characterEncoding=UTF-8&useJDBCCompliantTimezoneShift=true&useLegacyDatetimeCode=false&serverTimezone=UTC
        driver-class-name: com.mysql.jdbc.Driver
        username: root
        password: root
    mybatis:
      type-aliases-package: com.butterflytri.entity # entity別名
      mapper-locations: classpath:com/butterflytri/mapper/*Mapper.xml # mapper映射包掃描
    

    注意:yml文件中的192.168.129.100:9200是es對外的端口,使用的http協議進行操作,es服務器還有個9300端口,這個端口是es集群中各個節點進行交流的端口,使用的是tcp協議。所以我們連接的時候,端口要使用9200端口。

    項目啟動類沒有什麼特別的東西,就不展示了。

    ElasticsearchConfig.java

    package com.butterflytri.config;
    
    import org.apache.http.HttpHost;
    import org.elasticsearch.client.RestClient;
    import org.elasticsearch.client.RestHighLevelClient;
    import org.springframework.beans.factory.DisposableBean;
    import org.springframework.beans.factory.FactoryBean;
    import org.springframework.beans.factory.InitializingBean;
    import org.springframework.beans.factory.annotation.Value;
    import org.springframework.context.annotation.Configuration;
    
    /**
     * @author: WJF
     * @date: 2020/5/22
     * @description: ElasticSearchConfig
     */
    @Configuration
    public class ElasticSearchConfig implements FactoryBean<RestHighLevelClient>, InitializingBean, DisposableBean {
    
        /**
         * {@link FactoryBean<T>}:FactoryBean<T>是spring對外提供的對接接口,當向spring對象使用getBean("..")方法時,
         *                         spring會使用FactoryBean<T>的getObject 方法返回對象。所以當一個類實現的factoryBean<T>接口時,
         *                         那麼每次向spring要這個類時,spring就返回T對象。
         *
         * {@link InitializingBean}:InitializingBean接口為bean提供了初始化方法的方式,它只包括afterPropertiesSet方法,
         *                          凡是繼承該接口的類,在初始化bean的時候會執行該方法。在spring初始化bean的時候,如果該bean是
         *                          實現了InitializingBean接口,並且同時在配置文件中指定了init-method,系統則是
         *                          先調用afterPropertiesSet方法,然後在調用init-method中指定的方法。
         *
         * {@link DisposableBean}:DisposableBean接口為bean提供了銷毀方法destroy-method,會在程序關閉前銷毀對象。
         */
    
        @Value("#{'${butterflytri.host}'.split(':')}")
        private String[] host;
    
        private RestHighLevelClient restHighLevelClient;
    
        private RestHighLevelClient restHighLevelClient() {
            restHighLevelClient = new RestHighLevelClient(
    
                    RestClient.builder(new HttpHost(host[0],Integer.valueOf(host[1]),"http"))
    
            );
            return restHighLevelClient;
        }
    
        @Override
        public void destroy() throws Exception {
            restHighLevelClient.close();
        }
    
        @Override
        public RestHighLevelClient getObject() throws Exception {
            return restHighLevelClient;
        }
    
        @Override
        public Class<?> getObjectType() {
            return RestHighLevelClient.class;
        }
    
        @Override
        public void afterPropertiesSet() throws Exception {
            restHighLevelClient();
        }
    
    }
    

    ES的配置類,這個配置類實現了三個接口,三個接口的作用我也寫上了註釋,大家可以看下,需要注意的是FactoryBean這個接口,一但實現了這個接口,每當你需要使用泛型表示的對象T的時候,Spring不會從容器中去拿這個對象,而是會調用這個FactoryBean.getObject()方法去拿對象。其他的就沒有什麼了。

    Gson.java

    Gson是一個操作json數據的類,它的執行效率可能會慢一點,但是它在解析json數據的時候不會出Bug。

    package com.butterflytri.config;
    
    import com.google.gson.Gson;
    import org.springframework.context.annotation.Bean;
    import org.springframework.context.annotation.Configuration;
    
    /**
     * @author: WJF
     * @date: 2020/5/22
     * @description: GsonConfig
     */
    @Configuration
    public class GsonConfig {
    
        /**
         * {@link Gson}:一個操作json的對象,有比較好的json操作體驗,相對於Alibaba的FastJson來說速度慢一些,但是FastJson在解析
         *              複雜的的json字符串時有可能會出現bug。
         * @return Gson
         */
    
        @Bean
        public Gson gson() {
            return new Gson();
        }
    
    }
    

    Constants.java

    這是我寫的常量類,放一些ES使用的常量,直接寫字符串也行,但是我建議這樣做。

    package com.butterflytri.constants;
    
    
    /**
     * @author: WJF
     * @date: 2020/5/22
     * @description: Constants
     */
    public class Constants {
    
        /**
         * es搜索關鍵字
         */
        public static final String KEYWORD = ".keyword";
    
        /**
         * es的type類型:type字段將在 elasticsearch-version:8 中徹底刪除,本來就覺得沒得啥用。
         */
        public static final String DOC_TYPE = "_doc";
    
        /**
         * 學生信息索引類型
         */
        public static final String INDEX_STUDENT = "student_info";
    
    
        /**
         * 自定連接符
         */
        public static final String CONNECTOR = " --> ";
    
    }
    

    Student.java

    package com.butterflytri.entity;
    
    import lombok.Getter;
    import lombok.Setter;
    import lombok.ToString;
    
    import java.io.Serializable;
    
    /**
     * @author: WJF
     * @date: 2020/5/16
     * @description: Student
     */
    
    @ToString
    @Getter
    @Setter
    public class Student implements Serializable {
    
        private Long id;
    
        private String studentName;
    
        private String studentNo;
    
        private String sex;
    
        private Integer age;
    
        private String clazz;
    
    }
    

    StudentMapper.java

    package com.butterflytri.mapper;
    
    import com.butterflytri.entity.Student;
    import org.apache.ibatis.annotations.Mapper;
    
    import java.util.List;
    
    /**
     * @author: WJF
     * @date: 2020/5/16
     * @description: StudentMapper
     */
    @Mapper
    public interface StudentMapper {
    
        /**
         * 查詢所有學生信息
         * @return List<Student>
         */
        List<Student> findAll();
    
        /**
         * 通過id查詢學生信息
         * @param id:學生id
         * @return Student
         */
        Student findOne(Long id);
    
        /**
         * 通過學號查詢學生信息
         * @param studentNo:學生學號
         * @return Student
         */
        Student findByStudentNo(String studentNo);
    
    }
    

    mybatis的SQL映射文件我就不展示了,也很簡單,大家看接口方法名就應該可以想象得到SQL語句是怎樣的。

  • 2.3.3 索引數據到ES服務器

    IndexServiceImpl.java

    package com.butterflytri.service.impl;
    
    import com.butterflytri.constants.Constants;
    import com.butterflytri.entity.Student;
    import com.butterflytri.service.IndexService;
    import com.google.gson.Gson;
    import org.elasticsearch.action.ActionListener;
    import org.elasticsearch.action.index.IndexRequest;
    import org.elasticsearch.action.index.IndexResponse;
    import org.elasticsearch.client.RequestOptions;
    import org.elasticsearch.client.RestHighLevelClient;
    import org.elasticsearch.common.xcontent.XContentType;
    import org.springframework.stereotype.Service;
    
    import javax.annotation.Resource;
    import java.io.IOException;
    
    /**
     * @author: WJF
     * @date: 2020/5/22
     * @description: IndexServiceImpl
     */
    @Service
    public class IndexServiceImpl implements IndexService {
    
        @Resource
        private Gson gson;
    
        @Resource
        private RestHighLevelClient restHighLevelClient;
    
        @Override
        public String index(Student student) {
            StringBuilder builder = new StringBuilder();
            IndexRequest indexRequest = this.initIndexRequest(student);
            try {
                // 同步索引到elasticsearch服務器,獲取索引響應IndexResponse
                IndexResponse indexResponse = restHighLevelClient.index(indexRequest, RequestOptions.DEFAULT);
                String statusName = indexResponse.status().name();
                int statusCode = indexResponse.status().getStatus();
                builder.append(statusName).append(Constants.CONNECTOR).append(statusCode);
            } catch (IOException e) {
                builder.append("Fail").append(Constants.CONNECTOR).append(e.getMessage());
            }
            return builder.toString();
        }
    
    
        @Override
        public String indexAsync(Student student) {
            StringBuilder builder = new StringBuilder();
            IndexRequest indexRequest = this.initIndexRequest(student);
            // 異步索引到elasticsearch服務器,獲取索引響應IndexResponse
            restHighLevelClient.indexAsync(indexRequest, RequestOptions.DEFAULT,actionListener(builder));
            return builder.toString();
        }
    
    
    
        /**
         * 初始化IndexRequest,並設置數據源。
         * @param student
         * @return IndexRequest
         */
        private IndexRequest initIndexRequest(Student student) {
            // 構建IndexRequest,設置索引名稱,索引類型,索引id
            IndexRequest indexRequest = new IndexRequest(Constants.INDEX_STUDENT);
            // 可以不設置,默認就是'_doc'
            indexRequest.type(Constants.DOC_TYPE);
            // 設置索引id為studentId
            indexRequest.id(String.valueOf(student.getId()));
            // 設置數據源
            String studentJson = gson.toJson(student);
            indexRequest.source(studentJson, XContentType.JSON);
            return indexRequest;
        }
    
        /**
         * 異步索引的回調監聽器,根據不同的結果做出不同的處理
         * @param builder
         * @return ActionListener<IndexResponse>
         */
        private ActionListener<IndexResponse> actionListener(StringBuilder builder) {
            return new ActionListener<IndexResponse>() {
                // 當索引數據到es服務器時,返回不同的狀態
                @Override
                public void onResponse(IndexResponse indexResponse) {
                    String statusName = indexResponse.status().name();
                    int statusCode = indexResponse.status().getStatus();
                    builder.append(statusName).append(Constants.CONNECTOR).append(statusCode);
                }
    
                // 當索引數據時出現異常
                @Override
                public void onFailure(Exception e) {
                    builder.append("Fail").append(Constants.CONNECTOR).append(e.getMessage());
                }
            };
        }
    }
    

    上面的內容很簡單,就是將Student對象格式化為Json字符串,然後存到es服務器中,大家只要遵守一個規則就好,就是操作es服務器,不管是什麼操作都是用RestHighLevelClient這個類去操作,上面的就是student對象索引的es服務器中,使用restHighLevelClient.index(indexRequest, RequestOptions.DEFAULT),首先就是構建indexRequest對象,這個對象就是索引請求對象,具體幹了什麼看代碼上的註釋。這裏還有個restHighLevelClient.indexAsync()這個方法,這個方法和上面的index方法一樣的效果,只不過是異步調用。

    接下來我們測試一下這個代碼,請看:

    @Test
        public void indexTest() {
            List<Student> list = studentMapper.findAll();
            for (Student student : list) {
                String message = indexService.index(student);
                System.out.println(message);
            }
        }
    

    我們使用ElasticVue插件連接es服務器即可看到有一個索引庫:

    當我們點擊到show按鈕的時候,可以看到student_info索引庫中有幾條記錄:

    索引數據到數據庫成功了。

  • 2.3.4 獲取Es服務器數據

    獲取數據,是es提供給我們的API,這個Api只能獲取某個索引的某一條文檔,示例如下:

    GetServiceImpl.java

    	@Override
        public Student get(String id) {
            Student student = new Student();
            GetRequest getRequest = new GetRequest(Constants.INDEX_STUDENT, id);
            try {
                GetResponse getResponse = restHighLevelClient.get(getRequest, RequestOptions.DEFAULT);
                String source = getResponse.getSourceAsString();
                student = gson.fromJson(source, Student.class);
            } catch (IOException e) {
                e.printStackTrace();
            }
            return student;
        }
    

    接着我們在測試類中,調用這個方法然後打印一下結果:

    GetServiceTest.java

    	@Test
        public void getTest() {
            Student student = getService.get("1");
            System.out.println(student);
        }
    

    結果如下:

    更新數據文檔和刪除數據文檔我就不演示了,都是大同小異,大家可以拉下我的代碼,好好研究一下,都有詳細的註釋,覺得可以的話,給我點下star也是極好的。下面演示一下searchApi,這個Api是我們經常需要使用的,特別重要。

  • 2.3.5 搜索Es服務器數據

    ES的搜索API包含很多,比如說組合搜索,區間搜索,高亮显示,分詞搜索等等。我先給大家演示一下組合搜索,區間搜索其實也是組合搜索的一個子條件,其他的搜索其實也都是,代碼如下:

    SearchServiceImpl.java

    	@Override
        public List<Student> searchRange(Object from, Object to, String field, String index) {
            List<Student> list = new ArrayList<>();
            BoolQueryBuilder boolQueryBuilder = QueryBuilders.boolQuery();
            // 需要搜索的區間字段field
            RangeQueryBuilder rangeQueryBuilder = QueryBuilders.rangeQuery(field);
            // 左區間
            if (from != null) {
                rangeQueryBuilder.from(from, true);
            }
            // 右區間
            if (to != null) {
                rangeQueryBuilder.to(to, true);
            }
            boolQueryBuilder.must();
            SearchSourceBuilder searchSourceBuilder = new SearchSourceBuilder();
            searchSourceBuilder.query(boolQueryBuilder);
            SearchRequest searchRequest = new SearchRequest(index);
            searchRequest.source(searchSourceBuilder);
            try {
                SearchResponse search = restHighLevelClient.search(searchRequest, RequestOptions.DEFAULT);
                for (SearchHit hit : search.getHits()) {
                    String source = hit.getSourceAsString();
                    Student student = gson.fromJson(source, Student.class);
                    list.add(student);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return list;
        }
    

    上面的代碼其實很簡單,就是一個區間查詢構建器,查詢指定字段處於區間的所有數據,rangeQueryBuilder.from(from, true)的第一個參數就是字段的下邊界,第二個參數代表是否包含邊界。SearchResponse就是搜索的響應對象,所有的數據都在SearchHit對象中。

    接下來給大家演示一些組合查詢,這個方法搜索年齡在18到19歲並且班級為’G0305’的學生。記得ES默認是分頁的,如果想不分頁,一定要記得給搜索字段加上.keyword(字符串加,数字不支持)。

    SearchServiceImpl.java

    @Override
        public List<Student> searchBool() {
            List<Student> list = new ArrayList<>();
            BoolQueryBuilder boolQuery = QueryBuilders.boolQuery();
            boolQuery.must(QueryBuilders.rangeQuery("age").gte(18).lte(19));
            boolQuery.must(QueryBuilders.termQuery("clazz" + Constants.KEYWORD,"G0305"));
            SearchSourceBuilder searchSourceBuilder = new SearchSourceBuilder();
            searchSourceBuilder.query(boolQuery);
            SearchRequest searchRequest = new SearchRequest(Constants.INDEX_STUDENT);
            searchRequest.source(searchSourceBuilder);
            try {
                SearchResponse search = restHighLevelClient.search(searchRequest, RequestOptions.DEFAULT);
                for (SearchHit hit : search.getHits()) {
                    String source = hit.getSourceAsString();
                    Student student = gson.fromJson(source, Student.class);
                    list.add(student);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return list;
        }
    

    上面的代碼中的類BoolQueryBuilder就是組合查詢構建器,這個類可以用來構建組合的條件查詢。boolQuery.must()方法就是用來拼接條件的一種方式,使用這個方法代表必須滿足這個條件才會查詢出來,上面的代碼說明必須滿足年齡為18(包含18)到19(包含19)歲,並且班級為’G0305’的學生才會查詢出來。還有其他的一些常見的組合查詢方法,如下:

    • boolQuery.must():必須滿足此條件,相當於=或者&
    • boolQuery.mustNot():必須不滿足此條件,相當於!=
    • boolQuery.should():相當於||或者or
    • boolQuery.filter():過濾。

    然後是聚合查詢,很類似於MySQL中的聚合函數,這個示例我就不再解釋了,代碼註釋很清楚:

    @Override
        public void searchBoolAndAggregation() {
            BoolQueryBuilder boolQuery = QueryBuilders.boolQuery();
            boolQuery.must(QueryBuilders.rangeQuery("age").gte(18).lte(19));
            boolQuery.must(QueryBuilders.termQuery("clazz" + Constants.KEYWORD,"G0305"));
            // 聚合分組:按clazz字段分組,並將結果取名為clazz,es默認是分詞的,為了精確配置,需要加上‘.keyword’關鍵詞後綴。
            TermsAggregationBuilder aggregationBuilder = AggregationBuilders.terms("clazz").field("clazz" + Constants.KEYWORD);
            // 聚合求和:求符合查詢條件的學生的年齡的和,並將結果取名為ageSum,因為不是字符串,所以默認是精確匹配,不支持分詞。
            aggregationBuilder.subAggregation(AggregationBuilders.sum("ageSum").field("age"));
            // 聚合求平均:求符合查詢條件的學生的年齡的平均值,並將結果取名為ageAvg,因為不是字符串,所以默認是精確匹配,不支持分詞。
            aggregationBuilder.subAggregation(AggregationBuilders.avg("ageAvg").field("age"));
            // 聚合求數量:按學號查詢符合查詢條件的學生個數,並將結果取名為count,es默認是分詞的,為了精確配置,需要加上‘.keyword’關鍵詞後綴。
            aggregationBuilder.subAggregation(AggregationBuilders.count("count").field("studentNo" + Constants.KEYWORD));
            SearchSourceBuilder builder = new SearchSourceBuilder();
            builder.query(boolQuery);
            builder.aggregation(aggregationBuilder);
            // 按年齡降序排序。
            builder.sort("age", SortOrder.DESC);
            SearchRequest request = new SearchRequest("student_info");
            request.source(builder);
            try {
                SearchResponse search = restHighLevelClient.search(request, RequestOptions.DEFAULT);
                for (SearchHit hit : search.getHits()) {
                    String source = hit.getSourceAsString();
                    Student student = gson.fromJson(source, Student.class);
                    System.out.println(student);
                }
                // 使用Terms對象接收
                Terms clazz = search.getAggregations().get("clazz");
                for (Terms.Bucket bucket : clazz.getBuckets()) {
                    System.out.println(bucket.getDocCount());
    
                    System.out.println("=====================");
                    // 使用ParsedSum對象接收
                    ParsedSum ageCount = bucket.getAggregations().get("ageSum");
                    System.out.println(ageCount.getType());
                    System.out.println(ageCount.getValue());
                    System.out.println(ageCount.getValueAsString());
                    System.out.println(ageCount.getMetaData());
                    System.out.println(ageCount.getName());
    
                    System.out.println("=====================");
                    // 使用ParsedAvg對象接收
                    ParsedAvg ageAvg = bucket.getAggregations().get("ageAvg");
                    System.out.println(ageAvg.getType());
                    System.out.println(ageAvg.getValue());
                    System.out.println(ageAvg.getValueAsString());
                    System.out.println(ageAvg.getMetaData());
                    System.out.println(ageAvg.getName());
    
                    System.out.println("=====================");
                    // 使用ParsedValueCount對象接收
                    ParsedValueCount count = bucket.getAggregations().get("count");
                    System.out.println(count.getType());
                    System.out.println(count.getValue());
                    System.out.println(count.getValueAsString());
                    System.out.println(count.getMetaData());
                    System.out.println(count.getName());
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    

    最後還有分詞查詢,分詞查詢就不加.keyword關鍵字即可。

    @Override
        public List<Student> searchMatch(String matchStudentName) {
            List<Student> list = new ArrayList<>();
            BoolQueryBuilder boolQueryBuilder = QueryBuilders.boolQuery();
            // 分詞查詢時不加'.keyword'關鍵字
            boolQueryBuilder.must(QueryBuilders.matchQuery("studentName",matchStudentName));
            SearchSourceBuilder searchSourceBuilder = new SearchSourceBuilder();
            searchSourceBuilder.query(boolQueryBuilder);
            SearchRequest searchRequest = new SearchRequest("student_info");
            searchRequest.source(searchSourceBuilder);
            try {
                SearchResponse search = restHighLevelClient.search(searchRequest, RequestOptions.DEFAULT);
                for (SearchHit hit : search.getHits().getHits()) {
                    String source = hit.getSourceAsString();
                    Student student = gson.fromJson(source, Student.class);
                    list.add(student);
                }
    
            } catch (IOException e) {
                e.printStackTrace();
            }
            return list;
        }
    

    請記住,一般的進行分詞都是字符串才進行分詞搜索,数字等類型只能是精準匹配。

    最後,ES功能很強大,作為搜索界的扛把子,ES的功能遠遠不止這些,它還可以高亮搜索,數據分析等等。我在這裏演示的僅僅只是皮毛,甚至都不是皮毛,僅作為初學者的參考。如有大佬覺得我哪裡寫錯了,或者有不同見解,歡迎留言。

3. 項目地址

本項目傳送門:

  • GitHub —> spring-boot-elasticsearch
  • Gitee —> spring-boot-elasticsearch

此教程會一直更新下去,覺得博主寫的可以的話,關注一下,也可以更方便下次來學習。

  • 作者:Butterfly-Tri
  • 出處:Butterfly-Tri個人博客
  • 版權所有,歡迎保留原文鏈接進行轉載

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計最專業,超強功能平台可客製化

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家公司費用怎麼算?

分類
發燒車訊

一行代碼引來的安全漏洞就讓我們丟失了整個服務器的控制權

之前在某廠的某次項目開發中,項目組同學設計和實現了一個“引以為傲”,額,有點擴張,不過自認為還說得過去的 feature,結果臨上線前被啪啪打臉,因為實現過程中因為一行代碼(沒有標題黨,真的是一行代碼)帶來的安全漏洞讓我們丟失了整個服務器控制權(測試環境)。多虧了上線之前有公司安全團隊的人會對代碼進行掃描,才讓這個漏洞被扼殺在搖籃里。

下面我們就一起來看看這個事故,啊,不對,是故事。

背景說明

我們的項目是一個面向全球用戶的 Web 項目,用 SpringBoot 開發。在項目開發過程中,離不開各種異常信息的處理,比如表單提交參數不符合預期,業務邏輯的處理時離不開各種異常信息(例如網絡抖動等)的處理。於是利用 SpringBoot 各種現成的組件支持,設計了一個統一的異常信息處理組件,統一管理各種業務流程中可能出現的錯誤碼和錯誤信息,通過國際化的資源配置文件進行統一輸出給用戶。

統一錯誤信息配置管理

我們的用戶遍布全球,為了給各個國家用戶比較好的體驗會進行不同的翻譯。具體而言,實現的效果如下,為了方便理解,以“找回登錄密碼”這樣一個業務場景來進行闡述說明。

假設找回密碼時,需要用戶輸入手機或者郵箱驗證碼,假設這個時候用戶輸入的驗證碼通過後台數據庫(可能是Redis)對比發現已經過期。在業務代碼中,只需要簡單的 throw new ErrorCodeException(ErrorCodes.AUTHCODE_EXPIRED) 即可。具體而言,針對不同國家地區不同的語言看到的效果不一樣:

  • 中文用戶看到的提示就是“您輸入的驗證碼已過期,請重新獲取”;
  • 歐美用戶看到的效果是“The verification code you input is expired, …”;
  • 德國用戶看到的是:“Der von Ihnen eingegebene Verifizierungscode ist abgelaufen, bitte wiederholen” 。(我瞎找的翻譯,不一定準)
  • ……

統一錯誤信息配置管理代碼實現

關鍵信息其實就在於一個 GlobalExceptionHandler,對所有Controller 入口進行 AOP 攔截,根據不同的錯誤信息,獲取相應資源文件配置的 key,並從語言資源文件中讀取不同國家的錯誤翻譯信息。

@ControllerAdvice
public class GlobalExceptionHandler {

    @ExceptionHandler(BadRequestException.class)
    @ResponseBody
    public ResponseEntity handle(HttpServletRequest request, BadRequestException e){
        String i18message = getI18nMessage(e.getKey(), request);
        return ResponseEntity.status(HttpStatus.BAD_REQUEST).body(Response.error(e.getCode(), i18message));
    }
    
    @ExceptionHandler(ErrorCodeException.class)
    @ResponseBody
    public ResponseEntity handle(HttpServletRequest request, ErrorCodeException e){
        String i18message = getI18nMessage(e.getKey(), request);
        return ResponseEntity.status(HttpStatus.OK).body(Response.error(e.getCode(), i18message));
    }
}

 

不同語言的資源文件示例

private String getI18nMessage(String key, HttpServletRequest request) {
   try {
       return messageSource.getMessage(key, null, LanguaggeUtils.currentLocale(request));
   } catch (Exception e) {
       // log
       return key;
   }
}

 

詳細代碼實現可以參考本人之前寫的這篇文章一文教你實現 SpringBoot 中的自定義 Validator 和錯誤信息國際化配置,上面有附完整的代碼實現。

基於註解的表單校驗(含自定義註解)

還有一種常見的業務場景就是後端接口需要對用戶提交的表單進行校驗。以“註冊用戶”這樣的場景舉例說明, 註冊用戶時,往往會提交昵稱,性別,郵箱等信息進行註冊,簡單起見,就以這 3 個屬性為例。

定義的表單如下:

public class UserRegForm {
 private String nickname;
 private String gender;
 private String email;
}

 

對於表單的約束,我們有:

  • 昵稱字段:“nickname” 必填,長度必須是 6 到 20 位;
  • 性別字段:“gender” 可選,如果填了,就必須是“Male/Female/Other/”中的一種。說啥,除了男女還有其他?對,是的。畢竟全球用戶嘛,你去看看非死不可,還有更多。
  • 郵箱: “email”,必填,必須滿足郵箱格式。

對於以上約束,我們只需要在對應的字段上添加如下註解即可。

public class UserRegForm {
 @Length(min = 6, max = 20, message = "validate.userRegForm.nickname")
 private String nickname;

 @Gender(message="validate.userRegForm.gender")
 private String gender;

 @NotNull
 @Email(message="validate.userRegForm.email")
 private String email;
}

 

然後在各個語言資源文件中配置好相應的錯誤信息提示即可。其中, @Gender 就是一個自定義的註解。

基於含自定義註解的表單校驗關鍵代碼

自定義註解的實現主要的其實就是一個自定義註解的定義以及一個校驗邏輯。 例如定義一個自定義註解 CustomParam

@Documented
@Constraint(validatedBy = CustomValidator.class)
@Target({FIELD, METHOD, PARAMETER, ANNOTATION_TYPE})
@Retention(RetentionPolicy.RUNTIME)
public @interface CustomParam {
    String message() default "name.tanglei.www.validator.CustomArray.defaultMessage";

    Class<?>[] groups() default {};
    Class<? extends Payload>[] payload() default { };

    @Documented
    @Retention(RetentionPolicy.RUNTIME)
    @Target({FIELD, METHOD, PARAMETER, ANNOTATION_TYPE})
    @interface List {
        CustomParam[] value();
    }
}

 

校驗邏輯的實現 CustomValidator

public class CustomValidator implements ConstraintValidator<CustomParam, String> {
    @Override
    public boolean isValid(String s, ConstraintValidatorContext constraintValidatorContext) {
        if (null == s || s.isEmpty()) {
            return true;
        }
        if (s.equals("tanglei")) {
            return true;
        } else {
            error(constraintValidatorContext, "Invalid params: " + s);
            return false;
        }
    }

    @Override
    public void initialize(CustomParam constraintAnnotation) {
    }

    private static void error(ConstraintValidatorContext context, String message) {
        context.disableDefaultConstraintViolation();
        context.buildConstraintViolationWithTemplate(message).addConstraintViolation();
    }
}

 

上面例子只為了闡述說明問題,其中校驗邏輯沒有實際意義,這樣,如果輸入參數不滿足條件,就會明確提示用戶輸入的哪個參數不滿足條件。例如輸入參數 xx,則會直接提示:Invalid params: xx

這個跟第一部分的處理方式類似,因為現有的 validator 組件實現中,如果違反相應的約束也是一種拋異常的方式實現的,因此只需要在上述的 GlobalExceptionHandler中添加相應的異常信息即可,這裏就不詳述了。 這不是本文的重點,這裏就不詳細闡述了。 詳細代碼實現可以參考本人之前寫的這篇文章一文教你實現 SpringBoot 中的自定義 Validator 和錯誤信息國際化配置,上面有附完整的代碼實現。

場景重現

一切都顯得很完美,直到上線前代碼提交至安全團隊掃描,就被“啪啪打臉”,掃描報告反饋了一個嚴重的安全漏洞。而這個安全漏洞,屬於很高危的遠程代碼執行漏洞。

用前文提到的自定義 Validator,輸入的參數用: “1+1=${1+1}”,看看效果:

太 TM 神奇了,居然幫我運算出來了,返回 "message": "Invalid params: 1+1=2"

問題就出現在實現自定義註解進行校驗的這行代碼(如下圖所示):

其實,最開始的時候,這裏直接返回了“Invalid params”,當初為了更好的用戶體驗,要明確告訴用戶哪個參數沒有通過校驗,因此在輸出的提示上加上了用戶輸入的字段,也就是上面的"Invalid params: " + s,沒想到,這闖了大禍了(回過頭來想,感覺這裏沒必要這麼詳細啊,因為前端已經有相應的校驗了,正常情況下回攔住,針對不守規矩的用非常規手段來的接口請求,直接返回校驗不通過就行了,畢竟不是對外提供的 OpenAPI 服務)。

仔細看,這個方法實際上是 ConstraintValidatorContext這個接口中聲明的,看方法名字其實能知道輸入參數是一個字符串模板,內部會進行解析替換的(這其實也符合“見名知意”的良好編程習慣)。(教訓:大家應該把握好自己寫的每一行代碼背後實際在做什麼。)

/* ......
 * @param messageTemplate new un-interpolated constraint message
 * @return returns a constraint violation builder
 */
ConstraintViolationBuilder buildConstraintViolationWithTemplate(String messageTemplate);

 

這個 case,源碼調試進去之後,就能跟蹤到執行翻譯階段,在如下方法中: org.hibernate.validator.messageinterpolation.AbstractMessageInterpolator.interpolateMessage

再往後,就是表達式求值了。

以為就這樣就完了嗎?

剛開始感覺,能幫忙算簡單的運算規則也就完了吧,你還能把我怎麼樣?其實這個相當於暴露了一個入口,支持用戶輸入任意 EL 表達式進行執行。網上通過關鍵字 “SpEL表達式注入漏洞” 找找,就能發現事情並沒有想象中那麼簡單。

我們構造恰當的 EL 表達式(注意各種轉義,下文的輸入參數相對比較明顯在做什麼了,實際上還有更多黑科技,比如各種二進制轉義編碼啊等等),就能直接執行輸入代碼,例如:可以直接執行命令,“ls -al”, 返回了一個 UNIXProcess 實例,命令已經被執行過了。

比如,我們執行個打開計算器的命令,搞個計算器玩玩~

我錄製了一個動圖,來個演示可能更生動一些。

這還得了嗎?這相當於提供了一個 webshell 的功能呀,你看想運行啥命令就能運行啥命令,例如 ping 本人博客地址(ping www.tanglei.name),下面動圖演示一下整個過程(從運行 ping 到 kill ping)。

我錄製了一個視頻,點擊這裏可以訪問。

豈不是直接創建一個用戶,然後遠程登錄就可以了。後果很嚴重啊,別人想幹嘛就幹嘛了。

我們跟蹤下對應的代碼,看看內部實現,就會“恍然大悟”了。

經驗教訓

幸虧這個漏洞被扼殺在搖籃里,否則後果還真的挺嚴重的。通過這個案例,我們有啥經驗和教訓呢?那就是作為程序員,我們要對每一行代碼都保持“敬畏”之心。也許就是因為你的不經意的一行代碼就帶來了嚴重的安全漏洞,要是不小心被壞人利用,輕則……重則……(自己想象吧)

此外,我們也應該看到,程序員需要對常見的安全漏洞(例如XSS/CSRF/SQL注入等等)有所了解,並且要有足夠的安全意識(其實有時候研究一些安全問題還挺好玩的,比如這篇《RSA算法及一種”旁門左道”的攻擊方式》就比較有趣)。例如:

  • 用戶權限分離:運行程序的用戶不應該用 root,例如新建一個“web”或者“www”之類的用戶,並設置該用戶的權限,比如不能有可執行 xx 的權限之類的。本文 case,如果權限進行了分離(遵循最小權限原則),應該也不會這麼嚴重。(本文就剛好是因為是測試環境,所以沒有強制實施)
  • 任何時候都不要相信用戶的輸入,必須對用戶輸入的進行校驗和過濾,又特別是針對公網上的應用。
  • 敏感信息加密保存。退一萬步講,假設攻擊者攻入了你的服務器,如果這個時候,你的數據庫賬戶信息等配置都直接明文保存在服務器中。那數據庫也被脫走了。

如果可能的話,需要對開發者的代碼進行漏洞掃描。一些常見的安全漏洞現在應該是有現成的工具支持的。另外,讓專業的人做專業的事情,例如要有安全團隊,可能你會說你們公司沒有不也活的好好的,哈哈,只不過可能還沒有被壞人盯上而已,壞人也會考慮到他們的成本和預期收益的,當然這就更加對我們開發者提高了要求。一些敏感權限盡量控制在少部分人手中,配合相應的流程來支撐(不得不說,大公司繁瑣的流程還是有一定道理的)。

畢竟我不是專業研究Web安全的,以上說得可能也不一定對,如果你有不同意見或者更好的建議歡迎留言參与討論。

這篇文章從寫代碼做實驗,到錄屏做視頻動圖等等耗時還蠻久的(好幾個周末的時間呢),原創真心不易,希望你能幫我個小忙唄,如果本文內容你覺得有所啟發,有所收穫,請幫忙點個“在看”唄,或者轉發分享讓更多的小夥伴看到。

精彩推薦
  • 一個由跨平台產生的浮點數bug | 有你意想不到的結果。
  • RSA算法及一種”旁門左道”的攻擊方式。
  • 震驚! 阿里的程序員也不過如此,竟被一個簡單的 SQL 查詢難住。
  • 面了7輪 Google,最終還是逃不脫被掛的命運。

文章首發於本人微信公眾號(ID:tangleithu),請感興趣的同學關注我的微信公眾號,及時獲取技術乾貨。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※超省錢租車方案

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

※推薦台中搬家公司優質服務,可到府估價

分類
發燒車訊

03 . Prometheus監控容器和HTTP探針應用

Eeporter是什麼及來源?

是什麼?

廣義上講所有可以向Prometheus提供監控樣本數據的程序都可以被稱為一個Exporter。而Exporter的一個實例稱為target,如下所示,Prometheus通過輪詢的方式定期從這些target中獲取樣本數據:

來源有哪些?

社區提供的

Prometheus社區提供了豐富的Exporter實現,涵蓋了從基礎設施,中間件以及網絡等各個方面的監控功能。這些Exporter可以實現大部分通用的監控需求。下錶列舉一些社區中常用的Exporter:

範圍 常用Exporter
數據庫 MySQL Exporter, Redis Exporter, MongoDB Exporter, MSSQL Exporter等
硬件 Apcupsd Exporter,IoT Edison Exporter, IPMI Exporter, Node Exporter等
消息隊列 Beanstalkd Exporter, Kafka Exporter, NSQ Exporter, RabbitMQ Exporter等
存儲 Ceph Exporter, Gluster Exporter, HDFS Exporter, ScaleIO Exporter等
HTTP服務 Apache Exporter, HAProxy Exporter, Nginx Exporter等
API服務 AWS ECS Exporter, Docker Cloud Exporter, Docker Hub Exporter, GitHub Exporter等
日誌 Fluentd Exporter, Grok Exporter等
監控系統 Collectd Exporter, Graphite Exporter, InfluxDB Exporter, Nagios Exporter, SNMP Exporter等
其他 Blockbox Exporter, JIRA Exporter, Jenkins Exporter, Confluence Exporter等

用戶自定義的

除了直接使用社區提供的Exporter程序以外,用戶還可以基於Prometheus提供的Client Library創建自己的Exporter程序,目前Promthues社區官方提供了對以下編程語言的支持:Go、Java/Scala、Python、Ruby。同時還有第三方實現的如:Bash、C++、Common Lisp、Erlang,、Haskeel、Lua、Node.js、PHP、Rust等。

Exporter的運行方式

從Exporter的運行方式來講,又可以分為

獨立使用的

以我們已經使用過的Node Exporter為例,由於操作系統本身並不直接支持Prometheus,同時用戶也無法通過直接從操作系統層面上提供對Prometheus的支持。因此,用戶只能通過獨立運行一個程序的方式,通過操作系統提供的相關接口,將系統的運行狀態數據轉換為可供Prometheus讀取的監控數據。 除了Node Exporter以外,比如MySQL Exporter、Redis Exporter等都是通過這種方式實現的。 這些Exporter程序扮演了一个中間代理人的角色。

集成到應用中的

為了能夠更好的監控系統的內部運行狀態,有些開源項目如Kubernetes,ETCD等直接在代碼中使用了Prometheus的Client Library,提供了對Prometheus的直接支持。這種方式打破的監控的界限,讓應用程序可以直接將內部的運行狀態暴露給Prometheus,適合於一些需要更多自定義監控指標需求的項目。

Exporter規範

所有的Exporter程序都需要按照Prometheus的規範,返回監控的樣本數據。以Node Exporter為例,當訪問/metrics地址時會返回以下內容:

# HELP node_cpu Seconds the cpus spent in each mode.
# TYPE node_cpu counter
node_cpu{cpu="cpu0",mode="idle"} 362812.7890625
# HELP node_load1 1m load average.
# TYPE node_load1 gauge
node_load1 3.0703125

這是一種基於文本的格式規範,在Prometheus 2.0之前的版本還支持Protocol buffer規範。相比於Protocol buffer文本具有更好的可讀性,以及跨平台性。Prometheus 2.0的版本也已經不再支持Protocol buffer。

Exporter返回的樣本數據,主要由三個部分組成:樣本的一般註釋信息(HELP),樣本的類型註釋信息(TYPE)和樣本。Prometheus會對Exporter響應的內容逐行解析:

如果當前行以# HELP開始,Prometheus將會按照以下規則對內容進行解析,得到當前的指標名稱以及相應的說明信息:

# HELP <metrics_name> <doc_string>

如果當前行以# TYPE開始,Prometheus會按照以下規則對內容進行解析,得到當前的指標名稱以及指標類型:

# TYPE <metrics_name> <metrics_type>

TYPE註釋行必須出現在指標的第一個樣本之前。如果沒有明確的指標類型需要返回為untyped。 除了# 開頭的所有行都會被視為是監控樣本數據。 每一行樣本需要滿足以下格式規範:

metric_name [
  "{" label_name "=" `"` label_value `"` { "," label_name "=" `"` label_value `"` } [ "," ] "}"
] value [ timestamp ]

其中metric_name和label_name必須遵循PromQL的格式規範要求。value是一個float格式的數據,timestamp的類型為int64(從1970-01-01 00:00:00以來的毫秒數),timestamp為可選默認為當前時間。具有相同metric_name的樣本必須按照一個組的形式排列,並且每一行必須是唯一的指標名稱和標籤鍵值對組合。

需要特別注意的是對於histogram和summary類型的樣本。需要按照以下約定返回樣本數據:

1 . 類型為summary或者histogram的指標x,該指標所有樣本的值的總和需要使用一個單獨的x_sum指標表示

2 . 類型為summary或者histogram的指標x,該指標所有樣本的總數需要使用一個單獨的x_count指標表示。

3 . 對於類型為summary的指標x,其不同分位數quantile所代表的樣本,需要使用單獨的x{quantile=”y”}表示。

4 . 對於類型histogram的指標x為了表示其樣本的分佈情況,每一個分佈需要使用x_bucket{le=”y”}表示,其中y為當前分佈的上位數。同時必須包含一個樣本x_bucket{le=”+Inf”},並且其樣本值必須和x_count相同。

5 . 對於histogram和summary的樣本,必須按照分位數quantile和分佈le的值的遞增順序排序。

以下是類型為histogram和summary的樣本輸出示例

# A histogram, which has a pretty complex representation in the text format:
# HELP http_request_duration_seconds A histogram of the request duration.
# TYPE http_request_duration_seconds histogram
http_request_duration_seconds_bucket{le="0.05"} 24054
http_request_duration_seconds_bucket{le="0.1"} 33444
http_request_duration_seconds_bucket{le="0.2"} 100392
http_request_duration_seconds_bucket{le="+Inf"} 144320
http_request_duration_seconds_sum 53423
http_request_duration_seconds_count 144320

# Finally a summary, which has a complex representation, too:
# HELP rpc_duration_seconds A summary of the RPC duration in seconds.
# TYPE rpc_duration_seconds summary
rpc_duration_seconds{quantile="0.01"} 3102
rpc_duration_seconds{quantile="0.05"} 3272
rpc_duration_seconds{quantile="0.5"} 4773
rpc_duration_seconds_sum 1.7560473e+07
rpc_duration_seconds_count 2693

指定樣式格式的版本
在Exporter響應的HTTP頭信息中,可以通過Content-Type指定特定的規範版本,例如:

HTTP/1.1 200 OK
Content-Encoding: gzip
Content-Length: 2906
Content-Type: text/plain; version=0.0.4
Date: Sat, 17 Mar 2018 08:47:06 GMT

其中version用於指定Text-based的格式版本,當沒有指定版本的時候,默認使用最新格式規範的版本。同時HTTP響應頭還需要指定壓縮格式為gzip。

容器監控

Docker是一個開源的應用容器引擎,讓開發者可以打包他們的應用以及依賴包到一個可移植的容器中,然後發布到任何流行的Linux/Windows/Mac機器上。容器鏡像正成為一個新的標準化軟件交付方式。

例如,可以通過一下命令快速在本地啟動一個Nginx服務:

安裝docker
# 安裝一些必要的系統工具
sudo yum install -y yum-utils device-mapper-persistent-data lvm2
# 添加軟件源信息
# docker 官方源
sudo yum-config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo

# 阿里雲源
sudo yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo

sudo yum makecache fast

# CentOS7安裝 Docker-ce
yum -y install docker-ce   


mkdir /etc/docker
vim /etc/docker/daemon.json
{
"registry-mirrors": ["https://registry.docker-cn.com"]
}

# 啟動Docker後台服務
systemctl start docker && systemctl enable docker
systemctl daemon-reload                 # 守護進程重啟

# 運行一個nginx做測試
docker run -itd nginx

為了能夠獲取到Docker容器的運行狀態,用戶可以通過Docker的stats命令獲取到當前主機上運行容器的統計信息,可以查看容器的CPU利用率、內存使用量、網絡IO總量以及磁盤IO總量等信息。

docker stats
CONTAINER           CPU %      MEM USAGE / LIMIT     MEM %      NET I/O         BLOCK I/O   PIDS
9a1648bec3b2        0.30%      196KiB / 3.855GiB     0.00%      828B / 0B       827kB / 0B  1
# 除了使用命令以外,用戶還可以通過docker提供的http api查看容器的監控統計信息.

使用CAdvisor

CAdvisor是Google開源的一款用於展示和分析容器運行狀態的可視化工具。通過在主機上運行CAdvisor用戶可以輕鬆的獲取到當前主機上容器的運行統計信息,並以圖表的形式向用戶展示。

在本地運行CAdvisor也非常簡單,直接運行一下命令即可:

docker run \
  --volume=/:/rootfs:ro \
  --volume=/var/run:/var/run:rw \
  --volume=/sys:/sys:ro \
  --volume=/var/lib/docker/:/var/lib/docker:ro \
  --publish=8080:8080 \
  --detach=true \
  --name=cadvisor \
  google/cadvisor:latest
# 通過訪問http://localhost:8080可以查看,當前主機上容器的運行狀態.

CAdvisor是一個簡單易用的工具,相比於使用Docker命令行工具,用戶不用再登錄到服務器中即可以可視化圖表的形式查看主機上所有容器的運行狀態。

而在多主機的情況下,在所有節點上運行一個CAdvisor再通過各自的UI查看監控信息顯然不太方便,同時CAdvisor默認只保存2分鐘的監控數據。好消息是CAdvisor已經內置了對Prometheus的支持。訪問http://localhost:8080/metrics即可獲取到標準的Prometheus監控樣本輸出:

下面列舉了一些CAdvisor中獲取的典型監控指標

指標名稱 類型 含義
gauge 再過去10秒內容器CPU的平均負載
container_cpu_usage_seconds_total
指標名稱 類型 含義
container_cpu_load_average_10s gauge 過去10秒內容器CPU的平均負載
container_cpu_usage_seconds_total counter 容器在每個CPU內核上的累積佔用時間 (單位:秒)
container_cpu_system_seconds_total counter System CPU累積佔用時間(單位:秒)
container_cpu_user_seconds_total counter User CPU累積佔用時間(單位:秒)
container_fs_usge_bytes gauge 容器中文件系統的使用量(單位:字節)
container_network_receive_bytes_total counter 容器網絡累計接受數據總量(單位: 字節)
container_network_transmit_bytes_total counter 容器網絡累計傳輸數據總量(單位: 字節)

與Prometheus集成

修改/etc/prometheus/prometheus.yml,將cAdvisor添加監控數據採集任務目標當中:

  - job_name: 'docker'
    static_configs:
    - targets: ['172.19.0.27:8080']

systemctl restart prometheus

啟動Prometheus服務,可以在Prometheus UI中看到當前所有的Target狀態:

當能夠正常採集到cAdvisor的樣本數據后,可以通過一下錶達式計算容器的CPU使用率.

sum(irate(container_cpu_usage_seconds_total{image!=""}[1m])) without (cpu)

查詢容器內存使用量(單位: 字節)

container_memory_usage_bytes{image!=""}

查詢容器網絡接收量速率(單位: 字節/秒)

sum(rate(container_network_receive_bytes_total{image!=""}[1m])) without (interface)

查詢容器網絡傳輸量速率

sum(rate(container_network_transmit_bytes_total{image!=""}[1m])) without (interface)

查詢容器文件系統讀取速率

sum(rate(container_fs_reads_bytes_total{image!=""}[1m])) without (device)

# 為了方便看出效果,我們使用dd命令
docker exec -it 628d /bin/bash
dd if=/dev/zero of=test bs=1M count=1000

  • 查詢容器文件系統寫入速率(單位: 字節/秒)
sum(rate(container_fs_writes_bytes_total{image!=""}[1m])) without (device)

Prometheus網絡探測

接下來我們主要介紹Prometheus下如何進行白盒監控,我們之前監控主機的資源用量、容器的運行狀態、數據庫中間件的運行數據。 這些都是支持業務和服務的基礎設施,通過白盒能夠了解其內部的實際運行狀態,通過對監控指標的觀察能夠預判可能出現的問題,從而對潛在的不確定因素進行優化。而從完整的監控邏輯的角度,除了大量的應用白盒監控以外,還應該添加適當的黑盒監控。
黑盒監控即以用戶的身份測試服務的外部可見性,常見的黑盒監控包括HTTP探針、TCP探針等用於檢測站點或者服務的可訪問性,以及訪問效率等。

黑盒監控相較於白盒監控最大的不同在於黑盒監控是以故障為導向當故障發生時,黑盒監控能快速發現故障,而白盒監控則側重於主動發現或者預測潛在的問題。一個完善的監控目標是要能夠從白盒的角度發現潛在問題,能夠在黑盒的角度快速發現已經發生的問題。

安裝Blackbox Exporter

Blackbox Exporter是Prometheus社區提供的官方黑盒監控解決方案,其允許用戶通過:HTTP、HTTPS、DNS、TCP以及ICMP的方式對網絡進行探測。用戶可以直接使用go get命令獲取Blackbox Exporter源碼並生成本地可執行文件:

下載安裝blackbox_exporter

wget https://github.com/prometheus/blackbox_exporter/releases/download/v0.16.0/blackbox_exporter-0.16.0.linux-amd64.tar.gz

tar xvf blackbox_exporter-0.16.0.linux-amd64.tar.gz -C /usr/local/prometheus/
mv blackbox_exporter-0.16.0.linux-amd64/ blackbox_exporter
useradd prometheus
chown -R prometheus:prometheus /usr/local/prometheus/

vim /usr/lib/systemd/system/blackbox_exporter.service
[Unit]
Description=blackbox_exporter
After=network.target

[Service]
Type=simple
User=prometheus
ExecStart=/usr/local/prometheus/blackbox_exporter/blackbox_exporter --config.file=/usr/local/prometheus/blackbox_exporter/blackbox.yml
Restart=on-failure

[Install]
WantedBy=multi-user.target

systemctl enable blackbox_exporter.service
systemctl start blackbox_exporter.service

運行Blackbox Exporter時,需要用戶提供探針的配置信息,這些配置信息可能是一些自定義的HTTP頭信息,也可能是探測時需要的一些TSL配置,也可能是探針本身的驗證行為。在Blackbox Exporter每一個探針配置稱為一個module,並且以YAML配置文件的形式提供給Blackbox Exporter。 每一個module主要包含以下配置內容,包括探針類型(prober)、驗證訪問超時時間(timeout)、以及當前探針的具體配置項:

# 探針類型:http、 tcp、 dns、 icmp.
prober: <prober_string>
# 超時時間
[ timeout: <duration> ]
# 探針的詳細配置,最多只能配置其中的一個
[ http: <http_probe> ]
[ tcp: <tcp_probe> ]
[ dns: <dns_probe> ]
[ icmp: <icmp_probe> ]

下面是一個簡化的探針配置文件blockbox.yml,包含兩個HTTP探針配置項

modules:
  http_2xx:
    prober: http
    http:
      method: GET
  http_post_2xx:
    prober: http
    http:
      method: POST

通過運行一下命令,並指定使用的探針設置文件啟動Blockbox Exporter實例:

blackbox_exporter --config.file=/etc/prometheus/blackbox.yml
or
systemctl restart blackbox_exporter.service

啟動成功后,就可以通過訪問http://172.19.0.27:9115/probe?module=http_2xx&target=baidu.com對baidu.com進行探測。這裏通過在URL中提供module參數指定了當前使用的探針,target參數指定探測目標,探針的探測結果通過Metrics的形式返回:

# HELP probe_dns_lookup_time_seconds Returns the time taken for probe dns lookup in seconds
# TYPE probe_dns_lookup_time_seconds gauge
probe_dns_lookup_time_seconds 0.004359875
# HELP probe_duration_seconds Returns how long the probe took to complete in seconds
# TYPE probe_duration_seconds gauge
probe_duration_seconds 0.046153996
# HELP probe_failed_due_to_regex Indicates if probe failed due to regex
# TYPE probe_failed_due_to_regex gauge
probe_failed_due_to_regex 0
# HELP probe_http_content_length Length of http content response
# TYPE probe_http_content_length gauge
probe_http_content_length 81
# HELP probe_http_duration_seconds Duration of http request by phase, summed over all redirects
# TYPE probe_http_duration_seconds gauge
probe_http_duration_seconds{phase="connect"} 0.00105657
probe_http_duration_seconds{phase="processing"} 0.039457402
probe_http_duration_seconds{phase="resolve"} 0.004359875
probe_http_duration_seconds{phase="tls"} 0
probe_http_duration_seconds{phase="transfer"} 0.000337184
# HELP probe_http_last_modified_timestamp_seconds Returns the Last-Modified HTTP \
response header in unixtime
# TYPE probe_http_last_modified_timestamp_seconds gauge
probe_http_last_modified_timestamp_seconds 1.26330408e+09
# HELP probe_http_redirects The number of redirects
# TYPE probe_http_redirects gauge
probe_http_redirects 0
# HELP probe_http_ssl Indicates if SSL was used for the final redirect
# TYPE probe_http_ssl gauge
probe_http_ssl 0
# HELP probe_http_status_code Response HTTP status code
# TYPE probe_http_status_code gauge
probe_http_status_code 200
# HELP probe_http_uncompressed_body_length Length of uncompressed response body
# TYPE probe_http_uncompressed_body_length gauge
probe_http_uncompressed_body_length 81
# HELP probe_http_version Returns the version of HTTP of the probe response
# TYPE probe_http_version gauge
probe_http_version 1.1
# HELP probe_ip_protocol Specifies whether probe ip protocol is IP4 or IP6
# TYPE probe_ip_protocol gauge
probe_ip_protocol 4
# HELP probe_success Displays whether or not the probe was a success
# TYPE probe_success gauge
probe_success 1

從返回的樣本中,用戶可以獲取站點的DNS解析耗時,站點響應時間,HTTP響應狀態碼等等和站點訪問質量相關的監控指標,從而幫助管理員主動的發現故障和問題.

Prometheus集成

接下來,只需要在Prometheus下配置對Blockbox Exporter實例的採集任務即可、最直觀的配置方式.

  - job_name: 'baidu_http2xx_probe'
    params:
      module:
      - http_2xx
      target:
      - baidu.com
    metrics_path: /probe
    static_configs:
    - targets: ['172.19.0.27:9115']

  - job_name: 'prometheus_http2xx_probe'
    params:
      module:
      - http_2xx
      target:
      - prometheus.io
    metrics_path: /probe
    static_configs:
    - targets: ['172.19.0.27:9115']

systemctl restart prometheus

這裏分別配置了名為baidu_http2x_probe和prometheus_http2xx_probe的採集任務,並且通過params指定使用的探針(module)以及探測目標(target).

那問題就來了,假如我們有N個目標站點且都需要M種探測方式,那麼Prometheus中將包含N * M個採集任務,從配置管理的角度來說顯然是不可接受的。這裏我們也可以採用Relabling的方式對這些配置進行簡化,配置方式如下:

  - job_name: 'blackbox'
    metrics_path: /probe
    params:
      module: [http_2xx]
    static_configs:
      - targets:
        - http://prometheus.io    # Target to probe with http.
        - https://prometheus.io   # Target to probe with https.
        - http://example.com:8080 # Target to probe with http on port 8080.
    relabel_configs:
      - source_labels: [__address__]
        target_label: __param_target
      - source_labels: [__param_target]
        target_label: instance
      - target_label: __address__
        replacement: 172.19.0.27:9115

這裏針對每一個探針服務(如http_2xx)定義一個採集任務,並且直接將任務的採集目標定義為我們需要探測的站點,在採集樣本數據之前通過relabel_configs對採集任務進行動態配置.

* 第一步, 根據Target實例的地址,寫入__param_target標籤中,__param_<name>形式的標籤來表示,
	# 在採集任務時會在請求目標地址中添加<name>參數,等同於params的設置.
* 第二步,  獲取__param_target的值,並覆寫到instance標籤中.
* 第三步,  覆寫Target實例的__address__標籤值為BlockBox Exporter實例的訪問地址.

HTTP探針

HTTP探針是進行黑盒監控時最常用的探針之一,通過HTTP探針能夠網站或者HTTP服務建立有效的監控,包括其本身的可用性,以及用戶體驗相關的如響應時間等等。除了能夠在服務出現異常的時候及時報警,還能幫助系統管理員分析和優化網站體驗。

Blockbox Exporter中所有的探針均是以Module的信息進行配置。如下所示,配置了一個最簡單的HTTP探針:

modules:
  http_2xx_example:
    prober: http
    http:

通過prober配置項指定探針類型。配置項http用於自定義探針的探測方式,這裡有沒對http配置項添加任何配置,表示完全使用HTTP探針的默認配置,該探針將使用HTTP GET的方式對目標服務進行探測,並且驗證返回狀態碼是否為2XX,是則表示驗證成功,否則失敗。

自定義HTTP請求

HTTP服務通常會以不同的形式對外展現,有些可能就是一些簡單的網頁,而有些則可能是一些基於REST的API服務。 對於不同類型的HTTP的探測需要管理員能夠對HTTP探針的行為進行更多的自定義設置,包括:HTTP請求方法、HTTP頭信息、請求參數等。對於某些啟用了安全認證的服務還需要能夠對HTTP探測設置相應的Auth支持。對於HTTPS類型的服務還需要能夠對證書進行自定義設置。

如下所示,這裏通過method定義了探測時使用的請求方法,對於一些需要請求參數的服務,還可以通過headers定義相關的請求頭信息,使用body定義請求內容:

http_post_2xx:
    prober: http
    timeout: 5s
    http:
      method: POST
      headers:
        Content-Type: application/json
      body: '{}'

如果HTTP服務啟用了安全認證,Blockbox Exporter內置了對basic_auth的支持,可以直接設置相關的認證信息即可:

http_basic_auth_example:
    prober: http
    timeout: 5s
    http:
      method: POST
      headers:
        Host: "login.example.com"
      basic_auth:
        username: "username"
        password: "mysecret"

對於使用了Bear Token的服務也可以通過bearer_token配置項直接指定令牌字符串,或者通過bearer_token_file指定令牌文件。

對於一些啟用了HTTPS的服務,但是需要自定義證書的服務,可以通過tls_config指定相關的證書信息:

 http_custom_ca_example:
    prober: http
    http:
      method: GET
      tls_config:
        ca_file: "/certs/my_cert.crt"
  • 自定義探針行為
  • 在默認情況下HTTP探針只會對HTTP返回狀態碼進行校驗,如果狀態碼為2XX(200 <= StatusCode < 300)則表示探測成功,並且探針返回的指標probe_success值為1。
  • 如果用戶需要指定HTTP返回狀態碼,或者對HTTP版本有特殊要求,如下所示,可以使用valid_http_versions和valid_status_codes進行定義:
  http_2xx_example:
    prober: http
    timeout: 5s
    http:
      valid_http_versions: ["HTTP/1.1", "HTTP/2"]
      valid_status_codes: []

默認情況下,Blockbox返回的樣本數據中也會包含指標probe_http_ssl,用於表明當前探針是否使用了SSL:

# HELP probe_http_ssl Indicates if SSL was used for the final redirect
# TYPE probe_http_ssl gauge
probe_http_ssl 0

而如果用戶對於HTTP服務是否啟用SSL有強制的標準。則可以使用fail_if_ssl和fail_if_not_ssl進行配置。fail_if_ssl為true時,表示如果站點啟用了SSL則探針失敗,反之成功。fail_if_not_ssl剛好相反。

  http_2xx_example:
    prober: http
    timeout: 5s
    http:
      valid_status_codes: []
      method: GET
      no_follow_redirects: false
      fail_if_ssl: false
      fail_if_not_ssl: false

除了基於HTTP狀態碼,HTTP協議版本以及是否啟用SSL作為控制探針探測行為成功與否的標準以外,還可以匹配HTTP服務的響應內容。使用fail_if_matches_regexp和fail_if_not_matches_regexp用戶可以定義一組正則表達式,用於驗證HTTP返回內容是否符合或者不符合正則表達式的內容。

  http_2xx_example:
    prober: http
    timeout: 5s
    http:
      method: GET
      fail_if_matches_regexp:
        - "Could not connect to database"
      fail_if_not_matches_regexp:
        - "Download the latest version here"

最後需要提醒的時,默認情況下HTTP探針會走IPV6的協議。 在大多數情況下,可以使用preferred_ip_protocol=ip4強制通過IPV4的方式進行探測。在Bloackbox響應的監控樣本中,也會通過指標probe_ip_protocol,表明當前的協議使用情況:

# HELP probe_ip_protocol Specifies whether probe ip protocol is IP4 or IP6
# TYPE probe_ip_protocol gauge
probe_ip_protocol 6

除了支持對HTTP協議進行網絡探測以外,Blackbox還支持對TCP、DNS、ICMP等其他網絡協議![]

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※回頭車貨運收費標準

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

分類
發燒車訊

工業轉型與綠色振興聲明 就政策、技術、金融三個領域提出建言

文:台大風險政策中心 RSPRC;林怡均翻譯;趙家緯審校

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

網頁設計最專業,超強功能平台可客製化

※別再煩惱如何寫文案,掌握八大原則!

分類
發燒車訊

LeetCode 76,一題教會你面試算法時的思考套路

本文始發於個人公眾號:TechFlow,原創不易,求個關注

今天是LeetCode專題的第45篇文章,我們一起來看看LeetCode的76題,最小窗口子串Minimum Window Substring。

這題的官方難度是Hard,通過了也是34.2%,4202人點贊,299人反對。從通過率以及點贊比來看,這題的質量很高,稍稍有些偏難,所以小夥伴們請做好準備,這是一道有點挑戰的問題。

題意和樣例

我們一起來看下題意,這題的題意很短,給定兩個字符串S和T。要求設計一個複雜度為的算法,在S串當中找到一個子串,能夠包含T串當中的所有字符。要求返回合法且長度最小的窗口的內容。

注意:

  • 如果不存在這樣的窗口,返回“”。
  • 如果窗口存在,題目保證有且只有一個。

樣例:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

分析

我們來分析一下這個問題,從題意當中大家應該都能感受到它的難度。因為上來題目當中就限定了我們使用的算法的複雜度必須是,然而我們遍歷字符串的複雜度就已經是了,也就是說我們不能引入額外的計算開銷,否則一定不滿足題目的要求。

可能有些同學會想到傳說中在時間內判斷字符串匹配的KMP算法,如果你不知道這個算法也沒有關係,因為這個算法並不適用。因為我們要找的不是完全相等的子串的位置,而是找的是字符構成一樣的子串,所以並不能通過引入字符串匹配算法來解決。沒有學過KMP算法的同學可以松一口氣了,這題當中並不會引入新的算法。

解題的套路

一般來說當我們面臨一個算法問題的時候,我們常常的思考過程主要有兩種。一種是適配,說白了就是把可能可以用上的算法往問題上套。根據題意先感覺一下,大概會用到什麼樣的算法,然後詳細地推導適配的過程,看看是不是真的適用或者是有什麼坑,或者是會出現什麼新的問題。如果一切OK,能夠推理得通,那麼這個算法就是解。第二種方法是建模,也就是說從題意入手,對題意進行深入的分析,對問題進行建模和抽象,找到問題的核心,從而推導出用什麼樣的算法可以解決。

舉個很簡單的例子,一般來說我們的動態規劃算法都是適配。都是我們先感覺或者是猜測出可以使用動態規劃,然後再去找狀態和轉移,最後建立狀態轉移方程。而一些搜索問題一般是建模,我們先對問題進行分析,然後找出需要搜索的解的存在空間,然後設計算法去搜索和剪枝,最後找到答案。

據說一些頂級高手這兩種方法是一起使用的,所以才可以那麼快速地找到解。當然我不是頂級高手,所以這個也只是我的猜測。這個思考過程非常有用,特別是當我們面試的時候,遇到一個從未見過的問題,如果你什麼套路也沒有,頭腦一片空白或者是苦思冥想不得要領是很常見的事情。當你有了套路之後,你就可以試着慢慢找到答案了。

回到這道題本身,我們剛才已經試過了,拿字符串匹配的算法網上套是不行的。在視野里似乎也沒有其他的算法可以套用,所以我們換一種思路,試試看建模。

首先我們可以肯定一點,我們需要在遍歷的時候找到答案,這樣才可以保證算法的複雜度是。我們的目標是尋找子串,也就是說我們遍歷的過程應該對應一個子串,並且我們有方法可以快速判斷這個子串是否合法。這樣我們才可以做到遍歷的同時判斷答案的可行性。進而可以想到這是一個區間維護的問題,區間維護我們經常使用的方法就是two pointers。所以我們可以試試two pointers能否適用。

實際上這道題的正解就是two pointers。

題解

我們維護了一個區間,我們需要判斷區間里的字符構成,這個很容易想到可以使用dict,維護每一個字符出現的次數。在這個題目當中,我們只需要考慮覆蓋的情況,也就是說字符多了並不會構成非法。所以我們可以維護一個dict,每次讀入一個字符更新它,當dict當中的字符滿足要求的時候,為了使得區間長度盡量短,我們可以試着移動區間的左側,盡量縮短區間的長度。

從區間維護的角度來說,我們每次移動區間右側一個單位,只有當區間內已經滿足題意的時候才會移動左側。通過移動左側彈出元素來獲取能夠滿足題意的最佳區間。

我們來看下主要的流程代碼:

# 存儲區間內的字符
segement = {}
for i in range(n):
    segement[s[i]] += 1
    # 當滿足條件的時候移動區間左側
    while l <= i and satisified(segment):
        # 更新最佳答案
        if i - l + 1 < ans_len:
            ans_len = i - l + 1
            beg, end = l, i + 1
        # 彈出元素
  segement[s[l]] -= 1
        l += 1

到這裏還有一個小問題,就是怎麼樣判斷這個segment是否合法呢?我們可以用一個数字matched來記錄目前已經匹配上的字符的數量。當某個字符在segment當中出現的次數和T中的次數相等的時候,matched加一。當matched的數量和T中字符種類的數量相等的時候,就可以認為已經合法了。

我們把所有的邏輯串起來,就可以通過這題了。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter, defaultdict
        # 通過Counter直接獲取T當中的字符構成
        counter = Counter(t)
        n, m = len(s), len(counter)
        l, beg, end = 0, 0, 0
        cur = defaultdict(int)
        matched = 0
        flag = False
        # 記錄合法的字符串的長度
        ans_len = 0x3f3f3f3f
        
        for i in range(n):
            if s[i] not in counter:
                continue
                
            cur[s[i]] += 1
            # 當數量匹配上的時候,matched+1
            if cur[s[i]] == counter[s[i]]:
                matched += 1
                
            # 如果已經找到了合法的區間,嘗試縮短區間的長度
            while l <= i and matched == m:
                if i - l + 1 < ans_len:
                    flag = True
                    beg, end = l, i+1
                    ans_len = i - l + 1
                    
                # 彈出左側元素
                c = s[l]
                if c in counter:
                    cur[c] -= 1
                    if cur[c] < counter[c]:
                        matched -= 1
                        
                l += 1

        
        return "" if not flag else s[beg: end]

總結

到這裏,這道題就算是解決了。很多同學可能會覺得疑惑,為什麼我們用到了兩重循環,但是它依然還是的算法呢?

這個是two pointers算法的常見問題,也是老生常談的話題了。我們在分析複雜度的時候,不能只簡單地看用到了幾層循環,而是要抓住計算的核心。比如在這個問題當中,我們內部的while循環針對的變量是l,l這個變量對於i整體是遞增的。也就是說無論外面這個循環執行多少次,裏面的這個while循環一共最多累加只能執行n次。那麼,當然這是一個的算法。

這題總體來說有些難度,特別是一開始的時候可能會覺得沒有頭緒無從下手。這個時候有一個清晰的頭腦以及靠譜的思考鏈非常重要,希望大家都能學到這個其中思維的過程,這樣以後才可以應付更多的算法問題。

如果喜歡本文,可以的話,請點個關注,給我一點鼓勵,也方便獲取更多文章。

本文使用 mdnice 排版

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!