架構師訓練營 week8 總結

8.1 文件与硬盘 I/O：如何把硬盘的读写速度提高十万倍？







8.2 常见数据结构与Hash表原理分析

Hash 衝突解法

開放定址法，鏈地址法，再雜湊、建立公共溢位區

bloom filter 算法：https://www.cnblogs.com/sunsky303/p/11834102.html

8.3 红黑树原理与性能特性

紅黑樹在大量增刪的情況下效率更高。

紅黑樹的平衡性不如 balanced binary tree，查找效率較差



skiplist

1. skiplist的複雜度和紅黑樹一樣，而且實現起來更簡單。

2. 在並發環境下skiplist有另外一個優勢，紅黑樹在插入和刪除的時候可能需要做一些rebalance的操作，這樣的操作可能會涉及到整個樹的其他部分，而skiplist的操作更加局部性一些(需要更新的部分較少)，鎖需要盯住的節點更少，因此在這樣的情況下性能好一些。

There are a few reasons:

1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.



About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.



ref: https://blog.csdn.net/qq9808/article/details/104865385



8.4 经典算法

Brute-force

Recursive

Greedy

Dynamic programming

8.5 网络通信基本原理与性能优化







物理層：物理媒介上傳輸二進位格式數據

鏈路層：可以進行數據校驗，流量控制，記錄發送者和接收者的 MAC 地址



TCP建立連結3次握手

TCP關閉連結4次握手



HTTP 1.1 : reuse TCP connection, but 1 request per connection

HTTP 2: multiple requests per connection

HTTP 3: use QUIC (UDP package) as transport layer





8.6 非阻塞网络I/O