0. 前言·

几年前分析过持久化KV数据库–LevelDB, 从今天开始，逐渐分析内存KV数据库–Redis。实际上也是《Redis设计与实现》的读书笔记。

本篇为redis内常用基本数据结构介绍。

1. 前言·

一年多前做过mit 6824, 学习了raft，不过当时更多是从代码层面记录博文，最近正好在系统学习分布式的知识，本文从理论角度全面细谈Raft。

最近在读《深入理解分布式系统》，书中所描述的Multi-Paxos个人觉得不太好理解。本文结合书和网络上的资料，记录下Paxos的基本流程。

一直以来对"并发"相关的主题都蛮感兴趣的，但这一块也确实非常复杂，因为同时涉及了硬件设计和软件协议。比如再看c++ memory order时，一定见过这些词语：重排序、乱序执行，分支预测、预测执行、MSEI、volatile，内存屏障、store buffer, invalidate queue, sequential order(SC)、TSO、PSO内存模型、happens before, synchronized-with、sequenced-before、program order等等名词。作为一个非科班的开发人员，大概率是会被绕晕的。这篇文章，就来谈谈这些概念，当然最终目标是理解c++11中提出的几大常见内存序该如何使用。由于水平有限，难免出错，也希望指正。

string是c++中标准的字符类（其实字节类更贴切），几乎所有项目都在使用（除非是明令禁止），了解其内部实现，可以帮我们更好的使用它。今天来分析下它。

本文分析的是 3.3 版本string，额外介绍了一些新版的实现。

vector可以说用到最多的容器了。今天来从源码分析它。

这是stl源码阅读系列的第四篇，这一篇来看看stl中的 copy, fill和uninitialized函数族。本篇中，可以看到第二篇曾提到过的 iterator_category的作用。

这是stl源码阅读系列的第三篇，这一篇来看看stl中对象的构造与析构是如何处理的。

这是stl源码阅读系列的第二篇，这一篇来看看stl中迭代器traits的实现。

在stl中，有三个彼此关联的组件：

Containers(即我们常用的vector, list, deque等)装载数据结构，Algorithms装载数据操作，两者相互独立，Iterator作为中间人，将两者联系起来。iterator提供访问容器数据成员的接口，隐藏了每个容器的具体存储实现（即迭代器设计模式）。每个容量都会提供一份iterator实现，所以在分析容器前，先看看iterator。

另外，整个stl可以看做泛型编程的最佳实践，所以在本篇中也会介绍一些泛型（模板）编程的概念。

接近一年未更新博文，忙着适应工作环境，当然自己也变懒了不少。感觉还是得多抽时间充实自己，本文开始分析stl源码。

本系列分析的stl 版本为 sgi v3.3。

首先分析内存分配器，因为容器需要依赖内存分配器来实现。如最常用容器的定义:

1
2
3
4
5

// alloc 是 SGI STL 的空间配置器
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
  // requirements:

这里的 __STL_DEFAULT_ALLOCATOR 定义为：

1
2
3
4
5
6
7

# ifndef __STL_DEFAULT_ALLOCATOR
#   ifdef __STL_USE_STD_ALLOCATORS
#     define __STL_DEFAULT_ALLOCATOR(T) allocator< T >
#   else
#     define __STL_DEFAULT_ALLOCATOR(T) alloc
#   endif
# endif

allocator 内部实现也为 alloc, 所以本文分析的对象为 alloc。

关于 alloc 的实现，文件目录为 allocator/stl_alloc.h

关于alloc的定义有两种：(通过宏来开关是哪一种)：

1. 第一级配置器：

1
2

typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;  // 令 alloc 为第一级配置器

此时实际类为 __malloc_alloc_template

2. 第二级配置器:

1

typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;  // 令 alloc 为第二级配置器

此时实际类为 : __default_alloc_template