无锁队列的一种实现

队列作为最常用的基础数据结构之一，相信大家都已经非常非常熟悉了，这里省略关于队列的介绍。在平时开发中队列的出现频率非常非常高，因此我们也会很关心队列的性能问题。当并发访问队列时，队列的性能往往受到同步手段的制约，最简单的方式是使用互斥锁对整个队列加锁，但其并发性能却惨不忍睹。

因此，有了各式各样的无锁队列实现，本文介绍其中的一种实现。还是老样子，实现基于x86体系结构，Linux环境。

继续阅读：→

用户态同步之自旋锁

最近花了一些时间研究如何在用户态实现自旋锁，这里简单的总结一下。本文的所有代码以及配套的测试用代码都可以在我的github上找到。

问题在哪

首先明确问题，我们需要一种用户态实现的线程同步机制，正确性当然是最重要的。本文的目的是实现正确的自旋锁（自旋锁比较简单轻量，但了解了原理后实现互斥锁并不困难，自行维护等待关系并通过 futex 对线程执行挂起、唤醒操作就可以了）。

概念上这个问题很简单啊，是不是我们只要用一个线程共享的变量做互斥，然后在线程获得和释放锁时修改这个变量就行了？比如像下面这样：

#ifndef _FAKELOCK_H_
#define _FAKELOCK_H_

class FakeLock
{
public:
  FakeLock() {};
  virtual ~FakeLock() {};

  FakeLock(const FakeLock&) = delete;
  FakeLock &operator=(const FakeLock&) = delete;

  virtual int lock()
  {
    while (1L == lock_) {
      asm volatile("pause\n" ::: "memory");
    }
    lock_ = 1L;
    return 0;
  }

  virtual int unlock()
  {
    lock_ = 0L;
    return 0;
  }

 private:
  int64_t lock_;
};

#endif /* _FAKELOCK_H_ */

#ifndef _FAKELOCK_H_

#define _FAKELOCK_H_

class FakeLock

{

public:

FakeLock() {};

virtual ~FakeLock() {};

FakeLock(const FakeLock&) = delete;

FakeLock &operator=(const FakeLock&) = delete;

virtual int lock()

{

while (1L == lock_) {

asm volatile("pause\n" ::: "memory");

}

lock_ = 1L;

return 0;

}

virtual int unlock()

{

lock_ = 0L;

return 0;

}

private:

int64_t lock_;

};

#endif /* _FAKELOCK_H_ */

然而事情没这么简单，因为对这个变量的操作不是原子的，所以会导致这个锁无法正确的运行（即使在单核环境也如此），因此我们需要利用硬件提供的原子操作来实现锁（FYI. 一种不需要原子操作的锁实现方法见前文中提到过的Dekker算法，非常漂亮，但通用性不足）。

除此之外，另一个问题是多核争用的性能问题，这一点我会在后文中提到。

另外由于在用户态实现锁对硬件体系结构提供的一致性保证非常相关，所以必须注明，本文中所有实现针对于x86体系结构（~~也就是acquire-release语义~~TSO内存模型），不具备可移植性。

继续阅读：→

多核并发编程中的cache line对齐问题

先看一段代码：

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

static const int64_t MAX_THREAD_NUM = 128;

static int64_t n          = 0;
static int64_t loop_count = 0;

#pragma pack (1)
struct data
{
  int32_t pad[15];
  int64_t v;
};
#pragma pack ()

static data value __attribute__((aligned(64)));
static int64_t counter[MAX_THREAD_NUM];

void worker(int *cnt)
{
  for (int64_t i = 0; i < loop_count; ++i) {
    const int64_t t = value.v;

    if (t != 0L && t != ~0L) {
      *cnt += 1;
    }

    value.v = ~t;
    asm volatile("" ::: "memory");
  }
}

int main(int argc, char *argv[])
{
  pthread_t threads[MAX_THREAD_NUM];

  /* Check arguments to program*/
  if(argc != 3) {
      fprintf(stderr, "USAGE: %s <threads> <loopcount>\n", argv[0]);
      exit(1);
  }

  /* Parse argument */
  n          = min(atol(argv[1]), MAX_THREAD_NUM);
  loop_count = atol(argv[2]); /* Don't bother with format checking */

  /* Start the threads */
  for (int64_t i = 0L; i < n; ++i) {
    pthread_create(&threads[i], NULL, (void* (*)(void*))worker, &counter[i]);
  }

  int64_t count = 0L;
  for (int64_t i = 0L; i < n; ++i) {
    pthread_join(threads[i], NULL);
    count += counter[i];
  }

  printf("data size: %lu\n", sizeof(value));
  printf("data addr: %lX\n", (unsigned long)&value.v);
  printf("final: %016lX\n", value.v);

  return 0;
}

#include <pthread.h>

#include <stdlib.h>

#include <stdio.h>

#include <algorithm>

using namespace std;

static const int64_t MAX_THREAD_NUM = 128;

static int64_t n = 0;

static int64_t loop_count = 0;

#pragma pack (1)

struct data

{

int32_t pad[15];

int64_t v;

};

#pragma pack ()

static data value __attribute__((aligned(64)));

static int64_t counter[MAX_THREAD_NUM];

void worker(int *cnt)

{

for (int64_t i = 0; i < loop_count; ++i) {

const int64_t t = value.v;

if (t != 0L && t != ~0L) {

*cnt += 1;

}

value.v = ~t;

asm volatile("" ::: "memory");

}

int main(int argc, char *argv[])

{

pthread_t threads[MAX_THREAD_NUM];

/* Check arguments to program*/

if(argc != 3) {

fprintf(stderr, "USAGE: %s <threads> <loopcount>\n", argv[0]);

exit(1);

}

/* Parse argument */

n = min(atol(argv[1]), MAX_THREAD_NUM);

loop_count = atol(argv[2]); /* Don't bother with format checking */

/* Start the threads */

for (int64_t i = 0L; i < n; ++i) {

pthread_create(&threads[i], NULL, (void* (*)(void*))worker, &counter[i]);

}

int64_t count = 0L;

for (int64_t i = 0L; i < n; ++i) {

pthread_join(threads[i], NULL);

count += counter[i];

}

printf("data size: %lu\n", sizeof(value));

printf("data addr: %lX\n", (unsigned long)&value.v);

printf("final: %016lX\n", value.v);

return 0;

}

这段代码的逻辑很简单，开多个线程并行执行一个不断对全局变量取反的操作，你觉得最后的结果会是什么呢？

继续阅读：→

Sequential Consistency，Cache-Coherence及Memory barrier

如今多核CPU在服务器中已经是标配，如何更好的发挥多核CPU进行并行计算相信是每个后端开发都会遇到的难题。这篇文章主要是梳理一下我最近学习的一些关于C++多线程编程的知识。

并发 VS 并行

提到并发编程，有很多不同的编程模型，如多进程、多线程、协程，还可以结合使用I/O多路复用技术来进行异步并发编程，由此产生了很多不同类型的并发编程技巧来解决各类场景下的问题。

其中，协程模型也称为“用户态线程”，在用户态对程序流进行切换，避免了系统上下文切换的开销，属于并发而不是并行的（协程也可以和多进程、多线程模型结合，此处不做探讨），多进程和多线程的编程模型是真正并行的，即多个程序流是真正同时运行的，因此可以更好的利用多核优势，由于多线程之间共用进程地址空间，所以多线程模型相对多进程模型而言可以减少一些进程间的通信开销。

多线程同步

然而，凡事有利必有弊，共用进程地址空间带来了性能上的提高必然也会产生一些复杂的问题，及引入了线程间同步的问题。多个线程如果不加保护的访问共享的变量，必然会引发严重问题，这些在线程间共享的变量被称为“临界区”，最为经典的例子就是多个线程同时对单变量执行递增操作，相信诸位都已经听到耳朵起茧，就不再展开了。

在多线程编程中，常用的同步方式是使用pthread库中提供的线程同步手段（暂不考虑C++11中提供的线程库），如互斥锁、自旋锁、信号量、条件变量等等，但这些方法不是本文的主要内容，因此也不做展开，有兴趣的同学可以自行阅读《UNIX环境高级编程》中关于多线程同步的章节。

PS：在Linux内核中由于内核线程共用内核地址空间，所以内核线程之间也需要使用线程同步机制进行保护，Linux内核中所使用的几种常见同步机制分析见我之前的文章。

继续阅读：→

被误用的“一致性”

想必每个接触过分布式系统的同学都没少看到过“一致性”这个词，但是我最近有一个越来越强烈的感觉：“一致性”这个词已经被严重的误用了，以至于当我看到这个词的时候，我甚至得花些功夫去思考这到底指的是哪个“一致性”，更严重的是，当别人在谈到“一致性”的时候，实际上他们在谈的完全是另一种东西。

无辜的Paxos

故事的起因来源于Paxos（没错，又是这货），网上对于Paxos的文献太多，而且质量参差不齐，在绝大多数的中文文档中，你都可以看到这样的描述：“Paxos是一个分布式强一致性协议”，不瞒你说，每次看到这样的表述的时候，我的内心是崩溃的…且听我慢慢道来。

问题的由来很大一部分原因在于英文对中文的翻译，因此我们必须将术语还原到英文进行讨论，『一致性』对应的英文名词应该是Consistency没错了，然后我们在Lamport大神的原始论文《Paxos Made Simple》中搜索关键词，你会发现：

“Consistency” Not Found

没错，论文中一次都没有提到过Consistency，也就是说，Paxos和『一致性』根本半毛钱关系都没有啊！那Paxos究竟是什么呢？论文中写的很明确——”The Consensus Algorithm”。

PS：本文中所有使用中文“一致”均指Consistency，“共识”为Consensus。

继续阅读：→

分布式共识(Consensus)：Viewstamped Replication、Raft以及Paxos

从上篇文章到现在，已经有半年多的时间没有写过什么了，时间真是匆匆而过，感觉从上次写博客到现在似乎也就是一眨眼的功夫。

回顾我这大半年，完全可以用四个字概括：“不务正业”，先是跟着曼昆的书学习了微观、宏观经济学的基础知识，恶补了一下个人理财的基础理论（很有意思，但依然挡不住我买的基金嗷嗷跌），然后又入坑了摄影（其实就是买个微单瞎拍瞎修）。至于个人的技术提升方面就显得捉襟见肘了，先是跟着斯坦福CS145、CS245两门课程复习了一下数据库方面的知识，然后就在分布式系统的泥沼中挣扎到了现在…可能唯一一件值得纪念的事情就是去年年底抱大牛大腿参加某司举办的hackathon，过程中学到了一点Golang的皮毛，最后搞了个apple watch耍（队友大牛依然表示对结果不太满意…），另外出于对tby大牛的仰慕，又补习了一下前端开发技能，然并卵，已经又忘光了…

一不小心写了一大段流水账，回归主题。之前花了大概两个多月时间从头琢磨分布式系统，研一时候修这门课完全是白学了，本来学的就不好，两年过去基本也不剩什么了。翻了两本最出名的教材，看了一些高校的课程安排和slides，总算感觉自己有点“上道”了~

这篇文章主要总结一下我个人认为是整个分布式系统中最为重要的问题（没有之一）：分布式共识（Consensus）。

达成共识

PS：我在学习过程中是以《分布式系统：概念与设计》¹这本书作为基础的，在下文中如果没有特别指明，所提书中内容均指该书。

继续阅读：→

博弈论笔记:囚徒困境和重复博弈

继续上次的笔记，记录下之前几周课程中我觉得比较有意思的一个问题：大名鼎鼎的囚徒困境（Prisoner’s dilemma）。

囚徒困境

继续阅读：→

博弈论笔记:Normal form game and Nash equilibrium

斯坦福在coursera上的博弈论课程又开放了，这么高大上的课程怎么能错过呢？现在课程已经过半，回过头来对前几周的内容做个小结。

真实的博弈

继续阅读：→

字符串匹配的后缀算法

字符串匹配问题是算法领域的经典问题，C/C++中常用的 strstr函数就是这个问题的定义:

const char* strstr( const char* str, const char* target );
char* strstr( char* str, const char* target );

Finds the first occurrence of the byte string target in the byte string pointed to by str. The terminating null characters are not compared.

在目标字符串 str中寻找是否存在子串 target，字符串 str的长度为\(n\)， target的长度为\(m\)。这个问题最为人所熟知的算法应该是KMP（Knuth-Morris-Pratt）算法，其时间复杂度为\(O(n)\)，想法非常酷。

但是，Can we do better？

继续阅读：→

Kongfy's Blog

good good code, day day up!

无锁队列的一种实现

用户态同步之自旋锁

问题在哪

多核并发编程中的cache line对齐问题

推荐几个不错的VPS

Sequential Consistency，Cache-Coherence及Memory barrier

并发 VS 并行

多线程同步

被误用的“一致性”

无辜的Paxos

分布式共识(Consensus)：Viewstamped Replication、Raft以及Paxos

博弈论笔记:囚徒困境和重复博弈

博弈论笔记:Normal form game and Nash equilibrium

字符串匹配的后缀算法