weak_ptr&unique_ptr

weak_ptr

shared_ptr, Binary trees and the problem of Cyclic References

shared_ptr最大的优点是在不再使用的时候，能够自动释放相关的内存，但也存在缺点，就是循环引用——如果两个对象使用shared_ptr相互引用，在对象超出作用域时，就没办法删除内存。

这是因为由于相互引用，引用计数永远不会为0。

Now How to fix this problem?

答案就是使用weak_ptr，weak_ptr能够分享对象，但不会拥有这个对象，它是通过shared_ptr进行创建：

1
2

std::shared_ptr<int> ptr = std::make_shared<int>(4);
std::weak_ptr<int> weakPtr(ptr);

对于weak_ptr对象，我们无法直接使用操作符*和->去访问相关的内存，因此我们只能通过weak_ptr对像去创建shared_ptr，方法是调用lock函数。

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

#include <iostream>
#include <memory>
int main()
{
    std::shared_ptr<int> ptr = std::make_shared<int>(4);
    std::weak_ptr<int> weakPtr(ptr);
    std::shared_ptr<int> ptr_2 =  weakPtr.lock();
    if(ptr_2)
        std::cout<<(*ptr_2)<<std::endl;
    std::cout<<"Reference Count :: "<<ptr_2.use_count()<<std::endl;   
    if(weakPtr.expired() == false)
        std::cout<<"Not expired yet"<<std::endl;   
    return 0;
}

如果shared_ptr已经被删除，lock()函数返回空的shared_ptr。

unique_ptr

unique_ptr是c++11提供的智能指针实现之一，用于防止内存泄漏。unique_ptr对象包装了一个原始指针，并负责其生命周期。当该对象被破坏时，然后在其析构函数中删除关联的原始指针。

它跟shared_ptr的用法类似，也能使用原生指针的一些操作符。但不同的是归属权，unique_ptr对象始终是关联的原始指针的唯一所有者。 我们无法复制unique_ptr对象，它只能移动。也因为如吃，其析构函数中不需要任何引用计数，可以直接删除相关的指针。

1
2
3
4
5
6
7
8

// Create a unique_ptr object through raw pointer
std::unique_ptr<Task> taskPtr2(new Task(55));
 
// Compile Error : unique_ptr object is Not copyable
std::unique_ptr<Task> taskPtr3 = taskPtr2; // Compile error
 
// Compile Error : unique_ptr object is Not copyable
taskPtr = taskPtr2; //compile error

在unique_ptr类中，拷贝构造函数和赋值构造函数都已经被删除了。

Transfering the ownership of unique_ptr object

虽然不能拷贝一个unique_ptr对象，但我们可以move它们，即传递拥有权。

1
2

std::unique_ptr<Task> taskPtr2(new Task(55));
std::unique_ptr<Task> taskPtr4 = std::move(taskPtr2);

Releasing the associated raw pointer

对unique_ptr对象调用release()函数可以释放相关原始指针的拥有权，即返还一个原始指针。

1
2

std::unique_ptr<Task> taskPtr5(new Task(55));
Task * ptr = taskPtr5.release();

shared_ptr

What is std::shared_ptr<>

shared_ptr是c++11提出的一种智能指针类，能够自动地删除掉相关的不再被使用的指针，它能够帮助解决内存泄漏和悬空指针的问题。

shared_ptr有一个共享对象的概念，不同的shared_ptr可以共享相同的指针，并且通过内部的引用计数机制来实现这一功能。每个shared_ptr内部都指向两个内存区域，一个是指向对象的指针，另一个就是用来做引用计数的数据。

引用计数的使用方式：

• 当有一个新的shared_ptr与指针相关联后，其引用计数递增1；
• 当一个shared_ptr对象离开作用域时，其引用计数递减1。并且在引用计数变为0的时候，它会delete那部分内存；

Creating a shared_ptr Object

创建shared_ptr对象时需要绑定一个原生指针，如下：

1

std::shared_ptr<int> p1(new int());

这样，就在堆上创建了两块内存：一个是int，一个是引用计数的数据区域。

至于，要查看目前的引用计数是多少：

1

p1.use_count();

另外，要将一个指针赋值给shared_ptr，我们不能采用隐式的方式，因为其构造器是采用explicit的方式，所以隐式赋值会报错，但我们可以使用std::make_shared

1
2

std::shared_ptr<int> p1 = new int(); // Compile error
std::shared_ptr<int> p1 = std::make_shared<int>();

Detaching the associated Raw Pointer

要使shared_ptr对象取消附加其附加指针，可以调用reset()方法。

• 无参调用reset：

1

p1.reset(); // 递减引用计数

• 有参调用：

1

p1.reset(new int(34)); //指向新的指针，引用计数变为1

• 使用nullptr reset

1

p1 = nullptr;

shared_ptr可以看作是普通指针，即我们可以对shared_ptr对象使用*和->与，也可以像其他shared_ptr对象一样进行比较。

shared_ptr and Custom Deletor

在上文说过，shared_ptr对象超出作用域的时候，会递减引用计数，当计数为0时，默认情况下会调用delete函数删除指针。但如果我们的shared_ptr指向的是一个数组，就应该使用delete[]了。

因此，为了避免默认调用的错误，我们可以自定义删除器。

1
2
3
4
5
6

void deleter(Sample * x)
{
	std::cout << "DELETER FUNCTION CALLED\n";
	delete[] x;
}
std::shared_ptr<Sample> p3(new Sample[12], deleter);

当然也可以利用lambda函数或者函数对象来自定义删除器。

shared_ptr vs Pointer

与原生指针不同，shared_ptr只有以下的的操作符：

• ->, *, 比较符号；

不提供原生指针的这些操作：

• +, -, ++, —和[]；

当我们创建shared_ptr对象而不分配任何值时，它就是空的。而对于原生的指针来说，它会包含一个垃圾值。因此对于shared_ptr对象，我们可以这样检查：

1
2
3
4
5
6
7

std::shared_ptr<Sample> ptr3;
if(!ptr3)
	std::cout<<"Yes, ptr3 is empty" << std::endl;
if(ptr3 == NULL)
	std::cout<<"ptr3 is empty" << std::endl;
if(ptr3 == nullptr)
	std::cout<<"ptr3 is empty" << std::endl;

Create shared_ptr objects carefully

在创建shared_ptr对象时，有些情况需要注意的：

1. 不要使用相同的原始指针来创建多个shared_ptr对象，因为不同的shared_ptr对象并不知道它们正在与其它shared_ptr对象共享指针；
2. 不要从stack中创建shared_ptr对象，因为在stack内存上调用删除操作，程序会崩溃。因此我们应该使用make_shared<>之类的；

1
2
3

std::shared_ptr<int> ptr_1 = make_shared<int>();
 
std::shared_ptr<int> ptr_2 (ptr_1);

Designing Callbacks in C++

Function Pointers

首先来看一下什么是callback，callback实际上是一个函数，以参数的形式传递进另一个API中，在往后的某个时间点里面调用我们提供的callback。

callback的三种类型：

• Function Pointer
• Function Objects/Functors
• Lambda functions

假设我们的框架中存在一个API可以从提供的原生数据构建一个API，API执行以下的步骤：

1. 对原生数据添加头部和尾部；
2. 加密；
3. 返回信息；

现在这个API知道头部和尾部如何添加，但不了解如何进行加密，这个API可以接受一个函数指针回调如下：

1
2
3
4
5
6
7
8
9
10

std::string buildCompleteMessage(std::string rawData, std::string (* encrypterFunPtr)(std::string) )
{
    // Add some header and footer to data to make it complete message
    rawData = "[HEADER]" + rawData + "[FooTER]";
 
    // Call the callBack provided i.e. function pointer to encrypt the
    rawData = encrypterFunPtr(rawData);
 
    return rawData;
}

我们提供的加密方式如下：

1
2
3
4
5
6
7
8
9

std::string encryptDataByLetterInc(std::string data)
{
    for(int i = 0; i < data.size(); i++)
    {
        if( (data[i] >= 'a' && data[i] <= 'z' ) || (data[i] >= 'A' && data[i] <= 'Z' ) )
            data[i]++;
    }
    return data;
}

那么我们的API就可以这样调用了：

1
2

std::string msg = buildCompleteMessage("SampleString", &encryptDataByLetterInc);
    std::cout<<msg<<std::endl;

Function Objects & Functors

首先来看看什么是函数对象，实际上就是一个带状态的回调。一个重载了operator()的类对应的对象就是 Function Object or Functor，比如：

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

#include <iostream>
class MyFunctor
{
public:
    int operator()(int a , int b)
    {
        return a+b;
    }
};
//调用时
MyFunctor funObj;
std::cout<<funObj(2,3)<<std::endl;
funObj.operator()(2,3);

还是以上面的API为例子，假设我们系统API以三种不同的加密方式调用，加密方式分别是对每个字母加一、加二或者减一。如果是用函数指针的方式，我们需要定义三个不同函数，但实际上函数体是类似的。

但如果使用函数对象，那就可以在类里面绑定状态变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Encryptor {
    bool m_isIncremental;
    int m_count;
public:
    Encryptor() {
        m_isIncremental = 0;
        m_count = 1;
    }
    Encryptor(bool isInc, int count) {
        m_isIncremental = isInc;
        m_count = count;
    }
    std::string operator()(std::string data) {
        for (int i = 0; i < data.size(); i++)
            if ((data[i] >= 'a' && data[i] <= 'z')
                    || (data[i] >= 'A' && data[i] <= 'Z'))
                if (m_isIncremental)
                    data[i] = data[i] + m_count;
                else
                    data[i] = data[i] - m_count;
        return data;
    }
};

修改一下API的参数类型：

1
2
3
4
5
6
7
8
9
10

std::string buildCompleteMessage(std::string rawData,
        Encryptor encyptorFuncObj) {
    // Add some header and footer to data to make it complete message
    rawData = "[HEADER]" + rawData + "[FooTER]";
 
    // Call the callBack provided i.e. function pointer to encrypt the
    rawData = encyptorFuncObj(rawData);
 
    return rawData;
}

调用的时候只需要传递不同的参数到函数对象的构造器即可：

1
2
3

buildCompleteMessage("SampleString", Encryptor(true, 1));
// buildCompleteMessage("SampleString", Encryptor(true, 2));
// buildCompleteMessage("SampleString", Encryptor(false, 1));

Unordered Map

Basic Usage Detail and Example

Unordered map是C++11新出的特性，它提供了一种map的实现机制，可以存储键值对。Unordered map内部实现了哈希函数，当我们插入一个新的元素时：

• 首先对key做哈希函数处理，然后选择一个合适的bucket；
• 比较该bucket下的key是否重复；
• 在不重复的情况下，添加该元素到bucket中；

因此Unordered map时无序的，并且其搜索元素的时间复杂度为O(1)。

Different Ways to initialize an unordered_map

unordered map提供了三种不同的重载构造器：

• 通过initializer_list初始化

1
2
3
4

std::unordered_map<std::string, int> wordMap({
												  { "First", 1 },
												  { "Second", 2 },
												  { "Third", 3 } });

• 使用iterable range初始化

1

std::unordered_map<std::string, int> wordMap_2(wordMap.begin(), wordMap.end());

• 使用另一个unordered_map初始化

1

std::unordered_map<std::string, int> wordMap_3(wordMap);

Searching in unordered_map

unordered_map提供了一个成员函数find()，改函数接受一个key作为参数，在找到元素的时候就会返回一个相对应的迭代器，否则会返回map的尾部迭代器。

1

iterator find ( const key_type& k );

Different ways to insert elements in an unordered_map

unordered_map提供了多种insert()成员函数的重载版本，我们来一一讨论：

• 通过initializer_list插入多个元素；

1
2
3
4
5
6

void insert ( initializer_list<value_type> il );

// Example
std::unordered_map<std::string, int> wordMap;
// Inserting elements through an initializer_list
wordMap.insert({ {"First", 1}, {"Second", 2}, {"Third", 3} } );

这种插入方式有一个缺点，因为insert()返回的是void类型，因此在添加重复key的元素时，用户无法确定插入是否成功。

• unordered_map提供了一个重载版本，它接受std::pair of key – value 作为参数，并返回一对迭代器和bool变量，通过该bool变量我们就可以判断插入是否成功；

1
2
3
4
5
6
7
8
9
10

pair<iterator,bool> insert ( const value_type& val );

typedef std::unordered_map<std::string, int>::iterator UOMIterator;
// Pair of Map Iterator and bool value
std::pair< UOMIterator , bool> result;
 
// Inserting an element through pair
result = wordMap.insert(std::make_pair<std::string, int>("Second", 6));
if(result.second == false)
      std::cout<<"Element 'Second' not inserted again"<<std::endl;

Erasing an element

要想从unordered_map中删除元素，其提供了两种方式，如下：

• 通过提供key类型，即可删除该元素；

1

size_type erase ( const key_type& k );

它的返回值为0或1，对应的是被删除的元素数量

• 通过迭代器删除元素；

1

iterator erase ( const_iterator pos );

改函数接收一个迭代器对象，并删除其对应的元素。在删除1，返回指向被删除元素对应的下一个元素的迭代器。因此需要注意的是，在遍历迭代器的过程中删除元素，其返回值是一个有效的迭代器，为被删除元素的下一个。

std::map vs std::unordered_map

本节主要讨论std::map与std::unordered_map的区别，它们虽然都是存储键值对与实现了有效插入、搜索和删除操作，但有着以下的不同：

• 内部实现：与std::unordered_map不同，std::map是通过二叉搜索树存储元素的，因此它能通过key进行排序；
• 内存使用：std::unordered_map需要更多的内存来存储哈希表；
• 搜索的时间复杂度：由于std::map是树的结构，因此其时间复杂度为O(log n)，而std::unordered_map最好的时间复杂度是O(1)，最坏的情况是O(n)，即所有元素在同一个bucket；
• 自定义key的使用方法：使用自定义key时，对于std::map来说，需要重载<操作符或者传入外部的comparator比较器，对于std::unordered_map则需要提供std::hash<K>，同时我们还需要重载==操作符；

C++11: std::tuples

std::tuple Tutorial & Examples

what is std::tuple and why do we need it

std::tuple是一种可以将固定大小的异构值绑定在一起的类型。在创建元组对象时，我们需要将元素的类型指定为模版参数。

Creating a std::tuple object

首先是要include进头文件：

1

#include <tuple>

我们可以声明一个包含了int, double和string类型的tuple，实际上这种做法可以帮助我们从一个函数中返回多种值，避免创建不必要structure。

1

std::tuple<int, double, std::string> result(7, 9.8, "text");

Getting elements from a std::tuple

我们可以使用std::get函数获得隐藏在tuple对象中的元素，方法是将索引值指定为模版参数：

1

int iVal = std::get<0>(result);

Getting Out Of Range value from tuple

从tuple中获取索引大于元素数量的tuple元素会引起编译错误：

1

int iVal2 = std::get<4>(result); // Compile error

Wrong type cast while getting value from tuple

接收类型与tuple里面元素不符合也会导致编译错误：

1

std::string strVal2 = std::get<0>(result); // Compile error

Getting value from tuple by dynamic index

提供给std::get的模版参数必须是编译期常量，否则会引起编译错误：

1
2
3
4
5
6

int x = 1;
double dVal2 = std::get<x>(result); // Compile error

const int i = 1;
// Get second double value from tuple
double dVal3 = std::get<i>(result);

make_tuple Tutorial & Example

Initializing a std::tuple

我们可以通过传递参数到构造器的方式来初始化std::tuple：

1

std::tuple<int, double, std::string> result1 { 22, 19.28, "text" };

但tuple无法自动去推断类型：

1
2

auto result { 22, 19.28, "text" }; // Compile error
// error: unable to deduce ‘std::initializer_list<_Tp>’ from ‘{22, 1.9280000000000001e+1, "text"}’

于是C++11提供了std::make_tuple来解决这个问题：

std::make_tuple

std::make_tuple可以通过自动推断元素的类型来创建std::tuple对象：

1

auto result2 = std::make_tuple( 7, 9.8, "text" );

Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore

ABSTRACT

Spinnaker是一个实验性数据存储区，旨在在单个数据中心的大型商用服务器集群上运行。这篇文章介绍了Spinnaker基于Paxos的复制协议。Paxos的使用确保Spinnaker中的数据分区可用于读取和写入，只要其复制品的大部分存活。与最中一致的数据存储区相比，Spinnaker在读取时可以更快，但写入速度只有5%-10%。

INTRODUCTION

对数据库功能进行扩展时，一个有效的方法是在服务器集群使用手动分片，集群的每个节点负责部分数据并独立运行实例。后来也出现了新的数据库体系结构，可以进行自动化分片和负载平衡。

除了扩展要求外，还需要实现某种复制策略以实现高可用性和容错，一种可行方案是使用同步主从复制。但这不是一个理想的方法：

Limitations of Master-Slave Replication and the Case for Paxos

在传统的双向同步复制中，很可能存在这样的问题：

随着时间序列a-b-c-d的进行，从节点在b崩溃，在d恢复，主节点在c接受完写入后崩溃。此时从节点无法获取最新状态。因为根据要求，所有的写入都必须要路由到master，再由master的日志发送到slave。

因此，三向复制通常与商品服务器一起使用，可以避免其中一个节点数据丢失带来的问题或者便于在线升级。当有3个或多个副本时，Paxos协议被广泛认为是唯一经过验证的解决方案。Paxos解决了在2F + 1副本状态达成共识的一般问题，同时可以解决F故障。但paxos过于复杂和缓慢。

Strong vs. Eventual Consistency

在分布式系统中，一致性模型描述了不同副本如何保持同步。强一致性保证所有副本看起来与应用程序完全相同，这是构建应用程序的理想属性。CAP定理中提出，一致性，可用性和分区容差，最多只能保证两个。

Spinnaker

本文介绍了Spinnaker环境中一致性复制问题的解决方案，这是一个实验性数据存储，旨在在单个数据中心的大型商用服务器集群上运行。Spinnaker具有基于密钥的范围分区，3向复制和事务性get-put API。

对于复制，Spinnaker使用基于Paxos的协议，该协议将日志提交和恢复处理集成在一起。Spinnaker是CA系统的一个示例。

RELATED WORK

Two-Phase Commit

2PC是维持副本一致性的方法之一，具体可以参考。

由于其性能较差，所以一般不会使用。

Database Replication

与spinnaker相比，数据库备份主要关注在单个未分区数据库的上下文。

Dynamo, Bigtable, and PNUTS

亚马逊的Dynamo是一个基于key-value的存储，它使用最终的一致性来提供高可用性和分区容错。

谷歌的Bigtable是一个可扩展的数据存储区，可为单一操作事务提供强大的一致性支持。

而Yahoo的PNUTS也是一个可扩展的数据存储区，支持时间线一致性和单一操作事务。

DATA MODEL AND API

Spinnaker的数据模型和api与Bitable类似。数据以表格和行列的形式组成，每一行有一个唯一ID，并且包含了多个列（每一列又有其版本号和值）。至于API则是：

• get(key, colname, consistent): consistent是一个flag，true时选择强一致性，返回最新的值
• put(key, colname, colvalue)
• delete(key, colname)
• conditionalPut(key, colname, value, v)：v代表版本号，插入时该列的版本需等于'v'
• conditionalDelete(key, colname, v)

版本号是单调递增的整数，由Spinnaker管理并通过其get API暴露出去，因此我们可以这样使用api来更新某个计数器：

1
2

c = get(key, “c”, consistent=true);
ret = conditionalPut(key, “c”, c.value + 1, c.version);

每个API调用都作为单个操作事务执行。

ARCHITECTURE

本文主要介绍Spinnaker的架构。

Spinnaker通过范围分区的方式将一个表的行分布到集群中。以下图为例，这个Spinnaker集群有5个节点，每个节点都有一个key范围，这个范围会被备份到后面的N-1个节点中（这里N为3）。这样节点A-B-C形成key范围[0,199]的群组，节点B-C-D形成key范围为[200,399]的群组。

Node Architecture

Spinnaker每个节点都包含多个组件，每个组件都是线程安全的，这样就可以多线程地支持节点上三个key范围的其中一个使用。

每个节点的群组都有自己独立的逻辑LSN，以便共享相同的日志。

• commit queue是用来追踪pending的写入，在接收到群组足够的答应之后此才会将写入提交
• memtable则是用来放置提交的写入，定期排序并刷新到称为SSTable的不可变磁盘结构中
• SSTables按密钥和列名称编制索引，以便高效访问，并在后台中合并小的SSTables

Zookeeper

Zookeeper用于在Spinnaker中提供差错容忍和分布式协调服务。通过提供存储元数据和管理节点故障等事件的集中位置，Zookeeper极大地简化了Spinnaker的设计。

通常，Spinnaker节点和Zookeeper之间交换的唯一消息是心跳。

THE REPLICATION PROTOCOL

本节介绍Spinnaker的复制协议。该协议基于每个队列应用。

首先是每个群组都会有一个leader，而其它两个节点就是follower。这个协议有两个阶段：一是leader选举，后面则是称为quorum的阶段，leader会提出写入，follower会接受这个提议。

下图就是稳定状态下的复制协议流程：

首先是客户端提交写入W，被路由到相关key范围的leader节点。leader并行地启动日志刷到磁盘、将W添加到commit queue并发送一个消息到followers。

follower在接收到消息后，将W日志记录到磁盘，附加W到commit queue，并对leader作出应答。

leader收到至少一个应答后就会将W写入memtable。

另外，leader会周期性地发送异步消息给followers，以让followers将到某个LSN范围内的pending写入应用到memtable。对于强一致性来说。所有的读取都路由到leader；而时间轴一致性则可以路由到任意节点。因此由上图可得，一共会有三次log force和四次消息传递。

Conditional Put

Conditional Put与常规put的唯一区别就是前者需要检查版本是否匹配，如果不符合，不会写入任何数据，并且会向客户端返回错误代码。Conditional Put在组群的每个节点上具有相同的结果。

RECOVERY

接下来会讨论一个群组在某个节点挂掉后如何恢复。一个属于三群组的节点是共享日志、并行恢复的，因此这里主要以一个群组为例。

Follower Recovery

follower的恢复有两个阶段：local recovery和catch up。

首先假设f.cmt和f.lst分别是follower最近提交的日志LSN和最后的LSN，在local recovery阶段，follower会重播f.cmt之前的日志记录，至于f.cmt之后的，在catch up阶段，follower会先通知leader它的f.cmt，leader会将f.cmt之后提交的写入作为应答，然后follower会阻塞其他的写入，重播这些日志。

由于实际中，一个节点最旧的那部分日志很可能已经被SSTable捕获，如果catch up阶段需要，leader无法访问这部分日志。因此SSTable会记录其包含写入的日志LSN范围，在catch up无法满足要求时，SSTable会帮助获取这部分日志。

Logical Truncation of the Follower’s Log

前面提到过，f.cmt之后的写入状态是无法确定的，因为leader可能尚未提交，也可能旧leader提交了，但其挂掉后，新leader丢弃了部分日志。

为了解决这个问题，我们采用的是logical truncation的方法，则将f.cmt与f.lst之间日志的LSN记录到LSN的跳表中，如下：

Leader Takeover

当leader挂掉时，一个集群的key范围将变得不可写入，新leader会被选出，并保证老的leader的所有commit日志都会被包括进来。

如果老的leader挂掉了，有些可能在follower的处于pending状态下的，但已经在老leader里commit的日志。新leader的解决方法如下：

LEADER ELECTION

本文主要描述Spinnaker的leader选举协议，该协议是基于每个群组运行。当一个群组的leader挂掉或者系统重启后本地恢复时，leader的选举就会被触发。

Zookeeper’s Data Model and API

Zookeeper的数据模型与文件系统的目录树类似，树中的节点都由从根开始的路径标示，例如/a/b/c。这些znode包含了相关的二进制数据。

znode既可以是持久化的也可以是临时的，另外znode还可以包含一个顺序属性，使Zookeeper在创建时为znode添加一个唯一的，单调递增的标识符。

The Leader Election Protocol

每个Spinnaker节点都包含一个Zookeeper客户端。

假设r是进行选举的群组的key范围，那么选举所需要的信息都存储在Zookeeper的/r下。leader选举之前会有一个节点清除上一轮leader选举的状态。紧接着，群组的节点会宣称自己是candidate，此时会添加一个临时的znode在目录/r/candidates下。一旦有大多数的节点成为了candidate，就选择最大lst的节点作为leader。具体过程如下：

DISCUSSION

Availability and Durability Guarantees

使用N=3的默认备份设置时，Spinnaker会在日志成为大多数时才会真正commit。只要大多数节点启动，群组就可以继续进行强一致的读写操作。

在正常情况下，即使其中3个节点中的2个永久失败，群组也不会丢失已发送的数据。 但是，如果一个群组的领导者及其一个follower在快速连续中永久失败，那么一个小写的commit窗口可能会丢失。

Multi-Operation Transactions

目前，Spinnaker中的每个API调用都作为单个操作事务执行，但可以通过对其复制协议和恢复过程进行相当适度的扩展来支持多操作事务。

基本思想是让事务创建多个日志记录，但仅在提交时为一批日志记录调用复制协议。 然后在恢复期间，首先使用Paxos将日志的副本置于一致状态，然后是本地（每个节点）redo和撤消恢复过程。

std::initializer_list

std::initializer_list<T>是C++11引入的新特性，在C++11之前我们可以这样初始化一个数组，但要初始化容器类却无法一行代码完成：

1
2
3
4
5
6

int arr[]= {1,2,3,4,5};

// Old Way to initialize a vector
std::vector<int> vec1;
for(int i = 0; i < 5; i++)
		vec1.push_back(i);

而在C++11我们可以这样实现：

1

std::vector<int> vec= {1,2,3,4,5}; // Compile Error before C++ 11

对于std::initializer_list<T>，我们可以创建一个这样的对象：

1

std::initialzer_list<int> data = {1,2,4,5};

当编译器看到这样的形式时{a,b,c}，它会自动创建一个这样的对象std::initialzer_list<T>，另外像vector或者list之类的容器，也实现了一个参数化的构造器：

1
2
3
4

vector<T>::vector<T>(initializer_list<T>  elements)
{
......
}

Using std::initializer_list in constructors to initialize member variables

我们也可以用std::initializer_list<T>去初始化成员变量，假设我们有一个这样的类：

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

class Point {
    int mX;
    int mY;
    int mZ;
public:
    Point(int a, int b, int c) :
        mX(a), mY(b), mZ(c) {
    }
    void display() {
      	std::cout << "(" << mX << "," << mY << "," << mZ << ")\n";
    }
};

我们可以直接传递一个initializer_list作为参数：

1

Point pointobj({1,2,3]});

但如果我们有一个构造器，其参数恰好就是std::initializer_list<T>，那么它就会调用该构造起，而不是调用以上三参数形式的构造起。

How to Initialize a map in one line using initialzer_list ?

同样的，我们也可以用std::initialzer_list<T>初始化一个map：

1
2
3
4

std::map<std::string, int> mapOfMarks = {
		{"Riti",2},
		{"Jack",4}
};

相对应的，编译器会在内部创建这样的一个对象：

1
2
3
4

std::initializer_list<std::pair<const std::string, int> > = {
		{"Riti",2},
		{"Jack",4}
};

Move Contsructor & rvalue References

Problem of Temporary Objects

这篇文章的主要目的是研究如何使用move语义去降低内存中临时对象的负载。每次从函数中返回一个对象时，都会有一个临时对象被创建出来，然后进行拷贝。最终我们将会创建出两个对象，但实质上我们只需要一个。

举个例子，我们有一个容器类：

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

class Container {
		int * m_Data;
public:
    Container() {
        //Allocate an array of 20 int on heap
        m_Data = new int[20];

        std::cout << "Constructor: Allocation 20 int" << std::endl;
    }
    ~Container() {
        if (m_Data) {
          delete[] m_Data;
          m_Data = NULL;
        }
    }
    Container(const Container & obj) {
        //Allocate an array of 20 int on heap
        m_Data = new int[20];

        //Copy the data from passed object
        for (int i = 0; i < 20; i++)
          	m_Data[i] = obj.m_Data[i];

        std::cout << "Copy Constructor: Allocation 20 int" << std::endl;
    }
};

这个类中，我们每次创建一个容器对象，其默认构造器都会分配一个20个int大的数组在堆上。同理，容器类的靠背构造器也会做类似的工作，首先是分配数组，然后将传递进的数组内容拷贝到新创建出数组里。

一般来说，我们使用工厂类来创建对象：

1
2
3
4
5

Container getContainer() 
{
    Container obj;
    return obj;
}

假设我们创建一个容器类型的vector，每次插入一个由getContainer()返回的对象：

1
2
3
4
5
6
7
8
9

int main() {
    // Create a vector of Container Type
    std::vector<Container> vecOfContainers;

    //Add object returned by function into the vector
    vecOfContainers.push_back(getContainer());

    return 0;
}

vector里的一个对象，实际上背后我们为此创建了两个对象。

• 一个是在getContainer()使用Container类的默认函数创建出来的；
• 一个是在加入vector中使用Container类的拷贝构造函数创建出来的；

这样每一个对象，都会带来两次在heap上创建数组。

Solving Problem of Temporary Objects using rvalue references & Move Constructor

getContainer()函数实际上是一个右值，所以可以被右值引用指向。因此为了实现这个目的，我们可以重载一个新的构造器，即move构造器：

Move Constructor

Move构造函数将右值引用作为参数，并重载该函数。在move构造函数中，我们只是将传递对象的成员变量move到新对象的成员变量中，而不是分配新内存。

1
2
3
4
5
6
7
8
9
10

Container(Container && obj)
{
    // Just copy the pointer
    m_Data = obj.m_Data;

    // Set the passed object's member to NULL
    obj.m_Data = NULL;

    std::cout<<"Move Constructor"<<std::endl;
}

在移动构造函数中，我们只是复制了指针，即成员变量m_Data指向了堆上的相同内存，然后将传递进的对象的m_Data设置为NULL。所以我们并没有在该构造函数中分配新的内存，而是转移了内存的控制。

现在再将getContainer()返回的对象push到数组中，由于getContainer()是一个右值，因此会调用container类的move构造器，此时只会创建一个整数数组。

Rvalue in C++

lvalue vs rvalue

在C中，判断是左值还是右值比较容易，赋值运算符的左边就是左值，右边就是右值。但在C++中不能这样一概而论。

What is lvalue

左值意味着其地址是可以访问的，即我们可以使用&运算符去访问地址。例如：

1
2
3
4

int x = 1;
int *ptr = &x;

int *ptr2 = &(x+1); //Compiler Error

因为(x+1)在这个表达式之后不能再生效，因此这不是左值而是一个右值。

What is rvalue

非左值即为右值，如下：

1
2
3
4
5
6
7
8
9
10

int *ptr = &(1); //Compiler Error, 1 is rvalue
int *ptr2 = &(x+1); //Compiler Error, x+1 is rvalue

int getData()
{
    int data = 0;
    return data;
}

int *ptr = &getData(); //Compiler Error

getData()是一个右值，在赋值之后这个临时值就失效了，里面的data是拷贝出来的，因此我们不能取其地址。

Is rvalue immutable in C++

虽然我们不能获取右值的地址，但我们能根据右值的数据类型去修改其。

rvalues of builtin data type is Immutable

我们无法修改内置的数据类型，例如：

1
2
3
4
5

(x+7) = 7;

getData() = 9;

// Both Compile Error

rvalue of User Defined data type is not Immutable

如果右值是用户定义的数据类型，我们可以在同一个表达式中使用成员函数去修改右值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Person {
		int mAge;
public:
    Person() {
      	mAge = 10;
    }
    void incrementAge()
    {
      	mAge = mAge + 1;
    }
};

	
Person getPerson()
{
		return Person();
}

getPerson().incrementAge(); // persist in single expression

What is rvalue reference in C++11

lvalue references

在C++11以前只有引用，即指向现存变量的别名。

c++11将原来的引用变成了左值引用，只能引用左值：

1
2
3

int x = 1;
int & lvalueRef = x; // lvalueRef is a lvalue reference
int & lvalueRef2 = (x+1); // compile error

rvalue Reference

右值引用是C++11引入的新特性：

1
2
3
4
5
6

int && rvalueRef = (x+1);

int & lvalueRef3 = getData(); // compile error

const int & lvalueRef3 = getData(); // OK but its const
int && rvalueRef2 = getData();

packaged_task<> Example and Tutorial

本文将主要讨论std::packagded_task的特性和使用

std::packaged_task<>

std::packaged_task<>是一个代表异步任务的类模版，它包括两部分：

• 一个可调用的实体。例如函数、lambda函数或者函数对象；
• 一个存储着返回值的共享状态或者由相关回调抛出的异常；

Need of std::packaged_task<>

假设我们想利用以下的函数从DB中获取数据：

1
2
3
4
5
6

std::string getDataFromDB( std::string token)
{
	// Do some stuff to fetch the data
	std::string data = "Data fetched from DB by Filter :: " + token;
	return data;
}

一种方法是使用前面提及的，在函数中传递std::promise<>对象。

另一种方法就是使用std::packaged_task<>

Using packaged_task<> with function to create Asynchronous tasks

当std::packaged_task<>在独立的线程上调用时，它会调用相关的回调并把返回值存储到内部的共享状态里。这些值可以在其它线程或者main函数里通过future对象访问。

以上面的函数为例，我们可以创建一个packaged_task对象。

1

std::packaged_task<std::string (std::string)> task(getDataFromDB);

然后在将std::packaged_task传递进线程之前，先从中获取future对象。由于std::packaged_task是不可以拷贝的，因此需要用move。

1
2

std::future<std::string> result = task.get_future();
std::thread th(std::move(task), "Arg");

当此函数返回值时，std :: packaged_task<>将其设置为关联的共享状态，getDataFromDB()返回的结果或异常最终会在相关的future对象中可用。

main函数阻塞调用：

1

std::string data =  result.get();