计算机读书笔记

  A programming language can be the most important factor in a programmer’s day. However, a programming language is really a very tiny part of the world, and as such, it ought not be taken too seriously. Keep a sense of proportion and most importantly keep a sense of humor. Among major programming languages, C++ is the richest source of puns and jokes. That is no accident.
  Philosophy, like discussion of language features, does tend to get overly serious and preachy. For this, I apologize, but I felt like acknowledging my intellectual roots and I guess this is harmless - well, mostly harmless. And no, my preferences in literature are not limited to writers emphasizing philosophical and political themes; those are just the ones who left the most obvious traces in the fabric of C++.

《the design and evolution of c++ 》

最近看的书

《程序员的自我修养》

《程序员的自我修养》读书笔记

《Linux内核源代码情景分析》

《Linux内核源代码情景分析》

pdf文本无法复制，故截图记录
GPL许可证介绍

16位段地址+16位偏移量构成20位地址方法

多级页表构成


大页内存支持

linux内核与gcc版本的关系

由成员找到结构体首地址

内核缓冲区管理

一文读懂 | Linux对象分配器 SLAB 算法

Jeff发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池，而是将内存保持为针对特定目而初始化的状态。


灰色部分是着色区，绿色部分是slab管理结构，黄色部分是空闲对象链表的索引，红色部分是对象的实体。我们可以看到slab结构的s_mem字段指向了对象实体列表的起始地址。

早期进程间通信方式，对于信号的解释

System V IPC

BSD Unix

中断 异常和系统调用

进程四要素

文件系统层次

从文件逻辑空间到设备逻辑空间再到设备物理空间，不同层次维持不同的映射关系

设备驱动程序是上层的同步操作与底层的异步操作之间的桥梁

对称处理器存在的问题：

  • 处理器间的同步与互斥
  • 高速缓存与内存之间的一致性问题
  • 对于中断的处理

使用LOCK引线限制CPU内存访问

使用Advance Programable Interrupt Controller动态分配中断请求

《C专家编程》

《c专家编程》读书笔记

《GO语言并发之道》

由于不怎么熟悉GO，只做简单的摘录，敲敲示例代码
《Go语言并发之道》读书笔记

《C++沉思录》

《C++沉思录》读书笔记

过去看的书

Effective C++条款

术语
声明式（declaration）是告诉编译器某个东西的名称和类型，但略去细节。

1
2
3
4
5
6
extern int x; // 对象（object）声明式
int add(int lhs,int rhs); // 函数（function）声明式
class Widget; // 类（class）声明式

template<typename T> // 模板（template）声明式
class GraphNode;

定义式（definition）的任务是提供编译器一些声明式所遗漏的细节。对对象而言，定义式是编译器为此对象拨发内存的地点。对function或function template而言，定义式提供了代码本体。对class或class template而言，定义式列出它们的成员。

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
int x;
int add(int lhs,int rhs){
	return lhs + rhs;
}
class Widget{
public:
	Widget(){
		...
	}
	~Widget(){
		...
	}
	void test(){
		...
	}
}

template<typename T>
class GraphNode{
public:
	GraphNode(){
		...
	}
	~GraphNode(){
		...
	}
	...
}

初始化（initialization）是“给予对象初值”的过程。对用户自定义类型的对象而言，初始化由构造函数执行。所谓default构造函数是一个可被调用而不带任何实参者。这样的构造函数要不没有参数，要不就是每个参数都有缺省值
copy构造函数被用来“以同型对象初始化自我对象”，copy assignment操作符被用来“从另一个同型对象中拷贝其值到自我对象”

1. 让自己习惯C++

条款01： 视C++为一个语言联邦

  • C++由C，Object-Oriented C++，Template C++，STL四个次语言组成
  • C++高效编程守则视状况而变化，取决于你使用C++的哪一部分

条款02：尽量以const，enum，inline替换#define

  • 对于单纯常量，最好以const对象或enum替换#define
  • 对于形似函数的宏（macros），最好改用inline函数替换#define

条款03：尽可能使用const

  • 将某些东西声明为const可帮助编译器侦测出错误用法。const可被施加于任何作用域内的对象，函数参数，函数返回类型，成员函数本体。
  • 编译器强制实施bitwise constness，但你编写程序时应该使用“概念上的常量性”（conceptual constness）。
    bitwise constness：成员函数只有在不更改对象的任何成员变量（static除外）时才可以说是const，也就是说它不更改对象内的任何一个bit，潜在的风险是返回引用或指针间接修改对象成员。
  • 当const和non-const成员函数有着实质等价的实现时，令non-const版本调用const可避免代码重复。

条款04：确定对象被使用前已先被初始化

  • 为内置型对象进行手工初始化，因为C++不保证初始化它们。
  • 构造函数最好使用成员初值列（member initialization list），而不要在构造函数本体使用赋值操作。初值列列出的成员变量，其排列次序应该和它们在class中的声明次序相同。
  • 为免除“编译单元之初始化次序”问题，请以local static对象替换non-local static对象。

2. 构造/析构/赋值运算

条款05： 了解C++默默编写并调用哪些函数

  • 编译器可以暗自为class创建default构造函数，copy构造函数，copy assignment操作符，以及析构函数

条款06：若不想使用编译器自动生成的函数，就该明确拒绝

  • 为驳回编译器自动（暗自）提供的技能，可将相应的成员函数声明为private并且不予实现，或使用Uncopyable的基类，或在成员函数后加上=delete

条款07：为多态基类声明virtual析构函数

  • polymorphic（带多态性质的）base class应该声明应该virtual析构函数。如果class带有任何virtual函数，它就应该拥有一个virtual析构函数。
  • class的设计目的如果不是作为base class使用，或不是为了具备多态性（polymorphically），就不该声明virtual析构函数。

条款08：别让异常逃离析构函数

  • 析构函数绝对不要吐出异常。如果一个被析构函数调用的函数可能抛出异常，析构函数应该捕捉任何异常，然后吞下它们（不传播）或结束程序。
  • 如果客户需要对某个操作函数运行期间抛出的异常做出反应，那么class应该提供一个普通函数（而非在析构函数中）执行该操作。

条款09：绝不在构造和析构过程中调用virtual函数

  • 在构造和析构期间不要调用virtual函数，因为这类调用从不下降至derived class（比起当前执行构造函数和析构函数的那层）

条款10：令operator= 返回一个reference to *this

条款11：在operator= 中处理自我赋值

  • 注意自我赋值安全性与异常安全性
  • 确保对象自我赋值时operator=有良好行为。其中技术包括 比较“来源对象”和“目标对象”的地址，精心周到的语句顺序，以及copy-and-swap
  • 确定任何函数如果操作一个以上的对象，而其中多个对象是同一个对象时，其行为仍然正确

条款12：复制对象时勿忘其每一个成分

  • Copying函数应该确保复制“对象内的所有成员变量”及“所有base class成分”
  • 不要尝试以某个copying函数实现另一个copying函数。应该将共同机能放进第三个函数中，并由两个copying函数共同调用

3. 资源管理

所谓资源就是，一旦用了它，将来必须还给系统。C++程序中最常使用的资源就是动态分配内存，其他常见的资源包括文件描述符，互斥锁，数据库连接与socket。不论哪一种资源，重要的是，当你不再使用它时，必须将它还给系统

条款13：以对象管理资源

  • 为防止资源泄露，请使用RAII（Resource Acquisition Is Initialization）对象，它们在构造函数中获取资源并在析构函数中释放资源
  • C++11使用shared_ptr,unique_ptr,weak_ptr管理动态内存资源，使用lock_guard unique_lock shared_lock管理互斥锁

条款14：在资源管理类中小心copying行为

  • 复制RAII对象必须一并复制它管理的资源，所以资源的copying行为决定RAII对象的copying行为
  • 普遍而常见的RAII class copying行为是：抑制copying（unique_ptr：禁止拷贝，只能移动），施用引用计数法（reference counting）（shared_ptr：通过引用计数记录有多少个shared_ptr共同指向一个对象）。

条款15：在资源管理类中提供对原始资源的访问

  • API往往要求访问原始资源，所以每一个RAII class应该提供一个“取得其所管理资源”的方法。例如shared_ptr的get方法
    1
    element_type* get() const noexcept;
  • 对原始资源的访问可能经由显式转换或隐式转换。一般而言显式转换比较安全，但隐式转换对用户比较方便

条款16：成对使用new和delete时采取相同形式

  • 如果在new表达式中使用[]，必须在相应的delete表达式中也使用[]。如果在new表达式中不使用[]，一定不要在相应的delete表达式中使用[]

条款17：以独立语句将newed对象置入智能指针

  • 资源被创建（new Object）和资源被转换为资源管理对象（shared_ptr(Object*)）两个时间点之间可能发生异常干扰
  • 以独立语句将newed对象存储于智能指针内，否则异常抛出可能导致难以察觉的资源泄漏

4. 设计与声明

所谓软件设计，是“令软件做出你希望它做的事情”的步骤和做法，通常以颇为一般性的构想开始，最终演变成十足的细节，以允许特殊接口（interface）的开发，这些接口而后必须转换为C++声明式

条款18：让接口容易被正确使用，不易被误用

  • 好的接口很容易被正确使用，不容易被误用。你应该在你的所有接口中努力达成这些性质
  • “促进正确使用”的办法包括接口的一致性，以及与内置类型的行为兼容
  • “阻止误用”的办法包括建立新类型，限制类型上的操作，束缚对象值，以及消除客户的资源管理责任。

条款19：设计class犹如设计type

  • 新type的对象应该如何被创建和销毁？
  • 对象的初始化和对象的赋值应该有什么样的差别？
  • 新type的对象如果被passed by value，意味着什么？
  • 什么是新type的“合法值”
  • 你的新type需要配合某个继承图系吗？
  • 你的新type需要什么样的转换？
  • 什么样的操作符和函数对此新type而言是合理的？
  • 什么样的标准函数应该驳回？
  • 谁该取用新type的成员？
  • 什么是新type的“未声明接口”？ 它对效率，异常安全性，资源运用提供何种保证？
  • 你的新type有多么一般化？
  • 你真的需要一个新type吗？
  • Class的设计就是type的设计。在定义一个新type之前，请确定你已经考虑过上述问题

条款20：宁以pass-by-reference-to-const替换pass-by-value

  • 尽量以pass-by-reference-to-cost替换pass-by-value。前者通常比较高效，并可避免切割问题（slicing problem）
  • 以上规则并不使用于内置类型，以及STL的迭代器和函数对象。对它们而言，pass-by-value往往比较适合

条款21：必须返回对象时，别妄想返回其reference

  • 绝不要返回pointer或reference指向一个local stack对象，或返回reference指向一个head-allocated对象，或返回pointer或reference指向一个local static对象而可能同时需要多个这样的对象。

条款22：将成员变量声明为private

  • 切记将成员变量声明为private。这可赋予客户访问数据的一致性，可细微划分访问控制，允许约束条件获得保证，并提供class作者以充分的实现弹性
  • protected并不比public更具封装性

条款23：宁以non-member，non-friend替换member函数

  • 面向对象守则要求数据应该尽可能被封装，封装使我们能够改变事物而只影响有限客户
  • 宁可拿non-member non-friend函数替换member函数。这样做可以增加封装性，包裹弹性（packaging flexibility）和机能扩充性

条款24：若所有参数皆需类型转换，请为此采用non-member函数

  • 如果你需要为某个函数的所有参数（包括被this指针所指向的那个隐喻参数）进行类型转换，那么这个函数必须是non-member

条款25：考虑写出一个不抛异常的swap函数

  • 当std::swap对你的类型效率不高时，提供一个swap成员函数，并确定这个函数不抛出异常
  • 如果你提供一个member swap，也该提供一个non-member swap用来调用前者。对于class，也请特化std::swap
  • 调用swap时应针对std::swap使用using声明式，然后调用swap并且不带任何“命名空间资格修饰”
  • 为“用户自定义类型”进行std template全特化是好的，但千万不要尝试在std内加入某些对std而言全新的东西

5. 实现

大多数情况下，适当提出你的classes（class templates）定义以及functions（function templates）声明是花费心力最多的两件事。一旦正确完成他们，相应的实现大多直截了当。尽管如此，还是有些东西需要小心。太快定义变量可能造成效率上的拖延；过度使用转型可能导致代码变慢又难维护，又招来微妙难解的错误；返回对象“内部数据之号码牌（handles）”可能会破坏封装并留给客户虚吊号码牌（dangling handles）；未考虑异常带来的冲击则可能导致资源泄漏和数据败坏；过度热心地inlining可能引起代码膨胀；过度耦合（coupling）则可能导致让人不满意的冗长建置时间（build time）。

条款26：尽可能延后变量定义式的出现时间

  • 你不只应该延后变量的定义，直到非得使用该变量的前一刻为止，甚至应该尝试延后这份定义直到能够给它初值实参为止
  • 尽可能延后变量定义式的出现。这样做可增加程序的清晰度并改善程序效率
    循环结构
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 方法1：定义于循环外
    // 1次构造函数+1次析构函数+n次赋值操作
    Widget w;
    for(int i=0;i<n;i++){
    	w = s[i];
    	...
    }


    // 方法2：定义于循环内
    // n次构造函数+n次析构函数
    for(int i=0;i<n;i++){
    	Widget w = s[i];
    	...
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 我以前的风格，有可能有微乎其微的性能提升，但可读性变差
// a b len并不在循环外用到
int a;
int b;
for(int i=0;i<n;i++){
	a = ...
	b = ...
	...
}

int len = vec.size();
for(int i=0;i<len;i++){
}

// 可以改成
for(int i=0;i<n;i++){
	int a = ...
	int b = ...
	...
}
for(int i=0;i<vec.size();i++){
}

条款27：尽量少做转型动作

  • 如果可以，尽量避免转型，特别是在注重效率的代码中避免dynamic_cast。如果有个设计需要转型动作，试着发展无需转型的替代动作（类型安全容器，virtual函数往继承体系上方移动）
  • 如果转型是必要的，试着将它隐藏于某个函数背后。客户随后可以调用该函数，而不需将转型放进他们自己的代码内
  • 宁可使用C++style转型，不要使用旧式转型。前者很容易辨识出来，而且也比较有着分门别类的职掌

许多程序员相信，转型其实什么都没做，只是告诉编译器把某个类型视作另一种类型。这是错误的观念，任何一个类型转换往往真的令编译器编译出运行期间执行的码。

1
2
3
4
5
6
7
8
9
int x,y;
...
double d = static_cast<double>(x) / y;


class Base{...};
class Derived: public Base{...};
Derived d;
Base* pb = &d;
1
2
3
4
5
6
7
8
9
// C风格转型动作
(T)expression
T(expression)

// C++新式转型
const_cast<T>(expression): 移除对象常量性
dynamic_cast<T>(expression): 安全向下转型
reinterpret_cast<T>(expression): 意图执行低级转型，实际动作及结果可能取决于编译器
static_cast<T>(expression):	强迫隐式转换

条款28： 避免返回handles指向对象内部成分

  • 避免返回handles（包括references，指针，迭代器）指向对象内部。遵守这个条款可增加封装性，帮助const成员函数的行为像个const，并将发生“虚吊号码牌”（dangling handles）的可能性降至最低

条款29：为“异常安全”而努力是值得的

  • 异常安全函数（Exception-safe functions）即使发生异常也不会泄漏资源或允许任何数据结构败坏。这样的函数区分为三种可能的保证：基本型，强烈型，不抛异常型
  • “强烈保证”往往能够以copy-and-swap实现出来，但“强烈保证”并非对所有函数都可实现或具备现实意义
  • 函数保证的“异常安全保证”通常只等于其所有调用之各个函数的“异常安全保证”中的最弱者

条款30：透彻了解inlining的里里外外

  • 将大多数inlining限制在小型，被频繁调用的函数身上。这可使日后的调试过程和二进制升级（binary upgradability）更容易，也可使潜在的代码膨胀问题最小化，使程序的速度提升机会最大化
  • 不要只因为function template出现在头文件，就将它们声明为inline
  • 记住inline只是对编译器的一个申请，不是强制命令。这项申请可以隐喻提出，也可以明确提出。隐喻方式是将函数定义在class定义式内
  • inline函数通常一定被置于头文件内，inlining在大多数C++程序中是编译期行为，实际上构造函数和析构函数往往是inlining的糟糕候选人

条款31：将文件间的编译依存关系降至最低

  • 支持“编译依存性”最小化的一般构想是：相依于声明式，不要相依于定义式、基于此构想的两个手段是handle class和interface class
  • 程序库头文件应该以“完全且仅有声明式”（full and declaration-only form）的形式操作。这种做法不论是否涉及template都适用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// handle class pimpl idiom 

class Date;
class PersonImpl;

class Person{
public:
	Date GetBirthday();
private:
	PersonImpl* pImpl;
}

// interface class
class Date;
class Person{
	virtual ~Person();
	virtual Date GetBirthday() const = 0;	
};

Person* create(const Date& d);

6. 继承与面向对象设计

条款32：确定你的public继承塑模出is-a关系

  • public继承意味着is-a。适用于base class身上的每一件事情一定也适用于derived class身上，因为每一个derived class对象也都是base class对象

条款33：避免遮掩继承而来的名称

  • derived class内的名称会遮掩base class内的名称。在public继承下从来没人希望如此
  • 为了让遮掩的名称再见天日，可使用using声明式或转交函数（forwarding function）

条款34：区分接口继承和实现继承

  • 接口继承和实现继承不同。在public继承之下，derived class总是继承base class的接口
  • pure virtual函数只具体指定接口继承
  • 简单（非纯）impure virtual函数具体指定接口继承及缺省实现继承
  • non-virtual函数具体指定接口继承以及强制性实现继承
  • 为切断virtual函数接口与缺省实现的连接，可使用纯虚函数+函数实现/默认函数的方法
1
2
3
4
5
6
7
8
9
class Airplane{
public:
	virtual void fly() = 0;
protected:
	void defaultFly();
};

void Airplane::fly(){}
void Airplane::defaultFly(){}

条款35：考虑virtual函数以外的选择

  • virtual函数的替代方案包括NVI手法及strategy设计模式的多种形式。NVI手法自身是一种特殊形式的template method设计模式
  • 将机能从成员函数移到class外部函数，带来的一个缺点是，非成员函数无法访问class的non-public成员
  • std::function是一个函数包装器，该函数包装器模板能包装任何类型的可调用实体，如普通函数，函数对象，lamda表达式等。包装器可拷贝，移动等，并且包装器类型仅仅依赖于调用特征，而不依赖于可调用元素自身的类型
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
// NVI non-virtual interface
class Game{
public:
	int health(){
		... // 事先工作
		int ret = doHealth();
		... // 事后工作
	}	
private:
	virtual int doHealth(){}
};
// 策略模式
// 函数指针实现
class Game{	
	using healthfn=int(*)(const Game&);

private:
	healthfn fn; 
};

// 继承实现
class Game;
class HealthFunc{
	public:
		virtual int calc(const Game&);
}

class Game{
	
private:
	HealthFunc* pfn;
}

私有的纯虚函数，子类能重写么？

条款36：绝不重新定义继承而来的non-virtual函数

条款37：绝不重新定义继承而来的缺省参数值

  • 对象静态类型：程序中声明的类型，动态类型：目前所指对象的类型
  • virtual函数是动态绑定，缺省参数值是静态绑定
  • 可使用NVI手法，由non-virtual函数指定缺省参数，private virtual函数负责真正的工作

条款38：通过复合塑模出has-a或根据某物实现出

  • 复合（composition）的意义和public继承完全不同
  • 在应用域（application domain），复合意味has-a，在实现域（implement domain），复合意味is-implemented-in-term-of

条款39：明智而审慎地使用private继承

  • 如果class之间的继承关系是private，编译器不会自动将一个derived class对象转换为一个base class对象
  • private继承纯粹是一种实现技术，意味只有实现部分被继承，接口部分应略去，private继承在软件设计层面没有意义，其意义只及与软件实现层面
  • private继承意味着is-implemented-in-term-of。它通常比复合的优先级低，但当derived clas需要访问protected base class的成员，或需要重新定义继承而来的virtual函数时，这么设计是合理的
  • 和复合不同，private继承可以造成empty base最优化。这对致力于“对象尺寸最小化”的程序库开发者而言可能很重要

条例40：明智而审慎地使用多重继承

  • 多重继承比单一继承复杂。它可能导致新的歧义性，以及对virtual继承的需要
  • virtual继承会增加大小，速度，初始化复杂度等成本。如果virtual base class不带任何数据，将是最具实用价值的情况
  • 多重继承的确有正当用途。其中一个情节涉及“public继承某个interface class”和“private继承某个协助实现的class”的两相组合

7. 模板与泛型编程

条款41：了解隐式接口和编译期多态

  • class和template都支持接口（interface）和多态（polymorphism）
  • 对class而言接口是显式的（explicit），以函数签名为中心。多态则通过virtual函数发生于运行期
  • 对template参数而言，接口是隐式的（implicit），祭奠于有效表达式。多态则是通过template具现化和函数重载解析（function overloading resolution）发生于编译期

条款42：了解typename的双重意义

  • template内出现的名称如果相依于某个template参数，称之为从属名称（dependent names）。如果从属名称在class内呈嵌套状，我们称它为嵌套从属名称（nested dependent name）。
    1
    2
    3
    template<typename C>
    C::const_iterator // 有可能是静态成员变量，有可能是类型
    // 如果C++在template中遭遇一个嵌套从属名称，它便假设这名称不是类型
  • 声明template参数时，前缀关键字class和typename可互换
  • 请使用关键字typename标识嵌套从属类型名称，但不得用在base class list（基类列）或member initialization list（成员初值列）内以它作为base class修饰符

条款43：学习处理模板基类内的名称

  • 由于base class template有可能被特化，而那个特化版本可能不提供和一般性template相同的接口，所以编译器往往拒绝在templatized base class（模板化基类）内寻找继承而来的名称。就某种意义而言，当我们从object oriented C++跨向template C++，继承就不像以前那般畅通无阻了
  • 解决方法有：使用this->,使用using声明式，使用资格修饰符（关闭virtual绑定行为）
  • 根本而言，本条款探讨的是，面对“指涉base class member”之前无效reference，编译器的诊断时间可能发生在早期（当前解析derived class template的定义式时），也可能发生在晚期（当那些template被特定之template 实参具现化时）。C++的政策是宁愿较早诊断，这就是为什么“当base class从template中被具现化是”，它假设它对那些base class的内容毫无所悉的缘故

条款44：将于参数无关的代码抽离template

  • template生成多个class和多个函数，所以任何template代码都不该与某个造成膨胀的template参数产生相依关系
  • 因非类型模板参数（non-type template parameter）而造成的代码膨胀，往往可以消除，做法往往是以函数参数或class成员变量替换template参数
  • 因类型参数（type parameter）而造成的代码膨胀，往往可降低，做法是让带有完全相同二进制表示（binary represention）的具现类型（instantiation type）共享实现码

条款45：运用成员函数模板接受所有兼容类型

  • 请使用member function template（成员函数模板）生成“可接受所有兼容类型”的函数
  • 如果你声明member template用于“泛化copy构造”或“泛化assignment操作”，你还是需要声明正常的copy构造函数和copy assignment操作符

条款46：需要类型转换时请为模板定义非成员函数

  • 当我们编写一个class template，而它所提供之“与此template相关的”函数支持“所有参数之隐式类型转换”时，请将那些函数定义为“class template内部的friend函数”。

条款47：请使用traits classes表现类型信息

  • traits classes使用“类型相关信息”在编译期可用。它们以template和template特化实现
  • 整合重载技术（overloading）后，traits classes有可能在编译期对类型执行if…else测试
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
template<...>
class deque{
	class iterator{
		typedef random_access_iterator_tag iterator_category;
	}
}
template<...>
class list{
	class iterator{
		typedef bidirectional_iterator_tag iterator_category;
	}
}
...
template<typename IterT>
struct iterator_traits{
	typedef typename IterT::iterator_category iterator_category
}

template<typename IterT>
struct iterator_traits<IterT*>{		// 内置指针
	typedef random_access_iterator_tag iterator_category
}

void advance(...,random_access_iterator_tag);
void advance(...,bidirectional_iterator_tag);

advance(...,iterator_traits<IterT>::iterator_category)

条款48：认识template元编程

  • template metaprograming（TMP）可将工作由运行期移往编译期，因而得以实现早期错误侦测和更高的执行效率
  • TMP可被用来生成“基于政策选择组合”的客户定制代码，也可用来避免生成对某些特殊类型并不适合的代码
1
2
3
4
5
6
7
8
9
template<unsigned n>
struct Fact{
	enum { value = n * Fact<n-1>::value> };
}

template<>
struct Fact<0>{
	enum { value = 1 };
}

全特化与偏特化
C++的Enum hack

8. 定制new和delete

条款49：了解new-handler的行为

  • set_new_hander允许客户指定一个函数，在内存分配无法获得满足时调用
  • nothrow new是一个颇为局限的工具，因为它只适合内存分配：后续的构造函数调用还是可能抛出异常
    条款50：了解new和delete的合理替换时机
  • 为了检测运用错误
  • 为了收集动态分配内存之使用统计信息
  • 为了增加分配和归还的速度
  • 为了降低缺省内存管理器带来的空间额外开销
  • 为了弥补缺省分配器中的非最佳齐位
  • 为了将相关对象成簇集中
  • 为了获得非传统的行为
  • 有许多理由需要写个自定的new和delete，包括改善效能，对heap运用错误进行调试，收集heap使用信息
    条款51：编写new和delete时需固守常规
  • operator new应该内含一个无穷循环，并在其中尝试分配内存，如果它无法满足内存需求，就该调用new-handler。它也应该有能力处理0bytes申请。class专属版本则还应该处理“比正确大小更大（错误）申请”
  • operator delete应该在收到null指针时不做任何事。class专属版本则还应该处理“比正确大小更大的（错误）”申请

条款52：写了placement new也要写placement delete

  • 当你写一个placement operator new，请确定也写出了对应的placement operator delete。如果没有这样做，你的程序可能会发生隐蔽而时断时续的内存泄漏
  • 当你声明placement new和placement delete，请确定不要无意识（非故意）地遮掩它们的正常版本

C++ 工程实践(2)：不要重载全局 ::operator new()

9. 杂项讨论

条款53：不要轻忽编译器的警告

  • 严肃对待编译器发出的警告信息。努力在你的编译器的最高警告级别下争取“无任何警告”的荣誉
  • 不要过度依赖编译器的报警能力，因为不同的编译器对待事物的态度并不相同。一旦移植到另一个编译器上，你原本依赖的警告信息有可能消失

条款54：让自己熟悉包括TR1在内的标准程序库
条款55：让自己熟悉Boost

Effective Modern C++

在线阅读地址：Effective Modern C++
复制粘贴一下目录
第一章 类型推导
Item 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
template<typename T>
void f(ParamType param);

f(expr);                        //从expr中推导T和ParamType



int x=27;                       //x是int
const int cx=x;                 //cx是const int
const int& rx=x;                //rx是指向作为const int的x的引用
// ParamType是一个指针或引用，但不是通用引用

template<typename T>
void f(T& param);               //param是一个引用

f(x);                           //T是int，param的类型是int&
f(cx);                          //T是const int，param的类型是const int&
f(rx);                          //T是const int，param的类型是const int&

template<typename T>
void f(const T& param);         //param现在是reference-to-const

f(x);                           //T是int，param的类型是const int&
f(cx);                          //T是int，param的类型是const int&
f(rx);                          //T是int，param的类型是const int&

// ParamType是一个通用引用

// 如果expr是左值，T和ParamType都会被推导为左值引用
// 如果expr是右值，就使用正常的推导规则
template<typename T>
void f(T&& param);              //param现在是一个通用引用类型
        


f(x);                           //x是左值，所以T是int&，
                                //param类型也是int&

f(cx);                          //cx是左值，所以T是const int&，
                                //param类型也是const int&

f(rx);                          //rx是左值，所以T是const int&，
                                //param类型也是const int&

f(27);                          //27是右值，所以T是int，
                                //param类型就是int&&
// ParamType既不是指针也不是引用
template<typename T>
void f(T param);                //以传值的方式处理param


f(x);                           //T和param的类型都是int
f(cx);                          //T和param的类型都是int
f(rx);                          //T和param的类型都是int

Item 2:理解auto类型推导
Item 3:理解decltype
Item 4:学会查看类型推导结果
第二章 auto
Item 5:优先考虑auto而非显式类型声明
Item 6:auto推导若非己愿，使用显式类型初始化惯用法
第三章 移步现代C++
Item 7:区别使用()和{}创建对象
Item 8:优先考虑nullptr而非0和NULL
Item 9:优先考虑别名声明而非typedef
Item 10:优先考虑限域枚举而非未限域枚举

  • 使用限域enum来减少命名空间污染
  • 在它的作用域中，枚举名是强类型

Item 11:优先考虑使用deleted函数而非使用未定义的私有声明
Item 12:使用override声明重载函数
Item 13:优先考虑const_iterator而非iterator
Item 14:如果函数不抛出异常请使用noexcept
Item 15:尽可能的使用constexpr
Item 16:让const成员函数线程安全
Item 17:理解特殊成员函数函数的生成
第四章 智能指针
Item 18:对于独占资源使用std::unique_ptr
Item 19:对于共享资源使用std::shared_ptr
Item 20:当std::shared_ptr可能悬空时使用std::weak_ptr
Item 21:优先考虑使用std::make_unique和std::make_shared而非new
Item 22:当使用Pimpl惯用法，请在实现文件中定义特殊成员函数
第五章 右值引用，移动语义，完美转发
Item 23:理解std::move和std::forward

  • 移动语义使编译器有可能用廉价的移动操作来代替昂贵的拷贝操作。正如拷贝构造函数和拷贝赋值操作符给了你控制拷贝语义的权力，移动构造函数和移动赋值操作符也给了你控制移动语义的权力。移动语义也允许创建只可移动（move-only）的类型，例如std::unique_ptr，std::future和std::thread。

  • 完美转发使接收任意数量实参的函数模板成为可能，它可以将实参转发到其他的函数，使目标函数接收到的实参与被传递给转发函数的实参保持一致。

为了了解std::move和std::forward，一种有用的方式是从它们不做什么这个角度来了解它们。std::move不移动（move）任何东西，std::forward也不转发（forward）任何东西。在运行时，它们不做任何事情。它们不产生任何可执行代码，一字节也没有。
std::move和std::forward仅仅是执行转换（cast）的函数（事实上是函数模板）。std::move无条件的将它的实参转换为右值，而std::forward只在特定情况满足时下进行转换。它们就是如此。这样的解释带来了一些新的问题，但是从根本上而言，这就是全部内容。

Item 24:区别通用引用和右值引用
Item 25:对于右值引用使用std::move，对于通用引用使用std::forward
Item 26:避免重载通用引用
Item 27:熟悉重载通用引用的替代品
Item 28:理解引用折叠
Item 29:认识移动操作的缺点
Item 30:熟悉完美转发失败的情况
第六章 Lambda表达式
Item 31:避免使用默认捕获模式
Item 32:使用初始化捕获来移动对象到闭包中
Item 33:对于std::forward的auto&&形参使用decltype
Item 34:优先考虑lambda表达式而非std::bind
第七章 并发API
Item 35:优先考虑基于任务的编程而非基于线程的编程
Item 36:如果有异步的必要请指定std::launch::threads
Item 37:从各个方面使得std::threads unjoinable
Item 38:关注不同线程句柄析构行为
Item 39:考虑对于单次事件通信使用void
Item 40:对于并发使用std::atomic，volatile用于特殊内存区
第八章 微调
Item 41:对于那些可移动总是被拷贝的形参使用传值方式
Item 42:考虑就地创建而非插入

Effective STL

复制粘贴一下目录
容器
条款1: 仔细选择你要的容器
条款2: 小心对“容器无关代码”的幻想
条款3: 使容器里对象的拷贝操作轻量而正确
条款4: 用empty来代替检查size是否为0
条款5: 尽量使用范围成员函数代替他们的单元素兄弟
条款6: 警惕C++的及其令人恼怒的分析
条款7: 当使用new得指针的容器时，切记在容器销毁前delete那些指针
条款8: 千万不要把auto_ptr放入容器中
条款9: 小心选择删除选项
条款10: 当心allocator的协定和约束
条款11: 了解自定义allocator的正统使用法
条款12: 对STL容器的线程安全性的期待现实一些
vector和string
条款13: 尽量使用vector和string来代替动态申请的数组
条款14: 用reserve来避免不必要的内存重新分配
条款15: 当心string的实现中的变化
条款16: 如何将vector和string的数据传给传统的API
条款17: 用“交换技巧”来修正过度的容量
条款18: 避免使用vector
关联容器
条款19: 了解相等和等价的区别

  • 操作上来说，相等的概念是基于operator==的。如果表达式“x == y”返回true，x和y有相等的值，否则它们没有。
  • 等价是基于在一个有序区间中对象值的相对位置。等价一般在每种标准关联容器（比如，set、multiset、map和multimap）的一部分——排序顺序方面有意义。两个对象x和y如果在关联容器c的排序顺序中没有哪个排在另一个之前，那么它们关于c使用的排序顺序有等价的值。

条款20: 为包含指针的关联容器指定比较类型
条款21: 永远让比较函数对相等的值返回false
条款22: 避免对set和multiset的键值进行修改
条款23: 考虑用排序的vector代替关联容器
条款24: 当效率很关键时尽量用map::insert代替map::operator
条款25: 让自己熟悉非标准的hash容器
迭代器
条款26: 尽量使用iterator代替const_iterator，reverse_iterator和const_reverse_iterator
条款27: 使用distance和advance把const_iterators转化成iterators
条款28: 了解如何通过reverse_iterator的base得到iterator
条款29: 需要一字符一字符输入时请用istreambuf_iterator
算法
条款30: 确保目的范围足够大
条款31: 了解你的排序选项
条款32: 如果你真的想删除东西的话在remove-like的算法后紧接上erase
条款33: 当心在包含指针的容器使用remove-like的算法
条款34: 注意哪些算法需要排序过的范围
条款35: 通过mismatch或lexicographical_compare实现简单的忽略大小写字符串比较
条款36: 用not1和remove_copy_if来表现copy_if
条款37: 用accumulate或for_each来统计序列
仿函数，仿函数类，函数等等
条款38: 把仿函数类设计成值传递的
条款39: 用纯函数做predicate
条款40: 增强仿函数类的适应性
条款41: 明确ptr_fun, mem_fun和mem_fun_ref的区别
条款42: 保证less是operator<的意思
用STL编程
条款43: 尽量用算法调用代替手写循环
条款44: 尽量用成员函数代替同名的算法
条款45: 注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别
条款46: 考虑用函数对象代替函数作为算法的参数
条款47: 避免产生只写代码
条款48: 总是#include适当的头文件
条款49: 学会破解STL相关的编译器出错信息
条款50: 让自己熟悉STL相关的网站

数据密集型应用设计

非常推荐的一本书，常看常新。书籍地址：https://github.com/Vonng/ddia

第三章：存储与检索

建立秩序，省却搜索

日志结构（log-structured） 的存储引擎，以及面向页面（page-oriented） 的存储引擎（例如B树）

  • 一个数据库在最基础的层次上需要完成两件事情：当你把数据交给数据库时，它应当把数据存储起来；而后当你向数据库要数据时，它应当把数据返回给你
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/bin/bash
db_set () {
	echo "$1,$2" >> database
}

db_get () {
	grep "^$1," database | sed -e "s/^$1,//" | tail -n 1	# sed 将key,部分删除（替换为空）
}

root@ubuntu:~/.leetcode# source database.sh
root@ubuntu:~/.leetcode# db_set 123 abc
root@ubuntu:~/.leetcode# db_set 456 def
root@ubuntu:~/.leetcode# db_get 123
abc
root@ubuntu:~/.leetcode# db_set 123 xyz
root@ubuntu:~/.leetcode# db_get 123
xyz
root@ubuntu:~/.leetcode# cat database
123,abc
456,def
123,xyz
  • 索引背后的大致思想是，保存一些额外的元数据作为路标，帮助你找到想要的数据。如果您想在同一份数据中以几种不同的方式进行搜索，那么你也许需要不同的索引，建在数据的不同部分上
  • 索引是从主数据衍生的附加（additional）结构。精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度

SSTables存储引擎

  • 写入时，将其添加到内存中的平衡树数据结构（例如，红黑树）。这个内存树有时被称为内存表（memtable）。
  • 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的SSTable文件成为数据库的最新部分。当SSTable被写入磁盘时，写入可以继续到一个新的内存表实例。
  • 为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下一个较旧的段中找到该关键字。
  • 有时会在后台运行合并和压缩过程以组合段文件并丢弃覆盖或删除的值。
  • 为了避免数据库崩溃数据丢失，我们可以在磁盘上保存一个单独的日志，每个写入都会立即被附加到磁盘上，每当内存表写出到SSTable时，相应的日志都可以被丢弃

深入浅出分析LSM树（日志结构合并树）
LSM树的设计原则：

  • 先内存再磁盘
  • 内存原地更新
  • 磁盘追加更新
  • 归并保留新值

日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。相比之下，B树将数据库分解成固定大小的块或页面，传统上大小为4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。为了使数据库对崩溃具有韧性，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）

聚集索引与非聚集索引的总结
什么是聚集索引、非聚集索引
索引的作用及优缺点

第五章：复制

与可能出错的东西比，’不可能’出错的东西最显著的特点就是：一旦真的出错，通常就彻底玩完了。

复制意味着在通过网络连接的多台机器上保留相同数据的副本。我们希望能复制数据，可能出于各种各样的原因：

  • 使得数据与用户在地理上接近（从而减少延迟）
  • 即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）
  • 扩展可以接受读请求的机器数量（从而提高读取吞吐量）

复制的困难之处在于处理复制数据的变更（change），三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader）和无领导者（leaderless）。几乎所有分布式数据库都使用这三种方法之一

​ 存储数据库副本的每个节点称为副本（replica） 。当存在多个副本时，会不可避免的出现一个问题：如何确保所有数据都落在了所有的副本上？
​ 每一次向数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据。最常见的解决方案被称为基于领导者的复制（leader-based replication） （也称主动/被动（active/passive）或 主/从（master/slave）复制）。它的工作原理如下：

  1. 副本之一被指定为领导者（leader），也称为主库（master|primary）。当客户端要向数据库写入时，它必须将请求发送给领导者，领导者会将新数据写入其本地存储。
  2. 其他副本被称为追随者（followers），亦称为只读副本（read replicas），从库（slaves），备库（ sencondaries），热备（hot-standby）。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为复制日志（replication log）记录或变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
  3. 当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。 但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）。

    基于领导者的复制：一个同步从库和一个异步从库

处理节点宕机：
从库失效：追赶恢复
主库失效：故障切换

故障切换过程

  • 通过超时机制确认主库失效
  • 通过选举过程/控制器节点选择新的主库
  • 重新配置系统以启用新的主库

引发的问题

  • 异步复制带来的数据丢失问题
  • 脑裂问题与屏蔽措施
  • 难以选择合适的超时时间

复制日志的实现方式

  • 基于语句的复制
    主库记录下它执行的每个写入请求（语句（statement））并将该语句日志发送给其从库，语句执行有可能存在不确定性
  • 传输预写式日志（WAL）
    日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本，复制日志与存储引擎紧密耦合，主库/从库数据库软件版本需一致
  • 逻辑日志复制（基于行）
    复制和存储引擎使用不同的日志格式，这样可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。
  • 基于触发器的复制
    触发器允许您注册在数据库系统中发生数据更改（写入事务）时自动执行的自定义应用程序代码。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上任何业务逻辑处理，会后将数据变更复制到另一个系统去。

最终一致性：当应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致，但这种不一致只是一个暂时的状态——如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致

读己之写

实现读写一致性的技术

  • 读用户可能已经修改过的内容时，都从主库读：用户个人档案
  • 上次更新时间，从库复制延迟
  • 客户端记录最近一次写入时间戳

单调读

单调读取仅意味着如果一个用户顺序地进行多次读取，则他们不会看到时间后退，即，如果先前读取到较新的数据，后续读取不会得到更旧的数据。实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取

一致前缀读

一致前缀读（consistent prefix reads）。 这个保证说：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。一种解决方案是，确保任何因果相关的写入都写入相同的分区。

多主复制
基于领导者的复制模型的自然延伸是允许多个节点接受写入。 复制仍然以同样的方式发生：处理写入的每个节点都必须将该数据更改转发给所有其他节点。 称之为多领导者配置（也称多主、多活复制）。 在这种情况下，每个领导者同时扮演其他领导者的追随者。多主复制的主要缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的

冲突解决方法

  • 处理冲突的最简单的策略就是避免它们：如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生
  • 数据库必须以一种收敛（convergent）的方式解决冲突，这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。
    1 给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入胜利（LWW, last write wins）
    2 为每个副本分配一个唯一的ID，ID编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
    3 以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们
    4 用一种可保留所有信息的显式数据结构来记录冲突，并编写解决冲突的应用程序代码
  • 应用程序自定义冲突解决逻辑，在写时执行或读时执行

复制拓扑（replication topology）描述写入从一个节点传播到另一个节点的通信路径

无主复制

一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端的写入。在一些无领导者的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个协调者（coordinator）节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。

复制方案应确保最终将所有数据复制到每个副本。在一个不可用的节点重新联机之后，通过读修复和反熵过程赶上它错过的写入

更一般地说，如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。 只要w + r> n，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数（quorum）的读和写

宽松的法定人数：写和读仍然需要w和r成功的响应，但是那些可能包括不在指定的n个“主”节点中的值。比方说，如果你把自己锁在房子外面，你可能会敲开邻居的门，问你是否可以暂时停留在沙发上。

最后写入胜利（丢弃并发写入）
LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写入将被静默丢弃。

“此前发生”的关系和并发
如果操作B了解操作A，或者依赖于A，或者以某种方式构建于操作A之上，则操作A在另一个操作B之前发生。在另一个操作之前是否发生一个操作是定义什么并发的关键。如果两个操作都不在另一个之前发生，那么两个操作是并发的


因果依赖关系图
服务器可以通过查看版本号来确定两个操作是否是并发的。该算法的工作原理如下：

  • 服务器为每个键保留一个版本号，每次写入键时都增加版本号，并将新版本号与写入的值一起存储。
  • 当客户端读取键时，服务器将返回所有未覆盖的值以及最新的版本号。客户端在写入前必须读取。
  • 客户端写入键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。 （来自写入请求的响应可以像读取一样，返回所有当前值，这使得我们可以像购物车示例那样连接多个写入。）
  • 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持所有值更高版本号（因为这些值与传入的写入同时发生）。

当一个写入包含前一次读取的版本号时，它会告诉我们写入的是哪一种状态。如果在不包含版本号的情况下进行写操作，则与所有其他写操作并发，因此它不会覆盖任何内容 —— 只会在随后的读取中作为其中一个值返回。

GFS
gfs翻译

GFS集群由一个单个的master和多个chunkserver（块服务器）组成，GFS集群会有很多客户端client访问（图1）。每一个节点都是一个普通的Linux计算机，运行的是一个用户级别（user-level）的服务器进程。只要机器资源允许，并且允许不稳定的应用代码导致的低可靠性，我们就在同一台机器上运行chunkserver和client。
在GFS下，每一个文件都拆成固定大小的chunk(块)。每一个块都由master根据块创建的时间产生一个全局唯一的64位的chunk handle标志。Chunkservers在本地磁盘上用Linux文件系统保存这些chunk，并且根据chunk handle和字节区间，通过Linux文件系统读/写这些chunk的数据。出于可靠性的考虑，每一个块都会在不同的chunkserver上保存备份。默认情况下，我们保存3个备份，不过用户对于不同的文件namespace区域，可以指定不同的复制级别。
master负责管理所有的文件系统的元数据(metadata,元数据是指描述数据属性的信息，包括存储位置，历史数据等等)。包括namespace，访问控制信息，文件到chunk的映射关系，当前chunk的位置等等信息。master也同样控制系统级别的活动，比如chunk的分配管理，孤点chunk的垃圾回收机制，chunkserver之间的chunk镜像管理。master和这些chunkserver之间会有周期性的的心跳检测，并且在检测的过程中向其发出指令并收集其状态。
连接到各个应用系统的GFS客户端代码包含了文件系统的API，并且会和master和chunkserver进行通讯处理，代表应用程序进行读/写数据的操作。客户端和master进行元数据的操作，但是所有的数据相关的通讯是直接和chunkserver进行的。我们并没有提供POSIX API,因此不需要连接到Linux的vnode层。
客户端或者chunkserver都不会缓存文件数据。客户端缓存机制没有什么好处，这是因为大部分的应用都是流式访问超大文件或者操作的数据集太大而不能被缓存。不设计缓存系统使得客户端以及整个系统都大大简化了（不用设计解决缓存的一致性的问题，也就是缓存同步机制）(不过客户端缓存元数据)。chunkserver不需要缓存文件数据，因为chunks已经跟本地文件一样的被保存了，所以Linux的buffer cache已经把常用的数据缓存到了内存里。

一个变更是指一个改变chunk的内容或者metadata的操作，比如写操作或者append操作。每个变更都需要在所有chunk的副本上执行。我们使用租约来保持多个副本间变更顺序的一致性。Master授权给其中的一个副本一个该chunk的租约，我们把它叫做主副本(primary)。这个primary对所有对chunk更改进行序列化。然后所有的副本根据这个顺序执行变更。因此，全局的变更顺序首先是由master选择的租约授权顺序来确定的(可能有多个chunk需要进行修改)，而同一个租约内的变更顺序则是由那个主副本来定义的。
租约机制是为了最小化master的管理开销而设计的。一个租约有一个初始化为60s的超时时间设置。然而只要这个chunk正在变更，那个主副本就可以向master请求延长租约。这些请求和授权通常是与master和chunkserver间的心跳信息一起发送的。有时候master可能想在租约过期前撤销它(比如，master可能想使对一个正在重命名的文件的变更无效)。即使master无法与主副本进行通信，它也可以在旧的租约过期后安全的将租约授权给另一个新的副本。

第六章： 分区

我们必须跳出电脑指令序列的窠臼。 叙述定义、描述元数据、梳理关系，而不是编写过程。

分区是一种有意将大型数据库分解成小型数据库的方式。分区主要是为了可扩展性。不同的分区可以放在不共享集群中的不同节点上。因此，大数据集可以分布在多个磁盘上，并且查询负载可以分布在多个处理器上。
组合使用复制和分区：每个节点充当某些分区的领导者，其他分区充当追随者

分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量。 如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据偏斜的存在使分区效率下降很多。在极端的情况下，所有的负载可能压在一个分区上，其余9个节点空闲的，瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为热点（hot spot）。

根据键的范围分区

一种分区的方法是为每个分区指定一块连续的键范围（从最小值到最大值），Key Range分区的优势在于可以进行有效的范围查询，但是如果应用程序经常访问相邻的主键，则存在热点的风险。

根据键的散列分区
由于偏斜和热点的风险，许多分布式数据存储使用散列函数来确定给定键的分区。这种方法破坏了键的排序，使得范围查询效率低下，但可以更均匀地分配负载。
针对极端情况，所有的读写操作都是针对同一个键的，此时应用程序有义务进行额外工作减小偏斜，例如在主键前后添加随机数，将请求分散到多个分区，查询时从各个分区读取数据并合并。

二级索引分区方法：基于文档的分区（document-based）和基于关键词（term-based）的分区。

基于文档的分区：每个分区是完全独立的：每个分区维护自己的二级索引，仅覆盖该分区中的文档。它不关心存储在其他分区的数据。

关键词分区：覆盖所有分区数据的全局索引，可以采用与主键不同的分区方式。

分区再平衡方法

反面教材：hash mod N，N为节点数目，当N发生改变时数据需要频繁移动

固定数量的分区：创建比节点更多的分区，并为每个节点分配多个分区。如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。

动态分区：当分区增长到超过配置的大小时，会被分成两个分区，每个分区约占一半的数据。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。

按节点比例分区：每个节点具有固定数量的分区。在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变，但是当增加节点数时，分区将再次变小。

服务发现：当客户想要发出请求时，如何知道要连接哪个节点？


6.824 lab4的配置服务器就提供了协调服务的功能，客户端查询配置服务器得到负责对应分区的复制集群地址

第七章：事务

一些作者声称，支持通用的两阶段提交代价太大，会带来性能与可用性的问题。让程序员来处理过度使用事务导致的性能问题，总比缺少事务编程好得多。

  • 事务所提供的安全保证，通常由众所周知的首字母缩略词ACID来描述，ACID代表原子性（Atomicity），一致性（Consistency），隔离性（Isolation）和持久性（Durability）

  • ACID的原子性并不关于并发（concurrent）的。它并不是在描述如果几个进程试图同时访问相同的数据会发生什么情况，这种情况包含在缩写中，即隔离性（Isolation）

  • ACID原子性的定义特征是：能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。 或许 可中止性（abortability） 是更好的术语

  • ACID一致性的概念是，对数据的一组特定约束必须始终成立。即不变量（invariants）

  • 原子性，隔离性和持久性是数据库的属性，而一致性（在ACID意义上）是应用程序的属性。应用可能依赖数据库的原子性和隔离属性来实现一致性，但这并不仅取决于数据库。因此，字母C不属于ACID

  • ACID意义上的隔离性意味着，同时执行的事务是相互隔离的：它们不能相互冒犯

  • 数据库系统的目的是，提供一个安全的地方存储数据，而不用担心丢失。持久性 是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失

  • 单对象和多对象操作：CAS以及其他单一对象操作被称为“轻量级事务”，但是这个术语是误导性的。事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制。

  • 没有原子性，错误处理就要复杂得多，缺乏隔离性，就会导致并发问题。事务的一个关键特性是，如果发生错误，它可以中止并安全地重试。 ACID数据库基于这样的哲学：如果数据库有违反其原子性，隔离性或持久性的危险，则宁愿完全放弃事务，而不是留下半成品。

问题：
脏写：后面的写入会覆盖一个尚未提交的值

存在脏写，来自不同事务的冲突写入可能会混淆在一起

脏读：一个事务可以看到另一个事务未提交的数据
没有脏读：用户2只有在用户1的事务已经提交后才能看到x的新值

不可重复读（nonrepeatable read）或读取偏差

读取偏差：Alice观察数据库处于不一致的状态

读未提交：可以防止脏写，但不防止脏读
读已提交：防止脏写，防止脏读
快照隔离：防止脏写，防止脏读，防止读取偏差

读己提交的实现方式：
脏写：数据库通过使用行锁（row-level lock） 来防止脏写
脏读：读锁/保留旧版本数据

快照隔离：每个事务都从数据库的一致快照（consistent snapshot） 中读取——也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。
从性能的角度来看，快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它并排维护着多个版本的对象，所以这种技术被称为多版本并发控制（MVCC, multi-version concurrentcy control）。

并发写入问题
丢失更新：读取-修改-写入序列 解决：原子写 显式锁定 自动检测丢失的更新(CAS)
写入偏差：丢失更新问题的一般化，如果两个事务读取相同的对象，然后更新其中一些对象（不同的事务可能更新不同的对象），则可能发生写入偏差。在多个事务更新同一个对象的特殊情况下，就会发生脏写或丢失更新（取决于时机）。
导致写入偏差的幻读：

  1. 一个SELECT查询找出符合条件的行，并检查是否符合一些要求。
  2. 按照第一个查询的结果，应用代码决定是否继续。（可能会继续操作，也可能中止并报错）
  3. 如果应用决定继续操作，就执行写入（插入、更新或删除），并提交事务。

这个写入的效果改变了步骤2 中的先决条件。换句话说，如果在提交写入后，重复执行一次步骤1 的SELECT查询，将会得到不同的结果。因为写入改变符合搜索条件的行集
一个事务中的写入改变另一个事务的搜索查询的结果，被称为幻读
解决：物化冲突 可序列化

可序列化（Serializability） 隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的，就好像它们没有任何并发性，连续挨个执行一样。因此数据库保证，如果事务在单独运行时正常运行，则它们在并发运行时继续保持正确 —— 换句话说，数据库可以防止所有可能的竞争条件。
实现方式：

  1. 真的串行执行
  2. 两阶段锁 2PL
  3. 乐观并发控制技术，例如可序列化的快照隔离（serializable snapshot isolation）

SSI：
事务基于一个前提（premise） 采取行动。之后当事务要提交时，原始数据可能已经改变——前提可能不再成立。
事务中的查询与写入可能存在因果依赖。为了提供可序列化的隔离级别，如果事务在过时的前提下执行操作，数据库必须能检测到这种情况，并中止事务。
数据库如何知道查询结果是否可能已经改变？有两种情况需要考虑：

  • 检测对旧MVCC对象版本的读取（读之前存在未提交的写入）
  • 检测影响先前读取的写入（读之后发生写入）

15445不同隔离级别的实现
读未提交：只使用写锁
读己提交：使用写锁，读锁，读取前加读锁，读取后立即释放
可重复读： 使用写锁，读锁，读取前加读锁，事务提交/中止时释放，使用两段锁协议

第八章：分布式系统的麻烦

邂逅相遇,网络延迟,存之为吾,无食我数

  1. 分布式系统与运行在单台计算机上的程序的不同之处：没有共享内存，只有通过可变延迟的不可靠网络传递的消息，系统可能遭受部分失效，不可靠的时钟和处理暂停。
  2. 对于真实系统的建模，具有崩溃-恢复故障（crash-recovery）的部分同步模型（partial synchronous）通常是最有用的模型。
  3. 安全性通常被非正式地定义为，没有坏事发生，而活性通常就类似：最终好事发生。
  4. 这并不是说理论上抽象的系统模型是毫无价值的，恰恰相反。它们对于将实际系统的复杂性降低到一个我们可以推理的可处理的错误是非常有帮助的，以便我们能够理解这个问题，并试图系统地解决这个问题。我们可以证明算法是正确的，通过表明它们的属性总是保持在某个系统模型中。

第九章：一致性与共识

好死不如赖活着

构建容错系统的最好方法，是找到一些带有实用保证的通用抽象，实现一次，然后让应用依赖这些保证。这与事务处理方法相同：通过使用事务，应用可以假装没有崩溃（原子性），没有其他人同时访问数据库（隔离），存储设备是完全可靠的（持久性）。即使发生崩溃，竞态条件和磁盘故障，事务抽象隐藏了这些问题，因此应用不必担心它们。

分布式系统最重要的抽象之一就是共识（consensus）：就是让所有的节点对某件事达成一致。

最终一致性：如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值。最终一致性的一个更好的名字可能是收敛（convergence），因为我们预计所有的副本最终会收敛到相同的值

事务隔离主要是为了，避免由于同时执行事务而导致的竞争状态，而分布式一致性主要关于，面对延迟和故障时，如何协调副本间的状态。

在一个线性一致的系统中，只要一个客户端成功完成写操作，所有客户端从数据库中读取数据必须能够看到刚刚写入的值。维护数据的单个副本的错觉是指，系统能保障读到的值是最近的，最新的，而不是来自陈旧的缓存或副本。换句话说，线性一致性是一个新鲜度保证（recency guarantee）。


如果读取请求与写入请求并发，则可能会返回旧值或新值

任何一个读取返回新值后，所有后续读取（在相同或其他客户端上）也必须返回新值。

线性一致性的要求是，操作标记的连线总是按时间（从左到右）向前移动，而不是向后移动。这个要求确保了我们之前讨论的新鲜性保证：一旦新的值被写入或读取，所有后续的读都会看到写入的值，直到它被再次覆盖。

可序列化（Serializability） 是事务的隔离属性，每个事务可以读写多个对象（行，文档，记录）。它确保事务的行为，与它们按照某种顺序依次执行的结果相同（每个事务在下一个事务开始之前运行完成）。这种执行顺序可以与事务实际执行的顺序不同。

线性一致性（Linearizability）是读取和写入寄存器（单个对象）的新鲜度保证。它不会将操作组合为事务，因此它也不会阻止写偏差等问题。

线性一致性的用途：锁定和领导选举，约束和唯一性保证，跨信道的时序依赖


最安全的做法是：假设采用Dynamo风格无主复制的系统不能提供线性一致性。

CAP定理

  • 如果应用需要线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求。请求必须等到网络问题解决，或直接返回错误。（无论哪种方式，服务都不可用（unavailable））。
  • 如果应用不需要线性一致性，那么某个副本即使与其他副本断开连接，也可以独立处理请求（例如多主复制）。在这种情况下，应用可以在网络问题前保持可用，但其行为不是线性一致的。

如果你想要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比。

顺序相关上下文：

  • 领导者在单主复制中的主要目的就是，在复制日志中确定写入顺序（order of write）
  • 可序列化，是关于事务表现的像按某种序列顺序（some sequential order） 执行的保证。
  • 分布式系统中使用时间戳和时钟是另一种将顺序引入无序世界的尝试

顺序有助于保持因果关系（causality），因果关系对事件施加了一种顺序：因在果之前；消息发送在消息收取之前。而且就像现实生活中一样，一件事会导致另一件事：某个节点读取了一些数据然后写入一些结果，另一个节点读取其写入的内容，并依次写入一些其他内容，等等。这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。
如果一个系统服从因果关系所规定的顺序，我们说它是因果一致（causally consistent） 的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱。
全序与偏序
全序：允许任意两个元素进行比较，所以如果有两个元素，你总是可以说出哪个更大，哪个更小。 自然数集是全序的
偏序：在某些情况下，可以说一个集合大于另一个，但在其他情况下它们是无法比较的。数学集合是偏序

在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。在因果一致的系统中，操作是偏序的：如果两个事件是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。
线性一致性强于因果一致性
线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性。线性一致性并不是保持因果性的唯一途径 。一个系统可以是因果一致的，而无需承担线性一致带来的性能折损（尤其对于CAP定理不适用的情况）。实际上在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行的最强的一致性模型。而且在网络故障时仍能保持可用。

序列号顺序
我们可以使用与因果一致（consistent with causality） 的全序来生成序列号：我们保证，如果操作 A 因果后继于操作 B，那么在这个全序中 A 在 B 前（ A 具有比 B 更小的序列号）。并行操作之间可以任意排序。这样一个全序关系捕获了所有关于因果的信息，但也施加了一个比因果性要求更为严格的顺序。

兰伯特时间戳
每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合：（计数器，节点ID）

兰伯特时间戳与物理时间时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则计数器值大者是更大的时间戳。如果计数器值相同，则节点ID越大的，时间戳越大。
使兰伯特时间戳因果一致的关键思想：每个节点和每个客户端跟踪迄今为止所见到的最大计数器值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。

版本向量与兰伯特时间戳的区别
版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳总是施行一个全序。从兰伯特时间戳的全序中，你无法分辨两个操作是并发的还是因果依赖的。 兰伯特时间戳优于版本向量的地方是，它更加紧凑。

光有时间戳排序还不够
只有在所有的操作都被收集之后，操作的全序才会出现。如果另一个节点已经产生了一些操作，但你还不知道那些操作是什么，那就无法构造所有操作最终的全序关系：来自另一个节点的未知操作可能需要被插入到全序中的不同位置。

​ 总之：为了实诸如如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定。如果你有一个创建用户名的操作，并且确定在全序中，没有任何其他节点可以在你的操作之前插入对同一用户名的声称，那么你就可以安全地宣告操作执行成功。

全序广播
全序广播通常被描述为在节点间交换消息的协议。非正式地讲，它要满足两个安全属性：
可靠交付（reliable delivery）
​有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。
全序交付（totally ordered delivery）
​消息以相同的顺序传递给每个节点。

全序广播的一个重要表现是，顺序在消息送达时被固化：如果后续的消息已经送达，节点就不允许追溯地将（先前）消息插入顺序中的较早位置。这个事实使得全序广播比时间戳命令更强。

全序广播与线性一致
全序广播等价于共识，全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息何时被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

保证线性一致性读的方法（参考raft算法）：线性一致性和 Raft
LogRead：读请求同样应用 Log，将应用后的结果返回给 Client
ReadIndex：

  • 记录当前的 commit index，称为 ReadIndex
  • 向 Follower 发起一次心跳，如果大多数节点回复了，那就能确定现在仍然是 Leader
  • 等待状态机至少应用到 ReadIndex 记录的 Log
  • 执行读请求，将结果返回给 Client

LeaseRead：
基本的思路是 Leader 取一个比 Election Timeout 小的租期，在租期不会发生选举，确保 Leader 不会变，所以可以跳过 ReadIndex 的第二步
Wait Free:
到此为止 Lease 省去了 ReadIndex 的第二步，实际能再进一步，省去第 3 步。这样的 LeaseRead 在收到请求后会立刻进行读请求，不取 commit index 也不等状态机。由于 Raft 的强 Leader 特性，在租期内的 Client 收到的 Resp 由 Leader 的状态机产生，所以只要状态机满足线性一致，那么在 Lease 内，不管何时发生读都能满足线性一致性。有一点需要注意，只有在 Leader 的状态机应用了当前 term 的第一个 Log 后才能进行 LeaseRead。因为新选举产生的 Leader，它虽然有全部 committed Log，但它的状态机可能落后于之前的 Leader，状态机应用到当前 term 的 Log 就保证了新 Leader 的状态机一定新于旧 Leader，之后肯定不会出现 stale read。

共识等价问题：

  • 线性一致性的CAS寄存器
    寄存器需要基于当前值是否等于操作给出的参数，原子地决定是否设置新值。

  • 原子事务提交

    数据库必须决定是否提交或中止分布式事务。

  • 全序广播

    消息系统必须决定传递消息的顺序。

  • 锁和租约

    当几个客户端争抢锁或租约时，由锁来决定哪个客户端成功获得锁。

  • 成员/协调服务

    给定某种故障检测器（例如超时），系统必须决定哪些节点活着，哪些节点因为会话超时需要被宣告死亡。

  • 唯一性约束

    当多个事务同时尝试使用相同的键创建冲突记录时，约束必须决定哪一个被允许，哪些因为违反约束而失败。

原子提交：
在支持跨多节点或跨多分区事务的数据库中，一个事务可能在某些节点上失败，但在其他节点上成功。如果我们想要维护事务的原子性，我们必须让所有节点对事务的结果达成一致：要么全部中止/回滚（如果出现任何错误），要么它们全部提交（如果没有出错）。这个共识的例子被称为原子提交（atomic commit） 问题


两阶段提交（two-phase commit）

  1. 当应用想要启动一个分布式事务时，它向协调者请求一个事务ID。此事务ID是全局唯一的。
  2. 应用在每个参与者上启动单节点事务，并在单节点事务上捎带上这个全局事务ID。所有的读写都是在这些单节点事务中各自完成的。如果在这个阶段出现任何问题（例如，节点崩溃或请求超时），则协调者或任何参与者都可以中止。
  3. 当应用准备提交时，协调者向所有参与者发送一个准备请求，并打上全局事务ID的标记。如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务ID的中止请求。
  4. 参与者收到准备请求时，需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写入磁盘（出现故障，电源故障，或硬盘空间不足都不能是稍后拒绝提交的理由）以及检查是否存在任何冲突或违反约束。通过向协调者回答“是”，节点承诺，只要请求，这个事务一定可以不出差错地提交。换句话说，参与者放弃了中止事务的权利，但没有实际提交。
  5. 当协调者收到所有准备请求的答复时，会就提交或中止事务作出明确的决定（只有在所有参与者投赞成票的情况下才会提交）。协调者必须把这个决定写到磁盘上的事务日志中，如果它随后就崩溃，恢复后也能知道自己所做的决定。这被称为提交点（commit point）。
  6. 一旦协调者的决定落盘，提交或放弃请求会发送给所有参与者。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。没有回头路：如果已经做出决定，不管需要多少次重试它都必须被执行。如果参与者在此期间崩溃，事务将在其恢复后提交——由于参与者投了赞成，因此恢复后它不能拒绝提交。

因此，该协议包含两个关键的“不归路”点：当参与者投票“是”时，它承诺它稍后肯定能够提交（尽管协调者可能仍然选择放弃）。一旦协调者做出决定，这一决定是不可撤销的。这些承诺保证了2PC的原子性。 （单节点原子提交将这两个事件混为一谈：将提交记录写入事务日志。）

参与者投赞成票后，协调者崩溃。数据库1不知道是否提交或中止

存疑事务持有锁，如果其他事务想要访问相同的数据，就会被阻塞。这可能会导致应用大面积进入不可用状态，直到存疑事务被解决。

容错共识
非正式地，共识意味着让几个节点就某事达成一致。共识算法可以用来确定这些互不相容（mutually incompatible） 的操作中，哪一个才是赢家。

共识问题通常形式化如下：一个或多个节点可以提议（propose）某些值，而共识算法决定（decides）采用其中的某个值。

一致同意（Uniform agreement）

​ 没有两个节点的决定不同。

完整性（Integrity）

​ 没有节点决定两次。

有效性（Validity）

​ 如果一个节点决定了值 v ，则 v 由某个节点所提议。

终止（Termination）
由所有未崩溃的节点来最终决定值。

终止属性正式形成了容错的思想。它实质上说的是，一个共识算法不能简单地永远闲坐着等死 —— 换句话说，它必须取得进展。即使部分节点出现故障，其他节点也必须达成一项决定。 终止是一种活性属性，而另外三种是安全属性。2PC不符合终止属性的要求

全序广播相当于重复进行多轮共识（每次共识决定与一次消息传递相对应）：

  • 由于一致同意属性，所有节点决定以相同的顺序传递相同的消息。
  • 由于完整性属性，消息不会重复。
  • 由于有效性属性，消息不会被损坏，也不能凭空编造。
  • 由于终止属性，消息不会丢失。

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个时代编号（epoch number）（在Paxos中称为投票编号（ballot number），视图戳复制中的视图编号（view number），以及Raft中的任期号码（term number）），并确保在每个时代中，领导者都是唯一的。

 因此，我们有两轮投票：第一次是为了选出一位领导者，第二次是对领导者的提议进行表决。关键的洞察在于，这两次投票的法定人群必须相互重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举。因此，如果在一个提案的表决过程中没有出现更高的时代编号。那么现任领导者就可以得出这样的结论：没有发生过更高时代的领导选举，因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。
 这一投票过程表面上看起来很像两阶段提交。最大的区别在于，2PC中协调者不是由选举产生的，而且2PC则要求所有参与者都投赞成票，而容错共识算法只需要多数节点的投票。而且，共识算法还定义了一个恢复过程，节点可以在选举出新的领导者之后进入一个一致的状态，确保始终能满足安全属性。这些区别正是共识算法正确性和容错性的关键。

共识的局限性

  • 节点在做出决定之前对提议进行投票的过程是一种同步复制。
  • 共识系统总是需要严格多数来运转。
  • 共识算法的动态成员扩展（dynamic membership extension）允许集群中的节点集随时间推移而变化，但是它们比静态成员算法要难理解得多。
  • 共识系统通常依靠超时来检测失效的节点。网络延迟多变的环境下会引发频繁的领导者选举
  • 有时共识算法对网络问题特别敏感。如果整个网络工作正常，但只有一条特定的网络连接一直不可靠，Raft可能会进入领导频繁二人转的局面

像ZooKeeper这样的工具为应用提供了“外包”的共识、故障检测和成员服务。

深度探索C++对象模型

本书设计的内容包括：

  • 语言语意转换（language semantics transformions）
    这包括constructor/destructor的合成和扩展，memberwise初始化，对于memberwise copy的支持，在程序代码中安插conversion operators，临时性对象以及对constructor/destructor的调用
  • 程序代码和对象模型的转换
    这包括对virtual function，virtual base class和inheritance的一般支持，new和delete运算符，class object所组成的数组，local static instances，带有非常量表达式之global object的静态初始化操作。

本书介绍C++支持面向对象程序设计的底层实现机制

第一章：关于对象
C++在布局以及存取时间的主要额外负担是由virtual引起的引起的，包括：

  • virtual function机制：用以支持一个有效率的“执行期绑定”（runtime binding）
  • virtual base class：用以实现“多次出现在继承体系中的base class”有一个单一而被共享的实例

C++对象模型
在此模型中，non-static data member被配置于每一个class object之内，static data member则存放在个别class object之外。static和non-static function member也被放在个别的class object之中。virtual function则以两个步骤支持之：
1 每一个class产生出一堆指向virtual function的指针，放在表格之中。这个表格被称为virtual table（vtbl）
2 每一个class object被安插一个指针，指向相关的virtual table。通常这个指针被称为vptr。vptr的设定和重置都由class的constructor，destructor和copy assignment运算符自动完成。每一个class所关联的type_info object（用以支持runtime type identification RTTI）也经由virtual table被指出来，通常放在表格的第一个slot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Point {
 public:
  Point(float xval);
  virtual ~Point();

  float x() const;
  static int PointCount();

 protected:
  virtual ostream &print(ostream &) const;

 private:
  float _x;
  static int _point_count;
};

对象布局实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 测试程序
#include <iostream>
using namespace std;

class Point {
 public:
  Point(int xval) : x_(xval) {}
  virtual ~Point() = default;
  int x() const { return x_; }
  static int PointCount() { return point_count_; }
  virtual void print() { cout << "test" << endl; }

 private:
  int x_;
  static int point_count_;
};
int Point::point_count_ = 1;

int main() {
  Point p1(0x11111111);
  Point p2(0x22222222);
  Point::PointCount();
  p1.x();
}

使用gdb调试

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
53
54
55
56
57
58
59
60
61
62
63
64
Breakpoint 1, main () at model.cpp:18
warning: Source file is more recent than executable.
18      int main() {
(gdb) n
19        Point p1(0x11111111);
(gdb) n
20        Point p2(0x22222222);
(gdb) n
21        Point::PointCount();
(gdb) p p1.point_count_
$1 = 1
// 静态变量地址一致
(gdb) p &p1.point_count_
$2 = (int *) 0x555555558010 <Point::point_count_>
(gdb) p &p2.point_count_
$3 = (int *) 0x555555558010 <Point::point_count_>
(gdb) p sizeof(p1)
$4 = 16
(gdb) p &p1
$5 = (Point *) 0x7fffffffdee0
(gdb) x/16xb 0x7fffffffdee0
0x7fffffffdee0: 0x58    0x7d    0x55    0x55    0x55    0x55    0x00    0x00
0x7fffffffdee8: 0x11    0x11    0x11    0x11    0x55    0x55    0x00    0x00

0x58    0x7d    0x55    0x55    0x55    0x55    0x00    0x00	// vptr
0x11    0x11    0x11    0x11	// x_
0x55    0x55    0x00    0x00	// 填充对齐？
(gdb) p p1
$6 = {_vptr.Point = 0x555555557d58 <vtable for Point+16>, x_ = 286331153, static point_count_ = 1}
// 函数地址
(gdb) p Point::Point
$7 = {void (Point * const, int)} 0x5555555552d0 <Point::Point(int)>
(gdb) p Point::~Point
$8 = {void (Point * const)} 0x55555555537a <Point::~Point()>
(gdb) p Point::x
$9 = {int (const Point * const)} 0x5555555552fa <Point::x() const>
(gdb) p Point::PointCount
$10 = {int (void)} 0x55555555530f <Point::PointCount()>
(gdb) p Point::print
Cannot reference virtual member function "print"
(gdb) p  &p1.print
$11 = (void (*)(Point * const)) 0x555555555320 <Point::print()>
(gdb) p typeid(p1)
$12 = {_vptr.type_info = 0x7ffff7fa5008 <vtable for __cxxabiv1::__class_type_info+16>, __name = 0x55555555600a <typeinfo name for Point> "5Point"}
(gdb) p sizeof(typeid(p1))
$13 = 16
(gdb) x/64xb 0x555555557d58		// vptr
0x555555557d58 <_ZTV5Point+16>: 0x5c    0x53    0x55    0x55    0x55    0x55    0x00    0x00
0x555555557d60 <_ZTV5Point+24>: 0x7a    0x53    0x55    0x55    0x55    0x55    0x00    0x00
0x555555557d68 <_ZTV5Point+32>: 0x20    0x53    0x55    0x55    0x55    0x55    0x00    0x00
0x555555557d70 <_ZTI5Point>:    0x08    0x50    0xfa    0xf7    0xff    0x7f    0x00    0x00
0x555555557d78 <_ZTI5Point+8>:  0x0a    0x60    0x55    0x55    0x55    0x55    0x00    0x00
0x555555557d80: 0x01    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x555555557d88: 0x01    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x555555557d90: 0x01    0x00    0x00    0x00    0x00    0x00    0x00    0x00
(gdb) x/64xb 0x555555557d40
0x555555557d40: 0xa0    0x51    0x55    0x55    0x55    0x55    0x00    0x00
0x555555557d48 <_ZTV5Point>:    0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x555555557d50 <_ZTV5Point+8>:  0x70    0x7d    0x55    0x55    0x55    0x55    0x00    0x00	// 恰好为_ZTI5Point地址？
0x555555557d58 <_ZTV5Point+16>: 0x5c    0x53    0x55    0x55    0x55    0x55    0x00    0x00	
0x555555557d60 <_ZTV5Point+24>: 0x7a    0x53    0x55    0x55    0x55    0x55    0x00    0x00	// ~Point
0x555555557d68 <_ZTV5Point+32>: 0x20    0x53    0x55    0x55    0x55    0x55    0x00    0x00	// print
0x555555557d70 <_ZTI5Point>:    0x08    0x50    0xfa    0xf7    0xff    0x7f    0x00    0x00	// _vptr.type_info
0x555555557d78 <_ZTI5Point+8>:  0x0a    0x60    0x55    0x55    0x55    0x55    0x00    0x00	// __name

C++ typeid运算符：获取类型信息

需要多少内存才能表现一个class object？ 一般而言要有：

  • 其nonstatic data member的总和大小
  • 加上任何由于alignment的需求而填补（padding）上去的空间（可能存在与member之间，也可能存在于集合体边界）
  • 加上为了支持virtual而内部产生的任何额外负担

指向不同类型之各指针间的差异，既不在其指针表示法不同，也不在其内容（代表一个地址）不同，而是在其所寻址出来的object类型不同。也就是说，指针类型会教导编译器如何解释某个特定地址中的内存内容及其大小。

总而言之，多态是一种威力强大的设计机制，允许你继承一个抽象的public接口之后，封装相关的类型，但付出的代价便是额外的间接性——无论是在“内存的获得”或是在“类型的决断”上。c++通过class的pointer和reference来支持多态，这种程序设计风格就称为“面向对象”。
C++也支持具体的ADT程序风格，如今被称为object-based（OB）。例如std::string，string通过public接口和一个private实现品，包括数据与算法，但不支持类型的扩充。一个OB设计可能比一个对等的OO设计速度更快而且空间更紧凑。速度快是因为所有的函数调用操作都在编译时期解析完成，对象构建起来时不需要设置virtual机制：空间紧凑则是因为每一个class object不需要负担传统上为了支持virtual机制而需要的额外负荷，但OB设计同时也缺乏弹性！

NRV测试

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
#include <bits/stdc++.h>
using namespace std;

class Test {
 public:
  Test() {  // 构造函数
    value_ = 0;
    cout << "constructor" << endl;
  }
  ~Test() = default;     // 析构函数
  Test(const Test& t) {  // 拷贝构造函数
    value_ = t.value_;
    cout << "copy constructor" << endl;
  }
  void Set(int value) { value_ = value; }  // 赋值函数

 private:
  int value_;
};

Test NrvTest(int val) {
  Test t1;
  t1.Set(val);
  return t1;
}

void CompareTest(Test& t, int val) {
  t.Set(val);
  return;
}

int main() {
  Test res1 = NrvTest(12);
  Test res2;
  CompareTest(res2, 13);
}

/*
输出：
constructor
constructor
*/

加上-fno-elide-constructors关掉返回值优化

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
#include <bits/stdc++.h>
using namespace std;

class Test {
 public:
  Test() {  // 构造函数
    value_ = 0;
    cout << "constructor" << endl;
  }
  ~Test() = default;     // 析构函数
  Test(const Test& t) {  // 拷贝构造函数
    value_ = t.value_;
    cout << "copy constructor" << endl;
  }
  void Set(int value) { value_ = value; }  // 赋值函数

 private:
  int value_;
};

Test NrvTest(int val) {
  Test t1;  // 一：构造函数
  t1.Set(val);
  return t1;  // 二：拷贝构造函数生成临时对象
}

void CompareTest(Test& t, int val) {
  t.Set(val);
  return;
}

int main() {
  Test res1 = NrvTest(12);  // 三：拷贝构造函数生成对象res1
  Test res2;
  CompareTest(res2, 13);
}

/*
输出：
constructor
copy constructor
copy constructor
constructor
*/

可以看出，NRV省去了两次拷贝构造的开销

父类构造函数调用虚函数测试

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

class Base {
 public:
  Base(int value) : value_(value) {
    cout << "Base constructor" << endl;
    this->Function();
  }
  void CallFunction() { this->Function(); }

  virtual void Function() { cout << "Base Virtual Function" << endl; }

  virtual ~Base() {}

 private:
  int value_;
};

class Derived : public Base {
 public:
  Derived(int value, int extra) : Base(value), extra_(extra) { cout << "Derived constructor" << endl; }

  void Function() override { cout << "Derived Virtual Function" << endl; }

 private:
  int extra_;
};

int main() {
  cout << endl << "Base Test" << endl;
  Base b(0x1357);
  b.Function();
  b.CallFunction();

  cout << endl << "Base Pointer Test" << endl;
  Base* p1 = &b;
  p1->Function();
  p1->CallFunction();

  cout << endl << "Derived Test" << endl;
  Derived d(0x1234, 0x5678);
  d.Function();
  d.CallFunction();

  cout << endl << "Derived Pointer Test" << endl;
  Base* p2 = &d;
  p2->Function();
  p2->CallFunction();
}

/*

Base Test
Base constructor
Base Virtual Function
Base Virtual Function
Base Virtual Function

Base Pointer Test
Base Virtual Function
Base Virtual Function

Derived Test
Base constructor
Base Virtual Function
Derived constructor
Derived Virtual Function
Derived Virtual Function

Derived Pointer Test
Derived Virtual Function
Derived Virtual Function
*/

分析结果，Base的Test不用分析，不能指望父类对象调用子类函数，只是充当对照组，梳理一下Derived的输出信息

1
2
3
4
5
6
7
8
9
10
Derived Test 
Base constructor 				// 子类对象调用父类构造函数输出
Base Virtual Function			// 父类构造函数中调用虚函数
Derived constructor				// 子类构造函数
Derived Virtual Function		// d.Function();
Derived Virtual Function		// d.CallFunction();

Derived Pointer Test
Derived Virtual Function		// p2->Function();
Derived Virtual Function		// p2->CallFunction();

解决两个问题：
① 为什么父类构造函数中调用虚函数，却不是子类实现
② 为什么使用子类对象，父类指针，非虚函数CallFunction都调用Function函数的子类实现

第二个问题比较好回答，因为CallFunction函数是以指针的形式（this）调用Function，故可以呈现多态，C++的NVI方法也利用了这一点（令用户通过public non-virtual成员函数间接调用private virtual函数）
父类的私有虚函数
私有的纯虚函数，子类能重写么？
那么为什么父类构造函数中没有采用子类的实现呢？从设计角度上说，此时子类对象还未完全构造出来，调用子类的函数实现不太安全，从实现角度上说，此时的vptr仍然指向父类的vtbl，故即使这行函数调用转换成了vptr+偏移量的形式，也选择的是父类的实现，使用gdb进行简单验证。

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
41        cout << endl << "Derived Test" << endl;
(gdb) p b
$1 = {_vptr.Base = 0x555555557d28 <vtable for Base+16>, value_ = 4951}
(gdb) s

Derived Test
42        Derived d(0x1234, 0x5678);
(gdb) s
Derived::Derived (this=0x5555555556d0 <__libc_csu_init>, value=32767, extra=-134535424) at virtual_test.cpp:22
22        Derived(int value, int extra) : Base(value), extra_(extra) { cout << "Derived constructor" << endl; }
(gdb) s
Base::Base (this=0x7ffff7db26a0 <_IO_2_1_stdout_>, value=21845) at virtual_test.cpp:6
6         Base(int value) : value_(value) {
(gdb) s
7           cout << "Base constructor" << endl;
(gdb) p this
$2 = (Base * const) 0x7fffffffdef0
(gdb) x/2xg 0x7fffffffdef0
0x7fffffffdef0: 0x0000555555557d28      0x0000555500001234
(gdb) n
Base constructor
8           this->Function();
(gdb) n
Base Virtual Function
9         }
(gdb) s
Derived constructor
main () at virtual_test.cpp:43
43        d.Function();
(gdb) x/2xg 0x7fffffffdef0
0x7fffffffdef0: 0x0000555555557d00      0x0000567800001234
(gdb) p &d
$3 = (Derived *) 0x7fffffffdef0
(gdb) x/2xg 0x7fffffffdef0
0x7fffffffdef0: 0x0000555555557d00      0x0000567800001234
(gdb) p d
$4 = {<Base> = {_vptr.Base = 0x555555557d00 <vtable for Derived+16>, value_ = 4660}, extra_ = 22136}

对输出进行简单解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Base vptr地址： 		0x555555557d28
Derived vptr地址：	0x555555557d00
父类对象构成
(gdb) p b
$1 = {_vptr.Base = 0x555555557d28 <vtable for Base+16>, value_ = 4951}
子类调用父类构造函数时对象构成
(gdb) p this
$2 = (Base * const) 0x7fffffffdef0
(gdb) x/2xg 0x7fffffffdef0
0x7fffffffdef0: 0x0000555555557d28      0x0000555500001234
子类对象构造完成
$3 = (Derived *) 0x7fffffffdef0
(gdb) x/2xg 0x7fffffffdef0
0x7fffffffdef0: 0x0000555555557d00      0x0000567800001234
(gdb) p d
$4 = {<Base> = {_vptr.Base = 0x555555557d00 <vtable for Derived+16>, value_ = 4660}, extra_ = 22136}

所以说构造函数一般负责将对象vptr指向当前类的vtbl，特别的是，父类的复制构造函数中需要设置vptr为父类的vptr，这样直接将子类对象赋值给父类对象再调用虚函数就不会错误地调用子类的函数实现了。

书中的一个例子：
对象模型如何影响程序（how the object model effects programs）

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
X foobar() {
  X xx;
  X* px = new X;
  // foo()是一个virtual function
  xx.foo();
  px->foo();

  delete px;
  return xx;
}

// 可能的内部转换结果，涉及NRV，虚函数调用，new delete操作符流程
// 虚拟C++代码
void foobar(X& _result) {
  // 构造_result
  // _result用来取代local xx
  _result.X::X();

  // 扩展 X *px = new X;
  X* px = _new(sizeof(X));
  if (px != nullptr) {
    px->X::X();
  }

  // 扩展xx.foo(),但不使用virtual机制
  // 以_result取代xx
  foo(&_result);

  // 使用virtual机制扩展px->foo()
  (*px->vtbl[2])(px);

  // 扩展delete px
  if (px != nullptr) {
    (*px->vtbl[1])(px);  // destructor
    _delete(px);
  }

  // 无须使用named return statement
  // 无须摧毁local object xx
  return;
}

杂项

无符号整数

在知乎上看到以下这段代码，过一会才反应过来想要表达的是无符号整数的问题。由于size_t为无符号整数，i>=0永远成立，故会陷入死循环。我之前懒得用 static_cast转换类型，直接在for循环中使用size_t，不过都是正序，也没啥问题。还是强烈建议少用无符号整数！

1
2
for(size_t i=vec.size()-1;i>=0;i--)
typedef unsigned long size_t

示例程序

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> vec;
  for (int i = 0; i < 10; i++) {
    vec.emplace_back(i);
  }
  printf("order\n");
  for (size_t i = 0; i < vec.size(); i++) {
    printf("0x%lx: %d\n", i, vec[i]);
  }
  printf("reverse \n");
  for (size_t i = vec.size() - 1; i >= 0; i--) {
    printf("0x%lx: %d\n", i, vec[i]);
  }
}
/*
输出：
order
0x0: 0
0x1: 1
0x2: 2
0x3: 3
0x4: 4
0x5: 5
0x6: 6
0x7: 7
0x8: 8
0x9: 9
reverse 
0x9: 9
0x8: 8
0x7: 7
0x6: 6
0x5: 5
0x4: 4
0x3: 3
0x2: 2
0x1: 1
0x0: 0
0xffffffffffffffff: 0
0xfffffffffffffffe: 81
0xfffffffffffffffd: 0
0xfffffffffffffffc: 0
0xfffffffffffffffb: 7
0xfffffffffffffffa: 6
0xfffffffffffffff9: 5
0xfffffffffffffff8: 4
0xfffffffffffffff7: 22036
0xfffffffffffffff6: -6967280
0xfffffffffffffff5: 0
0xfffffffffffffff4: 0
0xfffffffffffffff3: 0
0xfffffffffffffff2: 49
0xfffffffffffffff1: 0
0xfffffffffffffff0: 0
0xffffffffffffffef: 22036
0xffffffffffffffee: -6967280
0xffffffffffffffed: 0
0xffffffffffffffec: 0
0xffffffffffffffeb: 0
0xffffffffffffffea: 33
0xffffffffffffffe9: 0
0xffffffffffffffe8: 0
0xffffffffffffffe7: 22036
0xffffffffffffffe6: -6967280
0xffffffffffffffe5: 22036
0xffffffffffffffe4: -6893872
0xffffffffffffffe3: 0
0xffffffffffffffe2: 33
0xffffffffffffffe1: 0
0xffffffffffffffe0: 0
0xffffffffffffffdf: 0
0xffffffffffffffde: 0
0xffffffffffffffdd: 0
0xffffffffffffffdc: 0
0xffffffffffffffdb: 0
0xffffffffffffffda: 0
0xffffffffffffffd9: 0
0xffffffffffffffd8: 0
0xffffffffffffffd7: 0
0xffffffffffffffd6: 0
0xffffffffffffffd5: 0
...
0xffffffffffffb842: 0
0xffffffffffffb841: 0
0xffffffffffffb840: 0
0xffffffffffffb83f: 0
0xffffffffffffb83e: 0
0xffffffffffffb83d: 0
0xffffffffffffb83c: 65538
0xffffffffffffb83b: 0
0xffffffffffffb83a: 657
0xffffffffffffb839: 0
0xffffffffffffb838: 0
fish: “./unsigned” terminated by signal SIGSEGV (Address boundary error)
*/

大小端

大小端总是有时候记住了，过段时间又忘了，复制粘贴定义到博客里加深一下记忆。

举一个例子，比如数字0x12 34 56 78在内存中的表示形式。
1)大端模式：Big-Endian就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。

　　　　　　　　　　　　（其实大端模式才是我们直观上认为的模式，和字符串存储的模式差类似）

低地址 ——————–> 高地址
0x12 | 0x34 | 0x56 | 0x78

2)小端模式：Little-Endian就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。
低地址 ——————–> 高地址
0x78 | 0x56 | 0x34 | 0x12

一般操作系统都是小端，而通讯协议是大端的。
详解大端模式和小端模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

int main() {
  unsigned int test = 0x12345678;
  unsigned char *p = (unsigned char *)&test;
  for (int i = 0; i < 4; i++) {
    printf("addr:%p val:0x%x\n", p, (*p) & 0xff);
    p++;
  }
}
/*
输出：
addr:0x7fff95ee4e68 val:0x78
addr:0x7fff95ee4e69 val:0x56
addr:0x7fff95ee4e6a val:0x34
addr:0x7fff95ee4e6b val:0x12
*/

栈内存限制

Linux对于每个用户，系统限制其最大进程数。为提高性能，可以根据设备资源情况，设置各linux 用户的最大进程数
可以用ulimit -a 来显示当前的各种用户进程限制。

1
2
3
4
5
6
7
8
9
10
11
ulimit -a
Maximum size of core files created                           (kB, -c) 0
Maximum size of a process’s data segment                     (kB, -d) unlimited
Maximum size of files created by the shell                   (kB, -f) unlimited
Maximum size that may be locked into memory                  (kB, -l) 65536
Maximum resident set size                                    (kB, -m) unlimited
Maximum number of open file descriptors                          (-n) 1048576
Maximum stack size                                           (kB, -s) 8192
Maximum amount of cpu time in seconds                   (seconds, -t) unlimited
Maximum number of processes available to a single user           (-u) 31362
Maximum amount of virtual memory available to the shell      (kB, -v) unlimited

如果栈内存申请超过8M，则会引发段错误
示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#define SIZE 8 * (1 << 20)
int main() {
  char msg[SIZE];
  msg[0] = 0x12;
  msg[1] = 0x34;
  msg[10] = 0x56;
  msg[SIZE - 1] = 0x78;
}

直接运行
./stack
fish: “./stack” terminated by signal SIGSEGV (Address boundary error)
gdb运行
Program received signal SIGSEGV, Segmentation fault.
0x0000555555555160 in main () at stack.c:3
3       int main() {

之前在main中申请数组太大，一运行就段错误，gdb看到在main函数之前就出错了都不知道咋调试了，后面才反应过来是内存申请太大了。所以如果看到在main之前出错可以看看是不是栈内存申请问题，将SIZE改成7M就运行正常了。
相关汇编：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000000000001129 <main>:
#include <stdio.h>
#define SIZE 7 * (1 << 20)
int main() {
    1129:	f3 0f 1e fa          	endbr64 
    112d:	55                   	push   %rbp
    112e:	48 89 e5             	mov    %rsp,%rbp
    1131:	4c 8d 9c 24 00 10 90 	lea    -0x6ff000(%rsp),%r11
    1138:	ff 
    1139:	48 81 ec 00 10 00 00 	sub    $0x1000,%rsp
    1140:	48 83 0c 24 00       	orq    $0x0,(%rsp)
    1145:	4c 39 dc             	cmp    %r11,%rsp
    1148:	75 ef                	jne    1139 <main+0x10>
    114a:	48 81 ec 88 0f 00 00 	sub    $0xf88,%rsp
  char msg[SIZE];
  msg[0] = 0x12;
    1151:	c6 85 00 00 90 ff 12 	movb   $0x12,-0x700000(%rbp)
  msg[1] = 0x34;
    1158:	c6 85 01 00 90 ff 34 	movb   $0x34,-0x6fffff(%rbp)
  msg[10] = 0x56;
    115f:	c6 85 0a 00 90 ff 56 	movb   $0x56,-0x6ffff6(%rbp)
  msg[SIZE - 1] = 0x78;
    1166:	c6 45 ff 78          	movb   $0x78,-0x1(%rbp)

epoll共享内存问题

以前总是时不时看见epoll使用mmap共享内存减少拷贝的说法，但总觉得有点不对劲，直到看到以下这个知乎回答：epoll实现中共享内存问题？

陈硕的回答真是开幕雷击，故在此简单记录一下

ep_poll函数最新内核实现：https://elixir.bootlin.com/linux/latest/source/fs/eventpoll.c#L1767
相关代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
/**
 * ep_poll - Retrieves ready events, and delivers them to the caller-supplied
 *           event buffer.
 *
 * @ep: Pointer to the eventpoll context.
 * @events: Pointer to the userspace buffer where the ready events should be
 *          stored.
 * @maxevents: Size (in terms of number of events) of the caller event buffer.
 * @timeout: Maximum timeout for the ready events fetch operation, in
 *           timespec. If the timeout is zero, the function will not block,
 *           while if the @timeout ptr is NULL, the function will block
 *           until at least one event has been retrieved (or an error
 *           occurred).
 *
 * Return: the number of ready events which have been fetched, or an
 *          error code, in case of error.
 */
static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events,
		   int maxevents, struct timespec64 *timeout)
	res = ep_send_events(ep, events, maxevents)
		events = epoll_put_uevent(revents, epi->event.data, events);
// 用户数据结构定义
typedef union epoll_data
{
  void *ptr;
  int fd;
  uint32_t u32;
  uint64_t u64;
} epoll_data_t;

struct epoll_event
{
  uint32_t events;	/* Epoll events */
  epoll_data_t data;	/* User data variable */
} __EPOLL_PACKED;

// 内核数据结构定义
typedef unsigned __bitwise __poll_t;
struct epoll_event {
	__poll_t events;
	__u64 data;
} EPOLL_PACKED;


static inline struct epoll_event __user *
epoll_put_uevent(__poll_t revents, __u64 data,
		 struct epoll_event __user *uevent)
{
	if (__put_user(revents, &uevent->events) ||
	    __put_user(data, &uevent->data))
		return NULL;

	return uevent+1;
}


/**
 * __put_user - Write a simple value into user space, with less checking.
 * @x:   Value to copy to user space.
 * @ptr: Destination address, in user space.
 *
 * Context: User context only. This function may sleep if pagefaults are
 *          enabled.
 *
 * This macro copies a single simple value from kernel space to user
 * space.  It supports simple types like char and int, but not larger
 * data types like structures or arrays.
 *
 * @ptr must have pointer-to-simple-variable type, and @x must be assignable
 * to the result of dereferencing @ptr.
 *
 * Caller must check the pointer with access_ok() before calling this
 * function.
 *
 * Return: zero on success, or -EFAULT on error.
 */



/*
 * Each file descriptor added to the eventpoll interface will
 * have an entry of this type linked to the "rbr" RB tree.
 * Avoid increasing the size of this struct, there can be many thousands
 * of these on a server and we do not want this to take another cache line.
 */
struct epitem {
	union {
		/* RB tree node links this structure to the eventpoll RB tree */
		struct rb_node rbn;
		/* Used to free the struct epitem */
		struct rcu_head rcu;
	};

	/* List header used to link this structure to the eventpoll ready list */
	struct list_head rdllink;

	/*
	 * Works together "struct eventpoll"->ovflist in keeping the
	 * single linked chain of items.
	 */
	struct epitem *next;

	/* The file descriptor information this item refers to */
	struct epoll_filefd ffd;

	/* List containing poll wait queues */
	struct eppoll_entry *pwqlist;

	/* The "container" of this item */
	struct eventpoll *ep;

	/* List header used to link this item to the "struct file" items list */
	struct hlist_node fllink;

	/* wakeup_source used when EPOLLWAKEUP is set */
	struct wakeup_source __rcu *ws;

	/* The structure that describe the interested events and the source fd */
	struct epoll_event event;
};

/*
 * This structure is stored inside the "private_data" member of the file
 * structure and represents the main data structure for the eventpoll
 * interface.
 */
struct eventpoll {
	/*
	 * This mutex is used to ensure that files are not removed
	 * while epoll is using them. This is held during the event
	 * collection loop, the file cleanup path, the epoll file exit
	 * code and the ctl operations.
	 */
	struct mutex mtx;

	/* Wait queue used by sys_epoll_wait() */
	wait_queue_head_t wq;

	/* Wait queue used by file->poll() */
	wait_queue_head_t poll_wait;

	/* List of ready file descriptors */
	struct list_head rdllist;

	/* Lock which protects rdllist and ovflist */
	rwlock_t lock;

	/* RB tree root used to store monitored fd structs */
	struct rb_root_cached rbr;

	/*
	 * This is a single linked list that chains all the "struct epitem" that
	 * happened while transferring ready events to userspace w/out
	 * holding ->lock.
	 */
	struct epitem *ovflist;

	/* wakeup_source used when ep_scan_ready_list is running */
	struct wakeup_source *ws;

	/* The user that created the eventpoll descriptor */
	struct user_struct *user;

	struct file *file;

	/* used to optimize loop detection check */
	u64 gen;
	struct hlist_head refs;

#ifdef CONFIG_NET_RX_BUSY_POLL
	/* used to track busy poll napi_id */
	unsigned int napi_id;
#endif

#ifdef CONFIG_DEBUG_LOCK_ALLOC
	/* tracks wakeup nests for lockdep validation */
	u8 nests;
#endif
};

select poll epoll相关函数接口

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// select
typedef long int fd_mask;
/* fd_set for select and pselect.  */

typedef struct {
  fd_mask fds_bits[__FD_SETSIZE / __NFDBITS];
} fd_set;

/* 
Check the first NFDS descriptors each in READFDS (if not NULL) for read
readiness, in WRITEFDS (if not NULL) for write readiness, and in EXCEPTFDS
(if not NULL) for exceptional conditions.  If TIMEOUT is not NULL, time out
after waiting the interval specified therein.  Returns the number of ready
descriptors, or -1 for errors.
This function is a cancellation point and therefore not marked with
__THROW.  
*/
int select(int nfds, fd_set* readfds, fd_set* writefds, fd_set* exceptfds, struct timeval* timeout);

// poll
/* Type used for the number of file descriptors.  */
typedef unsigned long int nfds_t;
/* Data structure describing a polling request.  */
struct pollfd {
  int fd;            /* File descriptor to poll.  */
  short int events;  /* Types of events poller cares about.  */
  short int revents; /* Types of events that actually occurred.  */
};
int poll(struct pollfd *fds, nfds_t nfds, int timeout);

// epoll
/* Valid opcodes ( "op" parameter ) to issue to epoll_ctl().  */
#define EPOLL_CTL_ADD 1 /* Add a file descriptor to the interface.  */
#define EPOLL_CTL_DEL 2 /* Remove a file descriptor from the interface.  */
#define EPOLL_CTL_MOD 3 /* Change file descriptor epoll_event structure.  */

typedef union epoll_data {
  void *ptr;
  int fd;
  uint32_t u32;
  uint64_t u64;
} epoll_data_t;

struct epoll_event {
  uint32_t events;   /* Epoll events */
  epoll_data_t data; /* User data variable */
};

/* Creates an epoll instance.  Returns an fd for the new instance.
   The "size" parameter is a hint specifying the number of file
   descriptors to be associated with the new instance.  The fd
   returned by epoll_create() should be closed with close().  */
int epoll_create(int size);
/* Manipulate an epoll instance "epfd". Returns 0 in case of success,
   -1 in case of error ( the "errno" variable will contain the
   specific error code ) The "op" parameter is one of the EPOLL_CTL_*
   constants defined above. The "fd" parameter is the target of the
   operation. The "event" parameter describes which events the caller
   is interested in and any associated user data.  */
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

/* Wait for events on an epoll instance "epfd". Returns the number of
   triggered events returned in "events" buffer. Or -1 in case of
   error with the "errno" variable set to the specific error code. The
   "events" parameter is a buffer that will contain triggered
   events. The "maxevents" is the maximum number of events to be
   returned ( usually size of "events" ). The "timeout" parameter
   specifies the maximum wait time in milliseconds (-1 == infinite).

   This function is a cancellation point and therefore not marked with
   __THROW.  */
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);

图文详解 epoll 原理【Redis，Netty，Nginx实现高性能IO的核心原理】epoll 详解

存储介质访问时间对比

图片来自：简要总结计算机各种延时（寄存器、cache、内存、磁盘）

自旋锁 休眠锁 信号量 条件变量

mit6.081中关于自旋锁与休眠锁的实现

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// 自旋锁
// Mutual exclusion lock.
struct spinlock {
  uint locked;  // Is the lock held?

  // For debugging:
  char *name;       // Name of lock.
  struct cpu *cpu;  // The cpu holding the lock.
};

// Mutual exclusion spin locks.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "proc.h"
#include "defs.h"

void initlock(struct spinlock *lk, char *name) {
  lk->name = name;
  lk->locked = 0;
  lk->cpu = 0;
}

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void acquire(struct spinlock *lk) {
  push_off();                         // disable interrupts to avoid deadlock.
  if (holding(lk)) panic("acquire");  // 防止重复加锁

  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
  //   a5 = 1
  //   s1 = &lk->locked
  //   amoswap.w.aq a5, a5, (s1)
  while (__sync_lock_test_and_set(&lk->locked, 1) != 0)  // 原子交换/测试并设置（TSL），当locked为0，表示当前未有线程持有锁，则locked被设置为1，且返回值为0
    ;

  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that the critical section's memory
  // references happen strictly after the lock is acquired.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();  // 为了不让临界区代码移出临界区，使用内存屏障，告知编译器和CPU不对屏障内部的load store指令进行重排

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

// Release the lock.
void release(struct spinlock *lk) {
  if (!holding(lk)) panic("release");  // 只能释放已持有的锁

  lk->cpu = 0;

  // Tell the C compiler and the CPU to not move loads or stores
  // past this point, to ensure that all the stores in the critical
  // section are visible to other CPUs before the lock is released,
  // and that loads in the critical section occur strictly before
  // the lock is released.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Release the lock, equivalent to lk->locked = 0.
  // This code doesn't use a C assignment, since the C standard
  // implies that an assignment might be implemented with
  // multiple store instructions.
  // On RISC-V, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked);  // 原子交换/将locked设为0

  pop_off();
}

// Check whether this cpu is holding the lock.
// Interrupts must be off.
int holding(struct spinlock *lk) {
  int r;
  r = (lk->locked && lk->cpu == mycpu());
  return r;
}

// push_off/pop_off are like intr_off()/intr_on() except that they are matched:
// it takes two pop_off()s to undo two push_off()s.  Also, if interrupts
// are initially off, then push_off, pop_off leaves them off.

void push_off(void) {
  int old = intr_get();

  intr_off();
  if (mycpu()->noff == 0) mycpu()->intena = old;
  mycpu()->noff += 1;
}

void pop_off(void) {
  struct cpu *c = mycpu();
  if (intr_get()) panic("pop_off - interruptible");
  if (c->noff < 1) panic("pop_off");
  c->noff -= 1;
  if (c->noff == 0 && c->intena) intr_on();
}

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
53
54
55
56
// 休眠锁
// Long-term locks for processes
struct sleeplock {
  uint locked;         // Is the lock held?
  struct spinlock lk;  // spinlock protecting this sleep lock

  // For debugging:
  char *name;  // Name of lock.
  int pid;     // Process holding lock
};

// Sleeping locks

#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "proc.h"
#include "sleeplock.h"

void initsleeplock(struct sleeplock *lk, char *name) {
  initlock(&lk->lk, "sleep lock");
  lk->name = name;
  lk->locked = 0;
  lk->pid = 0;
}

void acquiresleep(struct sleeplock *lk) {
  acquire(&lk->lk);      // 获取自旋锁
  while (lk->locked) {   // 休眠-查询循环，避免虚假唤醒情况
    sleep(lk, &lk->lk);  // 休眠前解锁，唤醒后加锁
  }
  lk->locked = 1;
  lk->pid = myproc()->pid;
  release(&lk->lk);
}

void releasesleep(struct sleeplock *lk) {
  acquire(&lk->lk);  // 获取自旋锁
  lk->locked = 0;
  lk->pid = 0;
  wakeup(lk);  // 唤醒等待在该chan上的线程
  release(&lk->lk);
}

int holdingsleep(struct sleeplock *lk) {
  int r;

  acquire(&lk->lk);
  r = lk->locked && (lk->pid == myproc()->pid);
  release(&lk->lk);
  return r;
}

休眠与唤醒操作实现

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
// void * chan即struct sleeplock *lk
// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void sleep(void *chan, struct spinlock *lk) {
  struct proc *p = myproc();

  // Must acquire p->lock in order to
  // change p->state and then call sched.
  // Once we hold p->lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup locks p->lock),
  // so it's okay to release lk.

  acquire(&p->lock);  // DOC: sleeplock1
  release(lk);

  // Go to sleep.
  p->chan = chan;
  p->state = SLEEPING;
  // 进程1->调度器->进程2 让出CPU，交给其他进程执行
  // 调度器负责释放p->lock
  sched();
  // 进程x->调度器->进程1，CPU重新执行进程1
  // 调度器负责请求p->lock
  // Tidy up.
  p->chan = 0;

  // Reacquire original lock.
  release(&p->lock);
  acquire(lk);
}

// Wake up all processes sleeping on chan.
// Must be called without any p->lock.
void wakeup(void *chan) {
  struct proc *p;

  for (p = proc; p < &proc[NPROC]; p++) {
    if (p != myproc()) {
      acquire(&p->lock);
      if (p->state == SLEEPING && p->chan == chan) {  // 找到等待在chan的所有进程并唤醒
        p->state = RUNNABLE;
      }
      release(&p->lock);
    }
  }
}

操作系统——信号量（理解什么是信号量，信号量如何解决同步互斥问题，信号量一些注意点）
使用条件变量与锁实现信号量

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
#include <bits/stdc++.h>
using namespace std;

class Semaphore {
 public:
  Semaphore(int count) : count_(count) {}

  void Down() {
    unique_lock<mutex> lk(mu_);
    count_--;
    if (count_ < 0) {
      cv_.wait(lk);
    }
  }
  void Up() {
    unique_lock<mutex> lk(mu_);
    count_++;
    if (count_ <= 0) {
      cv_.notify_one();
    }
  }

 private:
  int count_;
  mutex mu_;
  condition_variable cv_;
};

printf %p

之前一直使用%p来打印地址，但总觉得%p会对指针进行一些特殊的操作（例如解引用），后面看到mit6.081-page tables-Print a page table，正确输出让我很疑惑
相关代码与输出如下

1
2
3
4
5
6
7
8
9
10
11
12
13
#define PTE2PA(pte) (((pte) >> 10) << 12)
pagetable_t next_pagetable = (pagetable_t)PTE2PA(pte);
printf("%d: pte %p pa %p\n", i, pte, next_pagetable);  // %p pointer 以十六进制整数方式输出指针的值

 ..0: pte 0x0000000021fdac01 pa 0x0000000087f6b000
 .. ..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
 .. .. ..0: pte 0x0000000021fdb01f pa 0x0000000087f6c000
 .. .. ..1: pte 0x0000000021fda40f pa 0x0000000087f69000
 .. .. ..2: pte 0x0000000021fda01f pa 0x0000000087f68000
 ..255: pte 0x0000000021fdb801 pa 0x0000000087f6e000
 .. ..511: pte 0x0000000021fdb401 pa 0x0000000087f6d000
 .. .. ..510: pte 0x0000000021fddc07 pa 0x0000000087f77000
 .. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

完全看不出pte与pa的数学关系，就想是不是%p做了一些特殊操作，一个是指针，一个不是指针之类的
测试程序

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
#include <stdio.h>
#define PTE2PA(pte) (((pte) >> 10) << 12)
int main() {
  int a = 123;
  int* p = &a;
  int c = 0x1234;
  int* p_c = (int*)0x12345678;
  printf("%p  %p  %p\n", a, p, 0x1234);
  printf("%p  %p  %p\n", &a, &p, 0x1234);
  printf("%p  %p\n", c, p_c);

  long pte = 0x12345678;
  long pa = PTE2PA(pte);
  printf("pte:%p  pa:%p", pte, pa);
}

/*
000000000000007B  000000000061FE08  0000000000001234
000000000061FE08  000000000061FE00  0000000000001234
0000000000001234  0000000012345678
pte:0000000012345678  pa:0000000048D15000

10010001101000101011001111000     // 低10位清零并加两个零
1001000110100010101000000000000
*/

可以看出%p除了比%x多补了几个前导零以外没啥区别，虽然十六进制看不出啥关系，但二进制很容易看出对应的数学关系

相关书籍

阅读过的计算机书籍

  • 机器学习
  • 王道考研机试指南
  • 大话存储
  • 深入浅出SSD
  • 数据密集型应用设计
  • C和指针
  • 深入理解计算机系统
  • linux设备驱动程序
  • Effective C++
  • Effective STL
  • Effective modern c++
  • linux内核设计与实现
  • 设计模式
  • 深入探索C++对象模型
  • 深入linux内核
  • GO程序设计语言
  • C专家编程
  • GO语言并发之道
  • c++沉思录

待阅读

  • C缺陷与陷阱
  • Debug Hacks中文版—深入调试的技术和工具
  • C++语言的设计与演化