ARTS-WEEK4

2019-04-07
#ARTS #Leetcode #HTTP2 #Redis

本周ARTS

本周ARTS打卡内容：

  1. Algorithm 来源 LeetCode19，LeetCode20
  2. Review 分享 HTTP/2的优势以及怎么升级到HTTP/2
  3. Tip 分享 CAP原则(CAP定理)、BASE理论
  4. Share 分享 redis的总结精讲

Algorithm

LeetCode的19题，去除链表中倒数第N个节点：https://leetcode.com/problems/remove-nth-node-from-end-of-list/

样例：

1
2
3
给定链表: 1->2->3->4->5, and n = 2.

去除掉倒数第二个节点后，链表为 1->2->3->5.

  1. 遍历链表两次

首先想到的是解法是轮询链表两次，第一次得到链表的长度l，在从节点开始，数到l-n个节点，将该节点的下一个节点指向下下个节点，解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var node = head
	var k = 1
	for node.Next != nil {
		k++
		node = node.Next
	}
	if k == 1 {
		return nil
	}
	target := k -n
	node = head
	if target == 0 {
		return head.Next
	}
	for ;target != 1;target-- {
		node = node.Next
	}
	node.Next = node.Next.Next
	return head
}

需要注意删除的值是第一个元素的情况，和链表只有一个元素的情况

算法的时间复杂度O(n)

  1. 遍历链表一次

看了答案之后发现还有一种解法，就试了下，具体思路是，申明两个链表节点对象，第一个链表先走n步，然后两个链表再开始同时前进，到第一个链表指向最后一个值时，第二个链表的下一个值就是要删除的值，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var result, first = head, head
	for n>0 {
		first = first.Next
		n--
	}
	if first == nil {
		if n == 1{
			return nil
		}
		return result.Next
	}
	second := head
	for first.Next != nil {
		first = first.Next
		second = second.Next
	}
	second.Next = second.Next.Next
	return result
}

LeetCode20题，合法括号的问题，给定一个只包含括号’(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ , ‘]’的字符串，判断其是否合法，规定左括号必须有右括号和其对应，且括号的顺序必须正确，比如“{}”,“{()}”这是合法的，“（]”类似这样是不合法的， https://leetcode.com/problems/valid-parentheses/

栈的老题，使用栈来解决，遍历这个字符串，对于每个字符，若其为左括号则入栈，其为右括号则与栈定的元素比较，匹配则栈顶元素出栈，否则如栈，遍历完后，检查栈是否为空，为空则字符串合法，否则不合法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func isValid(s string) bool {
	var queue []rune
	if s == "" {
		return true
	}
	for _, v := range s {
		if v == '(' || v == '[' || v == '{' {
			queue = append(queue, v)
		} else {
			len := len(queue)
			if len == 0 {
				queue = append(queue, v)
				continue
			}
			k := queue[len-1]
			if (v == ')' && k == '(') || (v == ']' && k == '[') || (v == '}' && k == '{') {
				queue = queue[:len-1]
				continue
			}
			queue = append(queue, v)
		}
	}
	return len(queue) == 0
}

Review

本周的内容是：Migrating your REST APIs to HTTP/2: Why and How?

https://blog.usejournal.com/migrating-your-rest-apis-to-http-2-why-and-how-8caee7d798fb

文章主要介绍了HTTP/2的优势以及怎么升级到HTTP/2。

作为开发者，我们的主要目标是，将我们的产品更好、更快的传递给消费者，为此我们升级语言版本、web框架、消息队列、文本处理、操作系统等等，但是当前的HTTP协议已经几十年没有升级过了。HTTP/1.1是伟大的，但是我们的应用已经变的更大规模，更加复杂，所以是时候升级到HTTP/2了。

为了提高传输效率，HTTP/2对HTTP/1协议的底层数据传输方式有了根本性的改变。HTTP/2引入了一种新的二进制框架层来替代了HTTP/1.x复杂的客户端和服务端。

HTTP1vs2

HTTP/1.x是传统的使用换行文本的方式来传输数据(如上图)，因此传输的内容大，传输缓慢，容易出错。而HTTP/2使用二进制形式的DATA frame来传输数据。具体来说，对于web应用，我们可以保持暴露的HTTP APIs不变，改变其从API到传输的sockets的编码方式，web服务将根据它支持的HTTP版本选择不同的编码方式。对外暴露的API仍然维持传统的GET、PUT、POST、DELETE。

那么HTTP/2有哪些好处呢？

  1. 二进制数据处理。二进制的传输更快，传输的数据流更紧凑。相比于HTTP/1.x的四种解析方式，HTTP/2只有1种，同时，二进制能更好的处理空格、空行和特殊字符。
  2. 多路复用。在HTTP/1.x种，一次只能传递一个请求和响应。这就造成了响应的排队、堵塞，降低了TCP连接。而客户端也需要猜测响应报文正确的顺序。HTTP/2破除了这种方式，HTTP/2中的二进制流可以实现请求和响应的多路复用，因此，客户端只需要一个连接就能并行的传输多路请求和响应。这样通过减少不必要的等待时间和提升网络的可利用率来减少了页面的加载次数。
    HTTP2
  3. 头部压缩。HTTP/2使用HPACK压缩计算来压缩请求报文和响应报文种的头部。HPACK压缩使用霍夫曼编码方式，在客户端和服务器同时维护一套之前的headers列表，用来快速的编码和反编码。在今天的平均请求中，带cookies的头部，压缩和非压缩的相差kb，头部压缩极大的提升了效率。
    HPACK
  4. 服务推送。在HTTP/1.x种，服务端只有在客户端请求时才能沟通到客户端，而且沟通的方式只能是响应客户端的特定请求。而在HTTP/2种，服务端可以返回多个响应给客户端的一个请求。因此，服务端可以推送更多有用的信息给客户端。例如，在加载页面时服务端可以把javascript文件和格式表单发送给客户端，而不用等到客户端请求时在发送。还可以用来更新客户端的缓存，以加快渲染速度。

据有关机构统计，当前网络站点中有32.4%已经使用HTTP/2，预测这个比例会越来越高。文章作者使用Spring Boot + Tomcat:8.5.x为例来举例如何使用HTTP/2。只需要加入HTTP2升级协议到Tomcat的connector中：

1
2
3
4
5
6
7
8
9
10
11
@Bean
public EmbeddedServletContainerCustomizer tomcatCustomizer() {
    return (container) -> {
        if (container instanceof TomcatEmbeddedServletContainerFactory) {
            ((TomcatEmbeddedServletContainerFactory) container)
                    .addConnectorCustomizers((connector) -> {
                connector.addUpgradeProtocol(new Http2Protocol());
            });
        }
    };
}

就这么简单。

看完这篇文章，不自觉想到了HTTP/2的一个实现grpc，后端实现rpc很容易，但前端怎么与后端交互呢？然后看到了一篇文章gRPC-Web is going GA，CNCF的gRPC-Web，是一个Javascript客户端，使Web能直接与后端gRPC服务器通信，不需要HTTP服务器充当中介。如此，前端后端后可以实现gRPC，使用gRPC进行通信了。这是有别于REST的一种服务架构，在这种架构里前端变成了gRPC的一个层。实现了端到端的gRPC，前端不用关系HTTP状态、JSON解析等问题。

Tip

分享之前对CAP、BASE的总结

https://leitty.github.io/2019/04/07/CAP-and-BASE/

Share

分布式之redis复习精讲

https://www.cnblogs.com/rjzheng/p/9096228.html

redis的内容有好几讲，作者讲的非常清晰易懂。