Shadowsocks Server

Shadowsocks Server 的实现

shadowsocks: The original Python implementation.

shadowsocks-libev: Lightweight C implementation for embedded devices and low end boxes. Very small footprint (several megabytes) for thousands of connections.

go-shadowsocks2: Another Go implementation focusing on core features and code reusability.

shadowsocks-rust: A rust port of shadowsocks.

shadowsocks-libev

shadowsocks-libev，是一个基于 libev 库开发的 shadowsocks 代理套件。包含ss-local,ss-redir,ss-tunnel,ss-server四部分。
ss-server是shadowsocks 的服务端程序。
ss-local是shadowsocks 客户端程序。
ss-redir是透明代理工具。
ss-tunnel是本地端口转发工具，通常用于解决 dns 污染问题。

go-shadowsocks2

https://github.com/shadowsocks/go-shadowsocks2
shadowsocks-rust
- https://github.com/shadowsocks/shadowsocks-rust

...

Posted by Wei on 2019-06-19, Last Modified on 2025-08-11

【Data Structure】图（Graph）- 图的物理存储

图的顺序存储方法 - 邻接矩阵（Adjacency Matrix）

使用数组存储图时，需要使用两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。

如果只是存储图中包含的顶点，使用一维数组就足够了；
然而，我们还需要存储顶点之间的关系，因此要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。

这个二维数组称为邻接矩阵（Adjacency Matrix）。

不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网。

图，包括无向图和有向图；网，是指带权的图，包括无向网和有向网。

存储方式的不同，指的是：在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。

无向图

我们来看一个无向图的实例，下图的左图就是一个无向图：

对于无向图来说，二维数组构成的邻接矩阵，实际上是对称矩阵。因此，在存储时就可以采用压缩存储的方式存储下三角或者上三角。

通过二阶矩阵，可以直观地计算出各个顶点的度，为该行（或该列）非 0 值的和。例如，第一行有两个 1，说明 V1 有两个边，所以度为 2。

有向图

我们再来看一个有向图的样例，如下图所示的左图：

例如，arcs[0][1] = 1 ，证明从 V1 到 V2 有弧存在。且通过邻接矩阵，可以很轻松得知各顶点的出度和入度，出度为该行非 0 值的和，入度为该列非 0 值的和。例如，V1 的出度为 2 （因为第二行中有两个 1 ），为 2 ； V1 的入度为 1 （第二列中只有一个 1 ）。

...

Posted by Wei on 2019-06-14, Last Modified on 2023-03-23

【Data Structure】图（Graph） - 图的深度优先搜索（Depth First Search）

...

Posted by Wei on 2019-06-14, Last Modified on 2023-03-23

Trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树（k-ary search tree）结构。如下图：

...

Posted by Wei on 2019-06-13, Last Modified on 2025-08-11

索引（Index）

A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without having to search every row in a database table every time a database table is accessed. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records.

...

Posted by Wei on 2019-06-10, Last Modified on 2025-08-11

【Database】索引 - B 树和 B+ 树

背景

Binary tree：二叉树（Binary tree），每个节点只能存储一个key
B-tree：B树（B-Tree，并不是B“减”树，横杠为连接符，容易被误导）
- B树属于多叉树，同时也属于平衡多路查找树。每个节点可以包含多个key（包含多少个由磁盘的页的大小决定）。
- B+tree（B+树） 和 B*tree（B*树） 都是 B-tree 的变种

...

Posted by Wei on 2019-06-10, Last Modified on 2025-08-11

【Data Structure】平衡多路查找树（Balanced Multi-way Search Tree） - B+ 树（B+ Tree）

B+ 树（B+ Tree）

B+树（B+ Tree）是B树的一种变体，B+树也属于平衡多路查找树（Multi-way Search Tree）。

大体结构与B树相同，包含根节点、内部节点和叶子节点。与B树唯一的区别在于，B+树的内部节点不保存数据元素的value，只保存key（而B树的内部节点既保存数据元素的key，也保存数据元素的value），因此B+树能在内存中存放更多索引，增加缓存命中率。另外因为叶子节点相连遍历操作很方便，而且数据也具有顺序性，便于区间查找。

...

Posted by Wei on 2019-06-05, Last Modified on 2025-08-11

【Data Structure】平衡多路查找树（Balanced Multi-way Search Tree） - B树（B-Tree）

B树（B-tree）

在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以$O(log_2n)$的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的平衡查找树，因为其一个节点可以拥有多于2个子节点，因而也可以称为多路自平衡查找树（Multi-way Self-balancing Search Tree），简称为多路查找树。

...

Posted by Wei on 2019-06-04, Last Modified on 2025-08-11

【Data Structure】平衡多路查找树（Balanced Multi-way Search Tree）- 2-3 查找树和 2-4 查找树

背景

**二叉查找树（Binary Search Tree）**在很多情况下可以良好的工作，但它的限制是最坏情况下的时间复杂度为 O(n)。

**平衡二叉查找树（Self-balancing Binary Search Tree）**的设计则是保证其高度在最坏的情况下时间复杂度为 $O(log_2n)$，其插入、删除和查找操作的时间复杂度均为 $O(log_2n)$。常见的平衡二叉查找树包括 AVL树、红黑树。

**多路平衡查找树（Multi-way Self-balancing Search Tree）**作为一般化的平衡二叉查找树（Self-balancing Binary Search Tree），现在其实存在很多种类的平衡查找树，常见的有2-3查找树、2-4查找树、B 树、B+树等。

...

Posted by Wei on 2019-06-04, Last Modified on 2025-08-11

【Algorithm】查找算法（Search）

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想

顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以，顺序查找的时间复杂度为O(n)。

...

Posted by Wei on 2019-06-03, Last Modified on 2025-08-11

西维蜀黍

【Network】Shadowsocks 总结

Shadowsocks Server