ARTS-week18

发表于 分类于 本文字数： 3.8k 阅读时长 ≈ 3 分钟

Algorithms

Balanced Binary Tree
思路: 题目定义高度平衡二叉树是每一个结点的两个子树的深度差不能超过1。不断递归获得节点的左右子树深度，再进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:    
    bool isBalanced(TreeNode *root) {
        if (DepthNum(root) == -1) {
            return false;
        }
        else {
            return true;
        }
    }
    
    int DepthNum(TreeNode *root) {
        if (!root) {
            return 0;
        }
        int left = DepthNum(root->left);
        if (left == -1) {
            return -1;
        }
        int right = DepthNum(root->right);
        if (right == -1) {
            return -1;
        }
        if (abs(left - right) > 1) {
            return -1;
        }
        else {
            return max(left, right) + 1;
        }
    }
};

Minimum Depth of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (!root) {
            return 0;
        }
        if (root->left == NULL && root->right == NULL) {
            return 1;
        }
        int left = INT_MAX;
        int right = INT_MAX;
        if (root->left) {
            left = minDepth(root->left) + 1;
        }
        if (root->right) {
            right = minDepth(root->right) + 1;
        }
        return left < right ? left : right;
    }
};

Review

本周阅读英文文章 The Internet changes: HTTP/3 will not use TCP anymore、How to optimize C and C++ code in 2018

1).QUIC: Quick UDP Internet Connections，基于多路复用UDP连接的网络传输协议。
2).

QUIC uses a combination of TCP + TLS + SPDY over UDP with several enhancements with respect to the current HTTP/2 over TCP implementation.

关于SPDY，是Google开发的一种开放的网络传输协议，基于TCP，也是HTTP/2的前身，可查看如下链接进行详细的了解:
https://www.chromium.org/spdy/spdy-whitepaper
https://www.chromium.org/quic

3).用于TCP+TLS的1-3次往返相比，QUIC握手在发送有效载荷之前经常需要零往返。

The first time a QUIC client connects to a server, the client must perform a 1-roundtrip handshake in order to acquire the necessary information to complete the handshake. The client sends an inchoate (empty) client hello (CHLO), the server sends a rejection (REJ) with the information the client needs to make forward progress, including the source address token and the server’s certificates. The next time the client sends a CHLO, it can use the cached credentials from the previous connection to immediately send encrypted requests to the server.

4).每个重新传输的数据包都会消耗一个新的序列号，从而消除了歧义并防止了造成RTO的损失。

Technique

在本周阅读倪朋飞老师的文章中讲到的一些知识点:
1.为了维护CPU时间，Linux通过事先定义的节拍率(内核中表示为HZ)，触发时间中断，并使用全局变量Jiffies记录了开机以来的节拍数。每发生一次时间中断，Jiffies的值就加1。

节拍率是内核的可配选项，可设置100、250、1000等，也就是每秒钟触发250次时间中断，不同的系列可能设置不同数值，通过查询/boot/config内核选项查看配置值，节拍率HZ是内核选项，用户空间程序并不能直接访问，为了方便用户空间程序，内核还提供了一个用户空间节拍率USER_HZ，固定为100。 

1
2
$ grep 'CONFIG_HZ=' /boot/config-$(uname -r)
CONFIG_HZ=250

适合第一时间分析进程的CPU问题工具：perf。它以性能事件采样为基础，不仅可以分析系统的各种事件和内核性能，还可以用来分析指定应用程序的性能问题。

常见用法是perf top，类似于top，它能够实时显示占用CPU时钟最多的函数或者指令，因此可以用来查找热点函数，使用界面如下所示： 

1
2
3
4
5
6
7
8
Samples: 670  of event 'cpu-clock', Event count (approx.): 132999959                                                                                                               
Overhead  Shared Object       Symbol                                                                                                                                                
   7.48%  [kernel]            [k] memcpy
   6.48%  [kernel]            [k] vsnprintf
   5.18%  [kernel]            [k] kallsyms_expand_symbol.constprop.1
   5.04%  [kernel]            [k] format_decode
   4.14%  [kernel]            [k] 0x00007fff81859195
   3.74%  [kernel]            [k] module_get_kallsym

第一行包含三个数据，分别是采样数(Samples)、事件类型(event)和事件总数量(Event count)。如上，perf采集了670个CPU时钟事件，总事件数为132999959。

Overhead：是该符号的性能事件在所有采样中的比例，用百分比来表示。
Shared：是该函数或指令所在的动态共享对象，如内核、进程名、动态链接库名、内核模块等。
Object：是动态共享对象的类型。比如[.]表示用户空间的可执行程序、或者动态链接库、而[k]则表示内核空间。
Symbol：符号名，也就是函数名，当函数名未知时，用十六进制的地址来表示。

还有perf record和perf report可以使用。加上-g参数，可开启调用关系的采样。

Share

《HTTPS权威指南：在服务器和Web应用上部署SSL/TLS和PKI》8.7 钉扎

互联网的信任机制完全依赖于数百家CA厂商颁发的证书，证书用来验证服务器的合法性。对于一般的网站来讲，这种方法很适用，因为这些网站不太可能被伪造证书；高知名度网站的风险则高得多，原因在于任意一个CA都可以签发任意一个域名的证书。为了避免这个问题，可以使用一种被称为公钥钉扎（public key pinning）的技术，它允许你强制指定签发证书的CA，只有被指定的CA为你的域名签发的证书才能正常使用。
钉扎技术大大降低了证书伪造的攻击可能性，但是也需要付出一些代价：需要一定的投入才能建立起一个成熟的钉扎战略和运营机制，并且钉扎完全依赖于浏览器的内部验证机制。关于钉扎技术有几个不同的标准，目前正处于不同的发展阶段：DANE（基于DNSSEC）、HTTP公钥钉扎和TACK。