PBFT 核心概念以及基于 DPoS 的实现

众做周知, PBFT 是目前能够有效对抗拜占庭问题的算法之一, 使用 PBFT 意味着就算我们的系统中有 2/3 的节点有问题, 只要有 1/3 是好的, 那这个系统就依旧能正常运作. 最近需要在 DPoS 的基础上实现 PBFT 算法, 断断续续看了很久 PBFT 的论文, 提炼出在 DPoS 中需要注意的如下一些概念, 并分析在 DPoS 中如何实现 PBFT 的一些行为.

视图

整个分布式系统随时间往前推进, 每一个节点都可能成为主节点 (出块节点). 在 PBFT 中, 成为主节点的这段时间被称为视图, 视图是整数编号的, 每当发生主节点切换, 视图编号都会增一.

在 PBFT 的描述中, 主节点会发生切换是因为之前的主节点出问题, 而在 DPoS 中, 主节点总是变化的, 所以实际上视图也总是变化的. 实际上在我们的区块链实现中没有强调视图的存在, 主节点依靠 DPoS 协议, 在所有节点中随时间依次切换, 仅此而已.

三阶段提交

这是 PBFT 最重要的部分, 三个阶段分别称作: pre-prepare, prepare, commit.

在 pre-prepare 阶段中, 主节点会给要发出的消息 (区块) 分配一个编号 (hash 以及区块高度), 然后将消息广播给其它节点, 其它节点会根据情况决定要不要接受这个 pre-prepare 消息, PBFT 论文中对 pre-prepare 消息的接受提了四个条件, 我把这四个条件搬到我们的 DPoS 实现中, 可以转化成如下几条:

  1. pre-prepare 消息 (区块) 的发起节点是当前视图的主节点
    这一点是为了避免有非法节点冒充主节点出新块. DPoS 要想避免这个问题是很容易的, 由于 DPoS 机制规定了每一个区块的出块节点是确定的, 所以节点收到 pre-prepare 消息 (区块) 的节点只需要计算一下这个区块理应谁来出, 再用理应出块节点的公钥验证一下区块中的签名就知道真假了.
  2. 在同一个视图中, 收到相同高度, 不同哈希的区块的话, 只接受第一个
    这在 DPoS 中意味着见证人节点在瞎搞, 连续出了两个块, 高度还一样, 这样的见证人应当被踢掉.
  3. 在同一个视图中, 收到相同哈希的区块的话, 只接受第一个
    这里要说一下, 在我们的实现中, 区块高度也会被算进哈希里的, 所以哈希相同的话, 高度也是相同的, 所以这种情况的出现可能是 p2p 网络消息重复导致的. Anyway, 收到重复区块的节点, 忽略后收到的就好了.

PBFT 原文四个条件中的最后一个条件是对消息编号范围的规定, 原文称为高低水位, 其思想是说, 收到的消息编号不能比之前刚收到的消息的编号大太多也不能小太多. 这点我们在引入 PBFT 之前就加入了对区块高度的验证, 收到的区块的高度一定要比我们当前最新区块高度严格大一才会接受, 所以这点不是问题.

Ok, 只要上面的条件都能够满足, 节点就会广播对此区块的 prepare 消息给其他所有节点, 注意这个过程, 是所有收到 pre-prepare 消息并且验证上述条件都 ok 的节点, 都会广播 prepare 消息给其它所有节点, 所以这个过程的消息量是 n^2, 而前面 pre-prepare 的消息量只是 n.

这样一来, 每个节点都最多能够收到其它 n-1 个节点的 prepare 消息, PBFT 规定当节点收到 2f 条 prepare 消息 (包含自己一共 2f+1, 为什么是这个数后面再说) 时, 就说明这个区块被大部分节点认可了.

然后收到了 2f 条 prepare 消息的节点往外广播 commit 消息, 这个过程的消息量也是 n^2, 当节点收到 2f 条 commit 消息后, 就写区块.

Checkpoint 和 Stable Checkpoint

PBFT 中还提到了 checkpoint 和 stable checkpoint 的概念, 对应到 DPoS 区块链中, checkpoint 就是某个区块, stable checkpoint 实际上就是最后不可逆区块.

PBFT 中的 stable checkpoint 还是要靠节点之间发消息来确认, 在 DPoS 的最后不可逆区块机制中, 我们可以在每当有新区块产生时顺着往前找, 找到最新的被 2/3 的节点确认过 (指后面跟着 2/3 的见证人生产的区块) 的区块, 将其标记为最后不可逆区块.

垃圾收集

在 PBFT 中, 凡是在 stable checkpoint 之前的记录都说明已经有至少 f+1 的好节点执行过了, 因此 stable checkpoint 之前的记录可以删除以释放空间.

但是在实际实现中, 我想不会真的有人真的删除这些记录, 至少是会把这些记录落盘. 区块链就是这样. 比特币中每个区块的交易被执行后会算出一批新的 UTXO 维护在内存中, 但是原始区块一定也是要写入磁盘的, 只要有原始区块, 节点重启就能重放这些区块, 重新生成 UTXO 集合. 在我们的 DPoS 中也是如此.

但是在我们的实现中, 也确实存在 “垃圾” 需要收集, 就是那些未收到足够认可的 pre-prepare 区块, 这些区块在发起后, 由于没有足够认可, 被后续的新区块替代, 而这些区块会一直保存在各个节点的内存中等待着足够的 prepare/commit 消息. 这是需要被清理的.

为何 prepare 阶段需要收到 2f 条消息, 以及为何还需要 commit 阶段

PBFT 规定当节点收到 2f 条 prepare 消息 (包含自己一共 2f+1) 时, 就说明这个区块被大部分节点认可了, 为什么是 2f 条呢?

因为总共 3f+1 个节点中, 最多只有 f 个恶意节点, f 个故障节点, 如果我收到了 2f 条 prepare 消息, 那就说明这 2f 条消息中一定有至少 f 条消息是好节点发来的. 这里如果 “我” 也是恶意节点, 那 2f 中的好节点一定大于 f, 如果 “我” 是好节点, 2f 里的好节点加上我一定还是大于 f.

不论如何, 收到 2f 条 prepare 消息就说明整个系统中至少 f+1 数量的好节点都认可了这个区块.

所以现在这个区块是一个可写状态, 但是还不能写, 因为我收到了 2f 条 prepare 消息并不代表其它节点都收到了 2f 条 prepare, 虽然知道现在系统中有至少 f+1 的好节点认可了区块, 但是其他好节点可能会因为网络问题 (PBFT 基于异步网络, 不能保证有限时间内收到消息) 没有收够 2f 条 prepare, 万一只有我收够了 2f 然后我写区块了, 那岂不是只有我分叉了?

所以 PBFT 的做法是, 所有收到 2f 条 prepare 消息的节点, 继续向外广播 commit 消息, 然后再当节点收到 2f 条 commit 消息时, 再正式写区块. 和 2f 条 prepare 同样的道理, 当我收到 2f 条 commit 时, 就说明整个系统中至少 f+1 数量的好节点都收到了 2f 条 prepare 消息, 也就是至少 f+1 数量的好节点都准备要写这个区块了, 那我当然也可以放心大胆的写这个区块了.

然而, 这里实际上还存在问题, 那就是 commit 消息也未必被至少 f+1 个好节点收到 (异步网络问题), 可能只有少部分节点收到了 2f 条 commit 消息, 并执行了 commit 动作. 这种情况 PBFT 里有措施应对, 我没有仔细看, 但是在我们的设计中当然也有措施应对的, 其实这个情况无非就是导致两种后果:

  1. 未执行 commit 的节点成为下一个出块节点, 他会发起新的 pre-prepare, 前面少部分执行了 commit 的节点会拒绝这个 pre-prepare, 但是新的 pre-prepare 依然可能会进入 commit 阶段被 2f 以上的节点 commit. 结果就是产生分叉, 然后根据最长链准则决出胜负.
  2. 执行了 commit 的节点成为下一个出块节点, 在它发起新的 pre-prepare 后, 其他节点会过来请求同步区块信息, 不会产生分叉, 正常进行.

多线程同步与锁的本质

为什么需要锁

当多个线程共享同一块内存区域时, 我们需要保证任何一个线程在访问这块内存时, 所看到的内容是稳定的. 如果所有的线程对这块内存的访问都只是读取, 那么我们就不需要采取额外措施. 但哪怕其中有一个线程会修改这块内存, 那我们就要对这些线程进行同步.

之所以要这么做是因为修改内存的操作往往都不是原子操作, 而是分成多个时钟周期, 一个线程对内存的操作可能在任何一个周期被另一个线程打断, 从而导致这块内存的内容不稳定.

所谓线程同步, 也就是说当好几个线程同时想要操作某块内存时, 它们必须按照顺序一个一个来, 只有上一个线程对这块内存操作完毕了, 下一个线程才能接着对这块内存进行操作.

如何实现线程同步呢? 就是加锁.

对谁加锁

虽然我们都用过锁, 但有没有考虑过这个锁本质上是给谁加呢?

显然, 是对这块内存加锁, 好让某个线程操作这块内存时, 其他线程进不来.

锁的本质

那么这把锁得是什么形式的呢? 既然要锁内存, 是不是在内存上有这么一个物理元器件? 不得不说, 这是一种方法, 但实际并不是这么实现的. 但是硬件层面确实要提供一种原子的访问内存的指令, 别急, 我们一步一步分析.

假设两个线程都要去操作内存 A, 我们现在仅从软件角度考虑, 如果要实现这把锁, 我们可以选择另一块内存 L 来标记是否能够操作 A, 也就是: 线程操作 A 前, 要先取出 L 的值, 如果是 1 的话就将其改成 0, 然后操作 A, 访问完 A 就再将 L 改成 1; 如果 L 是 0 的话, 就说明别的线程正在操作 A, 那我就等着直到别人释放.

你应该注意到了, L 既然也是一块内存, 那修改 L 不也是会分多个时钟周期吗? 线程一取 L 的值进寄存器, 发现是 1, 于是在寄存器上改为 0, 然后正准备要写回去, 结果线程二打断了它, 也取了 L 的值发现是 1, 于是后面不就又两个线程同时访问 A 内存了吗? 这锁不管用啊!

别急, 虽然都是内存, 但是对 L 和 A 的操作还真是不一样的, 我们会采取手段使得对 L 的操作是原子的. 其中最简单直接的手段就是 — 关闭时钟中断 (后面简称为关中断. 或者是挂起调度器, 效果类似), 这可是很不得了的事情, 一旦执行了这个操作, 其它的线程可就捞不着执行了, 这样对 L 的操作当然就不会被打断了, 当然改完 L 之后一定要开时钟中断 (后面简称为开中断) 恢复调度器的.

说到挂起调度器, 多解释一下. 我们知道处理器有很多中断, 其中时钟中断是源自晶振的非常规律的周期性中断, 操作系统内核为了能够支持多任务, 需要利用这一点在每个时钟中断到来之时, 切换 CPU 上下文, 执行另一个任务. 我们可以认为, 捕获时钟中断, 并执行任务切换工作的这段代码就是调度器, 而挂起调度器什么呢? 意味着时钟中断将成为一个摆设, 除了挂起调度器的那个任务, 所有其他任务都将再也得不到执行. 所以, 挂起调度器是一个影响巨大的操作, 负责挂起调度器的那个任务, 一定, 必须, 绝对要负责随后恢复调度器! 挂起调度器实际上是触及到了操作系统内核的工作, 不过还没有介入到处理器这一层, 时钟中断实际上还在不断的产生, ISR (中断处理函数) 也会被调用, 只是操作系统内核不再去处理了罢了. 比这更进一步的就是直接关闭时钟中断, 这样一来中断直接不再产生. 关于这块内容, 可以参考回顾 FreeRTOS 的源代码. 从应用程序层面看, 挂起调度器这个操作已经足够危险了, 所以在 Linux 这样的操作系统中, 应用程序是没有权限做这个事情的, 必须要通过系统调用委托内核去做才行.

我知道你可能会想, 既然还有关中断这一招, 那还折腾出个 L 干什么? 直接在访问 A 的时候就关中断, 访问完了 A 就再恢复中断不就行了吗?

这个是不行的, L 只是存个标记, 不到 1 个字节就够, A 这块内存大小是不一定的, 可能大到好几兆, 假设访问一个字节是 1us, 那么访问一兆字节我们不妨认为需要 10^6us = 1s. 如果每个线程访问 A 都要把可能原本也没有打算访问 A 的, 无辜躺枪的其它线程全都挂起 1s, 这就没有王法了.

为什么需要原子访存指令

然而, 即便我们只是在访问 1 字节的 L 时关中断, 这种方式仍旧是存在很多问题的, 尤其是在多核处理器的情况下还是无效的! 因为关中断对单个 CPU 关中断, 但是线程可以切换到另一个 CPU 上执行, 从而无视前一个 CPU 的关中断.

除此之外关中断是权限极高的操作, 需要切换到 CPU 的特权模式进行, 这 linux 系统中这当然是要从用户态切换到内核态的; 另外关中断存在很大的风险, 就是关中断的线程死循环或者直接 crash 了, 这样其他线程就永远得不到执行了 — 除非重启机器; 再次, 关中断就意味着可能会丢失中断, 如果线程关中断时间太长, 会破坏线程调度机制, 这点上面我们已经看到了; 最后, 关中断这个操作效率上也是很低的.

所以用关中断来实现锁是不可取的, 实际上只有操作系统在执行关键任务时才会使用关中断的手段, 而且会严格控制关闭时间.

既然又不能关中断, 我们又想原子访存, 那怎么办? 那就是需要硬件层面提供一种原子访存指令了.

CPU 架构提供的原子访存指令典型的有如下这些, 这些指令也是实现所谓 “无锁编程” 的关键:

• Test-And-Set
• Compare-And-Swap
• Load-Linked and Store-Conditional
• Fetch-And-Add
• etc…

具体怎么用这些指令实现锁, 就是另一个话题了.

结语

Ok, 到此为止, 我们阐述了锁的本质, 实际上就是对一块内存进行原子访问, 而实现锁的这块内存, 它的名字就叫做 — 互斥量.

参考

1. 强烈推荐此书, 神作: http://pages.cs.wisc.edu/~remzi/OSTEP/ 第 28 章.
2. https://stackoverflow.com/questions/1485924/how-are-mutexes-implemented
3. https://en.wikipedia.org/wiki/Test-and-set
4. https://stackoverflow.com/questions/31978324/what-exactly-is-stdatomic

对协程的一点认识

协程的调度

我们知道线程是 CPU 的基本调度单元,线程调度靠的是时钟中断.

协程是执行于线程之内的更细粒度的执行单元,他的调度无法依赖时钟中断,而是要靠一个用户态的调度器,这个调度器可以是抢占式或非抢占式,抢占式调度器需要语言的运行时支持,据我所知只有 erlang 实现了协程的抢占式调度。大部分的协程实现都是非抢占式调度,非抢占式调度实际上是依靠协程之间相互让权 (yield) 来得到执行。

在非抢占式协程下,不存在协程同步问题。而在抢占式协程下则语言我们也考虑数据竞争,协程同步问题。

协程的好处

协程的一个典型应用是用在生产者 – 消费者问题中. 我们知道生产者 – 消费者问题也可以用多线程解决, 生产者线程和消费者线程共享一个上了锁的消息队列, 靠内核调度这两个线程执行来完成生产和消费过程, 然而这里有几个不足之处:

  • 靠内核调度线程, 存在线程切换开销
  • 消息队列加锁, 存在锁竞争和线程同步问题
  • 内核调度线程的时机不确定, 如果在调度消费者时队列中没有消息, 消费者只能什么也不干就退出, 白白浪费了一次调度而如果用协程解决的话, 就不存在上述问题. 首先生产者和消费者协程位于统一线程里, 不存在线程切换的开销; 其次由于是单线程, 无需加锁, 也就不存在锁竞争问题; 最后由于协程之间的执行是靠主动让权 (yield), 我们可以在实现的时候仅当队列不空时才让权给消费者, 同理消费者仅当队列不满时才让权给生产者.

另外使用协程还有一个好处就是能够以看似同步的方式写异步的代码.

协程实现

要实现协程就需要自己在线程中维护第二层栈空间 (第一层是线程自己的栈空间), 因为线程的切换内核会为我们将当前上下文 (主要是各个寄存器的值) 保存在线程栈空间中, 现在由于线程需要自己调度协程, 所以线程需要为每个协程维护栈空间, 好在协程切换时保存协程的上下文.

这里需要线程能够获去到当前执行上下文, 很多操作系统内核会提供相应的系统调用, 实现方式其实也很简单就是写一段内嵌的汇编获取各个寄存器的值.

在 C 标准库中, setjmp/longjmp 帮我们完成了这个任务. 关于其 setjmp/longjmp 的实现原理, 这篇文章 (google 搜索第一位) 讲的很清楚: https://www.embecosm.com/appnotes/ean9/html/ch04s01s02.html

在 C/C++ 中实现协程当然也可以不借助 setjmp/longjmp 而自己去实现上下文的获取和维护, 有很多库都提供了他们自己的协程实现. 比较知名的有:

  • 天才帅哥程序员 adam 的 protothreads: http://dunkels.com/adam/pt/
  • putty 作者, 大神 simon 的 stack-less 实现: https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
  • 借助 setjmp/longjmp 的实现: https://fanf.livejournal.com/105413.html

IO 阻塞问题

由于协程实际上就是不同的代码片段在同一个线程中交替执行 (这也被称作协作执行), 有一个协程因 IO 阻塞, 整个线程也就阻塞了, 其它协程也捞不着执行.

为了避免这个问题, 有些协程实现会 hook 所有的 IO 系统调用, 转化为非阻塞的, 然后协程调度器集中 select.

生成器

很多语言现在都支持生成器, 它们一般都是用关键字 yield 让一个方法变成生成器. 生成器其实是协程的一种特殊形式, 它被实现为在让权 (yield) 的时候总是让权给调用自己的位置, 而不是像自己写协程那样可以随便让权给任意位置.

使用生成器的好处, 一个是生成器为延迟计算提供了支持, 延迟计算就是指需要的时候才提供结果, 而不是事先提供好一堆结果, 这在大数据量处理的情境下可以节省大量内存. 另外就是使用生成器的代码一般来说能更简洁优雅, 提高代码可读性.

Continuation

(TBD…)

参考

  • https://en.wikipedia.org/wiki/Coroutine
  • libgo 作者对 libgo 的设计以及整个协程发展史做了一个介绍: https://my.oschina.net/yyzybb/blog/1817226#h1_1

区块链设计中的几个考量

关于区块存储

因为有区块浏览器这样的东西存在,
所以区块链的存取结构应当能够方便的从头遍历到尾, 同时也要能够从尾遍历到头.  => 双向链表

当收到其它节点传来的新区块时,
需要知道此区块的前一区块是否存在 (存在就 ok; 不存在的话可能本节点区块数据太旧, 触发从其他节点同步, 也可能是接收到的区块作假.
总之这种情况下不要接受区块, 如果确实是自己区块太旧, 从其他节点同步数据的过程也会将刚刚自己没有接受的块同步过来的, 不必担心块丢了.)  
=>  平衡二叉树 (avl 或者红黑树)

当用区块哈希而不是区块高度
(高度不唯一, 做不了) 来作为区块标识以后, 便不适合用平衡二叉树了, 因为平衡二叉树存区块的话, 要求 key 能够方便的比较大小,
然而区块的哈希并不是方便比较大小的类型. 这种情况下更适合用哈希表存区块.

但是前面也说了,
我们仍然要求区块的存储是按照高度有序的, 因为区块浏览器, 新加入的节点都需要能够从最旧区块同步到最新的区块.

那么问题来了,
现在我们既想要能够根据区块哈希块查找到区块, 又想能够根据区块高度快速遍历区块, 然而不幸的是, stl 里的容器们要么是只适合查找, 要么只适合排序,
没有同时满足两个的, 所以搁以前我们八成会用两个数据结构同时存区块来达到目的, 比如 std::unordered_map 和 std::map,
但这样增删都要同时改两个地方, 很不方便, 还多占空间.

现在不同了, boost 提供了一种 multi index 结构, 能够满足我们多维度对数据查询的需求 (暂不考虑持久化). 关于 multi index 这里介绍的很好, https://theboostcpplibraries.com/boost.multiindex

为什么需要区块哈希

区块是需要唯一标识的,
因为很多节点在同时生产区块, 仅靠区块高度是无法区分开它们的, 两个不同节点生产的区块可能位于同一高度, 这时候应当选用哪个区块,
就需要根据区块的唯一标识确定了.

区块的唯一标识可以用
sha256 哈希来计算.

关于 genesis time

我最初实现的代码中,
genesis_time_ 是在程序启动的时候被赋值的, 这是为了测试方便, 生产环境下这种方式不好. 一般来讲, 公链应当是好些个节点约定好一个未来的时间,
写死在代码里 (或者写在共同约定的配置里), 然后启动节点, 程序中会有逻辑判断是否到达了设定的时间, 一旦到达, 就开始出块.

这个 genesis
time 可以直接作为创世区块的时间戳, 比特币就是这样的.

关于消息同步

消息同步是 p2p
网络中的重要问题. 早期的 p2p 网络是真正的 “各个节点都平等”, 也就是我们所说的非结构 p2p 网络,
那个时候消息同步的典型的方法就是洪泛算法, 然而洪泛算法的问题也是众所周知的 — 网络风暴. 后来的 p2p 网络趋于向结构化发展, 比如 DHT,
归根结底就是掺杂了 “中心” 在里面, 以 “中心” 解决消息同步问题.

我希望实现一个非结构化的 p2p 网络, 真正实现各节点平等 (比特币就是如此). 有关非结构化 p2p 网络的消息同步已经做过了很多努力:

  • ttl
  • 邻居表

TODO:
贴中内外相关论文

关于最长链准则的几种情况

假设有 a, b, c
三个见证人轮流出块, 他们在出块的过程中可能会碰到如下的一些窘境.

首先是最简单的情况:

a, b, c
第一轮出块很完美, 第二轮开始 a 基于 c 出块, 依然正常. 但是 b 可能恰好 c 和 a 的块他都没收到, 也可能是它自己确实是坏人,
总之这第二轮它的块指向了自己在第一轮出的块. 接下来 c 出块时 (假设 c 正常收到了所有消息), 他看到的就是图上这番景象. 那么它出块应当基于 a
区块还是 b 区块呢? 根据最长链准则, 显然它应当基于 a 区块出.

这里我们讨论一个细节,
就是 c 怎么判断它看到的 a 和 b 谁的高度比较高. 分别从 a, b 往前推到头来计数肯定是很慢的, 所以在我们的实现中高度信息也会写到区块中.
那么问题又来了, 如果高度写到区块里, 那 b 在第二轮出块的时候把自己的块高度写的比较大不就行了吗? 当然是不行的, 在我们的实现中,
见证人收到每个块是都会验证前一个块在不在, 以及验证前一个块的高度是不是只比收到的块小 1, 如果不是的话, 块会被拒绝.

上面说的是最基本的情况,
下面是一个相对复杂一点的情况, 就是当轮到某个节点出块时, 它发现当前有两个块高度一样, 它不知道自己的块应该指向这两个块中的哪个.

这个情况的产生可能是由于
c 没有收到 b 的区块, 于是在 c 出块时 c 看到的只有 a 区块, 于是就继续在 a 后面出, 而 a 是成功收到了 b 和 c 的区块的. 于是再到
a 出块时, a 就会看到 b, c 高度都是 2, 并且都指向自己第一次出的块.

这个窘境怎么解呢? 我们规定, 但出现两个长度相同的链时, 见证人应当基于较早 (可以比较两个块的时间戳,
或者比较两个块出块人在见证人列表中的先后次序) 接收到的块出块. 这里显然 b 是较早接收到的块, 于是 a 这次出块应当基于 b 区块出.

DPoS 核心概念

本文基于 BM 的唯二的两篇阐述 DPoS 机制的文章, 第一篇文章是 BM 首次提出 DPoS 共识机制, 第二篇是 BM 后来对 DPoS
机制补充的白皮书. 两篇文章的链接见文末.

最近精读了这两篇文章, 从中提炼出了以下我认为是最核心的内容.

见证人选举与调度

DPoS
里最重要的两个部分就是见证人的选举以及调度出块.

见证人的选举靠持币人的投票,
并且是一币一票的规则, 持币量有多少, 投票权重就多大. 但我觉得这不好, 权重不应当随持币量而无节制的增大.

投票选举是 DPoS
与其它共识机制最大的不同点, DPoS 高度依赖投票机制来剔除不好的见证人, 从来维持链条运行在一个健康稳定的状态. 反观比特币等其它共识,
在发生节点作恶的情况时, 所能采取的措施就捉襟见肘了.

调度这块也是与比特币有着很大的不同,
比特币中是竞争出块, 而在 DPoS 中块由谁出则是被安排的明明白白. 在一个任期内经过选举选出一批见证人, 然后这批见证人就公平的轮流出块了,
任期的长短是可以被协商的. 在任何时候, 持币人都可以重新投票, 下一个任期会根据最新票数重新选举一批见证人. 在最初的 DPoS 机制中,
当这批见证人轮流出完一轮块之后, 他们的顺序还会被打乱, 不过在 EOS 中, 这个规则已经取消了, 后面会说到.

最长链准则 (一致性保证)

和比特币一样, DPoS
里见证人出块也遵守最长链准则, 这是所有节点的基本共识, 是一种弱一致性策略.

第二篇文章的前半部分讨论了几种可能的分叉情况,
比如消息延迟, 网络分区, 甚至是存在少量作恶节点等, 并说明了在最长链规则下这些问题会迎刃而解. 但这些基本上都是最长链准则所解决的, 这在比特币时代就是
work 的, 并不是 DPoS 的创新点. 虽然不是 DPoS 的创新, 但 DPoS 却确实改进了这个准则, 在第一篇文章里有这么一句话:

  • Because all witnesses
    are elected, highly accountable, and granted dedicated time slots to
    produce blocks, there is rarely any situation where two competing chains
    can exist. From time to time, network latency will prevent one witness
    from receiving the prior block in time. If this happens, the next witness
    will resolve the issue by building on whichever block they received first.

不像比特币的矿工可以随意加入退出,
DPoS 的见证人都是投票选出来的, 都是可追责的, 每个见证人都有他应该出块的时间点, 所以相比比特币, 显然 DPoS 的最长链更稳固一些.
当然这也是以牺牲了一些去中心为代价的.

另外, 原本 DPoS
中每轮出块见证人都会打乱顺序, 用第二篇文章的原话来说其目的如下:

  • This randomization
    ensures that block producer B doesn’t always ignore block producer A and
    that anytime there are multiple forks of identical producer counts that
    ties are eventually broken.

一方面是防止一些节点总是故意的忽略它前面节点的区块,
另外就是减小两个相同长度的分叉链存在的时间. 后来在 EOS 里取消了这一规则, 可能是因为 EOS 的社区监督太强,
存在故意忽略区块的或者故意分叉的节点的话一定会被投票下去, 所以这个规则显得没有必要了, 当然这使得整个链条的出块更清晰更有可预见性, 是好事情.

参与度与最新不可逆区块

DPoS 中存在参与度
(participation rate) 的概念, 这是什么概念? 第一篇文章给出了定义:

  • The participation rate is calculated by comparing the
    expected number of blocks produced vs the actual number of blocks
    produced.

基于参与度的概念,
DPoS 又定义了一个最新不可逆区块 (Last Irreversible Block) 的概念: 当某个区块已经被 2/3 的见证人认可 (意味着这个区块后跟着另外 2/3 的见证人出的块),
这个块就会成为最新不可逆区块.

LIB 的思想和比特币的
“6 次确认安全” 是一样的, 但是我认为相对于比特币的 6 次确认, DPoS 的 LIB 确实有所加强, 具体体现在这两点:

  1. 比特币的 6
    次确认是大众意识, 而 DPoS 中的 LIB 是写到代码里了, 如果一个新块的高度在 LIB 甚至之前, 这个块会被代码拒绝.
    相反比特币的代码中没有这个限制逻辑, 只要你算力够, 从第 1 个块开始重新出一条链都可以, 如果能出到现今比特币的区块高度,
    现有的所有比特币节点都会转到你的链上来.
  2. 由于 DPoS 中的出块节点的身份是可鉴别的, LIB
    机制保证了真的是有 2/3 的不同节点确认了 LIB 块. 相反在比特币中, 6 次确认可能是同一个节点确认的.

这两点使得在交易安全性方面
DPoS 比比特币更强一些. 因为在网络分区的情况下, 即便有 6 次确认, 也保证不了在分区消失后你看到的 6 个区块会被作为主链保留,
但是一般这种情况下我们就认为后交易是安全的了. 而在 LIB 的机制下, 如果发生了网络分区, 整条链的参与度会处在一个低水平,
这种情况下我们能够很明确我们的交易是不安全的.

这对于抵御双花攻击也是不错的改进.

TaPoS

Transactions
as Proof of Stake, 是在交易中包含最近的某个区块的哈希,
如果交易所包含的某区块的哈希不存在, 那么这次交易也会被作废. 这一措施可以看作是对 LIB 或者 6 次确认的安全性的补充, 而且这个措施是发生在用户端的.

假设有这么一个场景,
小明和小红约定了要交换一些 BTS 和 STEEM, 小红已经把 BTS 转给了小明, 这一交易被打包进了 a 区块,
然而由于网络分区或者见证人下线等问题导致当前整个链处于一个低参与度的状态, a 区块一直得不到 2/3 确认. 小明可以转 STEEM 给小红,
但是又怕网络稳定后 a 区块被废弃, 怎么办呢? 解决方法就是小明在交易中附带上 a 区块的哈希, 最终可能会有这么几个结果:

  1. 网络恢复稳定,
    小明的交易被打包进新区块, 但是验证 a 区块已经不在了, 小明的交易无效
  2. 网络恢复稳定, 小明的交易被打包进新区块, 验证 a 区块存在,
    交易达成
  3. 小明的交易被打包进新区块 c, 但是网络依然不稳定.
    后来网络稳定后 a, c 区块都存在, 交易达成
  4. 小明的交易被打包进新区块 c, 但是网络依然不稳定.
    后来网络稳定后 a 区块存在, c 不存在, 小明交易回退
  5. 小明的交易被打包进新区块 c, 但是网络依然不稳定.
    后来网络稳定后 a, c 都不存在, 小明交易回退

注意在后三种情况中,
不存在网络稳定后, a 不存在 c 存在的情况, 因为 c 里面包含引用 a 的交易.

总之可以看到, 有了
TaPoS 的保证, 小明肯定是不会有损失的.

另外 TaPoS
额外的好处就是, 用户在发起交易的同时相当于也对区块做了确认, 这使得链条更稳固.

参考

  1. https://bitshares.org/technology/delegated-proof-of-stake-consensus/
  2. https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper

主流挖矿算法介绍

挖矿实际上就是在算哈希,哈希者,摘要也。下文介绍的算法基本上是对抗 ASIC 的发展史.

SHA256

CPU 型, non ASIC  resistant

Scrypt

Scrypt 大量使用内存, 起初号称 GPU resistant, 结果失败了, 于是又号称 ASIC resistant, 结果还是失败了 因为早期内存价格高, 而现在内存价格下降, 厂商经过努力也研发出了能够 cover 住成本的 ASIC 矿机.

但 Scrypt 在 ASIC 对抗上做的努力也不是没有效果, 根据 WhatToMine 显示, 蚂蚁的比特币矿机算力可达到 14T/s, 而同期蚂蚁的 Scrypt 矿机算力才 500M/s.

Ethash

以太坊的哈希算法, 基于 Dagger-Hashimoto 改造. 内存型,并且所需内存是周期性增长的。目前尚未被 ASIC 矿机贡献。

首先 Ethash 要求矿工从最后几个区块里随机取几个交易算出来. 由于以太坊的交易可能包含智能合约, 智能合约中的运算可能是各种类型, 要计算各种类型的计算这是 CPU 的工作, 这就使得 ASIC 无用武之地.

其次, 白皮书里没说的一点是 Ethash 需要内存一定要快, ASIC 需要外挂 DRAM, 而 DRAM 的速度是完全比不上显卡里的 SRAM 的.

这两点正中 ASIC 要害, 从 whattomine.com 来看 Ethash 目前还是要用显卡挖.

但是前段时间也确实爆出了比特大陆要推 E3 以太坊矿机,参数都出来了,从暴露的参数来看,E3 矿机配备了 72G 大的 DDR 内存,相比比特币矿机 S9 只有 512M 内存,真是鲜明对比。

Equihash

Equihash 是 Zcash 采用的哈希算法,后来也被 ZenCash,BitcoinGold 所采用。

Equihash 也是内存型算法,其抵抗 ASIC 的关键是找到两个合适的常数来使得算法耗内存最大,一般所说的 Equihash 算法都是指这两个常数为 <200,9> 时的 Equihash 算法。

2018 年 4 月, 比特大陆推出 Z9 mini 矿机针对 Equihash 算法。

2018 年 6 月,BitcoinGold 发现了 Equihash 算法的另一对常数 <144,5> 能够耗更多的内存: https://forum.bitcoingold.org/t/our-new-equihash-equihash-btg/1512, 这篇文章也深入介绍了 ASIC 的短板,值得一看

Zhash

Zhash 是基于 Equihash 的强化版,由 bitcoinz 项目开发引入(待确认)

CryptoNight

特点是依赖 CPU 三级缓存,L3 缓存是 ASIC 和显卡所不配备的装置。 所以 CryptoNight 不但防 ASIC,还防显卡。

然而,2018 年 3 月, 比特大陆推出 X3 矿机针对 CryptoNight 算法。为此,门罗币 (XMR)还特意进行了硬分叉来对抗 X3 矿机,打了漂亮的一仗。灰头土脸的矿霸们为了矿机不打水漂,继续在老的门罗币上挖,并改名叫 XMC。

X11, X13, X15, X17 等

当 Scrypt 也被矿机攻陷, 达世币带着 X11 就出来了. X11 是 11 种算法串联计算, 上一个算法的输出作为下一个算法的输入, ASIC 上要实现这个逻辑要花一段时间.

X11 的 11 个算法是: blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo, 这 11 个都是 SHA3 家族算法 (bitcoin 出现时 SHA3 还未问世, 所以用的是 SHA2 家族的 SHA256 算法). 代码在 https://github.com/dashpay/dash_hash/blob/master/dash.c.

但 X11 最终也被矿机攻陷. 2017 年 8 月, 比特大陆发布蚂蚁 D3 矿机, 算力可达 34G/s.

X16R

RavenCoin 提出的算法. 不仅仅比 X11 多了几个算法, 这些个算法的次序还是可以改变的, 使用前一个区块的哈希值决定本区块的算法次序. 这使的再次在一段时间内不会出现 ASIC 矿机.

有句话这样说:

POW机制必然会导致中心化,专业程度越高,获得的市场份额就越多。所有的POW算法都无法阻挡ASIC矿机的出现,最多只能拖延一时。你可以用 Scrypt 算法来阻挡 SHA-256 的矿机,你可以用 X11 算法来阻挡 Scrypt 算法的矿机,顶多只能做到这样了。只要币价足够高,一定会导致ASIC矿机的出现。

参考

  1. https://bitcoin.stackexchange.com/questions/49199/how-is-scrypt-asic-resistant
  2. 关于 Ethash 抵抗 ASIC 属性分析的很好. https://ethereum.stackexchange.com/questions/16811/is-ethereum-asic-resistant
  3. 深度分析:比特大陆入局以太坊矿机将给行业带来怎样的影响? https://36kr.com/p/5127311.html
  4. 以太坊社区针对以太坊矿机的讨论,V 神认为这件事不是太大的威胁:https://cryptoslate.com/vitalik-buterin-ethash-asics-ethereum/
  5. CryptoNight算法沦陷,ASIC矿机即将上市,XMR矿工告急? https://zhuanlan.zhihu.com/p/34632126
  6. XMR顺利硬分叉,ASIC矿机出局,门罗社区保卫战胜利 https://mp.weixin.qq.com/s?__biz=MzUyNzMzMjE5MA==&mid=2247485689&idx=1&sn=e9d352a5ed86471e45299d518e8d23f9&chksm=fa006ec8cd77e7de2d0e59a99ea04cafaab67a8ad9cf376311e4e86abf46fcf41e1ed972303d&scene=21#wechat_redirect
  7. X 系列算法组成: https://getpimp.org/what-are-all-these-x11-x13-x15-algorithms-made-of/
  8. D3 矿机的出现毁了达世币 http://www.qukuaibiji.com/dash-kuangji.html, 看完就知道为什么各个币都要对抗 ASIC 矿机了

Docker 简明指南

一站式文档

docs.docker.com

架构

docker 是 C/S 架构, 一个 docker daemon 运行在后台, 我们直接使用的是 docker 的前端程序. 运行前端程序时, 前端程序会将相关的指令发给 daemon, daemon 解析执行再返回给前端.

镜像与容器

An image is a filesystem and parameters to use at runtime. It doesn’t have state and never changes. A container is a running instance of an image. When you ran the command, Docker Engine:

- checked to see if you had the hello-world software image
- downloaded the image from the Docker Hub (more about the hub later)
- loaded the image into the container and “ran” it

镜像来源

任何人都可以创建自己的镜像, 并将其放到 Docker Hub 上. docker daemon 默认会知道从 Docker Hub 上找镜像.

镜像的创建

自己创建镜像需要一个 Dockerfile 描述文件, 写好 Dockerfile 后执行 docker 命令, docker daemon 就会创建相应的镜像. 再执行 docker images 命令就能看到创建的这个镜像.

可以看到创建镜像我们只提供了一个描述文件, 没有提供创建镜像所需要软件和文件等, 也没指定创建好的镜像放在那里, 实际上我们自己创建的镜像和下载的镜像是放在一个专门的目录里的, 我们不需要操心镜像在本地的位置, docker 自己能找到它.

提示

docker 镜像一般是尽可能做的小, 以节省带宽和存储. 比如 Docker Hub 中的 ubuntu 镜像, 默认是连 ifconfig, ping 这样的工具都不包含的, 初次之外默认还砍掉了很多其他组件, 所以 ubuntu 的镜像总共才 100MB. 安装以后如果需要的话可以自己 apt-get install 添加.

Docker for Mac 的问题

Mac 版的 docker 没有 docker0 接口, 宿主机无法与容器直接通信.

https://docs.docker.com/docker-for-mac/networking/#use-cases-and-workarounds

Docker 的存储理解

理解镜像, 容器, 层以及存储驱动的概念:

https://docs.docker.com/engine/userguide/storagedriver/imagesandcontainers/

要持久化存储容器里的改动, 一个是 commit 自己的改动, 构建新自己的新的镜像. 一个是挂载 data volume, 将数据存 data volume 上.

data volume 就是宿主机上的文件或目录, 容器启动时可以挂载这个文件或目录. 多个容器可以共享相同的 data volume.

https://docs.docker.com/engine/userguide/storagedriver/imagesandcontainers/#data-volumes-and-the-storage-driver

Docker 的网络绑定

https://docs.docker.com/engine/userguide/networking/default_network/binding/

数据存储

https://docs.docker.com/engine/admin/volumes/

三种方式:

  • volumes
  • bind mounts
  • tmpfs volumes

这三种方式对容器内部而言表现一样, 展现给容器内部要么是一个目录, 要么是个文件.

osx 下的 bind mounts

在 osx 系统下, 因为种种原因, bind mounts 和在 Linux 系统下不太一样. osx 系统下需要先配置要 bind mounts 的目录, 这可以在 Preferences -> File Sharing 下完成, 默认有配置四个目录:

  • /Users
  • /Volumes
  • /tmp
  • /private

这四个目录包括子目录都能直接 mount 到容器里.

你可能也发现过有些目录不在这四个之中但是也 mount 成功了, 比如:

  • docker run -it -v /etc:/dockeroot ubuntu:16.04
  • docker run -it -v /bin:/dockeroot ubuntu:16.04

也都是可以成功的. 这是因为 docker for mac 里还存在一个叫做 Moby Linux VM 的东西, 当你 mount 了一个没在 File Sharing 中配置过的目录时, 就会从 Moby Linux VM 中找这个目录. 上面两个例子
, 如果仔细看一下, 其实挂载到 /dockeroot 下的内容并不是你 osx 机器的 /etc 或者 /bin 的内容.

关于这一点可以看官方的说明, 以及后两个链接:

https://docs.docker.com/docker-for-mac/osxfs/#namespaces
https://stackoverflow.com/questions/45122459/docker-mounts-denied-the-paths-are-not-shared-from-os-x-and-are-not-known
https://github.com/docker/for-mac/issues/1970

打造自己的开发环境

使用 macbook 有半个月了, 很好, 但是在服务器开发环境方面和 linux 确实还是有点距离的, 最简单的 php + fpm + nginx 的环境都不好搞. 所以今天想借助 docker 搞一个这样的环境试一下.

方法一:

所做的修改及时 commit

方法二:

自己写 Dockerfile 或者 compose.yaml

方法三:

使用这个项目: https://github.com/phusion/baseimage-docker

企业化

docker 实际使用时, 一个容器内可能启动多个服务, 如何管理这多个服务呢?

docker 容器里一般不包含 init 程序的, CMD 命令所指定的进程就是 dokcer 里的第一个程序, 一般我们使用 python 的 supervisord 框架来作为 docker 容器内的第一个进程, 并用它来管理其它的进程

Q&A

镜像 ID 是什么

关于镜像 ID, 官方文档说的很不清楚. 下面这个链接说的比较清楚, 认真看完这个链接, 就都懂了

http://windsock.io/explaining-docker-image-ids/

如何查看某镜像的创建历史及其父镜像

http://windsock.io/explaining-docker-image-ids/

docker inspect 命令结果的含义

http://windsock.io/explaining-docker-image-ids/

docker 镜像在 osx 系统上的位置

~/Library/Containers/com.docker.docker/Data/com.docker.driver.amd64-linux/Docker.qcow2, 这是一个 qmenu 镜像文件

Dockerfile 中的 FROM 指令对应 docker history 中的 ADD file, Add file 中的 “file” 是哪来的

https://stackoverflow.com/questions/41972328/docker-history-base-image-addsha256hash

如何得到某个镜像的 base image

https://stackoverflow.com/questions/31149775/docker-how-to-get-the-name-user-repotag-of-the-base-image-used-to-build-ano

docker history 命令的输出不是完全按照 Dockerfile 中的指令逆序输出的

Dockerfile 中这么写

FROM xxx
MAINTAINER cifer

生成的镜像, docker history 的输出可能是

ADD file:xxxxxxx
MAINTAINER cifer

镜像越来越大了, 删除文件然后 commit, 镜像不会减小的?

是的, 了解了镜像的结构就会明白了, 镜像本身包含的 layer 都是只读的. 容器运行时, 我们处于一个新的可写的 layer 中, 删除文件, 然后 commit, commit 会把这个新 layer 写入镜像, 我们对文件的
删除也只是在新的 layer 中删除了, 老的 layer 中是依然包含这个文件的, 所以镜像不会变小的. 但是启动镜像之后, 你所删的文件确实是没有了.

那该怎么办呢? 使用 docker save 或者 docker export 命令

https://stackoverflow.com/questions/22655867/what-is-the-difference-between-save-and-export-in-docker

https://tuhrig.de/difference-between-save-and-export-in-docker/ 这篇文章的作者就是上面 so 链接里的提问者, 作者收到的回答之后回去写了一篇博客作为总结, 赞!

docker tag 的作用

在我们本地构建的镜像会包含多个层, 执行 docker history 会发现每个层有一个对应的 IAMGE ID, 这是因为 Dockerfile 里的每条指令都会创建一个新层并 commit.

docker tag 可以让这个名字的镜像回到某个层. 但是似乎必须是在本地构建的层才能回去.

docker 中如何检测有效 cpu 核数

我们常常需要根据程序运行的宿主机的 cpu 核心数来决定程序要创建的线程或进程, 在物理机上查看 cpu 核心数可以通过 /proc/cpuinfo, 而在 docker 上就不行了.

因为 docker 容器可以利用 --cpuset-cpus 选项配置可以使用的 cpu 核数, 而 /proc/cpuinfo 反应的却是物理机的情况, 所以就不能用它来获取实际 docker 运行时实际拥有的核数了, 需要通过其他方式来获得, 详情参见:

  1. https://github.com/moby/moby/issues/20770
  2. https://stackoverflow.com/questions/47545960/how-to-check-the-number-of-cores-used-by-docker-container/47547987#47547987

最短的文字说明 git submodule 的原理

git submodule 的那几个命令每次查完都记不住, 所以这次就在这里好好思考一下其原理, 希望以后不要再忘了.

git submodule 的原理是在父模块中记录子模块的 commit, 并监控记录的 commit 和子模块的 HEAD 的差异.

父模块所记录的子模块 commit 属于父模块的版本信息, 这一信息的改变不会实际影响子模块的 HEAD. 当 cd 到子模块中做了一些更改提交, 或者父模块从远程 fetch 最新改动, 只要是会导致父模块记录的 commit 和子模块中 HEAD 不一样时, 父模块 git status 就会显示出这一差异, git submodule update 命令会将子模块的 HEAD 指向父模块中记录的 commit id, 从而抹平这一差异.

如果子模块嵌套了子模块, 可以用 git submodule update --recursive 递归更新所有嵌套的子模块的 HEAD.

如果想让子模块的 HEAD 更新到子模块的远程最新, 就用 git submodule update —remote, 这样一来子模块的 HEAD 一般往往也就比父模块记录的 commit 要新了, 父模块 git status 自然也会显示差异, 父模块可以提交这一信息将其记录在自身 — 这就是父模块 “携带” 某个特定版本子模块的方法.

C++ 的左右值与左右值引用

左值与右值

C++ 中左值和右值的概念来源于 C, 在 C 中左值和右值的区别很简单, 能出现在赋值号左侧的就是左值, 否则就是右值. 比如变量是左值, 字面常量或者 const 定义的常量是右值.

然而在 C++ 中, 左值和右值的区别就不再是那么简单了, 甚至和 C 还会有冲突, 比如在 C 中 const 定义的常量对象是右值, 而在 C++ 中却是左值.

实际上在 C++ 中左值和右值的情况非常复杂, 有时区分他们也是非常困难的. Scott Meyers 大师在其 Effective Modern C++ 一书所说的不失为一个好方法, 在理解这句话之前, 我们一定要有一个意识, 就是左值和右值是表达式的属性, 代表着表达式的运算结果是左值还是右值.

A useful heuristic to determine whether an expression is an lvalue is to ask if you can take its address. If you can, it typically is. If you can’t, it’s usually an rvalue. A nice feature of this heuristic is that it helps you remember that the type of an expression is independent of whether the expression is an lvalue or an rvalue.

也就是说, 表达式是左值还是右值, 就看这个表达式的结果是否在内存有对应的存储区域, 有的话就是左右, 没有的话就是右值 (TODO: 补充例子), 这点也可以参考 c++ primer 5th, p121.

另外还有两个有重要的准则:

  1. 对象 (对象是最简单的表达式) 被用作左值时, 用的是对象的地址; 被用作右值时, 用的是对象的值
  2. 在需要右值的地方, 可以用左值代替 (因为地址中存储着值), 这时左值被当成右值使用, 用的是左值里存储的值. 这条准则只有一个例外, 就是左值引用不能当做右值引用使用 (下面会讲到引用)

引用

在 C++11 以前, 引用就是对象的别名, 只能绑定到左值上, 并且一旦绑定到了某个对象上就永远绑定了, 不能通过赋值改变引用绑定的对象, 因此在定义引用时必须初始化.

定义引用绑定到对象时, 一般是要求所绑定到的对象的类型和引用的类型必须一致, 不过也有两个例外:

  1. 定义的基类引用可以用派生类对象初始化 (c++ primer 5th, p534)
  2. 常量引用 (对 const 的引用) 可以用任意表达式作为其初始值, 只要该表达式的结果能转换成引用类型即可 (c++ primer 5th, p55)

上面说的引用只能绑定到左值上, 在 C++11 中扩展了引用的概念, 允许引用绑定到右值表达式这样的右值上, 这新引入的引用类型被称为右值引用, 对应的之前的引用被称为左值引用.

那么右值引用有什么用呢? 如果仅仅是让我们能够绑定到字面常量这样的右值的话, 刚刚我们也看到了, 通过常量(左值)引用我们同样也能够绑定到字面常量等右值表达式上, 为什么还要引入右值引用呢?

然而右值引用不仅仅是让我们能够不借助 const 就能引用右值表达式, 它还支持了对象移动以及完美转发这两个重要的能力. 关于这两个能力就是另外的话题了, 我们简单介绍一下对象移动.

对象移动

对象移动的目的是减少对象拷贝, 被移动的对象内容会被 “掏空”, 赋予新对象中, 这个操作依赖于 “移动构造函数” 或者 “移动操作符”, 然而如何定义这两个方法却成了一个问题, 我们知道拷贝构造函数和赋值操作符是以对象的引用 (左值引用) 为参数的, 而如果要定义移动构造函数或移动操作符, 其参数当然也得以代表对象的某种形态为参数, 对象的引用这种形态已经不能用了, 对象的非引用更不能用 (原因见 c++ primer 5th, p422), 那么只能新发明一中语义了, 这个新的语义就是右值引用, 写作 T &&. 于是移动构造函数就可以这么定义了:

Foo (Foo && other);

如此一来, 只要传递给构造函数的是右值引用, 就会调用移动构造函数, 免去拷贝所造成的开销.

然而如何传递右值引用呢? 当发生如下情况时, 该调哪个构造函数又成了一个问题:

Foo (const Foo &other);
Foo (Foo && other);

Foo(foo);    // 该调哪个构造函数?

事实上由于拷贝构造函数先出现, 所以上面第 4 行的写法当然是会调拷贝构造函数的. 为了能够调到移动构造函数, 标准库提供了一个 std::move 方法, 这个方法总是返回右值引用, 因此我们只要这么写就能够调用移动构造函数了:

Foo(std::move(foo));

除了显式的通过 std::move 方法, 有些情况下编译器也能够自动判断是否可以调移动构造函数来降低开销, 比如编译器发现源对象是个临时对象.

关于右值引用带来的另一个功能完美转发就不再敖述, 可以参考文末链接 1 关于右值引用的提案.

参考

  1. 右值引用提案: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html