跳躍表確定不了解下

redis源碼分析系列文章

[Redis源碼系列]在Liunx安裝和常見API 

為什麼要從Redis源碼分析 

String底層實現——動態字符串SDS 

Redis的雙向鏈表一文全知道

面試官:說說Redis的Hash底層 我:……(來自閱文的面試題)

前言

hello,大家好,周五見了。前面幾周我們一起看了Redis底層數據結構,如動態字符串SDS,雙向鏈表Adlist,字典Dict,如果有對Redis常見的類型或底層數據結構不明白的請看上面傳送門。

今天我們來看下ZSET的底層架構,如果不知道ZSET是什麼的,可以看上面傳送門第一篇。簡單來說,ZSET是Redis提供的根據數據和分數來判斷其排名的數據結構。最常見的就是微信運動的排名,每個用戶對應自己的步數,每天晚上可以給出用戶的排名。

有小夥伴可能會想,如果是實現排名的話,各種排序方法都可以實現的,沒必要引入Redis的ZSET結構啊?

當然,如果是採用排序方法的話,是可以實現相同功能的,但是代碼裏面需要硬編碼,會添加工作量,還會提供代碼的Bug哦,哈哈哈。而且Redis的底層是C實現的,直接操作內存,速度也會比Java方法實現提升。

綜上,使用Redis的ZSET結構,好處多多。那話不多說,開始把。在正式開始之前,我們需要引入下跳躍表的概念,其是ZSET結構的底層實現。以下可能有點枯燥,我盡量說的簡單點哈。

什麼是跳躍表?

對於數據量大的鏈表結構,插入和刪除比較快,但是查詢速度卻很慢。那是因為無法直接獲取某個節點,需要從頭節點開始,藉助某個節點的next指針來獲取下一節點。即使數據是有序排放的,想要查詢某個數據,只能從頭到尾遍歷變量,查詢效率會很低,時間複雜度為O(n)。

如果我們需要快速查詢鏈表有啥辦法呢?有同學說用數組存放,但是如果不改數據結構呢?

我們可以先想想在有序數組結構中有二分法,每次將範圍都縮小一半,這樣查詢速度提升了很多,那麼在鏈表中能不能也使用這種思想。

這就到了今天講的主角——跳躍表。(一點也生硬的引出概念)

步驟一  新建有序單項鏈表

先看下圖有序單向鏈表,存放了1,2,3,4,5,6,7這7個元素。

步驟二 抽取二級索引節點

我們可以在鏈表中抽取部分節點,下圖抽取了1,3,5,7四個節點,也就是每兩個節點提取了一個節點到上級,抽取出來的叫做索引。

注意不是每次都能抽取到這麼完美,這其實就跟拋硬幣一樣,每個硬幣的正反兩面的概率是一樣的,都是1/2。當數據量小的時候,正反的概率可能差別較大。但是隨着數據量的加大,正反的概率越來越接近於1/2。類比過來是一個意思,每個節點的機會都是一樣的,要麼停留原級,要麼提取到上級,概率都是1/2。但是隨着節點數量的增加,抽取的節點越來越接近與1/2。

步驟三 抽取三級索引節點

我們可以在鏈表中抽取部分節點,下圖抽取了1,5兩個節點,也就是每兩個節點提取了一個節點到上級,抽取出來的叫做索引。

步驟四 類二分法查詢

我們假設要查找值為6的節點,先從三級索引開始,找到值為1的節點,發現比5小,根據值為1節點的next指針,找到值為5的節點,5後面沒有其他的三級索引啦。

於是順着往下找,到了二級索引,根據值為5的節點的next指針找到值為7的節點,發現比6小,說明要找到的節點6在此範圍內。

再接着到了一級索引位置,根據值為5的節點next指針指向值為6的節點,發現是想要查詢的數據,所以查詢過程結束。

根據上面的查詢過程(下圖的藍色連線),我們發現其採用的核心思想是二分法,不斷縮小查詢範圍,如果在上層索引找到區間,則順延深入到下一層找到真正的數據。

總結

從上面的整個過程中可以看出,數據量小的時候,這種拿空間換時間,消耗內存方法的並不是最優解。所以Redis的zset結構在數據量小的時候採用壓縮表,數據量大的時候採用跳躍表。

像這種鏈表加多級索引的結構,就是跳躍表。這名字起的形象,過程是跳躍着來查詢的。

Redis中跳躍表圖解

下圖簡單來說是對跳躍表的改進和再封裝,首先引入了表頭的概念,這與雙向鏈表,字典結構一樣,都是對數據的封裝,因為他們都是採用的指針,而指針必然導致在計算長度,獲取最後節點的數據問題上會產生查詢太慢的性能問題,所以封裝表頭是為了在這些問題上提升速度,浪費的只是添加,刪除等操作的時間,與此對比,是可以忽略的。

其次是引入管理所有節點的層數數組,我們可以看到有32層,即32個數組,這和後面的數據節點結構是一樣的。引入它是為了便於直接根據此數組的層數定位到每個元素。

再其次是數據節點的每個level都有層級和span(也就是下圖箭頭指針上的数字,其是為了方便統計兩個節點相距多少長度)。

最後就是數據節點的後退指針backward,引入目的是Level數組只有前指針,即只能指向下一個節點地址,而後退指針是為了能往回找節點。

上圖主要分為3大塊:(這邊大致看下就行,下面將對各模塊進行代碼詳細解釋)

表頭

主要包括四個屬性,分別是頭指針header,尾指針tail,節點長度length,所有節點的最大level。

header:指向跳躍表的表頭節點,通過這個指針地址可以直接找到表頭,時間複雜度為O(1)。

tail:指向跳躍表的表尾節點,通過這個指針可以直接找到表尾,時間複雜度為O(1)。

length:記錄跳躍表的長度,即不包含表頭節點,整個跳躍表中有多少個元素。

level:記錄當前跳躍表內,所有節點層數最大的level(排除表頭節點)。

管理所有節點層數level的數組

其對象值為空,level數組為32層,目的是為了管理真正的數據節點。關於具體的level有哪些屬性放在數據節點來說。

數據節點

主要包括四個屬性對象值obj,分數score,後退指針backward和level數組。每個數據的Level數組有多少層,是隨機產生的,這跟上面說過的跳躍表是一樣的。

成員對象obj:真正的實際數據,每個節點的數據都是唯一的,但是節點的分數可能相同。兩個相同分數的節點是按照成員對象在字典中的大小進行排序的,成員對象較小的節點會排在前面,成員對象較大的節點會排在後面。

分數score:各個節點中的数字是節點所保存的分數,在跳躍表中,節點按各自所保存的分數從小到大排列。

後退指針backward:用於從表尾向表頭遍歷,每個節點只有一個後退指針,即每次只能後退一步。

層級level:節點中用1,2,3等字樣標記節點的各個層,L1代表第一層,L2代表第二層,L3代表第三層,並以此類推。

跳躍表的定義

表頭結構zskiplist

 

typedef struct zskiplist {
    //表頭的頭指針header和尾指針tail
    struct zskiplistNode *header, *tail;
    //一共有多少個節點length
    unsigned long length;
    // 所有節點最大的層級level
   int level;
} zskiplist;

具體數據節點zskiplistNode

 

//跳錶的具體節點 
typedef struct zskiplistNode {
    sds ele; //具體的數據,對應張三
    double score;//分數,對應70
    struct zskiplistNode *backward;//後退指針backward
     //層級數組    struct zskiplistLevel {
        struct zskiplistNode *forward;//前進指針forward
        unsigned int span;//跨度span
    } level[];
} zskiplistNode; 

 

跳躍表的實現(源碼分析)

redis關於跳躍表的API都定義在t_zset.c文件中。

千萬不要看到源碼分析就跑開了,一定要看哦。

創建跳躍表

創建空的跳躍表,其實就是創建表頭和管理所有的節點的level數組。首先,定義一些變量,嘗試分配內存空間。其次是初始化表頭的level和length,分別賦值1和0。接着創建管理所有節點的Level的數組,是調用zslCreateNode函數,輸入參數為數組大小宏常量ZSKIPLIST_MAXLEVEL(32),分數為0,對象值為NULL。(此為跳躍表得以實現重點)。再接着就是為此數組每個元素的前指針forword和跨度span初始化。最後初始化尾指針並返回值。

可以參照下面的圖解和源碼:

 

//創建一個空表頭的跳躍表
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    //嘗試分配內存空間
    zsl = zmalloc(sizeof(*zsl));
    //初始化level和length
    zsl->level = 1;
    zsl->length = 0;
    //調用下面的方法zslCreateNode,傳入的參數有數組長度ZSKIPLIST_MAXLEVEL 32
    //分數0,對象值NuLL
    //這一步就是創建管理所有節點的數組
    //並且設置表頭的頭頭指針為此對象的地址
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    //為這32個數組賦值前指針forward和跨度span
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    //設置尾指針
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    //返回對象
    return zsl;
}
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

 

插入節點

比如有下圖6個元素,需要插入值為趙六,分數為101的元素,我們大致想一想,大致的步驟包括找到要插入的位置新建一個數據節點,然後調整與之相關的頭尾指針的level數組。那就看看redis咋做的,和我們想的一樣不一樣呢?

噔噔噔噔,答案揭曉。當然了大框架是相同的。

正文開始了:(先來圖片)

1.遍歷管理所有節點的level數組,從最大的level開始,即3,挨個對比值,如果有分數比他大的值或者分數相同,但是數據的值比他大,記錄到數組裡面,同時記錄跨度。

這樣說太抽象了。拿上圖舉個例子,從表頭的level即3開始,首先到張三的L3,發現分數70,比目標分數101小跳過,根據其前指針找到趙六的L3,發現分數102,比目標分數101大,將趙六L3記錄在待更新數組update中,同時記錄跨度span為4。接着到下一層,張三的L2層,發現分數70比目標分數101小跳過,根據前指針找到王五的L2,發現分數90,比目標分數101小跳過,根據前指針找到趙六的L2,發現分數102比目標分數101大,將趙六的L2記錄到待更新數組update中,同時記錄跨度span為2。最後到下一層,張三的L1層,邏輯和剛才一樣的,也是記錄趙六的L1層和跨度span為1。

2.為新節點隨機生成層級數level(通過位運算),如果生成的level大於目前level最大值3,則將將大於部分挨個遍歷,並將跨度等信息記錄到上面update表中。

比如,新節點生成的level為5,目前level最大值為3,說明這個節點只會有一個,並且跨越了之前的所有節點,那麼我們將從第四層和第五層都遍歷下,記錄到待更新數組update中。

3.準備工作都做好了,找到了該節點將插入到哪一位置,處於哪一層,每層對應的跨度是多少,下面就要新增數據節點了。把上兩步的信息都添加到新節點上,並且調整位置前後指針即可。

4.最後就是一些收尾工作,比如修改表頭的層級level,節點大小length和尾指針tail等屬性。

綜上,整個流程就已經結束了。可能看着有點複雜,可以對照下面代碼來。

 

//插入節點,輸入參數為
//zsl:表頭
//score:插入元素的分數score
//ele:插入元素的具體數據ele
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    //使用update數組記錄每層待插入元素的前一個元素
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    //記錄前置節點與第一個節點之間的跨度,即元素在列表中的排名-1
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    serverAssert(!isnan(score));
    x = zsl->header;
    //從最大的level開始遍歷,從頂到底,找到每一層待插入的位置
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
    //直接找到第一個分數比該元素大的位置
    //或者分數與該元素相同但是對象的ASSICC碼比該元素大的位置
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            //將已走過元素的跨越元素進行計數,得到元素在列表中排名,或者是已搜尋的路徑長度
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
    //記錄待插入位置
        update[i] = x;
    }
     //隨機產生一個層數,在1到32之間,層數越高,生成的概率越低
    level = zslRandomLevel();
    //如果產生的層數大於現有的最高層數,則超出層數都需要初始化
    if (level > zsl->level) {
        //開始循環
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            //該元素作為這些層的第一個節點,前節點就是header
            update[i] = zsl->header;
            //初始化后這些層每層有兩個元素,走一步就是跨越所有元素
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    //創建節點
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        //將新節點插入到各層鏈表中
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        // rank[0]是第0層的前置節點P1(也就是底層插入節點前面那個節點)與第一個節點的跨度
        // rank[i]是第i層的前置節點P2(這一層里在插入節點前面那個節點)與第一個節點的跨度
        // 插入節點X與後置節點Y的跨度f(X,Y)可由以下公式計算
        // 關鍵在於f(P1,0)-f(P2,0)+1等於新節點與P2的跨度,這是因為跨度呈扇形形向下延伸到最底層
        // 記錄節點各層跨越元素情況span, 由層與層之間的跨越元素總和rank相減而得
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
               // 插入位置前一個節點的span在原基礎上加1即可(新節點在rank[0]的后一個位置)

 update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    // 第0層是雙向鏈表, 便於redis常支持逆序類查找
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

 

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

 

獲取節點排名

擔心大家忘了這張圖,再粘貼一遍。如下圖,這部分邏輯比較簡單,就不寫了,具體參考代碼分析。

 

//得到節點的排名
//輸入參數為表頭結構zsl,分數score,真正的數據ele
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;
    //先獲取表頭的頭指針,即找到管理所有節點的level數組
    x = zsl->header;
     //從表頭的level,即最大值開始循環遍歷
    for (i = zsl->level-1; i >= 0; i--) {
        //如果找到分數小於目標分數的,排名加上其跨度
        //或者分數相同,但是具體數據小於目標數據的,排名也加上跨度
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                sdscmp(x->level[i].forward->ele,ele) <= 0))) {
            rank += x->level[i].span;
            x = x->level[i].forward;
        }

        //確保在第i層找到分值相同,且對象相同時才會返回排位值
        if (x->ele && sdscmp(x->ele,ele) == 0) {
            return rank;
        }
    }
    return 0;
}

 

結語

該篇主要講了Redis的ZSET數據類型的底層實現跳躍表,先從跳躍表是什麼,引出跳躍表的概念和數據結構,剖析了其主要組成部分,進而通過多幅過程圖解釋了Redis是如何設計跳躍表的,最後結合源碼對跳躍表進行描述,如創建過程,添加節點過程,獲取某個節點排名過程,中間穿插例子和過程圖。

如果覺得寫得還行,麻煩給個贊,您的認可才是我寫作的動力!

如果覺得有說的不對的地方,歡迎評論指出。

好了,拜拜咯。

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

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

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

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

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

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

用一個圖書庫實例搞懂二分搜索樹的底層原理

目錄

  • 一、背景
  • 二、概念
    • 1、定義
    • 2、 動畫示例
  • 三、圖書庫實例
    • 3.1、項目需求
    • 3.2、代碼結構
    • 3.3、圖書類
    • 3.4、二分搜索樹的底層實現
    • 3.5、圖書庫的構建
  • 四、深入理解

一、背景

二叉樹是一種常用的數據結構,更是實現眾多算法的一把利器。本文將通過建立一個圖書庫的實例對二叉樹中的常用類型:二分搜索樹(Binary Search Tree)進行底層原理的深入理解。

二、概念

1、定義

1 二分搜索樹是一顆二叉樹
2 二分搜索樹每個節點的左子樹的值都小於該節點的值,每個節點右子樹的值都大於該節點的值
3 任意一個節點的每棵子樹都滿足二分搜索樹的定義

2、 動畫示例

三、圖書庫實例

3.1、項目需求
  • 創建一個圖書類:圖書類中需包含ISBN號,書名,作者,定價,出版社、出版日期等
  • 用二分搜索樹的數據結構創建一個圖書庫,每種圖書需有當前數量
  • 圖書庫需實現添加圖書,遍歷整個圖書庫,及可根據ISBN號進行快速查找
3.2、代碼結構

3.3、圖書類
  • 在圖書類的定義中,重寫compareTo方法:通過比較ISBN(國際標準書號)的大小表示圖書在二叉樹的結點順序。
/**
 - 用二分搜索樹實現圖書庫--圖書類
 -  - @author zhuhuix
 - @date 2020-06-23
 */
public class Books implements Serializable, Comparable {
    // ISBN
    private Long bookId;
    // 作者
    private String author;
    // 分類
    private String category;
    // 書名
    private String bookName;
    // 定價
    private BigDecimal bookPrice;
    // 出版社
    private String bookPublisher;
    // 出版時間
    private LocalDate bookDate;
    // 當前數量
    private Integer bookCount;

    public Books(Long bookId, String bookName, String category, String author, BigDecimal bookPrice, String bookPublisher, LocalDate bookDate, Integer bookCount) {
        this.bookId = bookId;
        this.author = author;
        this.category = category;
        this.bookName = bookName;
        this.bookPrice = bookPrice;
        this.bookPublisher = bookPublisher;
        this.bookDate = bookDate;
        this.bookCount = bookCount;
    }

    public Books(Long bookId){
        this.bookId= bookId;
    }

    // 通過ISBN號進行比較大小
    @Override
    public int compareTo(Object o) {
        if (o instanceof Books) {
            return this.getBookId().compareTo(((Books) o).getBookId());
        } else {
            return -1;
        }
    }

    public Long getBookId() {
        return bookId;
    }


    public Integer getBookCount() {
        return bookCount;
    }

    public void setBookCount(Integer bookCount) {
        this.bookCount += bookCount;
    }

    @Override
    public String toString() {
        return "{" +
                "ISBN=" + bookId +
                ", 書名='" + bookName + '\'' +
                ", 作者='" + author + '\'' +
                ", 分類='" + category + '\'' +
                ", 價格=" + bookPrice +
                ", 出版社='" + bookPublisher + '\'' +
                ", 出版時間=" + bookDate +
                ", 當前數量=" + bookCount +
                '}';
    }
}
3.4、二分搜索樹的底層實現
  • 底層創建內部結點類(class Node):元素,左子樹,右子樹
  • add方法:使用遞歸方法增加結點:
    如果圖書種類不存在,則創建新結點。
    如果圖書種類存在,則對數量進行累加。
  • traverse方法:使用遞歸方法對所有結點進行遍歷
  • search方法:根據ISBN碼查找結點
/**
 * 用二分搜索樹實現圖書庫--二分搜索樹
 *
 * @author zhuhuix
 * @date 2020-06-23
 */
public class BinarySearchTree {

    // 結點
    private Node root;
    // 書的種類
    private int bookSize;
    // 書的總數量
    private int bookCount;

    public BinarySearchTree() {
        this.root = null;
        this.bookSize = 0;
        this.bookCount = 0;
    }

    // 增加元素
    public void add(Books data) {
        this.root = addNode(this.root, data);
    }

    // 用遞歸方法實現結點的添加
    private Node addNode(Node node, Books data) {
        // 遞歸退出條件 書不存在拉加結點,並將結點數量加1
        if (node == null) {
            this.bookSize++;
            this.bookCount += data.getBookCount();
            return new Node(data);
        }

        if (node.data.compareTo(data) < 0) {
            node.right = addNode(node.right, data);
        } else if (node.data.compareTo(data) > 0) {
            node.left = addNode(node.left, data);
        } else if (node.data.compareTo(data) == 0) {
            // 如果結點已存在,則將書的數量累加
            this.bookCount += data.getBookCount();
            node.getData().setBookCount(data.getBookCount());
        }
        return node;
    }

    // 用遞歸方法實現結點前序遍歷
    public void traverse(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.getData().toString());
        traverse(node.left);
        traverse(node.right);
    }

    // 用遞歸方法實現通過isbn查找圖書
    public Books search(Long isbn) {
        Node node = nodeSearch(this.root, new Books(isbn));
        if (node != null) {
            return node.getData();
        } else {
            return null;
        }
    }

    private Node nodeSearch(Node node, Books books) {
        if (node == null) {
            return null;
        }
        if (books.compareTo(node.getData()) == 0) {
            return node;
        } else if (books.compareTo(node.getData()) < 0) {
            return nodeSearch(node.left, books);
        } else {
            return nodeSearch(node.right, books);
        }
    }

    public Node getRoot() {
        return root;
    }

    // 返回書的種類數
    public int getBookSize() {
        return bookSize;
    }

    // 返回書的總數量
    public int getBookCount() {
        return bookCount;
    }

    // 私有內部類-樹結點
    private class Node {
        Books data;
        Node left, right;

        Node(Books data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }

        Books getData() {
            return data;
        }
    }
}

3.5、圖書庫的構建
  1. 構建一棵二分搜索樹;
  2. 將京東十大暢銷圖書加入二分搜索樹;
  3. 統計圖書種類及數量,並遍歷輸出;
  4. 加入3種已經進入圖書庫的圖書;
  5. 再次統計圖書種類及數量,並遍歷輸出;
  6. 根據某個ISBN號查找圖書。
/**
 * 用二分搜索樹實現圖書庫
 *
 * @author zhuhuix
 * @date 2020-06-23
 */
public class BookStore {
    public static void main(String[] args) {

        // 構建一棵二分搜索樹
        BinarySearchTree bst = new BinarySearchTree();

        // 將十大暢銷圖書加入二分搜索樹
        bst.add(new Books(9787115428028L,"Python編程 從入門到實踐",
                "編程語言與程序設計","埃里克·馬瑟斯",
                BigDecimal.valueOf(61.40),"人民郵電出版社",
                LocalDate.of(2017,07,01),1));

        bst.add(new Books(9787115525963L,"說服力 工作型PPT該這樣做",
                "辦公軟件","秦陽",
                BigDecimal.valueOf(66.30),"人民郵電出版社",
                LocalDate.of(2020,05,01),1));

        bst.add(new Books(9787569222258L,"零基礎學Python(全彩版)",
                "編程語言與程序設計","明日科技",
                BigDecimal.valueOf(67.00),"吉林大學出版社",
                LocalDate.of(2018,04,01),1));

        bst.add(new Books(9787121388361L,"PS之光:一看就懂的Photoshop攻略(全彩)",
                "圖形圖像/多媒體","馮注龍",
                BigDecimal.valueOf(60.70),"电子工業出版社",
                LocalDate.of(2020,06,01),1));

        bst.add(new Books(9787302423287L,"機器學習",
                "人工智能","周志華",
                BigDecimal.valueOf(64.80),"清華大學出版社",
                LocalDate.of(2016,01,01),1));

        bst.add(new Books(9787111641247L,"深入理解Java虛擬機:JVM高級特性與最佳實踐(第3版)",
                "編程語言與程序設計","周志明",
                BigDecimal.valueOf(106.40),"机械工業出版社",
                LocalDate.of(2019,12,01),1));

        bst.add(new Books(9787115472588L,"鳥哥的Linux私房菜 基礎學習篇 第四版",
                "操作系統","鳥哥",
                BigDecimal.valueOf(93.00),"人民郵電出版社",
                LocalDate.of(2018,10,01),1));

        bst.add(new Books(9787115293800L,"算法(第4版)",
                "編程語言與程序設計","Robert Sedgewick,Kevin Wayne",
                BigDecimal.valueOf(66.30),"人民郵電出版社",
                LocalDate.of(2012,10,01),1));

        bst.add(new Books(9787115537973L,"數學之美 第三版",
                "計算機理論、基礎知識","吳軍",
                BigDecimal.valueOf(54.40),"人民郵電出版社",
                LocalDate.of(2020,05,01),1));

        bst.add(new Books(9787302255659L,"大話數據結構",
                "編程語言與程序設計","程傑",
                BigDecimal.valueOf(47.20),"清華大學出版社",
                LocalDate.of(2011,06,01),1));

        // 遍歷圖書庫
        System.out.println("圖書庫新建:");
        System.out.println("書的種類數:"+bst.getBookSize());
        System.out.println("書的總數量:"+bst.getBookCount());
        bst.traverse(bst.getRoot());

        // 再次增加相同的書
        bst.add(new Books(9787302255659L,"大話數據結構",
                "編程語言與程序設計","程傑",
                BigDecimal.valueOf(47.20),"清華大學出版社",
                LocalDate.of(2011,06,01),1));

        bst.add(new Books(9787115472588L,"鳥哥的Linux私房菜 基礎學習篇 第四版",
                "操作系統","鳥哥",
                BigDecimal.valueOf(93.00),"人民郵電出版社",
                LocalDate.of(2018,10,01),1));

        bst.add(new Books(9787115293800L,"算法(第4版)",
                "編程語言與程序設計","Robert Sedgewick,Kevin Wayne",
                BigDecimal.valueOf(66.30),"人民郵電出版社",
                LocalDate.of(2012,10,01),1));

        // 再次遍歷圖書庫
        System.out.println("圖書庫同種圖書加入:");
        System.out.println("書的種類數:"+bst.getBookSize());
        System.out.println("書的總數量:"+bst.getBookCount());
        bst.traverse(bst.getRoot());

        // 根據ISBN號查找圖書
        Books books =bst.search(9787115472588L);
        if (books!=null) {
            System.out.println("已找到該圖書:");
            System.out.println(books.toString());
        }
    }
}

程序輸出如下:

圖書庫新建:
書的種類數:10
書的總數量:10
{ISBN=9787115428028, 書名='Python編程 從入門到實踐', 作者='埃里克·馬瑟斯', 分類='編程語言與程序設計', 價格=61.4, 出版社='人民郵電出版社', 出版時間=2017-07-01, 當前數量=1}
{ISBN=9787111641247, 書名='深入理解Java虛擬機:JVM高級特性與最佳實踐(第3版)', 作者='周志明', 分類='編程語言與程序設計', 價格=106.4, 出版社='机械工業出版社', 出版時間=2019-12-01, 當前數量=1}
{ISBN=9787115293800, 書名='算法(第4版)', 作者='Robert Sedgewick,Kevin Wayne', 分類='編程語言與程序設計', 價格=66.3, 出版社='人民郵電出版社', 出版時間=2012-10-01, 當前數量=1}
{ISBN=9787115525963, 書名='說服力 工作型PPT該這樣做', 作者='秦陽', 分類='辦公軟件', 價格=66.3, 出版社='人民郵電出版社', 出版時間=2020-05-01, 當前數量=1}
{ISBN=9787115472588, 書名='鳥哥的Linux私房菜 基礎學習篇 第四版', 作者='鳥哥', 分類='操作系統', 價格=93.0, 出版社='人民郵電出版社', 出版時間=2018-10-01, 當前數量=1}
{ISBN=9787569222258, 書名='零基礎學Python(全彩版)', 作者='明日科技', 分類='編程語言與程序設計', 價格=67.0, 出版社='吉林大學出版社', 出版時間=2018-04-01, 當前數量=1}
{ISBN=9787121388361, 書名='PS之光:一看就懂的Photoshop攻略(全彩)', 作者='馮注龍', 分類='圖形圖像/多媒體', 價格=60.7, 出版社='电子工業出版社', 出版時間=2020-06-01, 當前數量=1}
{ISBN=9787115537973, 書名='數學之美 第三版', 作者='吳軍', 分類='計算機理論、基礎知識', 價格=54.4, 出版社='人民郵電出版社', 出版時間=2020-05-01, 當前數量=1}
{ISBN=9787302423287, 書名='機器學習', 作者='周志華', 分類='人工智能', 價格=64.8, 出版社='清華大學出版社', 出版時間=2016-01-01, 當前數量=1}
{ISBN=9787302255659, 書名='大話數據結構', 作者='程傑', 分類='編程語言與程序設計', 價格=47.2, 出版社='清華大學出版社', 出版時間=2011-06-01, 當前數量=1}
圖書庫同種圖書加入:
書的種類數:10
書的總數量:13
{ISBN=9787115428028, 書名='Python編程 從入門到實踐', 作者='埃里克·馬瑟斯', 分類='編程語言與程序設計', 價格=61.4, 出版社='人民郵電出版社', 出版時間=2017-07-01, 當前數量=1}
{ISBN=9787111641247, 書名='深入理解Java虛擬機:JVM高級特性與最佳實踐(第3版)', 作者='周志明', 分類='編程語言與程序設計', 價格=106.4, 出版社='机械工業出版社', 出版時間=2019-12-01, 當前數量=1}
{ISBN=9787115293800, 書名='算法(第4版)', 作者='Robert Sedgewick,Kevin Wayne', 分類='編程語言與程序設計', 價格=66.3, 出版社='人民郵電出版社', 出版時間=2012-10-01, 當前數量=2}
{ISBN=9787115525963, 書名='說服力 工作型PPT該這樣做', 作者='秦陽', 分類='辦公軟件', 價格=66.3, 出版社='人民郵電出版社', 出版時間=2020-05-01, 當前數量=1}
{ISBN=9787115472588, 書名='鳥哥的Linux私房菜 基礎學習篇 第四版', 作者='鳥哥', 分類='操作系統', 價格=93.0, 出版社='人民郵電出版社', 出版時間=2018-10-01, 當前數量=2}
{ISBN=9787569222258, 書名='零基礎學Python(全彩版)', 作者='明日科技', 分類='編程語言與程序設計', 價格=67.0, 出版社='吉林大學出版社', 出版時間=2018-04-01, 當前數量=1}
{ISBN=9787121388361, 書名='PS之光:一看就懂的Photoshop攻略(全彩)', 作者='馮注龍', 分類='圖形圖像/多媒體', 價格=60.7, 出版社='电子工業出版社', 出版時間=2020-06-01, 當前數量=1}
{ISBN=9787115537973, 書名='數學之美 第三版', 作者='吳軍', 分類='計算機理論、基礎知識', 價格=54.4, 出版社='人民郵電出版社', 出版時間=2020-05-01, 當前數量=1}
{ISBN=9787302423287, 書名='機器學習', 作者='周志華', 分類='人工智能', 價格=64.8, 出版社='清華大學出版社', 出版時間=2016-01-01, 當前數量=1}
{ISBN=9787302255659, 書名='大話數據結構', 作者='程傑', 分類='編程語言與程序設計', 價格=47.2, 出版社='清華大學出版社', 出版時間=2011-06-01, 當前數量=2}
已找到該圖書:
{ISBN=9787115472588, 書名='鳥哥的Linux私房菜 基礎學習篇 第四版', 作者='鳥哥', 分類='操作系統', 價格=93.0, 出版社='人民郵電出版社', 出版時間=2018-10-01, 當前數量=2}

四、深入理解

  1. 二分搜索樹的底層是一個鏈點,可以實現高效地插入,刪除以及動態維護。
  2. 二分搜索樹的結點是有序的,可以很快地求出最大,最小之類的關係值。
  3. 也正是因為二分搜索樹的結點是有序的,在極端情況下,二分搜索樹會褪化成一個鏈表

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

【其他文章推薦】

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

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

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

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

新北清潔公司,居家、辦公、裝潢細清專業服務

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

CCNA-Part1:網絡基礎概念

由於身處一家網絡公司,日常項目中涉及到的網絡概念較多,恰逢之後公司組織相關培訓。藉此機會,打算寫下一系列文章用於之后梳理並回顧。文章主要涉及 NA,NP 中所覆蓋的知識。由於網絡分為較多方向,如路由交換,無線,安全等。在今年,大綱正好有所改變,其中無線和路由交換放在一起合稱為企業架構。所以本系列文章以企業架構為主。

在網絡界,Cisco 證書一直被普遍認可,其中分為三個等級 NA,NP,IE. 對於開發人員來說,掌握 NA 水平一般即可,本系列文章會 NA 開始,到 NP 結束。NA 內容較為寬泛,其中涉及知識面較寬,但不深入,用於入門。NP 在 NA 基礎上,更加深入,涉及到更多的協議與概念。

話不多說,在閱讀本文後,應該了解以下內容:

  1. 了解網絡的組成?
  2. 衡量網絡的指標?
  3. 不同應用程序對網絡的要求?

什麼是網絡?

網絡的組成

先看一下網絡的組成組件:

主要分為 4 大類:

  • 終端設備:產生和接受數據的設備,如 PC ,服務器,電話
  • 中間設備:常見叫法為2,3層設備,如 2 層設備交換機,3層設備路由器
  • 媒介:數據傳輸時的媒介,如無線,線纜,光纖。
  • 服務:如應用服務器,taobao,QQ 等

由此可見,網絡就是由上述設備組成,在其中進行數據產生,轉發的過程。在討論網絡時,一般討論的都是企業網絡,下面是常見的一張企業網絡的架構圖。

從圖中我們可以看到,網絡的大體架構由,終端設備,接入層設備(交換機,用於將設備接入),轉發層設備(路由器)和數據中心組成。舉例子來說,如果左下角的同學 A 想要和右上角的同學 B 同學通信,則需要經歷如下過程:

  1. 通過接入層設備接入企業內網
  2. 通過核心層設備,將數據轉發至 ISP(服務提供商,如聯通電信等)
  3. ISP 將數據轉發至同學 B 所在核心層設備。
  4. B 所在核心層設備轉發至接入層設備。
  5. 接入層設備轉發給用戶B。

接口類型

設備連入的端口,稱為接口,下面是常見的接口類型。

接口名稱 速度
Ethernet 10M
Fast Ethernet 100M
GigabitEthernet 1000M
10GigabitEthernet 10000M
40GigabitEthernet 40000M
100GigabitEthernet 1000000M
Serial – 串行口

衡量網絡的主要指標

在討論或者設計一個網絡架構是,往往會在如下的方面進行討論:

帶寬

表示數據的發送速率,單位為比特每秒(b/s),意思為一秒鐘發送的比特數,因此帶寬又稱為比特率。(以太網: 10Mbps, 快速以太網:100Mbps)

可用性與可靠性:

拓展性:

在設計網絡架構時,要考慮到可拓展性,公司的人數會隨着時間增加。

安全性:

數據傳輸和存儲的安全。

服務質量 (Qos):

對流量進行分類整理,拿家庭具體,分類出訪問 QQ 的流量,訪問 P2P 的流量,然後對其進行限制設置上限,防止一個服務佔用過大的帶寬,造成其他服務無法正常訪問。

開銷(Cost):

設備及搭建網絡的費用。

虛擬化:

將一個物理設備虛擬化成多個虛擬設備,例如交換機,路由器等。

拓撲:

物理拓撲:實際設備之間的物理連接的布局,稱為物理拓撲。

物理之間拓撲的比較:

拓撲類型 優點
總線拓撲 1. 所用電纜少
2. 結構簡單
3. 易於擴充
4. 布線方便
1. 傳輸距離有限,通信範圍受到限制
2.故障診斷和隔離較困難
3.所有數據經過總線傳送,不具有實時功能
4. 單點故障:所有 PC 不得不共享線纜,一個節點出錯,將影響整個網絡
環形拓撲 1. 增加或減少工作站時,僅需要簡單的連接操作
2. 電纜長度短
3. 傳輸延遲確定
1. 傳輸距離有限,通信範圍受到限制
2. 故障診斷和隔離困難
3. 節點過多時影響傳輸效率
4. 任意節點出現故障,整個網絡將癱瘓
星型拓撲-局域網較為常見 1. 集中控制,控制簡單
2. 故障診斷和隔離容易
3. 網絡延遲短
1. 中央節點的負擔較重,形成瓶頸
2. 各節點的分佈處理能力較低
3. 網絡共享能里較差
部分網狀拓撲-廣域網常見 1. 系統可靠性高,比較容易擴展 1. 結構複雜,每一結點都與多點進行連結
2. 因此必須採用路由算法和流量控制方法。

邏輯拓撲:以數據轉發的過程為側重,描述節點之間數據的轉發過程。

應用程序流量分類

在網絡中提供服務的應用種類較多,對應對網絡的要求也一般不同,可大致分為如下幾類:

總結

本篇內容中,多為網絡的基礎概念,方便大家入門,只需理解有個印象就好。接下來的內容,才是真正學習的網絡的開始。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

必知必會的8個Python列表技巧

原作者:Nik Piepenbreier

翻譯&內容補充:費弗里

原文地址:https://towardsdatascience.com/advanced-python-list-techniques-c6195fa699a3

  列表(List)是你使用Python過程中接觸最為頻繁的數據結構,也是功能最為強大的幾種數據結構之一。Python列表非常的萬能且蘊含着許多隱藏技巧,下面我們就來探索一些常用的列表技巧。

1 列表元素的過濾

1.1 filter()的使用

  filter()函數接受2個參數:1個函數對象以及1個可迭代的對象,接下來我們定義1個函數然後對1個列表進行過濾。

  首先我們創建1個列表,並且剔除掉小於等於3的元素:

圖1

  回顧一下發生了什麼:

  1. 我們定義了列表original_list
  2. 接着我們定義了一個接受數值型參數number的函數filter_three,當傳入的參數值大於3時會返回True,反之則會返回False
  3. 我們定義了filter對象filtered,其中filter()接受的第一個參數是函數對象,第二個參數是列表對象
  4. 最終我們將filter對象轉化為列表,最終得到經filter_three過濾后original_list內留下的元素。

1.2 使用列表推導式

  類似的,我們也可以利用列表推導式來過濾列表元素,作為一種生成和修改列表優雅的方式,列表推導式想必大家都比較熟悉了,下面是使用列表推導完成同樣任務的過程:

圖2

2 修改列表

2.1 map()的使用

  Python中內置的map()函數使得我們可以將某個函數應用到可迭代對象內每一個元素之上。

  比方說我們想獲取到一個列表對象中每一個元素的平方,就可以使用到map()函數,就像下面的例子一樣:

圖3

  類似filter()的工作過程,下面我們來看看發生了什麼:

  1. 首先我們定義了列表original_list,以及接受數值型參數並返回其平方值的函數square()
  2. 接着我們定義了map對象squares,類似filter()map()接受的第一個參數是函數對象,第二個參數是列表對象
  3. 最終我們將map對象squares列表化,就得到了想要的結果

2.2 使用列表推導式

  同樣的我們也可以使用列表推導式完成同樣的任務:

圖4

3 利用zip()來組合列表

  有些情況下我們需要將兩個或以上數量的列表組合在一起,這類需求使用zip()來完成非常方便。

  zip()函數接收多個列表作為參數傳入,進而得到每個位置上一一對應的元素組合,就像下面的例子一樣:

圖5

4 顛倒列表

  Python中的列表是有序的數據結構,正因如此,列表中元素的順序很重要,有些時候我們需要翻轉列表中所有元素的順序,可以通過Python中的切片操作,用::-1來快捷地實現:

圖6

5 檢查列表中元素的存在情況

  有些情況下我們想要檢查列表中是否存在某個元素,這種時候就可以使用到Python中的in運算符,譬如說我們有一個記錄了所有比賽獲勝隊伍名稱的列表,當我們想查詢某個隊名是否已獲勝時,可以像下面的例子一樣:

圖7

6 找出列表中出現次數最多的元素

  有些情況下我們想要找出列表中出現次數最多的元素,譬如對記錄若干次拋硬幣結果的列表,找出哪一種結果出現次數最多,就可以參考下面的例子:

圖8

7 展平嵌套列表

  有些情況下我們會遇到一些嵌套的列表,其每個元素又是各自不同的列表,這種時候我們就可以利用列表推導式來把這種嵌套列表展平,如下面2層嵌套的例子:

圖9

額外補充

  原作者這裏只考慮到兩層嵌套的列表,如果是更多層嵌套,就需要有多少層寫多少for循環,比較麻煩,其實還有一種更好的方法,我們可以使用pip install dm-tree來安裝tree這個專門用於展平嵌套結構的庫,可以展平任意層嵌套列表,使用例子如下:

圖10

8 檢查唯一性

  如果你想要查看列表中的值是否都是唯一值,可以使用Python中的set數據結構的特點,譬如下面的例子:

圖11

  以上就是本文的全部內容,如有疑問歡迎在評論區討論~

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

【其他文章推薦】

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

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

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

※超省錢租車方案

一分鐘開始持續集成之旅系列之:C 語言 + Makefile

作者:CODING – 朱增輝

前言

make 工具非常強大,配合 makefile 文件可以實現軟件的自動化構建,但是執行 make 命令依然需要經歷手動輸入執行、等待編譯完成、將目標文件轉移到合適位置等過程,我們真正關心的是最終的輸出,卻在這些中間過程上浪費了很多時間。利用 CODING 持續集成功能可以實現自動觸發構建,構建全程自動化,無須分心看護,節省時間。

本文通過一個 C 語言 + Makefile Demo 項目講解如何使用 CODING 持續集成功能創建構建計劃,自動觸發構建,以及如何將生成的目標文件發布到 CODING generic 製品庫。

準備工作

環境

本文涉及到以下工具,請確認已存在,或者根據鏈接的文檔進行安裝。

  • git
  • make
  • gcc

另外,您還需準備一個 CODING 項目。

代碼

我已經準備了一份簡單的示例代碼,使用 make 工具構建 Hello-world 程序。

// hello.c
#include <stdio.h>

int main() {
    printf("Hello, World!\n");
    return 0;
}

您可以通過下面的命令克隆到本地。

git clone https://e.coding.net/coding-public/demo-c-make.git

倉庫中還包含了一個 makefile 文件,定義了簡單的規則來完成軟件構建。

all: hello

hello: hello.o
	gcc -o hello hello.o

hello.o: hello.c
	gcc -c hello.c

clean:
	rm -rf hello.o hello

您可以在本地執行 make 命令以驗證構建正常。

下面我們正式開始通過一個 Demo 演示 CODING 平台持續集成功能的使用。

步驟一 創建製品庫

為了方便隨時使用構建出來的目標文件,我們將構建物存儲到 CODING 平台製品庫,因此需要先創建合適的製品倉庫,這裏創建 generic 倉庫比較合適。

從左側導航欄打開製品庫

單擊新建倉庫,選擇 generic 類型,按照提示指定倉庫名稱,這裏倉庫名取為 generic。

步驟二 創建並配置構建計劃

從左側導航欄打開持續集成 --> 構建計劃頁面,點擊新建構建計劃配置創建並配置新的構建計劃。在彈出的頁面中,輸入構建計劃名稱,選擇代碼倉庫,配置來源指的的該構建計劃的構建腳本存放位置,對於簡單的、變動不頻繁的腳本可以使用靜態配置的選項,否則更推薦使用代碼倉庫中的腳本,這樣更加靈活,方便管理

點擊使用模板,可根據自己需要選擇合適模板,這裏選擇 簡易模板

保存構建計劃后,系統會自動將構建模板對應的 Jenkinsfile 推送到倉庫,默認為 master 分支。

步驟三 編寫構建腳本

構建腳本定義構建過程的具體步驟,是構建計劃的核心部分。CODING 平台提供了圖形化編輯器方便您快速編寫構建腳本。

CODING 持續集成底層基於開源 CI/CD 軟件領導者 Jenkins 實現,完全兼容 Jenkins pipeline 構建腳本語法,根據 Jenkins 官方提供的腳本編寫指南,可以實現更複雜的構建任務,CODING 也提供了文本編輯器方便您在線編輯。

代碼倉庫中已包含一個簡單的構建腳本(Jenkisnfile),您可以按照自己的想法參考編寫。

// Jenkinsfile
pipeline {
  agent any
  stages {
    stage('檢出') {
      steps {
        checkout([
          $class: 'GitSCM',
          branches: [[name: env.GIT_BUILD_REF]],
          userRemoteConfigs: [[
            url: env.GIT_REPO_URL,
            credentialsId: env.CREDENTIALS_ID
          ]]])
        }
      }
      stage('構建') {
        steps {
          echo '構建中...'
          sh 'make'
          echo '構建完成.'
        }
      }
      stage('發布') {
        steps {
          echo '發布中...'
          codingArtifactsGeneric(
            files: 'hello',
            repoName: "${env.GENERIC_REPO_NAME}",
            version: "${env.GIT_COMMIT}",
          )
          echo '發布完成'
        }
      }
    }
  }
}

構建腳本中的大部分內容都比較容易理解,稍顯陌生的是 codingArtifactsGeneric 步驟,這是 CODING 官方提供的插件,方便上傳到 CODING generic 製品庫。該插件通過環境變量 GENERIC_REPO_NAME 獲取倉庫名,因此需要配置構建計劃設置該變量值。

步驟四 配置觸發構建規則

CODING 持續功能支持多種觸發方式包括代碼源觸發、定時觸發、API 觸發及手動觸發,這幾種觸發方式可以同時配置互不衝突,其中代碼源觸發又可配置為推送到指定分支或標籤觸發,觸發方式多樣,可滿足絕大部分場景需要。

如前言中所說,我們希望把更多的精力放在源代碼上,盡量減少構建所帶來的干擾,因此這裏必不可少的是配置通過代碼源觸發,通過配置如下正則表達式,可以在推送代碼到匹配的分支名時自動觸發構建。

^refs/(heads/(release|release-.*|build-.*|feat-.*|fix-.*|test-.*|mr/.*))

步驟五 執行構建

執行構建最簡單的方式是手動觸發構建,選中想要構建的構建計劃,單擊立即構建會彈出配置窗口,在這裏可以配置此次構建使用的參數,單擊確定即可開始構建。

按照步驟四的配置,我們的構建計劃也支持推送的匹配分支觸發構建,您可以執行如下命令創建新分支並推送到遠端倉庫,即可觸發構建。

git checkout -b build-ci-test
git push origin HEAD

觸發后,構建會自動執行,您可以繼續做其他事情。

步驟六 下載目標文件

步驟三中定義的構建腳本會將構建出的目標文件發布到 CODING 製品庫,如果我們想要在本地使用也是很方便下載的。在製品倉庫中單擊文件名即可看到指引頁,裏面給出了對文件不同操作的命令。

總結

本文通過一個 C 語言 + makefile 的 Demo 項目講解了 CODING 持續集成、製品庫的簡單使用。藉由 CODING 平台的這些功能,我們像是雇了一個永不會累的助手,承擔了耗時的構建工作,從而節省了時間,提高了效率。

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

【其他文章推薦】

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

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

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

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

基於雲服務的個人網站架構設計

本文介紹如何基於各種雲服務優雅且低成本地搭建個人網站,涉及的雲產品有雲服務器、SSL、企業郵箱、對象存儲、CDN、雲函數、API網關、雲監控等。

概述

如今雲服務提供商們提供了大量涵蓋計算、網絡、存儲等方面的雲服務,其中一些雲產品功能強大,如果能善加利用可以大幅降低開發和運維的成本。下面以基於騰訊雲搭建的個人網站為例,對網站整體的架構進行介紹。

網站目前的主要功能是個人博客,後續可以擴展如個人網盤等其他應用。當前架構圖如下:

一、基礎設施

1.雲服務器CVM

雲服務器使用的是CVM,1核2G,下行帶寬1Mbps,這個配置用來搭建起步階段的個人博客是完全夠用了,購買學生機或者在活動時購買價格也比較便宜。

有了服務器資源就可以開始博客搭建,我選的博客系統是極簡主義的Typecho,安裝過程可以參考這篇博文,主要是在服務器上安裝nginx、mysql、php以及typecho的源碼。

2.域名

註冊 – 備案 – 解析

服務器創建后同時會分配一個公網ip,但是為了便於分享和傳播,建議進行域名註冊。註冊后需要進行備案,現在的備案流程也已經簡化為在小程序上操作,省去了原有的幕布拍照環節,前後大概1-2周時間就可以完成備案。之後在控制台進行域名解析,即綁定域名和服務器ip,注意對帶或不帶www前綴的域名都要進行解析,完成解析后就可以在瀏覽器通過域名來訪問網頁了。

主域名的確定

為了便於SEO,建議根據個人喜好確定一個主域名,因為搜索引擎對於帶www和不帶www前綴的地址是當成兩個網站分開計算權重的。國內網站一般帶www,而國外網站(如github、stackoverflow、leetcode)等是不帶www的。我這裡是選擇不帶www的地址(zhayujie.com),並在nginx中配置對帶www的訪問301重定向到不帶www上,以集中權重。

企業郵箱

擁有域名后,還可以註冊以自己域名為後綴的企業郵箱,基礎版免費使用且賬號數量無上限,再也不用擔心郵箱號不夠用了(如微信公眾平台註冊),郵箱格式類似於 zyj@zhayujie.com

3.全站HTTPS

為了網站安全以及利於SEO,建議支持https協議訪問網站。可以申請免費的SSL證書,將證書和私鑰放置到服務器,並在nginx中開啟並配置SSL。同樣為了避免分散權重,可以把http訪問的請求301重定向到https上。以我的網站為例,帶不帶www以及是否使用https都會統一訪問https://zhayujie.com/。

二、基於COS和CDN的圖床

1.對象存儲COS

由於服務器下行帶寬有限,如果圖片存儲於我們自己的服務器,出現併發訪問時可能導致帶寬超限,訪問速度下降。所以可以把圖片存儲到 COS(Cloud Object Storage)中,搭建自己的圖床,這樣當博客同步到其他博客平台時,也便於對圖片資源進行統一管理。

COS的使用比較簡單,類似於網盤,在存儲桶中可以建立樹狀目錄結構,每個存儲桶(bucket)會分配一個公網域名,其下的文件通過https://{bucket}/{dir}/{filename}的形式進行訪問。但在博客中直接使用該鏈接是不妥的,因為一旦我們遷移到其他雲服務商或者切換其他的存儲方式了,原有的鏈接就失效了,一一修改成本太高。好在cos支持配置自定義域名,可以通過類似http://{domain}/{dir}/{filename}的地址進行訪問。

2.內容分髮網絡CDN

COS的自定義源站域名不支持https訪問,為了不影響我們的全站https,並且同時提升訪問速度和減少流量成本,可以配合CDN服務,開啟自定義CDN加速域名,具體步驟見文檔。

可以選取一個子域名作為cdn自定義域名,添加CNAME解析,這樣通過自定義域名會首先訪問cdn邊緣服務器,如果未命中則回源到cos。例如上面的圖片我配置的地址是https://blog.cos.zhayujie.com/web/blog-cloud-arch.jpg。

三、基於Serverless的消息服務

1.雲函數SCF

在博客開發過程中會遇到一些發送消息的功能,比如讀者回復文章時給筆者發送通知,筆者回複評論時給讀者發送通知,博文發布時給訂閱的讀者發送通知等等。這種消息通知的功能是很適合單獨拆分出來形成一個消息服務的,如果寫在博客源碼中則復用性差(網站下其他應用要發送消息時需要重寫),而單獨部署服務又會增加運維的成本(如果服務掛掉怎麼辦),這時候可以考慮serverless(無服務器)的架構,僅將我們的核心代碼片段託管給雲服務商。

騰訊雲提供了雲函數SCF(Serverless Cloud Function),是一種FaaS技術。對於消息通知這種異步、無狀態的功能,很適合使用雲函數編寫,比如接收到請求後向指定接收人發送一封郵件。

2.API網關

雲函數的觸發方式有多種,最常用的有定時任務和API網關。由於消息通知是通過事件觸發而不是定時觸發,所以選擇API網關,創建了觸發器后便可從公網直接訪問該函數,與Nginx反向代理的作用類似。

API網關的域名是隨機生成的,不利於對未來變化的擴展,故同樣綁定自定義域名,使用https://{domain}/{function}形式的地址觸發函數。例如我的郵件發送函數地址配置為https://apigw.zhayujie.com/commentNotice,在業務代碼中只需向該地址發送POST請求即可觸發郵件投遞。

四、監控、快照和統計

1.監控告警

服務器的監控和告警同樣很重要,有助於我們及時發現並排查問題。監控部分一般直接在控制台的 雲服務器 – 實例 – 監控 中進行查看,有對不同時間周期和時間粒度下的CPU、內存、帶寬、磁盤等的詳細數據。

告警部分則在雲監控中配置,可以配置多種報警策略如對cpu、內存、帶寬等指標超出閾值後進行告警,以及一些機器故障事件(如ping不可達、機器重啟等)。對COS的報警同樣可以在此配置。告警渠道可以是微信、郵件和短信。

2.快照

為了防止服務器硬盤中的數據遭到攻擊或被誤刪,可以在 雲服務器 – 快照 控制台中設置進行快照備份,並且支持定期快照策略,設置每隔一段時間自動創建新的快照。

3.訪問統計

對網站的訪問情況進行統計分析有利於我們優化網站內容和體驗。對於訪問數據統計使用的是百度統計,使用埋點方式接入,可以查看每一個訪客的地域,來源,搜索詞,轉化等信息,統計訪問量趨勢。

對於搜索引擎工具使用的是百度站長工具,用於提交頁面收錄,查看索引量、抓取頻次等數據。

總結

以上就是一個功能齊全的個人博客的搭建過程,大致計算一下成本,雲服務器活動期購買一百一年,域名一般幾十塊一個,而COS、CDN、SCF等產品都有大量的免費額度,且在建站初期流量費用同樣是微乎其微,所以總體算下來成本是極低的。個人開發者可以把個人網站當做一個產品來做,思考如何利用好公有雲的各種雲產品資源來提升用戶體驗,提高開發效率,降低運維成本。

原文鏈接:https://zhayujie.com/blog-cloud-arch.html

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

【其他文章推薦】

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

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

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

南投搬家公司費用需注意的眉眉角角,別等搬了再說!

新北清潔公司,居家、辦公、裝潢細清專業服務

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

虹軟人臉識別——官方 Qt Demo 移植到 Linux

一、前言

最近需要在 Linux 平台下開發一個人臉識別相關的應用,用到了虹軟的人臉識別 SDK。之前在 Windows 平台用過,感覺不錯,SDK 裏面還帶了 Demo 可以快速看到效果。打開 Linux 版本的 SDK 裏面沒有發現 Demo,於是想着把 Windows 的 Demo 移植到 Linux。這篇文章記錄了移植的過程,Linux 用的是 Ubuntu 20.04(使用虛擬機 VMware Workstation 15 Player)。

二、配置依賴

2.1 ArcFace SDK

到虹軟官網下載人臉識別 SDK 3.1 Linux 增值版本 解壓到合適的目錄,並從官網獲取 APP_ID、SDK_KEY 和 ACTIVE_KEY,用於寫到配置文件用來激活 SDK。

2.2 OpenCV

到 OpenCV 官網下載源碼,我用的版本是 3.4.9。可以按照官網的教程 Installation in Linux 自行編譯,我參考官網教程使用下面的這些命令在 GCC 9.3.0(Ubuntu 20.04 自帶的編譯器) 上編譯成功。

sudo apt update
sudo apt install build-essential
sudo apt install cmake git libgtk2.0-dev pkg-config libavcodec-dev libavformat-dev libswscale-dev
cd <OpenCV 源碼目錄>
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=<自定義目錄> ..
make -j3    # 可以使用核心數 - 1 個線程來編譯
sudo make install

2.3 Qt

Qt 使用的是 5.14.2 版本。

三、項目文件

3.1 .pro 文件

原 Windows Demo 使用的是 Visual Studio 2015,在 Linux 下我這裏用到了 Qt Creator 進行開發,因此需要編寫 .pro 文件,包括以下幾個方面:

  • 用到的 Qt 模塊
  • 編譯出來的程序名
  • 用到的頭文件、源文件和資源文件
  • 依賴庫的頭文件及庫名

更具體的內容查看文末提供的源碼。

3.2 文件編碼

原源碼文件使用的是 GBK 編碼,需要轉換為 UTF-8 編碼。將下面的命令保存到 convert.sh 文件中並用 chmod u+x convert.sh 賦予可執行權限。

#!/bin/bash

for i in "$@"; do
    desc=$(file "$i")
    if $(echo $desc | grep -i "UTF-8 Unicode" > /dev/null); then
        if $(echo $desc | grep -i "(with BOM)" > /dev/null); then
            echo "Remove UTF-8 BOM: " $i
            sed -i "1s/^\xef\xbb\xbf//" "$i"
        fi
    elif $(echo $desc | grep -i "ISO-8859" > /dev/null); then
        echo     "GBK --> UTF-8   : " $i
        temp=temp.txt
        iconv -f gbk -t utf-8 -o "$temp" "$i"
        mv "$temp" "$i"
    fi
done

在源碼根目錄下運行 find . -type f \( -name "*.h" -o -name "*.cpp" \) | xargs -I{} ./convert.sh "{}" 將所有的文件的編碼從 GBK 轉為 UTF-8,並去除現有 UTF-8 文件的 BOM 頭。

四、代碼修改

到這裏已經可以用 Qt Creator 打開項目了,但在代碼中還存在一些問題,一方面是原代碼使用了一些 Windows 平台特有的 API,一方面是有些代碼在 Linux 有兼容性問題。先去除 Windows 特有的依賴到編譯通過,再補充必要的依賴,最後解決兼容性問題。

4.1 修改報錯直至編譯通過

直接進行編譯,逐步解決編譯錯誤,通過下面的方式可以解決編譯錯誤:

  • 刪除 Utils.cpp 中報錯的頭文件、GUID 宏、listDevices 函數的主體、UTF8_To_string 和 string_To_UTF8 函數。
  • 將所有包含的 qDebug 改為 QDebug
  • Sleep(milli) 改為 std::this_thread::sleep_for(std::chrono::milliseconds(milli))
  • 刪除 MSVC 的鏈接庫的編譯指令 #pragma comment ...
  • 將原來使用 OpenCV 2 的接口遷移到目前的 OpenCV 3。
    • IplImage 到 cv::Mat 的轉換由 cv::Mat mat(ipl, false) 改成 cv::Mat mat = cv::cvarrToMat(ipl)
    • cv::Mat 到 IplImage 的轉換由 IplImage(mat) 改成 cvIplImage(mat),在原來的代碼里 cv::Mat 轉為 IplImage 後有個取地址,對右值取地址是不安全的,需要用一個變量保存轉換后的值再對這個變量取地址。
    • 在調用 cvRectangle 時將 CV_RGB 改成 cvScalar
    • 使用 cv::cvtColor 需要額外包含頭文件 opencv2/imgproc.hpp
    • 使用 cv::VideoCapture 需要額外包含頭文件 opencv2/videoio.hpp
  • strcpy_s 改成 strncpy,僅有參數位置上的改變。
  • TRUE 改為 true,將 FALSE 改為 false

改了編譯錯誤后,忽略警告已經可以編譯通過了,接下來是補充剛才刪除的一些必要依賴及解決兼容性問題。

因為環境差異,可能出現錯誤的順序不一致,但基本上是上面提到的錯誤之一。

4.2 重新實現獲取攝像頭列表的函數

原 Windows Demo 使用了 Windows 特有的 dshow 來查找攝像頭,在這裏直接用 cv::VideoCapture 嘗試打開來獲取攝像頭的索引:

auto list = std::vector<int>();
for (auto i = 0; i != 10; ++i)
{
    auto cap = cv::VideoCapture(i);
    if (cap.isOpened()) { list.emplace_back(i); }
    cap.release();
}

Demo 可以只打開一個RGB攝像頭,也可以同時打開一個RGB攝像頭和一個IR攝像頭。原代碼保存獲取攝像頭的名稱,僅用來統計數量,具體打開哪個攝像頭是通過settings.ini文件來配置的。在改變探測攝像頭存在的數量的方式后,順帶改變了打開攝像頭的邏輯,僅一個攝像頭就認為是僅打開普通攝像頭。在settings.ini文件中配置兩種攝像頭的索引,如果索引為 -1,則自動把小的索引認為是普通攝像頭,大的索引認為是紅外攝像頭,如果和真實情況不一致可手動指定攝像頭索引。

settings.ini文件在後面運行 Demo 時會有更多的說明。

4.3 修復彈出文件選擇框失敗的兼容性問題

在 Ubuntu 20.04 下,Qt 的 QFileDialog::getOpenFileName 和 QFileDialog::getExistingDirectory 存在一些問題,在打開時會卡死界面,通過將最後一個參數設置為 QFileDialog::DontUseNativeDialog 可以解決這個問題。

五、運行 Demo

5.1 界面預覽

5.2 配置

  1. 配置文件已經隨源碼打包好了,在運行時需要移動到可執行程序所在的同級目錄下。
  2. 在配置文件中填入官網獲取的 APP_ID、SDK_KEY 和 ACTIVE_KEY。
  3. 編譯並運行。

六、源碼下載

基於官方windows Qt Demo修改后的源碼

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

【其他文章推薦】

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

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

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

※幫你省時又省力,新北清潔一流服務好口碑

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

HTTPS協議詳解

HTTPS協議詳解

從事移動互聯網軟件開發的小夥伴肯定了解:自Android 9.0開始,應用程序的網絡請求默認使用https;基本是同期蘋果IOS在應用網絡請求方面,也強制使用https禁止http。
這一期間如果你去面試,不了解Https的握手過程,都不好意思講工資。
本人一個普通程序員,項目期間工期緊張,並未抽出時間詳細了解Https網絡請求過程中TLS握手過程,因此這件事一直在我的待辦記錄中…
這篇文章以Wireshark抓包,詳細了解Https請求中TLS的握手過程 與 客戶端證書校驗過程。

  • HTTPS簡介
  • SSL/TLS握手過程
  • 客戶端 證書校驗

一、HTTPS簡介

HTTPS (Secure Hypertext Transfer Protocol)安全超文本傳輸協議,是一種通過計算機網絡進行安全通信的傳輸協議。
HTTPS 利用 SSL/TLS 來加密數據包,經由 HTTP 進行通信。
其設計的主要目的是,提供對網站服務器的身份認證、保護交換數據的隱私與完整性。

TLS/SSL

  • SSL(Secure Socket Layer) 1994年由 瀏覽器開發商Netscape公司 率先倡導研發,為數據通訊提供安全支持,開發了最初的幾個版本SSL 1.0、SSL 2.0、SSL 3.0。
  • TLS(Transport LayerSecurity)前身為SSL,1999年從 3.1 開始被 IETF(Internet Engineering Task Force,Internet 工程任務組)標準化並改名,發展至今已經有 TLS 1.0、TLS 1.1、TLS 1.2 三個版本。
    SSL3.0和TLS1.0由於存在安全漏洞,已經很少被使用到;
    TLS 1.3 改動會比較大,目前還在草案階段,目前使用最廣泛的是TLS 1.1、TLS 1.2;

TLS/SSL是介於TCP和HTTP之間的一層安全協議。

Http

HTTP(HyperText Transfer Protocol)超文本傳輸協議。
HTTP是一個客戶端(用戶)和服務端之間請求和應答的標準,其最初的設計目的是為了提供一種發布和接收HTML頁面的方法。

Http協議不是本文重點,感興趣的同學可參考文章:
HTTP 協議詳解
https://blog.csdn.net/xiaxl/article/details/104541274

二、SSL/TLS握手過程

SSL/TLS握手過程用一句話總結就是:用非對稱加密的手段傳遞密鑰,然後用密鑰進行對稱加密傳遞數據
以下為SSL/TLS握手過程的時序圖:

這裏以客戶端百度主頁發起Https請求為例,用Wireshark抓包對SSL/TLS握手的各個環節進行介紹,Wireshark抓包示意圖如下圖所示:

2.1、Client Hello ( Client——>Server )

握手第一步是客戶端向服務端發送 Client Hello 消息,消息中包含客戶端的 TSL版本信息、秘鑰隨機數、加密套件候選列表、壓縮算法候選列表、擴展字段等信息,相關信息通過Wireshark抓包如下:

  • Version : 支持的最高TSL協議版本,從低到高依次 SSLv2 SSLv3 TLSv1 TLSv1.1 TLSv1.2;
  • Random:隨機數 random_C 用於後續的密鑰協商;
  • Session ID:有或者無,有則客戶端傳上一次session的id可以恢復session;
  • Cipher Suite:客戶端支持的密碼算法列表,供服務器選擇;
  • Compression Methods:客戶端支持的壓縮算法列表,用於後續的信息壓縮傳輸;
  • extensions:擴展字段;
2.2、Server Hello ( Server——>Client )

服務端向客戶端發送 Server Hello 消息:包括服務端選擇使用的TSL協議版本、選擇的加密套件、選擇的壓縮算法、服務端生成的隨機數等,相關信息通過Wireshark抓包如下:

  • Version:服務器選擇的版本;
  • Random:隨機數 random_S 用於後續的密鑰協商;
  • Session ID:有或者無,有則客戶端傳上一次session的id可以恢復session;
  • Cipher Suite:服務端選擇的密鑰算法;
  • Compression Methods:服務端選擇的壓縮算法;

到此客戶端和服務端都擁有了兩個隨機數(random_C+ random_S),這兩個隨機數會在後續生成對稱秘鑰時用到。

2.3、Certificate ( Server——>Client )

服務端下發服務端的公鑰證書給客戶端,相關信息通過Wireshark抓包如下:

  • Certificate 服務端的公鑰證書;
2.4、Server Key Exchange ( Server——>Client )

該消息的目的是攜帶密鑰交換的額外數據,該消息內容對於不同的協商算法套件會存在差異:

  • 對於使用DHE/ECDHE非對稱密鑰協商算法的SSL握手,服務器發送其使用的DH參數;
  • RSA算法不會繼續該握手流程(DH、ECDH也不會發送server key exchange)。
2.5、Server Hello Done ( Server——>Client )

通知客戶端服務端已經將所有預計的握手消息發送完畢。

2.5、證書校驗 (客戶端進行證書校驗)

客戶端拿到服務端公鑰證書后,需對該證書的合法性進行校驗,校驗內容如下:

  • 證書鏈的可信性;
  • 證書是否吊銷;
  • 證書有效期;
  • 證書域名校驗,核查證書域名是否與當前的訪問域名匹配;

注:
證書的詳細校驗過程將在下文進行詳細介紹

2.6、Client Key Exchange,Change Cipher Spec Protocol,Encrypted Handshake Message ( Client——>Server )
  • Client Key Exchange
    證書合法性驗證通過之後,客戶端產生隨機数字Pre-master,計算生成秘鑰enc_keyenc_key=Fuc(random_C, random_S, Pre-Master),將Pre-masterenc_key證書公鑰加密(非對稱加密算法)發送給服務端;
  • Change Cipher Spec Protocol
    客戶端通知服務端後續的通信都採用協商的通信密鑰加密算法進行加密通信;
  • Encrypted Handshake Message
    客戶端將之前所有的握手數據(包括接受、發送)生成摘要,然後用協商好的秘鑰enc_key加密(對稱加密算法),發送給對應的服務端;
    服務端收到消息后,會用秘鑰enc_key解密客戶端的摘要信息,然後用與客戶端相同的算法生成服務端摘要信息,最後對比兩個摘要信息相同,則驗證通過;
2.7、Change Cipher Spec Protocol ( Server——>Client )

服務器同樣發送 Change Cipher Spec Protocol 以告知客戶端後續的通信都採用協商的密鑰與算法進行加密通信;

2.8、Encrypted Handshake Message ( Server——>Client )

服務端也會將握手過程的消息生成摘要再用秘鑰加密,這是服務端發出的第一條加密消息;
客戶端接收後會用秘鑰解密,能解出來說明協商的秘鑰是一致的。

2.9、Application Data ( Client——>Server )

到這裏,雙方已安全地協商出了同一份秘鑰enc_key,所有的應用層數據都會用這個秘鑰加密后再通過 TCP 進行可靠傳輸。

2.10 總結

SSL/TLS握手過程:用非對稱加密的手段傳遞密鑰,然後用密鑰進行對稱加密傳遞數據

三、證書校驗

客戶端驗證服務端下發的證書,主要包括以下幾個方面:

  • 第一,校驗證書是否是受信任的CA根證書頒發機構頒發;
  • 第二,校驗證書是否在上級證書的吊銷列表;
  • 第三,校驗證書是否過期;
  • 第四,校驗證書域名是否一致。
3.1、校驗證書是否是由受信任的CA根證書頒發機構頒發

為了確保客戶端獲取到的服務端公鑰不被篡改,需引入權威的第三方CA機構。
CA機構負責核實公鑰擁有者信息頒發“證書(對服務端公鑰進行簽名)”,同時為使用者提供證書驗證服務

CA機構頒發證書的基本原理為:

  • 服務端生成一對服務端公鑰服務端私鑰
  • 服務端將自己的服務端公鑰提供給CA機構;
  • CA機構核實服務端公鑰擁有者信息(核實申請者提供信息的真實性,如組織是否存在、企業是否合法、是否擁有域名的所有權等);
  • CA機構計算服務端公鑰的摘要信息,利用CA機構的私鑰(CA機構有一對公鑰、私鑰)進行加密,加密后的服務端公鑰即CA機構頒發的“證書”

客戶端驗證服務端公鑰的基本原理為:

  • Https網絡請求過程中,客戶端獲取到服務端的公鑰
  • 客戶端用存儲在本地的CA機構的公鑰,對 服務端公鑰進行解密,獲取到服務端公鑰的摘要信息A
  • 客戶端計算服務端公鑰的摘要信息B;
  • 對比摘要信息A與B,相同則證書驗證通過;
3.2、校驗證書是否在上級證書的吊銷列表

CA機構能夠簽發證書,同樣也存在機制宣布以往簽發的證書無效。使用者私鑰丟失,使用者申請讓證書無效等情況,CA機構需要廢棄該證書。
主要存在兩類機制:CRL 與 OCSP。

  • CRL(Certificate Revocation List)
    證書吊銷列表是一個單獨的文件,該文件包含了 CA機構 已經吊銷的證書序列號與吊銷日期;
    證書中一般會包含一個 URL 地址 CRL Distribution Point,通知使用者去哪裡下載對應的 CRL 以校驗證書是否吊銷。
    該吊銷方式的優點是不需要頻繁更新,但是不能及時吊銷證書,因為 CRL 更新時間一般是幾天,這期間可能已經造成了極大損失。
  • OCSP(Online Certificate Status Protocol)
    證書狀態在線查詢協議,一個實時查詢證書是否吊銷的方式。
    請求者發送證書的信息並請求查詢,服務器返回正常、吊銷或未知中的任何一個狀態。
    證書中一般也會包含一個 OCSP 的 URL 地址,要求查詢服務器具有良好的性能。
    部分 CA 或大部分的自簽 CA (根證書)都是未提供 CRL 或 OCSP 地址的,對於吊銷證書會是一件非常麻煩的事情。
3.3、校驗證書是否過期

校驗證書的有效期是否已經過期

3.4、校驗證書域名是否一致

校驗證書域名是否一致:核查證書域名是否與當前的訪問域名匹配
這裏核驗的是我們請求的域名 www.baidu.com 是否與證書文件中DNS標籤下所列的域名相匹配;

注:
具體的證書文件舉例,請查看第四節 “四、證書舉例” 。

一種錯誤的寫法:

Android 軟件開發中,我們經常會遇到以下代碼,用來忽略證書的域名驗證,其實這是一種不安全的寫法:

// 對於自簽名證書,用以下代碼來忽略證書的域名驗證
HostnameVerifier hostnameVerifier = new HostnameVerifier() {
    @Override
    public boolean verify(String urlHostName, SSLSession session) {
		// 忽略證書的域名驗證
        return true;
    }
};

四、證書舉例

這裏以百度的Https證書舉例:

Certificate:
	Data:
	    Version: 3 (0x2)
	    Serial Number:
	        72:58:78:36:6e:9f:56:e8:1d:41:88:48
	Signature Algorithm: sha256WithRSAEncryption
	    Issuer: C=BE, O=GlobalSign nv-sa, CN=GlobalSign Organization Validation CA - SHA256 - G2
	    Validity
	        Not Before: Apr  2 07:04:58 2020 GMT
	        Not After : Jul 26 05:31:02 2021 GMT
	    Subject: C=CN, ST=beijing, L=beijing, OU=service operation department, O=Beijing Baidu Netcom Science Technology Co., Ltd, CN=baidu.com
	    Subject Public Key Info:
	        Public Key Algorithm: rsaEncryption
	            Public-Key: (2048 bit)
	            Modulus:
	                00:c1:a9:b0:ae:47:1a:d2:57:eb:1d:15:1f:6e:5c:
	                b2:e4:f8:0b:20:db:ea:00:df:29:ff:a4:6b:89:26:
	                4b:9f:23:2f:ec:57:b0:8a:b8:46:40:2a:7e:bc:dc:
	                5a:45:97:4f:ad:41:0e:bc:20:86:4b:0c:5d:55:21:
	                47:e2:31:3c:57:a7:ec:99:47:eb:47:0d:72:d7:c8:
	                16:54:75:ef:d3:45:11:0f:4b:ce:60:7a:46:5c:28:
	                74:ae:8e:1b:be:d8:70:66:7b:a8:93:49:28:d2:a3:
	                76:94:55:de:7c:27:f2:0f:f7:98:0c:ad:86:da:c6:
	                ae:fd:9f:f0:d9:81:32:9a:97:e3:21:ee:04:92:96:
	                e4:78:11:e5:c4:10:0e:10:31:7a:4a:97:a0:eb:c7:
	                9b:c4:da:89:37:a9:c3:37:d7:56:b1:7f:52:c7:d9:
	                26:0a:d6:af:38:16:b1:6d:fb:73:79:b1:68:79:03:
	                90:eb:88:7b:8c:48:91:98:51:a5:07:94:86:a5:78:
	                46:79:8f:58:9b:e9:35:59:a7:f1:7b:57:31:0a:90:
	                cf:24:ce:0d:24:e7:92:b2:6a:e9:e6:96:37:0a:b8:
	                7c:87:2f:74:d2:5c:e8:4b:0a:5f:66:18:a7:41:86:
	                cf:26:a6:08:8e:a5:49:17:92:53:b3:91:a5:cf:53:
	                b0:31
	            Exponent: 65537 (0x10001)
	    X509v3 extensions:
	        X509v3 Key Usage: critical
	            Digital Signature, Key Encipherment
	        Authority Information Access: 
	            CA Issuers - URI:http://secure.globalsign.com/cacert/gsorganizationvalsha2g2r1.crt
	            OCSP - URI:http://ocsp2.globalsign.com/gsorganizationvalsha2g2

	        X509v3 Certificate Policies: 
	            Policy: 1.3.6.1.4.1.4146.1.20
	              CPS: https://www.globalsign.com/repository/
	            Policy: 2.23.140.1.2.2

	        X509v3 Basic Constraints: 
	            CA:FALSE
	        X509v3 CRL Distribution Points: 

	            Full Name:
	              URI:http://crl.globalsign.com/gs/gsorganizationvalsha2g2.crl

	        X509v3 Subject Alternative Name: 
	            DNS:baidu.com, DNS:baifubao.com, DNS:www.baidu.cn, DNS:www.baidu.com.cn, DNS:mct.y.nuomi.com, DNS:apollo.auto, DNS:dwz.cn, DNS:*.baidu.com, DNS:*.baifubao.com, DNS:*.baidustatic.com, DNS:*.bdstatic.com, DNS:*.bdimg.com, DNS:*.hao123.com, DNS:*.nuomi.com, DNS:*.chuanke.com, DNS:*.trustgo.com, DNS:*.bce.baidu.com, DNS:*.eyun.baidu.com, DNS:*.map.baidu.com, DNS:*.mbd.baidu.com, DNS:*.fanyi.baidu.com, DNS:*.baidubce.com, DNS:*.mipcdn.com, DNS:*.news.baidu.com, DNS:*.baidupcs.com, DNS:*.aipage.com, DNS:*.aipage.cn, DNS:*.bcehost.com, DNS:*.safe.baidu.com, DNS:*.im.baidu.com, DNS:*.baiducontent.com, DNS:*.dlnel.com, DNS:*.dlnel.org, DNS:*.dueros.baidu.com, DNS:*.su.baidu.com, DNS:*.91.com, DNS:*.hao123.baidu.com, DNS:*.apollo.auto, DNS:*.xueshu.baidu.com, DNS:*.bj.baidubce.com, DNS:*.gz.baidubce.com, DNS:*.smartapps.cn, DNS:*.bdtjrcv.com, DNS:*.hao222.com, DNS:*.haokan.com, DNS:*.pae.baidu.com, DNS:*.vd.bdstatic.com, DNS:click.hm.baidu.com, DNS:log.hm.baidu.com, DNS:cm.pos.baidu.com, DNS:wn.pos.baidu.com, DNS:update.pan.baidu.com
	        X509v3 Extended Key Usage: 
	            TLS Web Server Authentication, TLS Web Client Authentication
	        X509v3 Authority Key Identifier: 
	            keyid:96:DE:61:F1:BD:1C:16:29:53:1C:C0:CC:7D:3B:83:00:40:E6:1A:7C

	        X509v3 Subject Key Identifier: 
	            ......

五、參考

TSL:
https://tools.ietf.org/html/rfc5246

SSL/TSL 原理:
https://www.cnblogs.com/chenjingquan/p/10531305.html

TLS/SSL握手過程
https://blog.csdn.net/hherima/article/details/52469674

========== THE END ==========

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

【其他文章推薦】

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

新北清潔公司,居家、辦公、裝潢細清專業服務

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

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

※超省錢租車方案

python多線程+生產者和消費者模型+queue使用

多線程簡介

多線程:在一個進程內部,要同時干很多事情,就需要同時執行多個子任務,我們把進程內的這些子任務叫線程。
線程的內存空間是共享的,每個線程都共享同一個進程的資源
模塊:
1、_thread模塊 低級模塊(在python3里基本已棄用)
2、threading模塊 高級模塊 對_thread模塊進行了封裝

threading模塊使用

1.使用元組傳遞 threading.Thread(target=方法名,arg=(參數1,參數2...))
2.用字典傳遞 threading.Thread(target=方法名,kwargs={“參數名”:參數1,“參數名”:參數2,....})
3.混合使用元組和字典 threading.Thread(target=方法名,args=(參數1,參數2,...),kwargs={“參數名”:參數1,“參數名”:參數2,....})
4.查看線程數:
使用threading.enumerate()函數便可以看到當前線程的數量。
5.查看當前線程的名字:
使用threading.current_thread()可以看到當前線程的信息。
6.join([time]):等待至線程終止。這阻塞調用線程直至線程的join()方法被調用終止、正常退出或者拋出未處理的異常、或者是可選的超時發生。
7.isAlive():返回線程是否活動
8.getName(): 返回線程名
9.setNmae():設置線程名
10.後台線程(守護線程)
後台線程有一個特徵:如果所有的前台線程都死亡了,那麼後台線程也會自動死亡。
調用Thread對象的daemon屬性可將指定線程設置為後台線程。在下面程序可以看到程序里的線程被指定為後台線程,當所有前台程序都死亡了后,後台線程隨之死亡。當在整個虛擬機里只剩下後台線程時,程序就沒有繼續運行的必要了,所以程序也就退出了。

import threading
# 定義後台線程的線程執行體與普通線程沒有任何區別
def action(max):
    for i in range(max):
        print(threading.current_thread().name + "  " + str(i))
t = threading.Thread(target=action, args=(100,), name='後台線程')
# 將此線程設置成後台線程
# 也可在創建Thread對象時通過daemon參數將其設為後台線程
t.daemon = True
# 啟動後台線程
t.start()
for i in range(10):
    print(threading.current_thread().name + "  " + str(i))
# -----程序執行到此處,前台線程(主線程)結束------
# 後台線程也應該隨之結束

上面程序中的粗體字代碼先將t線程設置成後台線程,然後啟動該線程。本來該線程應該執行到i等於99時才會結束,但在運行程序時不難發現,該後台線程無法運行到99,因為當主線程也就是程序中唯一的前台線程運行結東后,程序會主動退出,所以後台線程也就被結東了。從上面的程序可以看出,主線程默認是前台線程,t線程默認也是前台線程。但並不是所有的線程默認都是前台線程,有些線程默認就是後台線程一一前台線程創建的子線程默認是前台線程,後台線程創建的子線程默認是後台線程
可見,創建後台線程有兩種方式。

  1. 主動將線程的 daemon屬性設置為True
  2. 後台線程啟動的線程默認是後台線程。

以下看一個簡單的多線程程序:

import threading
import time

def coding():
    for x in range(3):
        print('%s正在寫代碼' % x)
        time.sleep(1)

def drawing():
    for x in range(3):
        print('%s正在畫圖' % x)
        time.sleep(1)


def single_thread():
    coding()
    drawing()

def multi_thread():
    t1 = threading.Thread(target=coding)
    t2 = threading.Thread(target=drawing)

    t1.start()
    t2.start()

if __name__ == '__main__':
    multi_thread()

繼承自threading.Thread類:

為了讓線程代碼更好的封裝。可以使用threading模塊下的Thread類,繼承自這個類,然後實現run方法,線程就會自動運行run方法中的代碼。示例代碼如下:

import threading
import time

class CodingThread(threading.Thread):
    def run(self):
        for x in range(3):
            print('%s正在寫代碼' % threading.current_thread())
            time.sleep(1)

class DrawingThread(threading.Thread):
    def run(self):
        for x in range(3):
            print('%s正在畫圖' % threading.current_thread())
            time.sleep(1)

def multi_thread():
    t1 = CodingThread()
    t2 = DrawingThread()

    t1.start()
    t2.start()

if __name__ == '__main__':
    multi_thread()

start()和run()

start()
start()方法來啟動線程,真正實現了多線程運行。這時無需等待run方法體代碼執行完畢,可以直接繼續執行下面的代碼;通過調用Thread類的start()方法來啟動一個線程, 這時此線程是處於就緒狀態, 並沒有運行。 然後通過此Thread類調用方法run()來完成其運行操作的, 這裏方法run()稱為線程體,它包含了要執行的這個線程的內容, Run方法運行結束, 此線程終止。然後CPU再調度其它線程。run()
run()
run()方法當作普通方法的方式調用。程序還是要順序執行,要等待run方法體執行完畢后,才可繼續執行下面的代碼; 程序中只有主線程——這一個線程, 其程序執行路徑還是只有一條, 這樣就沒有達到寫線程的目的。
記住:多線程就是分時利用CPU,宏觀上讓所有線程一起執行 ,也叫併發。start() 和 run()的區別說明

start() : 它的作用是啟動一個新線程,新線程會執行相應的run()方法。start()不能被重複調用。
run() : run()就和普通的成員方法一樣,可以被重複調用。單獨調用run()的話,會在當前線程中執行run(),而並不會啟動新線程!

Lock版本生產者和消費者模型

生產者和消費者模式是多線程開發中經常見到的一種模式。生產者的線程專門用來生產一些數據,然後存放到一个中間的變量中。消費者再從這个中間的變量中取出數據進行消費。但是因為要使用中間變量,中間變量經常是一些全局變量,因此需要使用鎖來保證數據完整性。以下是使用threading.Lock鎖實現的“生產者與消費者模式”的一個例子:

import threading
import random
import time

gMoney = 1000
glo = threading.Lock()
gTotaltime = 10
gTime = 0
class Consumer(threading.Thread):
    def run(self):
        global gMoney
        global gTime
        while True:
            money = random.randint(100,1000)
            glo.acquire()
            if gMoney>= money:
                gMoney -= money
                print("{}消費了{}元,當前剩餘{}元".format(threading.current_thread(),money,gMoney))
            else:
                print("{}準備消費{}元,當前剩餘{}元,不足,不能消費".format(threading.current_thread(),money,gMoney))
            if gTime >= gTotaltime and money > gMoney:
                glo.release()
                break
            glo.release()
            time.sleep(0.7)

class Porducer(threading.Thread):
    def run(self):
        global gMoney
        global gTime
        while True:
            Money = random.randint(100,700)
            glo.acquire()
            if gTime == gTotaltime:
                glo.release()
                break
            gMoney += Money
            print("{}生產了{}元錢,剩餘{}元錢".format(threading.current_thread(),Money,gMoney))
            gTime += 1
            glo.release()
            time.sleep(0.5)

def main():
    for x in range(3):
       t1 = Porducer(name="生產者")
       t1.start()

    for i in range(5):
       t = Consumer(name="消費者")
       t.start()

if __name__ == '__main__':
    main()

queue線程安全隊列

在線程中,訪問一些全局變量,加鎖是一個經常的過程。如果你是想把一些數據存儲到某個隊列中,那麼Python內置了一個線程安全的模塊叫做queue模塊。Python中的queue模塊中提供了同步的、線程安全的隊列類,包括FIFO(先進先出)隊列Queue,LIFO(后入先出)隊列LifoQueue。這些隊列都實現了鎖原語(可以理解為原子操作,即要麼不做,要麼都做完),能夠在多線程中直接使用。可以使用隊列來實現線程間的同步。相關的函數如下:

  1. 初始化Queue(maxsize):創建一個先進先出的隊列。
  2. qsize():返回隊列的大小。
  3. empty():判斷隊列是否為空。
  4. full():判斷隊列是否滿了。
  5. get():從隊列中取最後一個數據。
  6. put(item,block=Ture,timeout=None):將一個數據放到隊列中。如果隊列已滿,且block參數為Ture(阻塞),當前線程被阻塞,timeout指定阻塞時間,如果將timeout設置為None,則代表一直阻塞,直到有元素被放入隊列中:如果隊列已空,且block參數設置為False(不阻塞),則直接引發queue.Empty異常。
    下面就可以用queue來進行線程通信
import queue
import time
import threading

def set_value(q):
    index = 0
    while True:
        q.put(index)
        index += 1
        time.sleep(3)

def get_value(q):
    index = 0
    while True:
        print(q.get())
        time.sleep(0.5)
def main():
    q = queue.Queue(4)
    t1 = threading.Thread(target=set_value,args=[q])
    t2 = threading.Thread(target=get_value,args=[q])
    t1.start()
    t2.start()


if __name__ == '__main__':
    main()

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

【其他文章推薦】

新北清潔公司,居家、辦公、裝潢細清專業服務

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

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

※超省錢租車方案

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

手寫React的Fiber架構,深入理解其原理

熟悉React的朋友都知道,React支持jsx語法,我們可以直接將HTML代碼寫到JS中間,然後渲染到頁面上,我們寫的HTML如果有更新的話,React還有虛擬DOM的對比,只更新變化的部分,而不重新渲染整個頁面,大大提高渲染效率。到了16.x,React更是使用了一個被稱為Fiber的架構,提升了用戶體驗,同時還引入了hooks等特性。那隱藏在React背後的原理是怎樣的呢,Fiberhooks又是怎麼實現的呢?本文會從jsx入手,手寫一個簡易版的React,從而深入理解React的原理。

本文主要實現了這些功能:

簡易版Fiber架構

簡易版DIFF算法

簡易版函數組件

簡易版Hook: useState

娛樂版Class組件

本文代碼地址:https://github.com/dennis-jiang/Front-End-Knowledges/tree/master/Examples/React/fiber-and-hooks

本文程序跑起來效果如下:

JSX和creatElement

以前我們寫React要支持JSX還需要一個庫叫JSXTransformer.js,後來JSX的轉換工作都集成到了babel裏面了,babel還提供了在線預覽的功能,可以看到轉換后的效果,比如下面這段簡單的代碼:

const App =
(
  <div>
    <h1 id="title">Title</h1>
    <a href="xxx">Jump</a>
    <section>
      <p>
        Article
      </p>
    </section>
  </div>
);

經過babel轉換后就變成了這樣:

上面的截圖可以看出我們寫的HTML被轉換成了React.createElement,我們將上面代碼稍微格式化來看下:

var App = React.createElement(
  'div',
  null,
  React.createElement(
    'h1',
    {
      id: 'title',
    },
    'Title',
  ),
  React.createElement(
    'a',
    {
      href: 'xxx',
    },
    'Jump',
  ),
  React.createElement(
    'section',
    null,
    React.createElement('p', null, 'Article'),
  ),
);

從轉換后的代碼我們可以看出React.createElement支持多個參數:

  1. type,也就是節點類型
  2. config, 這是節點上的屬性,比如idhref
  3. children, 從第三個參數開始就全部是children也就是子元素了,子元素可以有多個,類型可以是簡單的文本,也可以還是React.createElement,如果是React.createElement,其實就是子節點了,子節點下面還可以有子節點。這樣就用React.createElement的嵌套關係實現了HTML節點的樹形結構。

讓我們來完整看下這個簡單的React頁面代碼:

渲染在頁面上是這樣:

這裏面用到了React的地方其實就兩個,一個是JSX,也就是React.createElement,另一個就是ReactDOM.render,所以我們手寫的第一個目標就有了,就是createElementrender這兩個方法。

手寫createElement

對於<h1 id="title">Title</h1>這樣一個簡單的節點,原生DOM也會附加一大堆屬性和方法在上面,所以我們在createElement的時候最好能將它轉換為一種比較簡單的數據結構,只包含我們需要的元素,比如這樣:

{
  type: 'h1',
  props: {
    id: 'title',
    children: 'Title'
  }
}

有了這個數據結構后,我們對於DOM的操作其實可以轉化為對這個數據結構的操作,新老DOM的對比其實也可以轉化為這個數據結構的對比,這樣我們就不需要每次操作都去渲染頁面,而是等到需要渲染的時候才將這個數據結構渲染到頁面上。這其實就是虛擬DOM!而我們createElement就是負責來構建這個虛擬DOM的方法,下面我們來實現下:

function createElement(type, props, ...children) {
  // 核心邏輯不複雜,將參數都塞到一個對象上返回就行
  // children也要放到props裏面去,這樣我們在組件裏面就能通過this.props.children拿到子元素
  return {
    type,
    props: {
      ...props,
      children
    }
  }
}

上述代碼是React的createElement簡化版,對源碼感興趣的朋友可以看這裏:https://github.com/facebook/react/blob/60016c448bb7d19fc989acd05dda5aca2e124381/packages/react/src/ReactElement.js#L348

手寫render

上述代碼我們用createElement將JSX代碼轉換成了虛擬DOM,那真正將它渲染到頁面的函數是render,所以我們還需要實現下這個方法,通過我們一般的用法ReactDOM.render( <App />,document.getElementById('root'));可以知道他接收兩個參數:

  1. 根組件,其實是一個JSX組件,也就是一個createElement返回的虛擬DOM
  2. 父節點,也就是我們要將這個虛擬DOM渲染的位置

有了這兩個參數,我們來實現下render方法:

function render(vDom, container) {
  let dom;
  // 檢查當前節點是文本還是對象
  if(typeof vDom !== 'object') {
    dom = document.createTextNode(vDom)
  } else {
    dom = document.createElement(vDom.type);
  }

  // 將vDom上除了children外的屬性都掛載到真正的DOM上去
  if(vDom.props) {
    Object.keys(vDom.props)
      .filter(key => key != 'children')
      .forEach(item => {
        dom[item] = vDom.props[item];
      })
  }
  
  // 如果還有子元素,遞歸調用
  if(vDom.props && vDom.props.children && vDom.props.children.length) {
    vDom.props.children.forEach(child => render(child, dom));
  }

  container.appendChild(dom);
}

上述代碼是簡化版的render方法,對源碼感興趣的朋友可以看這裏:https://github.com/facebook/react/blob/3e94bce765d355d74f6a60feb4addb6d196e3482/packages/react-dom/src/client/ReactDOMLegacy.js#L287

現在我們可以用自己寫的createElementrender來替換原生的方法了:

可以得到一樣的渲染結果:

為什麼需要Fiber

上面我們簡單的實現了虛擬DOM渲染到頁面上的代碼,這部分工作被React官方稱為renderer,renderer是第三方可以自己實現的一個模塊,還有個核心模塊叫做reconsiler,reconsiler的一大功能就是大家熟知的diff,他會計算出應該更新哪些頁面節點,然後將需要更新的節點虛擬DOM傳遞給renderer,renderer負責將這些節點渲染到頁面上。但是這個流程有個問題,雖然React的diff算法是經過優化的,但是他卻是同步的,renderer負責操作DOM的appendChild等API也是同步的,也就是說如果有大量節點需要更新,JS線程的運行時間可能會比較長,在這段時間瀏覽器是不會響應其他事件的,因為JS線程和GUI線程是互斥的,JS運行時頁面就不會響應,這個時間太長了,用戶就可能看到卡頓,特別是動畫的卡頓會很明顯。在React的官方演講中有個例子,可以很明顯的看到這種同步計算造成的卡頓:

而Fiber就是用來解決這個問題的,Fiber可以將長時間的同步任務拆分成多個小任務,從而讓瀏覽器能夠抽身去響應其他事件,等他空了再回來繼續計算,這樣整個計算流程就顯得平滑很多。下面是使用Fiber后的效果:

怎麼來拆分

上面我們自己實現的render方法直接遞歸遍歷了整個vDom樹,如果我們在中途某一步停下來,下次再調用時其實並不知道上次在哪裡停下來的,不知道從哪裡開始,即使你將上次的結束節點記下來了,你也不知道下一個該執行哪個,所以vDom的樹形結構並不滿足中途暫停,下次繼續的需求,需要改造數據結構。另一個需要解決的問題是,拆分下來的小任務什麼時候執行?我們的目的是讓用戶有更流暢的體驗,所以我們最好不要阻塞高優先級的任務,比如用戶輸入,動畫之類,等他們執行完了我們再計算。那我怎麼知道現在有沒有高優先級任務,瀏覽器是不是空閑呢?總結下來,Fiber要想達到目的,需要解決兩個問題:

  1. 新的任務調度,有高優先級任務的時候將瀏覽器讓出來,等瀏覽器空了再繼續執行
  2. 新的數據結構,可以隨時中斷,下次進來可以接着執行

requestIdleCallback

requestIdleCallback是一個實驗中的新API,這個API調用方式如下:

// 開啟調用
var handle = window.requestIdleCallback(callback[, options])

// 結束調用
Window.cancelIdleCallback(handle) 

requestIdleCallback接收一個回調,這個回調會在瀏覽器空閑時調用,每次調用會傳入一個IdleDeadline,可以拿到當前還空餘多久,options可以傳入參數最多等多久,等到了時間瀏覽器還不空就強制執行了。使用這個API可以解決任務調度的問題,讓瀏覽器在空閑時才計算diff並渲染。更多關於requestIdleCallback的使用可以查看MDN的文檔。但是這個API還在實驗中,兼容性不好,所以React官方自己實現了一套。本文會繼續使用requestIdleCallback來進行任務調度,我們進行任務調度的思想是將任務拆分成多個小任務,requestIdleCallback裏面不斷的把小任務拿出來執行,當所有任務都執行完或者超時了就結束本次執行,同時要註冊下次執行,代碼架子就是這樣:

function workLoop(deadline) {
  while(nextUnitOfWork && deadline.timeRemaining() > 1) {
    // 這個while循環會在任務執行完或者時間到了的時候結束
    nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
  }

  // 如果任務還沒完,但是時間到了,我們需要繼續註冊requestIdleCallback
  requestIdleCallback(workLoop);
}

// performUnitOfWork用來執行任務,參數是我們的當前fiber任務,返回值是下一個任務
function performUnitOfWork(fiber) {
  
}
requestIdleCallback(workLoop);

上述workLoop對應React源碼看這裏。

Fiber可中斷數據結構

上面我們的performUnitOfWork並沒有實現,但是從上面的結構可以看出來,他接收的參數是一個小任務,同時通過這個小任務還可以找到他的下一個小任務,Fiber構建的就是這樣一個數據結構。Fiber之前的數據結構是一棵樹,父節點的children指向了子節點,但是只有這一個指針是不能實現中斷繼續的。比如我現在有一個父節點A,A有三個子節點B,C,D,當我遍歷到C的時候中斷了,重新開始的時候,其實我是不知道C下面該執行哪個的,因為只知道C,並沒有指針指向他的父節點,也沒有指針指向他的兄弟。Fiber就是改造了這樣一個結構,加上了指向父節點和兄弟節點的指針:

上面的圖片還是來自於官方的演講,可以看到和之前父節點指向所有子節點不同,這裡有三個指針:

  1. child: 父節點指向第一個子元素的指針。
  2. sibling:從第一個子元素往後,指向下一個兄弟元素。
  3. return:所有子元素都有的指向父元素的指針。

有了這幾個指針后,我們可以在任意一個元素中斷遍歷並恢復,比如在上圖List處中斷了,恢復的時候可以通過child找到他的子元素,也可以通過return找到他的父元素,如果他還有兄弟節點也可以用sibling找到。Fiber這個結構外形看着還是棵樹,但是沒有了指向所有子元素的指針,父節點只指向第一個子節點,然後子節點有指向其他子節點的指針,這其實是個鏈表。

實現Fiber

現在我們可以自己來實現一下Fiber了,我們需要將之前的vDom結構轉換為Fiber的數據結構,同時需要能夠通過其中任意一個節點返回下一個節點,其實就是遍歷這個鏈表。遍歷的時候從根節點出發,先找子元素,如果子元素存在,直接返回,如果沒有子元素了就找兄弟元素,找完所有的兄弟元素后再返回父元素,然後再找這個父元素的兄弟元素。整個遍歷過程其實是個深度優先遍歷,從上到下,然後最後一行開始從左到右遍歷。比如下圖從div1開始遍歷的話,遍歷的順序就應該是div1 -> div2 -> h1 -> a -> div2 -> p -> div1。可以看到這個序列中,當我們return父節點時,這些父節點會被第二次遍歷,所以我們寫代碼時,return的父節點不會作為下一個任務返回,只有siblingchild才會作為下一個任務返回。

// performUnitOfWork用來執行任務,參數是我們的當前fiber任務,返回值是下一個任務
function performUnitOfWork(fiber) {
  // 根節點的dom就是container,如果沒有這個屬性,說明當前fiber不是根節點
  if(!fiber.dom) {
    fiber.dom = createDom(fiber);   // 創建一個DOM掛載上去
  } 

  // 如果有父節點,將當前節點掛載到父節點上
  if(fiber.return) {
    fiber.return.dom.appendChild(fiber.dom);
  }

  // 將我們前面的vDom結構轉換為fiber結構
  const elements = fiber.children;
  let prevSibling = null;
  if(elements && elements.length) {
    for(let i = 0; i < elements.length; i++) {
      const element = elements[i];
      const newFiber = {
        type: element.type,
        props: element.props,
        return: fiber,
        dom: null
      }

      // 父級的child指向第一個子元素
      if(i === 0) {
        fiber.child = newFiber;
      } else {
        // 每個子元素擁有指向下一個子元素的指針
        prevSibling.sibling = newFiber;
      }

      prevSibling = newFiber;
    }
  }

  // 這個函數的返回值是下一個任務,這其實是一個深度優先遍歷
  // 先找子元素,沒有子元素了就找兄弟元素
  // 兄弟元素也沒有了就返回父元素
  // 然後再找這個父元素的兄弟元素
  // 最後到根節點結束
  // 這個遍歷的順序其實就是從上到下,從左到右
  if(fiber.child) {
    return fiber.child;
  }

  let nextFiber = fiber;
  while(nextFiber) {
    if(nextFiber.sibling) {
      return nextFiber.sibling;
    }

    nextFiber = nextFiber.return;
  }
}

React源碼中的performUnitOfWork看這裏,當然比我們這個複雜很多。

統一commit DOM操作

上面我們的performUnitOfWork一邊構建Fiber結構一邊操作DOMappendChild,這樣如果某次更新好幾個節點,操作了第一個節點之後就中斷了,那我們可能只看到第一個節點渲染到了頁面,後續幾個節點等瀏覽器空了才陸續渲染。為了避免這種情況,我們應該將DOM操作都搜集起來,最後統一執行,這就是commit。為了能夠記錄位置,我們還需要一個全局變量workInProgressRoot來記錄根節點,然後在workLoop檢測如果任務執行完了,就commit:

function workLoop(deadline) {
  while(nextUnitOfWork && deadline.timeRemaining() > 1) {
    // 這個while循環會在任務執行完或者時間到了的時候結束
    nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
  }

  // 任務做完后統一渲染
  if(!nextUnitOfWork && workInProgressRoot) {
    commitRoot();
  }

  // 如果任務還沒完,但是時間到了,我們需要繼續註冊requestIdleCallback
  requestIdleCallback(workLoop);
}

因為我們是在Fiber樹完全構建后再執行的commit,而且有一個變量workInProgressRoot指向了Fiber的根節點,所以我們可以直接把workInProgressRoot拿過來遞歸渲染就行了:

// 統一操作DOM
function commitRoot() {
  commitRootImpl(workInProgressRoot.child);    // 開啟遞歸
  workInProgressRoot = null;     // 操作完后將workInProgressRoot重置
}

function commitRootImpl(fiber) {
  if(!fiber) {
    return;
  }

  const parentDom = fiber.return.dom;
  parentDom.appendChild(fiber.dom);

  // 遞歸操作子元素和兄弟元素
  commitRootImpl(fiber.child);
  commitRootImpl(fiber.sibling);
}

reconcile調和

reconcile其實就是虛擬DOM樹的diff操作,需要刪除不需要的節點,更新修改過的節點,添加新的節點。為了在中斷後能回到工作位置,我們還需要一個變量currentRoot,然後在fiber節點裏面添加一個屬性alternate,這個屬性指向上一次運行的根節點,也就是currentRootcurrentRoot會在第一次render后的commit階段賦值,也就是每次計算完后都會把當次狀態記錄在alternate上,後面更新了就可以把alternate拿出來跟新的狀態做diff。然後performUnitOfWork裏面需要添加調和子元素的代碼,可以新增一個函數reconcileChildren。這個函數裏面不能簡單的創建新節點了,而是要將老節點跟新節點拿來對比,對比邏輯如下:

  1. 如果新老節點類型一樣,復用老節點DOM,更新props
  2. 如果類型不一樣,而且新的節點存在,創建新節點替換老節點
  3. 如果類型不一樣,沒有新節點,有老節點,刪除老節點

注意刪除老節點的操作是直接將oldFiber加上一個刪除標記就行,同時用一個全局變量deletions記錄所有需要刪除的節點:

      // 對比oldFiber和當前element
      const sameType = oldFiber && element && oldFiber.type === element.type;  //檢測類型是不是一樣
      // 先比較元素類型
      if(sameType) {
        // 如果類型一樣,復用節點,更新props
        newFiber = {
          type: oldFiber.type,
          props: element.props,
          dom: oldFiber.dom,
          return: workInProgressFiber,
          alternate: oldFiber,          // 記錄下上次狀態
          effectTag: 'UPDATE'           // 添加一個操作標記
        }
      } else if(!sameType && element) {
        // 如果類型不一樣,有新的節點,創建新節點替換老節點
        newFiber = {
          type: element.type,
          props: element.props,
          dom: null,                    // 構建fiber時沒有dom,下次perform這個節點是才創建dom
          return: workInProgressFiber,
          alternate: null,              // 新增的沒有老狀態
          effectTag: 'REPLACEMENT'      // 添加一個操作標記
        }
      } else if(!sameType && oldFiber) {
        // 如果類型不一樣,沒有新節點,有老節點,刪除老節點
        oldFiber.effectTag = 'DELETION';   // 添加刪除標記
        deletions.push(oldFiber);          // 一個數組收集所有需要刪除的節點
      }

然後就是在commit階段處理真正的DOM操作,具體的操作是根據我們的effectTag來判斷的:

function commitRootImpl(fiber) {
  if(!fiber) {
    return;
  }

  const parentDom = fiber.return.dom;
  if(fiber.effectTag === 'REPLACEMENT' && fiber.dom) {
    parentDom.appendChild(fiber.dom);
  } else if(fiber.effectTag === 'DELETION') {
    parentDom.removeChild(fiber.dom);
  } else if(fiber.effectTag === 'UPDATE' && fiber.dom) {
    // 更新DOM屬性
    updateDom(fiber.dom, fiber.alternate.props, fiber.props);
  }

  // 遞歸操作子元素和兄弟元素
  commitRootImpl(fiber.child);
  commitRootImpl(fiber.sibling);
}

替換和刪除的DOM操作都比較簡單,更新屬性的會稍微麻煩點,需要再寫一個輔助函數updateDom來實現:

// 更新DOM的操作
function updateDom(dom, prevProps, nextProps) {
  // 1. 過濾children屬性
  // 2. 老的存在,新的沒了,取消
  // 3. 新的存在,老的沒有,新增
  Object.keys(prevProps)
    .filter(name => name !== 'children')
    .filter(name => !(name in nextProps))
    .forEach(name => {
      if(name.indexOf('on') === 0) {
        dom.removeEventListener(name.substr(2).toLowerCase(), prevProps[name], false);
      } else {
        dom[name] = '';
      }
    });

  Object.keys(nextProps)
    .filter(name => name !== 'children')
    .forEach(name => {
      if(name.indexOf('on') === 0) {
        dom.addEventListener(name.substr(2).toLowerCase(), nextProps[name], false);
      } else {
        dom[name] = nextProps[name];
      }
    });
}

updateDom的代碼寫的比較簡單,事件只處理了簡單的on開頭的,兼容性也有問題,prevPropsnextProps可能會遍歷到相同的屬性,有重複賦值,但是總體原理還是沒錯的。要想把這個處理寫全,代碼量還是不少的。

函數組件

函數組件是React裏面很常見的一種組件,我們前面的React架構其實已經寫好了,我們這裏來支持下函數組件。我們之前的fiber節點上的type都是DOM節點的類型,比如h1什麼的,但是函數組件的節點type其實就是一個函數了,我們需要對這種節點進行單獨處理。

首先需要在更新的時候檢測當前節點是不是函數組件,如果是,children的處理邏輯會稍微不一樣:

// performUnitOfWork裏面
// 檢測函數組件
function performUnitOfWork(fiber) {
  const isFunctionComponent = fiber.type instanceof Function;
  if(isFunctionComponent) {
    updateFunctionComponent(fiber);
  } else {
    updateHostComponent(fiber);
  }
  
  // ...下面省略n行代碼...
}

function updateFunctionComponent(fiber) {
  // 函數組件的type就是個函數,直接拿來執行可以獲得DOM元素
  const children = [fiber.type(fiber.props)];

  reconcileChildren(fiber, children);
}

// updateHostComponent就是之前的操作,只是單獨抽取了一個方法
function updateHostComponent(fiber) {
  if(!fiber.dom) {
    fiber.dom = createDom(fiber);   // 創建一個DOM掛載上去
  } 

  // 將我們前面的vDom結構轉換為fiber結構
  const elements = fiber.props.children;

  // 調和子元素
  reconcileChildren(fiber, elements);
}

然後在我們提交DOM操作的時候因為函數組件沒有DOM元素,所以需要注意兩點:

  1. 獲取父級DOM元素的時候需要遞歸網上找真正的DOM
  2. 刪除節點的時候需要遞歸往下找真正的節點

我們來修改下commitRootImpl:

function commitRootImpl() {
  // const parentDom = fiber.return.dom;
  // 向上查找真正的DOM
  let parentFiber = fiber.return;
  while(!parentFiber.dom) {
    parentFiber = parentFiber.return;
  }
  const parentDom = parentFiber.dom;
  
  // ...這裏省略n行代碼...
  
  if{fiber.effectTag === 'DELETION'} {
    commitDeletion(fiber, parentDom);
  }
}

function commitDeletion(fiber, domParent) {
  if(fiber.dom) {
    // dom存在,是普通節點
    domParent.removeChild(fiber.dom);
  } else {
    // dom不存在,是函數組件,向下遞歸查找真實DOM
    commitDeletion(fiber.child, domParent);
  }
}

現在我們可以傳入函數組件了:

import React from './myReact';
const ReactDOM = React;

function App(props) {
  return (
    <div>
      <h1 id="title">{props.title}</h1>
      <a href="xxx">Jump</a>
      <section>
        <p>
          Article
        </p>
      </section>
    </div>
  );
}

ReactDOM.render(
  <App title="Fiber Demo"/>,
  document.getElementById('root')
);

實現useState

useState是React Hooks裏面的一個API,相當於之前Class Component裏面的state,用來管理組件內部狀態,現在我們已經有一個簡化版的React了,我們也可以嘗試下來實現這個API。

簡單版

我們還是從用法入手來實現最簡單的功能,我們一般使用useState是這樣的:

function App(props) {
  const [count, setCount] = React.useState(1);
  const onClickHandler = () => {
    setCount(count + 1);
  }
  return (
    <div>
      <h1>Count: {count}</h1>
      <button onClick={onClickHandler}>Count+1</button>
    </div>
  );
}

ReactDOM.render(
  <App title="Fiber Demo"/>,
  document.getElementById('root')
);

上述代碼可以看出,我們的useState接收一個初始值,返回一個數組,裏面有這個state的當前值和改變state的方法,需要注意的是App作為一個函數組件,每次render的時候都會運行,也就是說裏面的局部變量每次render的時候都會重置,那我們的state就不能作為一個局部變量,而是應該作為一個全部變量存儲:

let state = null;
function useState(init) {

  state = state === null ? init : state;

  // 修改state的方法
  const setState = value => {
    state = value;

    // 只要修改了state,我們就需要重新處理節點
    workInProgressRoot = {
      dom: currentRoot.dom,
      props: currentRoot.props,
      alternate: currentRoot
    }

    // 修改nextUnitOfWork指向workInProgressRoot,這樣下次就會處理這個節點了
    nextUnitOfWork = workInProgressRoot;
    deletions = [];
  }

  return [state, setState]
}

這樣其實我們就可以使用了:

支持多個state

上面的代碼只有一個state變量,如果我們有多個useState怎麼辦呢?為了能支持多個useState,我們的state就不能是一個簡單的值了,我們可以考慮把他改成一個數組,多個useState按照調用順序放進這個數組裡面,訪問的時候通過下標來訪問:

let state = [];
let hookIndex = 0;
function useState(init) {
  const currentIndex = hookIndex;
  state[currentIndex] = state[currentIndex] === undefined ? init : state[currentIndex];

  // 修改state的方法
  const setState = value => {
    state[currentIndex] = value;

    // 只要修改了state,我們就需要重新處理這個節點
    workInProgressRoot = {
      dom: currentRoot.dom,
      props: currentRoot.props,
      alternate: currentRoot
    }

    // 修改nextUnitOfWork指向workInProgressRoot,這樣下次就會處理這個節點了
    nextUnitOfWork = workInProgressRoot;
    deletions = [];
  }

  hookIndex++;

  return [state[currentIndex], setState]
}

來看看多個useState的效果:

支持多個組件

上面的代碼雖然我們支持了多個useState,但是仍然只有一套全局變量,如果有多個函數組件,每個組件都來操作這個全局變量,那相互之間不就是污染了數據了嗎?所以我們數據還不能都存在全局變量上面,而是應該存在每個fiber節點上,處理這個節點的時候再將狀態放到全局變量用來通訊:

// 申明兩個全局變量,用來處理useState
// wipFiber是當前的函數組件fiber節點
// hookIndex是當前函數組件內部useState狀態計數
let wipFiber = null;
let hookIndex = null;

因為useState只在函數組件裏面可以用,所以我們之前的updateFunctionComponent裏面需要初始化處理useState變量:

function updateFunctionComponent(fiber) {
  // 支持useState,初始化變量
  wipFiber = fiber;
  hookIndex = 0;
  wipFiber.hooks = [];        // hooks用來存儲具體的state序列
  
  // ......下面代碼省略......
}

因為hooks隊列放到fiber節點上去了,所以我們在useState取之前的值時需要從fiber.alternate上取,完整代碼如下:

function useState(init) {
  // 取出上次的Hook
  const oldHook = wipFiber.alternate && wipFiber.alternate.hooks && wipFiber.alternate.hooks[hookIndex];

  // hook數據結構
  const hook = {
    state: oldHook ? oldHook.state : init      // state是每個具體的值
  }

  // 將所有useState調用按照順序存到fiber節點上
  wipFiber.hooks.push(hook);
  hookIndex++;

  // 修改state的方法
  const setState = value => {
    hook.state = value;

    // 只要修改了state,我們就需要重新處理這個節點
    workInProgressRoot = {
      dom: currentRoot.dom,
      props: currentRoot.props,
      alternate: currentRoot
    }

    // 修改nextUnitOfWork指向workInProgressRoot,這樣下次requestIdleCallback就會處理這個節點了
    nextUnitOfWork = workInProgressRoot;
    deletions = [];
  }

  return [hook.state, setState]
}

上面代碼可以看出我們在將useState和存儲的state進行匹配的時候是用的useState的調用順序匹配state的下標,如果這個下標匹配不上了,state就錯了,所以React裏面不能出現這樣的代碼:

if (something) {
    const [state, setState] = useState(1);
}

上述代碼不能保證每次something都滿足,可能導致useState這次render執行了,下次又沒執行,這樣新老節點的下標就匹配不上了,對於這種代碼,React會直接報錯:

用Hooks模擬Class組件

這個功能純粹是娛樂性功能,通過前面實現的Hooks來模擬實現Class組件,這個並不是React官方的實現方式哈~我們可以寫一個方法將Class組件轉化為前面的函數組件:

function transfer(Component) {
  return function(props) {
    const component = new Component(props);
    let [state, setState] = useState(component.state);
    component.props = props;
    component.state = state;
    component.setState = setState;

    return component.render();
  }
}

然後就可以寫Class了,這個Class長得很像我們在React裏面寫的Class,有state,setStaterender

import React from './myReact';

class Count4 {
  constructor(props) {
    this.props = props;
    this.state = {
      count: 1
    }
  }

  onClickHandler = () => {
    this.setState({
      count: this.state.count + 1
    })
  }

  render() {
    return (
      <div>
        <h3>Class component Count: {this.state.count}</h3>
        <button onClick={this.onClickHandler}>Count+1</button>
      </div>
    ); 
  }
}

// export的時候用transfer包裝下
export default React.transfer(Count4);

然後使用的時候直接:

<div>
  <Count4></Count4>
</div>

當然你也可以在React裏面建一個空的class Component,讓Count4繼承他,這樣就更像了。

好了,到這裏我們代碼就寫完了,完整代碼可以看我GitHub。

總結

  1. 我們寫的JSX代碼被babel轉化成了React.createElement
  2. React.createElement返回的其實就是虛擬DOM結構。
  3. ReactDOM.render方法是將虛擬DOM渲染到頁面的。
  4. 虛擬DOM的調和和渲染可以簡單粗暴的遞歸,但是這個過程是同步的,如果需要處理的節點過多,可能會阻塞用戶輸入和動畫播放,造成卡頓。
  5. Fiber是16.x引入的新特性,用處是將同步的調和變成異步的。
  6. Fiber改造了虛擬DOM的結構,具有父 -> 第一個子子 -> 兄子 -> 父這幾個指針,有了這幾個指針,可以從任意一個Fiber節點找到其他節點。
  7. Fiber將整棵樹的同步任務拆分成了每個節點可以單獨執行的異步執行結構。
  8. Fiber可以從任意一個節點開始遍歷,遍歷是深度優先遍歷,順序是父 -> 子 -> 兄 -> 父,也就是從上往下,從左往右。
  9. Fiber的調和階段可以是異步的小任務,但是提交階段(commit)必須是同步的。因為異步的commit可能讓用戶看到節點一個一個接連出現,體驗不好。
  10. 函數組件其實就是這個節點的type是個函數,直接將type拿來運行就可以得到虛擬DOM。
  11. useState是在Fiber節點上添加了一個數組,數組裡面的每個值對應了一個useStateuseState調用順序必須和這個數組下標匹配,不然會報錯。

參考資料

A Cartoon Intro to Fiber

妙味課堂大聖老師:手寫react的fiber和hooks架構

React Fiber

這可能是最通俗的 React Fiber(時間分片) 打開方式

淺析 React Fiber

React Fiber架構

文章的最後,感謝你花費寶貴的時間閱讀本文,如果本文給了你一點點幫助或者啟發,請不要吝嗇你的贊和GitHub小星星,你的支持是作者持續創作的動力。

作者博文GitHub項目地址: https://github.com/dennis-jiang/Front-End-Knowledges

作者掘金文章匯總:https://juejin.im/post/5e3ffc85518825494e2772fd

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

【其他文章推薦】

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

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

※回頭車貨運收費標準

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

※超省錢租車方案