注：本文转载自常用数据结构及复杂度 - sangmado - 博客园，原文基础上略有删减。

常用数据结构的时间复杂度

如何选择数据结构

• Array (T[])

  当元素的数量是固定的，并且需要使用下标时。

• Linked list (LinkedList

  当元素需要能够在列表的两端添加时。否则使用 List。

• Resizable array list (List)

  当元素的数量不是固定的，并且需要使用下标时。

• Stack (Stack)

  当需要实现 LIFO（Last In First Out）时。

• Queue (Queue)

  当需要实现 FIFO（First In First Out）时。

• Hash table (Dictionary<K,T>)

  当需要使用键值对（Key-Value）来快速添加和查找，并且元素没有特定的顺序时。

• Tree-based dictionary (SortedDictionary<K,T>)

  当需要使用价值对（Key-Value）来快速添加和查找，并且元素根据 Key 来排序时。

• Hash table based set (HashSet)

  当需要保存一组唯一的值，并且元素没有特定顺序时。

• Tree based set (SortedSet)

  当需要保存一组唯一的值，并且元素需要排序时。

Array

在计算机程序设计中，数组（Array）是最简单的而且应用最广泛的数据结构之一。在任何编程语言中，数组都有一些共性：

• 数组中的内容是使用连续的内存（Contiguous Memory）来存储的。
• 数组中的所有元素必须是相同的类型，或者类型的衍生类型。因此数组又被认为是同质数据结构（Homegeneous Data Structures）。
• 数组的元素可以直接被访问。比如你需要访问数组的第 i 个元素，则可以直接使用 arrayName[i] 来访问。

对于数组的常规操作包括：

• 分配空间（Allocation）
• 数据访问（Accessing）

在 C# 中，可以通过如下的方式声明数组变量。

1
2
3

1 int allocationSize = 10;
2 bool[] booleanArray = new bool[allocationSize];
3 FileInfo[] fileInfoArray = new FileInfo[allocationSize];

上面的代码将在 CLR 托管堆中分配一块连续的内存空间，用以容纳数量为 allocationSize ，类型为 arrayType 的数组元素。如果 arrayType 为值类型，则将会有 allocationSize 个未封箱（unboxed）的 arrayType 值被创建。如果 arrayType 为引用类型，则将会有 allocationSize 个 arrayType 类型的引用被创建。

如果我们为 FileInfo[] 数组中的一些位置赋上值，则引用关系为下图所示。

.NET 中的数组都支持对元素的直接读写操作。语法如下：

1
2
3
4
5

1 // 读数组元素
2 bool b = booleanArray[7];
3 
4 // 写数组元素
5 booleanArray[0] = false;

访问一个数组元素的时间复杂度为 O(1)，因此对数组的访问时间是恒定的。也就是说，与数组中包含的元素数量没有直接关系，访问一个元素的时间是相同的。

ArrayList

由于数组是固定长度的，并且数组中只能存储同一种类型或类型的衍生类型。这在使用中会受到一些限制。.NET 提供了一种数据结构 ArrayList 来解决这些问题。

1
2
3
4
5
6

1   ArrayList countDown = new ArrayList();
2   countDown.Add(3);
3   countDown.Add(2);
4   countDown.Add(1);
5   countDown.Add("blast off!");
6   countDown.Add(new ArrayList());

ArrayList 是长度可变的数组，并且它可以存储不同类型的元素。

但这些灵活性是以牺牲性能为代价的。在上面 Array 的描述中，我们知道 Array 在存储值类型时是采用未装箱（unboxed）的方式。由于 ArrayList 的 Add 方法接受 object 类型的参数，导致如果添加值类型的值会发生装箱（boxing）操作。这在频繁读写 ArrayList 时会产生额外的开销，导致性能下降。

List

当 .NET 中引入泛型功能后，上面 ArrayList 所带来的性能代价可以使用泛型来消除。.NET 提供了新的数组类型 List。

泛型允许开发人员在创建数据结构时推迟数据类型的选择，直到使用时才确定选择哪种类型。泛型（Generics）的主要优点包括：

• 类型安全（Type Safety）：使用泛型定义的类型，在使用时仅能使用指定的类型或类型的衍生类型。
• 性能（Performance）：泛型移除了运行时类型检测，消除了装箱和拆箱的开销。
• 可重用（Reusability）：泛型打破了数据结构与存储数据类型之间的紧耦合。这提高了数据结构的可重用性。

List 等同于同质的一维数组（Homogeneous self-redimensioning array）。它像 Array 一样可以快速的读取元素，还可以保持长度可变的灵活性。

1
2
3
4
5

1       // 创建 int 类型列表
2       List<int> myFavoriteIntegers = new List<int>();
3 
4       // 创建 string 类型列表
5       List<string> friendsNames = new List<string>();

List 内部同样使用 Array 来实现，但它隐藏了这些实现的复杂性。当创建 List 时无需指定初始长度，当添加元素到 List 中时，也无需关心数组大小的调整（resize）问题。

1
2
3
4
5
6
7
8

1   List<int> powersOf2 = new List<int>();
2 
3   powersOf2.Add(1);
4   powersOf2.Add(2);
5 
6   powersOf2[1] = 10;
7 
8   int sum = powersOf2[1] + powersOf2[2];

List 的渐进运行时（Asymptotic Running Time）复杂度与 Array 是相同的。

LinkedList

在链表（Linked List）中，每一个元素都指向下一个元素，以此来形成了一个链（chain）。

在创建一个链表时，我们仅需持有头节点 head 的引用，这样通过逐个遍历下一个节点 next 即可找到所有的节点。

链表与数组有着同样的线性运行时间 O(n)。例如在上图中，如果我们要查找 Sam 节点，则必须从头节点 Scott 开始查找，逐个遍历下一个节点直到找到 Sam。

同样，从链表中删除一个节点的渐进时间也是线性的O(n)。因为在删除之前我们仍然需要从 head 开始遍历以找到需要被删除的节点。而删除操作本身则变得简单，即让被删除节点的左节点的 next 指针指向其右节点。下图展示了如何删除一个节点。

向链表中插入一个新的节点的渐进时间取决于链表是否是有序的。如果链表不需要保持顺序，则插入操作就是常量时间O(1)，可以在链表的头部或尾部添加新的节点。而如果需要保持链表的顺序结构，则需要查找到新节点被插入的位置，这使得需要从链表的头部 head 开始逐个遍历，结果就是操作变成了O(n)。下图展示了插入节点的示例。

链表与数组的不同之处在于，数组的中的内容在内存中时连续排列的，可以通过下标来访问，而链表中内容的顺序则是由各对象的指针所决定，这就决定了其内容的排列不一定是连续的，所以不能通过下标来访问。如果需要更快速的查找操作，使用数组可能是更好的选择。

使用链表的最主要的优势就是，向链表中插入或删除节点无需调整结构的容量。而相反，对于数组来说容量始终是固定的，如果需要存放更多的数据，则需要调整数组的容量，这就会发生新建数组、数据拷贝等一系列复杂且影响效率的操作。即使是 List 类，虽然其隐藏了容量调整的复杂性，但仍然难逃性能损耗的惩罚。

链表的另一个优点就是特别适合以排序的顺序动态的添加新元素。如果要在数组的中间的某个位置添加新元素，不仅要移动所有其余的元素，甚至还有可能需要重新调整容量。

所以总结来说，数组适合数据的数量是有上限的情况，而链表适合元素数量不固定的情况。

在 .NET 中已经内置了LinkedList 类，该类实现了双向链表（doubly-linked list）功能，也就是节点同时持有其左右节点的引用。而对于删除操作，如果使用 Remove(T)，则运算复杂度为 O(n)，其中 n 为链表的长度。而如果使用 Remove(LinkedListNode)， 则运算复杂度为 O(1)。

Queue

当我们需要使用先进先出顺序（FIFO）的数据结构时，.NET 为我们提供了 Queue。Queue 类提供了 Enqueue 和 Dequeue 方法来实现对 Queue 的存取。

Queue 内部建立了一个存放 T 对象的环形数组，并通过 head 和 tail 变量来指向该数组的头和尾。

默认情况下，Queue 的初始化容量是 32，也可以通过构造函数指定容量。

Enqueue 方法会判断 Queue 中是否有足够容量存放新元素。如果有，则直接添加元素，并使索引 tail 递增。在这里的 tail 使用求模操作以保证 tail 不会超过数组长度。如果容量不够，则 Queue 根据特定的增长因子扩充数组容量。

默认情况下，增长因子（growth factor）的值为 2.0，所以内部数组的长度会增加一倍。也可以通过构造函数中指定增长因子。Queue 的容量也可以通过 TrimExcess 方法来减少。

Dequeue 方法根据 head 索引返回当前元素，之后将 head 索引指向 null，再递增 head 的值。

Stack

当需要使用后进先出顺序（LIFO）的数据结构时，.NET 为我们提供了 Stack。Stack 类提供了 Push 和 Pop 方法来实现对 Stack 的存取。

Stack 中存储的元素可以通过一个垂直的集合来形象的表示。当新的元素压入栈中（Push）时，新元素被放到所有其他元素的顶端。当需要弹出栈（Pop）时，元素则被从顶端移除。

Stack 的默认容量是 10。和 Queue 类似，Stack 的初始容量也可以在构造函数中指定。Stack 的容量可以根据实际的使用自动的扩展，并且可以通过 TrimExcess 方法来减少容量。

如果 Stack 中元素的数量 Count 小于其容量，则 Push 操作的复杂度为 O(1)。如果容量需要被扩展，则 Push 操作的复杂度变为 O(n)。Pop 操作的复杂度始终为 O(1)。

Hashtable

现在假设我们要使用员工的社保号作为唯一标识进行存储。社保号的格式为 DDD-DD-DDDD（D 的范围为数字 0-9）。

如果使用 Array 存储员工信息，要查询社保号为 111-22-3333 的员工，则将会尝试遍历数组的所有位置，即执行渐进时间为 O(n) 的查询操作。好一些的办法是将社保号排序，以使查询渐进时间降低到 O(log(n))。但理想情况下，我们更希望查询渐进时间为 O(1)。

一种方案是建立一个大数组，范围从 000-00-0000 到 999-99-9999 。

这种方案的缺点是浪费空间。如果我们仅需要存储 1000 个员工的信息，那么仅利用了 0.0001% 的空间。

第二种方案就是用哈希函数（Hash Function）压缩序列。

我们选择使用社保号的后四位作为索引，以减少区间的跨度。这样范围将从 0000 到 9999。

在数学上，将这种从 9 位数转换为 4 位数的方式称为哈希转换（Hashing）。可以将一个数组的索引空间（indexers space）压缩至相应的哈希表（Hash Table）。

在上面的例子中，哈希函数的输入为 9 位数的社保号，输出结果为后 4 位。

1

H(x) = last four digits of x

上图中也说明在哈希函数计算中常见的一种行为：哈希冲突（Hash Collisions）。即有可能两个社保号的后 4 位均为 0000。

当要添加新元素到 Hashtable 中时，哈希冲突是导致操作被破坏的一个因素。如果没有冲突发生，则元素被成功插入。如果发生了冲突，则需要判断冲突的原因。因此，哈希冲突提高了操作的代价，Hashtable 的设计目标就是要尽可能减低冲突的发生。

处理哈希冲突的方式有两种：避免和解决，即冲突避免机制（Collision Avoidance）和冲突解决机制（Collision Resolution）。

避免哈希冲突的一个方法就是选择合适的哈希函数。哈希函数中的冲突发生的几率与数据的分布有关。例如，如果社保号的后 4 位是随即分布的，则使用后 4 位数字比较合适。但如果后 4 位是以员工的出生年份来分配的，则显然出生年份不是均匀分布的，则选择后 4 位会造成大量的冲突。我们将这种选择合适的哈希函数的方法称为冲突避免机制（Collision Avoidance）。

在处理冲突时，有很多策略可以实施，这些策略称为冲突解决机制（Collision Resolution）。其中一种方法就是将要插入的元素放到另外一个块空间中，因为相同的哈希位置已经被占用。

通常采用的冲突解决策略为开放寻址法（Open Addressing），所有的元素仍然都存放在哈希表内的数组中。

开放寻址法的最简单的一种实现就是线性探查（Linear Probing），步骤如下：

1. 当插入新的元素时，使用哈希函数在哈希表中定位元素位置；
2. 检查哈希表中该位置是否已经存在元素。如果该位置内容为空，则插入并返回，否则转向步骤 3。
3. 如果该位置为 i，则检查 i+1 是否为空，如果已被占用，则检查 i+2，依此类推，直到找到一个内容为空的位置。

现在如果我们要将五个员工的信息插入到哈希表中：

• Alice (333-33-1234)
• Bob (444-44-1234)
• Cal (555-55-1237)
• Danny (000-00-1235)
• Edward (111-00-1235)

则插入后的哈希表可能如下：

元素的插入过程：

• Alice 的社保号被哈希为 1234，因此存放在位置 1234。
• Bob 的社保号被哈希为 1234，但由于位置 1234 处已经存放 Alice 的信息，则检查下一个位置 1235，1235 为空，则 Bob 的信息就被放到 1235。
• Cal 的社保号被哈希为 1237，1237 位置为空，所以 Cal 就放到 1237 处。
• Danny 的社保号被哈希为 1235，1235 已被占用，则检查 1236 位置是否为空，1236 为空，所以 Danny 就被放到 1236。
• Edward 的社保号被哈希为 1235，1235 已被占用，检查1236，也被占用，再检查1237，直到检查到 1238时，该位置为空，于是 Edward 被放到了1238 位置。

线性探查（Linear Probing）方式虽然简单，但并不是解决冲突的最好的策略，因为它会导致同类哈希的聚集（Primary Clustering）。这导致搜索哈希表时，冲突依然存在。例如上面例子中的哈希表，如果我们要访问 Edward 的信息，因为 Edward 的社保号 111-00-1235 哈希为 1235，然而我们在 1235 位置找到的是 Bob，所以再搜索 1236，找到的却是 Danny，以此类推直到找到 Edward。

一种改进的方式为二次探查（Quadratic Probing），即每次检查位置空间的步长为平方倍数。也就是说，如果位置 s 被占用，则首先检查 s + 12 处，然后检查s - 12，s + 22，s - 22，s + 32 依此类推，而不是象线性探查那样以 s + 1，s + 2 … 方式增长。尽管如此，二次探查同样也会导致同类哈希聚集问题（Secondary Clustering）。

.NET 中的 Hashtable 类的实现，要求添加元素时不仅要提供元素（Item），还要为该元素提供一个键（Key）。例如，Key 为员工社保号，Item 为员工信息对象。可以通过 Key 作为索引来查找 Item。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 1       Hashtable employees = new Hashtable();
 2 
 3       // Add some values to the Hashtable, indexed by a string key
 4       employees.Add("111-22-3333", "Scott");
 5       employees.Add("222-33-4444", "Sam");
 6       employees.Add("333-44-55555", "Jisun");
 7 
 8       // Access a particular key
 9       if (employees.ContainsKey("111-22-3333"))
10       {
11         string empName = (string)employees["111-22-3333"];
12         Console.WriteLine("Employee 111-22-3333's name is: " + empName);
13       }
14       else
15         Console.WriteLine("Employee 111-22-3333 is not in the hash table...");

Hashtable 类中的哈希函数比前面介绍的社保号的实现要更为复杂。哈希函数必须返回一个序数（Ordinal Value）。对于社保号的例子，通过截取后四位就可以实现。但实际上 Hashtable 类可以接受任意类型的值作为 Key，这都要归功于 GetHashCode 方法，一个定义在 System.Object 中的方法。GetHashCode 的默认实现将返回一个唯一的整数，并且保证在对象的生命周期内保持不变。

Hashtable 类中的哈希函数定义如下：

1

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize

这里的 GetHash(key) 默认是调用 key 的 GetHashCode 方法以获取返回的哈希值。hashsize 指的是哈希表的长度。因为要进行求模，所以最后的结果 H(key) 的范围在 0 至 hashsize - 1 之间。

当在哈希表中添加或获取一个元素时，会发生哈希冲突。前面我们简单地介绍了两种冲突解决策略：

• 线性探查（Linear Probing）
• 二次探查（Quadratic Probing）

在 Hashtable 类中则使用的是一种完全不同的技术，称为二度哈希（rehashing）（有些资料中也将其称为双重哈希（double hashing））。

二度哈希的工作原理如下：

有一个包含一组哈希函数 H1…Hn 的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数 H1。如果导致冲突，则尝试使用 H2，以此类推，直到 Hn。所有的哈希函数都与 H1 十分相似，不同的是它们选用的乘法因子（multiplicative factor）。

通常，哈希函数 Hk 的定义如下：

1

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

当使用二度哈希时，重要的是在执行了 hashsize 次探查后，哈希表中的每一个位置都有且只有一次被访问到。也就是说，对于给定的 key，对哈希表中的同一位置不会同时使用 Hi 和 Hj。在 Hashtable 类中使用二度哈希公式，其始终保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 与 hashsize 互为素数（两数互为素数表示两者没有共同的质因子）。

二度哈希使用了 Θ(m2) 种探查序列，而线性探查（Linear Probing）和二次探查（Quadratic Probing）使用了Θ(m) 种探查序列，故二度哈希提供了更好的避免冲突的策略。

Hashtable 类中包含一个私有成员变量 loadFactor，loadFactor 指定了哈希表中元素数量与位置（slot）数量之间的最大比例。例如：如果 loadFactor 等于 0.5，则说明哈希表中只有一半的空间存放了元素值，其余一半都为空。

哈希表的构造函数允许用户指定 loadFactor 值，定义范围为 0.1 到 1.0。然而，不管你提供的值是多少，范围都不会超过 72%。即使你传递的值为 1.0，Hashtable 类的 loadFactor 值还是 0.72。微软认为loadFactor 的最佳值为 0.72，这平衡了速度与空间。因此虽然默认的 loadFactor 为 1.0，但系统内部却自动地将其改变为 0.72。所以，建议你使用缺省值1.0（但实际上是 0.72）。

向 Hashtable 中添加新元素时，需要检查以保证元素与空间大小的比例不会超过最大比例。如果超过了，哈希表空间将被扩充。步骤如下：

• 哈希表的位置空间几乎被翻倍。准确地说，位置空间值从当前的素数值增加到下一个最大的素数值。
• 因为二度哈希时，哈希表中的所有元素值将依赖于哈希表的位置空间值，所以表中所有值也需要重新二度哈希。

由此看出，对哈希表的扩充将是以性能损耗为代价。因此，我们应该预先估计哈希表中最有可能容纳的元素数量，在初始化哈希表时给予合适的值进行构造，以避免不必要的扩充。

Dictionary<K,T>

Hashtable类是一个类型松耦合的数据结构，开发人员可以指定任意的类型作为 Key 或 Item。当 .NET 引入泛型支持后，类型安全的 Dictionary<K,T> 类出现。Dictionary<K,T> 使用强类型来限制 Key 和 Item，当创建 Dictionary<K,T> 实例时，必须指定 Key 和 Item 的类型。

1

Dictionary<keyType, valueType> variableName = new Dictionary<keyType, valueType>();

如果继续使用上面描述的社保号和员工的示例，我们可以创建一个 Dictionary<K,T> 的实例：

1

Dictionary<int, Employee> employeeData = new Dictionary<int, Employee>();

这样我们就可以添加和删除员工信息了。

1
2
3
4
5
6

1 // Add some employees
2 employeeData.Add(455110189) = new Employee("Scott Mitchell");
3 employeeData.Add(455110191) = new Employee("Jisun Lee");
4 
5 // See if employee with SSN 123-45-6789 works here
6 if (employeeData.ContainsKey(123456789))

Dictionary<K,T> 与 Hashtable的不同之处还不止一处。除了支持强类型外，Dictionary<K,T> 还采用了不同的冲突解决策略（Collision Resolution Strategy），这种技术称为链接技术（chaining）。

前面使用的探查技术（probing），如果发生冲突，则将尝试列表中的下一个位置。如果使用二度哈希（rehashing），则将导致所有的哈希被重新计算。而链接技术（chaining）将采用额外的数据结构来处理冲突。Dictionary<K,T> 中的每个位置（slot）都映射到了一个链表。当冲突发生时，冲突的元素将被添加到桶（bucket）列表中。

下面的示意图中描述了 Dictionary<K,T> 中的每个桶（bucket）都包含了一个链表以存储相同哈希的元素。

上图中，该 Dictionary 包含了 8 个桶，也就是自顶向下的黄色背景的位置。一定数量的 Employee 对象已经被添加至 Dictionary 中。如果一个新的 Employee 要被添加至 Dictionary 中，将会被添加至其 Key 的哈希所对应的桶中。如果在相同位置已经有一个 Employee 存在了，则将会将新元素添加到列表的前面。

向 Dictionary 中添加元素的操作涉及到哈希计算和链表操作，但其仍为常量，渐进时间为 O(1)。

对 Dictionary 进行查询和删除操作时，其平均时间取决于 Dictionary 中元素的数量和桶（bucket）的数量。具体的说就是运行时间为 O(n/m)，这里 n 为元素的总数量，m 是桶的数量。但 Dictionary 几乎总是被实现为 n = O(m)，也就是说，元素的总数绝不会超过桶的总数，所以 O(n/m) 也变成了常量 O(1)。

以下文章来源于阿里巴巴中间件，作者简锋

每个人的时间都是有限的，在有限的时间里选择一项值得投入的技术会变得尤为重要。

笔者从 2008 年开始工作到现在也有 12 个年头了，一路走来都在和数据打交道，做过很多大数据底层框架内核的开发（Hadoop，Pig，Hive，Tez，Spark），也做过多年上层数据计算框架（Livy, Zeppelin）以及数据应用开发，包括数据处理，数据分析以及机器学习。现在是 Apache Member 以及多个 Apache 项目的 PMC 。2018 年加入阿里巴巴实时计算团队专注在 Flink 的研发。

今天我想结合自己过去的职业经历来聊聊如何评估一项技术是否值得学习。我一直在大数据这个圈子，从最初的 Hadoop 到后来的 Hadoop 生态项目 Pig，Hive，Tez，然后又到新一代的计算引擎 Spark ，再到最近在做的 Flink ，大数据计算引擎贯穿我的整个职业生涯。我个人来说是比较幸运的，在每个阶段都在做比较火的技术，当时更多的是凭着自己的兴趣和直觉在选择技术类型。现在回过头来看我觉得需要从下面 3 个大的纬度来评估一项技术是否值得学习。

1. 技术深度
2. 生态广度
3. 进化能力

以下文章来源于阿里巴巴中间件，作者石佳宁

最重要的是选择，最困难的是坚持。

我是在 2014 年入职饿了么，从前端和 PHP 一直做到后端架构和团队，从 2014 年到 2017 年陆续负责过公司客服、销售、代理商、支付、清结算、订单这些业务的产研与团队；2018 年从业务研发团队抽身，6 个人组起一个小组投身机器学习，试图结合实际的业务场景通过技术改造业务；2019 年回归到平台（中台）研发，负责交易、金融、营销三个中台的研发和团队工作。基于我在饿了么4年和阿里巴巴 2 年研发经历，从技术、业务、管理和架构层面分享一些我的思考。

技术层面

对开发同学而言，技术是立身之本，虽然往往面试造火箭入职拧螺丝，但不可否认的是，技术就是你从业的的基石。不管是基本的动手能力还是问题分析能力，包括你的思维逻辑乃至对事物认知的能力，技术思维都会时刻影响你。最明显的影响就是当你面对无数个问题的钉子时，技术是不是你最顺手的那把锤子。

技术上我比较关注的几个层面：

• 基本功（语言、编码这个层面，主要是动手能力）
• 大型分布式系统的实战经验（RPC、SOA、MySQL、Redis、MQ）
• 项目（ DB 设计、API契约、DDD抽象、链路设计、项目风险把控）
• 稳定性（可用 & 资损）

以下文章来源于IT人的职场进阶 ，作者骆俊武

高并发，几乎是每个程序员都想拥有的经验。原因很简单：随着流量变大，会遇到各种各样的技术问题，比如接口响应超时、CPU load升高、GC频繁、死锁、大数据量存储等等，这些问题能推动我们在技术深度上不断精进。

在过往的面试中，如果候选人做过高并发的项目，我通常会让对方谈谈对于高并发的理解，但是能系统性地回答好此问题的人并不多，大概分成这样几类：

1、对数据化的指标没有概念：不清楚选择什么样的指标来衡量高并发系统？分不清并发量和QPS，甚至不知道自己系统的总用户量、活跃用户量，平峰和高峰时的QPS和TPS等关键数据。

2、设计了一些方案，但是细节掌握不透彻：讲不出该方案要关注的技术点和可能带来的副作用。比如读性能有瓶颈会引入缓存，但是忽视了缓存命中率、热点key、数据一致性等问题。

3、理解片面，把高并发设计等同于性能优化：大谈并发编程、多级缓存、异步化、水平扩容，却忽视高可用设计、服务治理和运维保障。

4、掌握大方案，却忽视最基本的东西：能讲清楚垂直分层、水平分区、缓存等大思路，却没意识去分析数据结构是否合理，算法是否高效，没想过从最根本的IO和计算两个维度去做细节优化。

这篇文章，我想结合自己的高并发项目经验，系统性地总结下高并发需要掌握的知识和实践思路，希望对你有所帮助。内容分成以下3个部分：

• 如何理解高并发？
• 高并发系统设计的目标是什么？
• 高并发的实践方案有哪些？

文章转载自在docker-compose环境下以ws+tls方式一键搭建v2ray(So easy)，根据实际搭建情况，略有修改

通常以ws+tls方式搭建v2ray的步骤比较繁琐，比如安装v2ray、安装nginx、申请证书等等。那有没有比较简便的方法自动完成这一系列工作呢？答案就在下面。

在docker-compose环境下以ws+tls方式搭建v2ray的具体步骤如下：

一、环境准备

1.获取域名及VPS

第一步你应该先拥有一个VPS和一个域名，获取VPS和域名的方法如下：

• 免费域名注册： 免费域名申请；；
• VPS推荐搬瓦工，支持支付宝付款，注册地址：注册搬瓦工，注册教程：史上最详细搬瓦工VPS注册/购买图文教程(内附优惠券)，特价促销款：搬瓦工促销。
• 通过此【链接】注册Vultr VPS，即可获得$100，推荐刚上新的韩国机房，参考： Vultr韩国机房上线，韩国SK线路，附简单测试和新用户优惠。

然后将域名解析到你VPS的对应的IP地址。

通过史上最详细搬瓦工VPS注册/购买图文教程(内附优惠券)这篇文章，你应该知道如何使用xshell进行VPS的连接工作了。使用xshell远程连接后进行下面操作。

2.安装docker-ce并启动

以下操作我都是以root用户进行的。

• 安装

1
2

$ curl -fsSL https://get.docker.com -o get-docker.sh
$ sh get-docker.sh

注： 这一步如果是CENTOS 8，可能会出现 requires containerd.io >= 1.2.2-3错误 -> 解决办法。

• 添加用户到用户组

1

gpasswd -a $USER docker

• 启动

1

systemctl start docker

• 设置docker开机自启动

1

systemctl enable docker

3.安装docker-compose

1
2
3
4
5

$  curl -L "https://github.com/docker/compose/releases/download/1.25.4/docker-compose-$(uname -s)-$(uname -m)" -o /usr/local/bin/docker-compose

$ chmod +x /usr/local/bin/docker-compose

$ ln -s /usr/local/bin/docker-compose /usr/bin/docker-compose

4.安装git并clone代码

1
2
3
4

yum -y install git


git clone https://github.com/aitlp/docker-v2ray.git

或者你可以下载后在上传到你的VPS。

二、修改v2ray配置

下载部署配置文件，然后使用WinSCP等工具上传到你的VPS(当然，也可以安装git后直接clone)，地址： https://github.com/aitlp/docker-v2ray，如果不会下载请邮件联系 aitlpmw(at)gmail.com，我发送给你。

1.init-letsencrypt.sh

将里面的domains和email修改为自己的域名和邮箱。

2.docker-compose.yml

可以不用动。

3.data/v2ray/config.json

修改ID，"id": "bae399d4-13a4-46a3-b144-4af2c0004c2e"，也可以不修改。

4.data/nginx/conf.d/v2020_v2ray.conf

修改所有your_domain为自己的域名，其他地方，如果上面可以修改的地方你没修改，那么除了域名之外的也不用修改了。

三、一键部署v2ray

1
2
3

chomod +x ./init-letsencrypt.sh

sudo ./init-letsencrypt.sh

下面是我运行的详细过程：

四、客户端配置

现在你可以开始使用了。

参考： 2020年最新v2ray搭建详细图文教程(从小白到老炮)

相关配置参考： centos7基于nginx搭建v2ray服务端配置vmess+tls+websocket完全手册

文章转载自Nginx启用Let’s Encrypt SSL证书，根据实际搭建情况，略有修改

Let’ s Encrypt 是一个免费的 SSL/TLS 证书发行机构, 证书有效期为90天, 到期前30内可续期，因此不需要担心费用问题。

服务器环境：

• nginx-1.10.1
• php-7.0.4
• mariadb-10.1.13

启用证书的主要过程包括：客户端安装、获取证书、配置Nginx、证书自动续期等几个方面。

客户端下载

Let’ s Encrypt客户端现已更名为certbot，客户端的地址为https://github.com/certbot/certbot/releases 。

1
2
3
4
5
6
7
8

#下载
wget  https://github.com/certbot/certbot/archive/v1.5.0.tar.gz -O certbos.releases.tar.gz

#解压
tar xzvf certbos.releases.tar.gz

#进入目录
cd certbot-1.5.0

运行一次客户端，进行检查升级：

1
2
3
4
5

#进入目录
cd ~/certbot

#执行检查
./certbot-auto --help

如果没什么问题的话，会显示帮助文档。

获取证书

申请过程中要验证绑定的域名是否属于申请人, 其原理就是申请人在域名所在的服务器上申请证书, 然后 Let’ s Encrypt 会访问绑定的域名与客户端通信成功即可通过。

验证的方式有两种，一种是停止当前的 web server 服务, 让出 80 端口, 由客户端内置的 web server 启动与 Let’ s Encrypt 通信；一种是在域名根目录下创建一个临时目录, 并要保证外网通用域名可以访问这个目录，这种方式不需要停止当前的 web server 服务。

证书获取方式1：通过访问80端口方式验证

1
2
3
4
5
6
7
8

#停止nginx
systemctl stop nginx

#获取证书, --standalone 参数:使用内置web server. --email 参数:管理员邮箱,证书到期前会发邮件到此邮箱提醒. -d 参数:要绑定的域名,同一域的不同子域都要输入.
./certbot-auto certonly --standalone --email admin@4spaces.org -d ray.servehttp.com

#启动nginx
systemctl start nginx

证书获取方式2：通过临时目录验证

1
2

#--webroot 参数:指定使用临时目录的方式. -w 参数:指定后面-d 域名所在的根目录, 如果一次申请多个域的, 可以附加更多 -w...-d... 这段.
./certbot-auto certonly --webroot --email admin@4spaces.org -w /usr/share/nginx/html -d 4spaces.org -d www.4spaces.org

完成上面的操作即可获得 SSL 证书, 保存在 “/etc/letsencrypt/live/根域名/” 目录下, 会产生 4 个文件, 其中3个证书文件, 1个私钥文件. 不要移动证书的位置, 以免续期时出现错误。关于Letsencrypt使用的更多命令参见「这里」。

我这里是通过方式2申请的证书。

配置Nginx启用https

上面你的Nginx配置并没有启用ssl，下面我们需要开始配置nginx，让其支持https。进行这一步的前提是你前面已经成功生成证书。

编辑文件/etc/nginx/conf.d/default.conf(我是通过yum的方式安装的nginx，配置目录在这里，你根据自己的情况来)，进行如下配置（这个是我的完整配置）：

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
41
42
43
44
45
46
47
48
49
50
51
52

#设置非安全连接永久跳转到安全连接
server{
    listen 80;
    server_name 4spaces.org www.4spaces.org;
    #告诉浏览器有效期内只准用 https 访问
    add_header Strict-Transport-Security max-age=15768000;
    #永久重定向到 https 站点
    return 301 https://$server_name$request_uri;
}
server {
   #启用 https, 使用 http/2 协议, nginx 1.9.11 启用 http/2 会有bug, 已在 1.9.12 版本中修复.
   listen 443 ssl http2;
   server_name 4spaces.org www.4spaces.org;
   #首页
   index  index.php index.html index.htm;
   #网站根目录
   root   /usr/share/nginx/4spaces;
   #告诉浏览器当前页面禁止被frame
   add_header X-Frame-Options DENY;
   #告诉浏览器不要猜测mime类型
   add_header X-Content-Type-Options nosniff;

   #证书路径
   ssl_certificate /etc/letsencrypt/live/4spaces.org/fullchain.pem;
   #私钥路径
   ssl_certificate_key /etc/letsencrypt/live/4spaces.org/privkey.pem;
   #安全链接可选的加密协议
   ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
   #可选的加密算法,顺序很重要,越靠前的优先级越高.
   ssl_ciphers EECDH+CHACHA20:EECDH+CHACHA20-draft:EECDH+AES128:RSA+AES128:EECDH+AES256:RSA+AES256:EECDH+3DES:RSA+3DES:!MD5;
   #在 SSLv3 或 TLSv1 握手过程一般使用客户端的首选算法,如果启用下面的配置,则会使用服务器端的首选算法.
   ssl_prefer_server_ciphers on;
   #储存SSL会话的缓存类型和大小
   ssl_session_cache shared:SSL:10m;
   #缓存有效期
   ssl_session_timeout 60m;

    location / {
        try_files $uri $uri/ /index.php?$args;  #修改内容
    }

    # pass the PHP scripts to FastCGI server listening on 127.0.0.1:9000
    #
    #修改此处内容支持php
    location ~ \.php$ {
        fastcgi_pass   127.0.0.1:9000;
        fastcgi_index  index.php;
        fastcgi_param  SCRIPT_FILENAME  $document_root/$fastcgi_script_name;
        include        fastcgi_params;
    }

}

证书续期

前面说了，证书的有效期是3个月，你可以在证书过期前的30天内，进行续期，也可以进行脚本自动续期。

方式1
进入你在下载的certbot客户端目录，执行证书续期的脚本命令如下：

1

./certbot-auto renew

renew 参数是官方推荐的续期方式, 使用这个参数会遍历 /etc/letsencrypt/live 下所有的证书, 如果证书在可续期的时间范围内(过期前30天内), 就会申请新的证书并替换原有证书, 否则跳过。

方式2

如果要指定更新某个域名的证书, 则要使用 certonly 参数, 其实和新申请证书时的命令差不多.

1

./certbot-auto certonly --webroot --renew-by-default --email admin@4spaces.org -w /usr/share/nginx/html -d 4spaces.org -d www.4spaces.org

方式3

上面两种方式，都是手动去执行的，我们可以将上面两种方式跟linux的定时任务进行结合，最终脚本如下：

1）通过端口验证的脚本

1
2
3
4
5
6
7
8
9
10

#!/bin/sh
#停止 nginx 服务,使用 --standalone 独立服务器验证需要停止当前 web server.
systemctl stop nginx
if ! /path/to/certbot-auto renew -nvv --standalone > /var/log/letsencrypt/renew.log 2>&1 ; then
    echo Automated renewal failed:
    cat /var/log/letsencrypt/renew.log
    exit 1
fi
#启动 nginx
systemctl start nginx

2）通过临时目录的脚本

1
2
3
4
5
6
7
8
9
10
11

#!/bin/sh
# This script renews all the Let's Encrypt certificates with a validity < 30 days

if ! /path/to/certbot-auto renew > /var/log/letsencrypt/renew.log 2>&1 ; then
    echo Automated renewal failed:
    cat /var/log/letsencrypt/renew.log
    exit 1
fi

# 需要重启nginx证书才能生效
systemctl restart nginx

上面两个脚本中的/path/to/certbot-auto代表你下载客户端解压后的目录，其中目录下有个certbot-auto。

选取一种方式，将对应的脚本保存为 certbotrenew.sh。

添加可执行权限

1

chmod +x certbotrenew.sh

编辑 crontab 配置文件或执行 crontab -e 添加 cron 任务

1
2

#编辑定时任务
sudo crontab -e

我这里设置为每月28号23点执行此脚本:

1

0 23 28 * * /bin/sh /home/michael/certbot/certbotrenew.sh

保存退出即可。

内容参考：

• https://blog.itnmg.net/letsencrypt-ssl/；
• https://community.letsencrypt.org/t/certbot-auto-deployment-best-practices/91979/

文章转载自CentOS 7通过yum安装Nginx，根据实际搭建情况，略有修改

创建文件：

1

vi /etc/yum.repos.d/nginx.repo

添加如下内容：

1
2
3
4
5

[nginx]
name=nginx repo
baseurl=http://nginx.org/packages/centos/7/$basearch/
gpgcheck=0
enabled=1

然后执行

1

sudo yum install nginx

具体配置：

1

vi /etc/nginx/nginx.conf

服务：

1
2
3

systemctl start nginx.service # 启动Nginx服务

systemctl enable nginx.service #开机自启

参考内容：

1. http://nginx.org/en/linux_packages.html#mainline；
2. https://gist.github.com/ifels/c8cfdfe249e27ffa9ba1；

文章转载自centos7基于nginx搭建v2ray服务端配置vmess+tls+websocket完全手册，根据实际搭建情况，略有修改

一直都是使用自建shadowsocks科学上网，服务很稳定，虽然v2ray出现了很久，但是没花心思研究两者之间有什么区别。后来无意间查询自己手机的上网记录，出现下图信息，我感觉还是让上网更隐蔽一点更好。

注意：使用下文的方法出现rejected v2ray.com/core/proxy/vmess/encoding: invalid user，搞不通，有空再验证试试

本文转载自java命令学习系列，文章内容略有调整。

Java开发必须掌握的线上问题排查命令

作为一个合格的开发人员，不仅要能写得一手还代码，还有一项很重要的技能就是排查问题。这里提到的排查问题不仅仅是在coding的过程中debug等，还包括的就是线上问题的排查。由于在生产环境中，一般没办法debug（其实有些问题，debug也白扯。。。）,所以我们需要借助一些常用命令来查看运行时的具体情况，这些运行时信息包括但不限于运行日志、异常堆栈、堆使用情况、GC情况、JVM参数情况、线程情况等。

给一个系统定位问题的时候，知识、经验是关键，数据是依据，工具是运用知识处理数据的手段。为了便于我们排查和解决问题，Sun公司为我们提供了一些常用命令。这些命令一般都是jdk/lib/tools.jar中类库的一层薄包装。随着JVM的安装一起被安装到机器中，在bin目录中。下面就来认识一下这些命令以及具体使用方式。