并发级别

蓝色是阻塞的算法，绿色是非阻塞算法，金字塔越上方，并发级别越高，性能越好，右边的金字塔是实现工具（原子操作、锁、互斥体等）

Wait-freedom 无等待并发

每一个线程都一直运行下去而无须等待外部条件，整个流程中任何操作都能在一个有限的步骤内完成，这是最高的并发级别，没有任何阻塞。可以简单认为能够直接调用一个原子操作实现的算法或程序就属于Wait-free，例如：

1
2
3
4
5

// 多个线程可以同时调用这个函数对同一个内存变量进行自增，而无须任何阻塞
//（其实也是有阻塞的，是总线锁级别）
void increment_reference_counter(rc_base* obj) { 
atomic_increment(obj->rc);
}

Lock-freedom 无锁并发

整个系统作为一个整体一直运行下去，系统内部单个线程某段时间内可能会饥饿，这是比wait-freedom弱的并发级别，但系统整体上看依然是没有阻塞的。所有wait-free的算法显然都满足lock-free的要求。通常可以通过同步原语CAS实现, 例如：

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

void stack_push(stack* s, node* n)
{
    node* head;
    do
    {
        head = s->head;
        n->next = head;
    }
    while (!atomic_compare_exchange(s->head, head, n)); 
    // atomic_compare_exchange如果内存位置的s->head值和head相等则s->head的值设置成n
}

// increment_reference_counter的lock-free实现，某些线程可能会因为CAS失败而回绕若干次循环
void increment_reference_counter(rc_base* obj)
{
       Int rc;
       do {
       	rc = obj->rc;
		} while(!atomic_compare_exchange(obj->rc,rc,rc+1));

}

Obstruction-freedom 无阻塞并发

指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行，一旦共享数据被修改，Obstruction-free 要求中止已经完成的部分操作，并进行回滚，obstruction-free 是并发级别更低的非阻塞并发，该算法在不出现冲突性操作的情况下提供单线程式的执行进度保证，所有 Lock-Free 的算法都是 Obstruction-free 的。

Blocking algoithms 阻塞并发

可以简单认为基于锁的实现是blocking的算法。Lock-based 和 Lockless-based 两者之间的区别仅仅是加锁粒度的不同。Lock-based方案就是大家经常使用的 mutex 和 semaphore 等方案，代码复杂度低，但运行效率也最低。

CAS原语

CAS原语负责将某处内存地址的值（1 个字节）与一个期望值进行比较，如果相等，则将该内存地址处的值替换为新值

1
2
3
4

do{ 
       备份旧数据；
       基于旧数据构造新数据；
}while(!CAS( 内存地址，备份的旧数据，新数据 ))

当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的 commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

HDFS

HDFS 从设计上来说，主要考虑以下的特征：超大文件，最大能支持 PB 级别的数据；流式数据访问，一次写入，多次读取；在不可靠的文件，故障率高的商用硬件上能运行。Hadoop 的不利之处，是不适应低时间延迟的数据访问，不适应大量的小文件，也不适应多用户写入任意修改文件的情况。

NameNode 是 HDFS 的管理者, 存储着整个集群的元数据信息，比如所有文件和目录信息等。HDFS 将大文件分割成数据块，每个数据块是 64M，也可以设置成 128M或者 256M，然后将这些数据块以普通文件的形式存放到数据节点上，为了防止 DataNode 意外失效，HDFS 会将每个数据块复制若干份放到不同的数据节点。

HDFS能够存储TB甚至PB规模的数据是有前提的，首先数据要以大文件为主，其次NameNode的内存要足够大。当元数据信息较多时，NameNode的启动会变得很慢，也比较容易触发GC操作。显然当数据到了一定的量级，元数据管理会成为HDFS的一个瓶颈，其实这也是为什么说它适合存储大文件的原因。如果解决了元数据管理的问题，其实HDFS是可以支撑海量小文件的。

HDFS-Client

HDFS-VFS

VFS 是Linux 内核和真正文件系统之间的抽象层，它提供统一的接口，真正的文件系统和 Linxu 内核必须通过 VFS 的接口进行沟通。内核的 I\O 路径是这样的：user space -> VFS -> FS -> I\O layer -> I\O scheduler(optional) -> block_driver -> block_device, 一个 I\O 经过了这些才真正到达了对应的存储上。一个用户态的系统调用先通过 VFS 找到对应的文件系统再向下传递 I\O，这是 I\O 的一般路径。对于用户来说，一切都是操作文件。

Hadoop VFS兼容层，可以把HDFS当作一个标准的文件系统mount到本地的Linux文件系统上。这样用户便可以使用标准Unix命令，例如“ls”、“cd”、“cp”、“mkdir”、“find”、“grep”等，来操作一个hdfs的实例；也可以使用标准POSIX的开发库，例如C、C++、Python、Perl、JAVA、bash等的打开、写、读、关闭方法来操作一个hdfs的实例。

HDFS-VFS特性

• 最好情况下，单线程读速度能达100MB/s，写速度能达70MB/s
• 不支持tail –f、chown、chgrp、make、link、mmap命令，以及pwrite等随机写函数
• 不要在HDFS挂载点目录下执行scp、wget等会在当前路径下创建临时文件的操作

如何从零开始造个云存储系统？

单硬盘扩展成RAID磁盘阵列，再从单机RAID扩展到集群多机器，再到引入副本存储提高可靠性，再到引入一致性哈希进行动态扩展，再到跨机房多AZ备份和CDN区域加速。

如何实现靠谱的分布式锁？

分布式锁是用来控制分布式系统中互斥访问共享资源的一种手段(进程之间共享资源)，避免多线程并行访问导致结果不可控。基本的实现原理和单进程锁是一致的，通过一个共享标识来确定唯一性，对共享标识进行修改时能够保证原子性和和对锁服务调用方的可见性。由于分布式环境需要考虑各种异常因素，为实现一个靠谱的分布式锁服务引入了一定的复杂度。

分布式锁一般需要能够保证以下几点：

1. 同一时刻只能有一个线程持有锁

2. 锁能够可重入

3. 不会发生死锁

4. 具备阻塞锁特性，且能够及时从阻塞状态被唤醒

5. 锁服务保证高性能和高可用

6. 锁数据本身的安全性

基于 Redis 实现的锁服务

1. 加锁：SETNX key value资源不存在时才能够成功执行 set 操作，用于保证锁持有者的唯一性；同时设置过期时间用于防止死锁；记录锁的持有者，用于防止解锁时解掉了不符合预期的锁。
2. 解锁：只需要删除这个key就可以了，不过删除之前需要判断，这个key对应的value是当初自己设置的那个
3. Lua脚本对比解锁者是否所有者、解锁是一个原子操作
4. 通过过期时间PX millisecond来避免死锁，时间选择很关键
5. Redis 的主从异步复制机制可能丢失数据，造成 A、B 两个线程并发访问同一个资源

基于 ZooKeeper 实现的锁服务

1. 加锁是线程去zookeeper上的某个指定节点的目录下创建一个唯一的临时有序节点，确定当前线程创建节点序号是否最小，是则加锁成功；否则去序列中寻找并监听序号较小的前一个节点。当监听到这个节点被删除了，那就再去判断一次自己当初创建的节点是否变成了序列中最小的。如果是，则获取锁，如果不是，则重复上述步骤。
2. 解锁流程是删除当前线程创建的临时接点。

基于数据库实现的锁服务

1. 乐观锁机制：表中每条记录添加version字段，每次更新操作需要CAS
2. 悲观锁机制：在Mysql中是基于 for update 来实现加锁的

如何实现分布式文件系？

分布式文件系统是分布式领域的一个基础应用，其中最著名的毫无疑问是 HDFS/GFS。

DFS特性要求

• 符合 POSIX 的文件接口标准，兼容易用
• 对用户透明，能够像使用本地文件系统那样直接使用
• 持久化，保证数据不会丢失
• 具有伸缩性，当数据压力逐渐增长时能顺利水平扩容
• 具有可靠的安全机制，保证数据安全

• 数据一致性，只要文件内容不发生变化，什么时候去读，得到的内容应该都是一样的

• 支持的空间越大越好

• 支持的并发访问请求越多越好
• 性能越快越好
• 硬件资源的利用率越高越合理，就越好

DFS架构

从业务模型和逻辑架构上，分布式文件系统需要这几类组件：

• 存储组件：负责存储文件数据，它要保证文件的持久化、副本间数据一致、数据块的分配 / 合并等等；
• 管理组件：负责 meta 信息，即文件数据的元信息，包括文件存放在哪台服务器上、文件大小、权限等，除此之外，还要负责对存储组件的管理，包括存储组件所在的服务器是否正常存活、是否需要数据迁移等；
• 接口组件：提供接口服务给应用使用，形态包括 SDK(Java/C/C++ 等)、CLI 命令行终端、以及支持 FUSE 挂载机制。

GFS —- 有中心节点

中心节点负责文件定位、维护文件 meta 信息、故障检测、数据迁移等管理控制的职能。一般中心节点并不参与真正的数据读写，而是将文件 meta 信息返回给 Client 之后，即由 Client 与数据节点直接通信。其主要目的是降低中心节点的负载，防止其成为瓶颈。这种有中心节点的方案，在各种存储类系统中得到了广泛应用，因为中心节点易控制、功能强大。

Ceph —- 无中心节点

每个节点都是自治的、自管理的，整个 ceph 集群只包含一类节点 —- RADOS 就是 ceph 定义的“同时包含 meta 数据和文件数据”的节点。无中心化的最大优点是解决了中心节点自身的瓶颈，这也就是 ceph 号称可以无限向上扩容的原因。CRUSH算法解决meta查找数据位置的问题

内部DFS

原来大量使用SAS磁盘和Raid卡。SAS盘+Raid的成本直逼SSD，但性能比SSD有数量级的落后。如果这些业务 把状态从本地磁盘转移到分布式文件系统，则不再依赖本地磁盘的可靠性，不再需要SAS盘和Raid卡。因此诞生了NFS。

NFS提供Posix接口，支持随机写操作，并针对这种访问模式做了大量的 优化工作；而AFS提供API访问接口，不支持文件的随机写操作。因此两者没有替代关系。从长远来看，NFS和AFS会长期并存，独立发展，不存在谁取代谁的关系。不仅如此，在实现上，NFS是AFS的底层，AFS自身的元信息，是存储在下层的NFS集群的。因此NFS除了继续提供Posix访问接口，取代本地硬盘这一目标外，还会进一步优化可用性。

持久化数据

• 如何保证每个副本的数据是一致的? 同步写入或者W+R>N 的方式
• 如何分散副本，以使灾难发生时，不至于所有副本都被损坏? 两地三中心
• 怎么检测被损坏或数据过期的副本，以及如何处理?
  • 如果有中心节点，则数据节点定期和中心节点进行通信，汇报自己的数据块的相关信息，中心节点将其与自己维护的信息进行对比
  • 如果没有中心节点，以 ceph 为例，它在自己的节点集群中维护了一个比较小的 monitor 集群，数据节点向这个 monitor 集群汇报自己的情况，由其来判定是否被损坏或过期
  • FailOver机制
• 该返回哪个副本给 Client? round-robin、速度最快的节点、成功率最高的节点、CPU 资源最空闲的节点、甚至就固定选第一个作为主节点，也可以选择离自己最近的一个

存储节点的伸缩性

• 如何尽量使各存储节点的负载相对均衡?
• 怎样保证新加入的节点，不会因短期负载压力过大而崩塌? 预热时间
• 如果需要数据迁移，那如何使其对业务层透明?

中心节点的伸缩性

HDFS 的数据块的大小是 64M，ceph 的的数据块的大小是 4M，都远远超过单机文件系统的 4k。它的意义在于大幅减少 meta data 的数量，使中心节点的单机内存就能够支持足够多的磁盘空间 meta 信息

中心节点的高可用

当前内存服务 + 日志文件持久化是主流方式。为了解决日志文件会随着时间增长越来越大的问题，以让系统能以尽快启动和恢复，需要辅助以内存快照的方式——定期将内存 dump 保存，只保留在 dump 时刻之后的日志文件

万兆网卡每秒传输大约 1250M 字节的数据，而 SATA 磁盘的读写速度这些年基本达到瓶颈，在 300-500M/s 附近。

安全性

主流文件系统的权限模型：DAC、MAC、RBAC

面向小文件的分布式文件系统

主流的实现方式是仍然是以大数据块的形式存储，小文件以逻辑存储的方式存在，即文件 meta 信息记录其是在哪个大数据块上，以及在该数据块上的 offset 和 length 是多少，形成一个逻辑上的独立文件。这样既复用了大数据块系统的优势和技术积累，又减少了 meta 信息。

文件指纹和去重

文件指纹就是根据文件内容，经过算法，计算出文件的唯一标识。如果两个文件的指纹相同，则文件内容相同。在使用网络云盘的时候，发现有时候上传文件非常地快，就是文件指纹发挥作用。云盘服务商通过判断该文件的指纹，发现之前已经有人上传过了，则不需要真的上传该文件，只要增加一个引用即可。在文件系统中，通过文件指纹可以用来去重、也可以用来判断文件内容是否损坏、或者对比文件副本内容是否一致，是一个基础组件。指纹算法有md5、sha256、simhash 和 minhash

1. 问题描述：并发20个线程，每个线程使用一个单独的BosClient去执行5G文件的PUT/GET操作，并比较下载文件和原文件的MD5，发现偶尔出现文件MD5对不上，文件大小大于5G的情况的情况，出现几率大概1%；
2. 问题定位：
   • 查看sdk日志和BOS日志，发现该情况下client发送了2次GET请求，第一次返回200但是err msg是PartialContentError
   • 进一步查看nginx error log发现是客户端主动关闭了连接，可能是因为TCP连接超时等原因导致client主动关闭连接
   • 但是从client日只看并没有触发重试机制，那么多出来的GET请求可能就是sdk用到的http库主动发起的
3. 问题原因：
   • 定位发现sdk引用了第三方库rest-client，rest-client又引用了ruby语言自带的net::http库来发起http请求
   • 查看net::http库源码发现，默认自带了一次重试机制；重试时不会对重置读取到的body stream，而是会继续追加写，导致文件大小大于5G
   • Net::HTTP read_timeout causes double requests

4. 解决方案：
   net::http库默认重试一次的机制不合理，因此有用户提出了bug，建议retry次数可配置Net::HTTP retries idempotent requests once after a timeout, but its not configurable；AWS ruby sdk也发现了这一问题，提交了PR，不过要到ruby 2.5版本才支持直接设置重试次数。考虑到版本向下兼容问题，我们采取monkey patching的方式来解决这一问题，两个思路：

   • 方案一：第二次重试的时候将body stream重置到起始位置

     module Net
     class HTTP
     def transport_request(req)
           count = 0
           begin
             begin_transport req
             res = catch(:response) {
               req.exec @socket, @curr_http_version, edit_path(req.path)
               begin
                 res = HTTPResponse.read_new(@socket)
                 res.decode_content = req.decode_content
               end while res.kind_of?(HTTPContinue)
               res.uri = req.uri
               res
             }
             res.reading_body(@socket, req.response_body_permitted?) {
               yield res if block_given?
             }
           rescue Net::OpenTimeout
             raise
           rescue Net::ReadTimeout, IOError, EOFError,
                  Errno::ECONNRESET, Errno::ECONNABORTED, Errno::EPIPE,
                  # avoid a dependency on OpenSSL
                  defined?(OpenSSL::SSL) ? OpenSSL::SSL::SSLError : IOError,
                  Timeout::Error => exception
             if count == 0 && IDEMPOTENT_METHODS_.include?(req.method)
               count += 1
               @socket.close if @socket and not @socket.closed?
               D "Conn close because of error #{exception}, and retry"
               // 添加重置body_stream操作
               if req.body_stream
                 if req.body_stream.respond_to?(:rewind)
                   req.body_stream.rewind
                 else
                   raise
                 end
               end
               retry
             end
             D "Conn close because of error #{exception}"
             @socket.close if @socket and not @socket.closed?
             raise
           end
           end_transport req, res
           res
         rescue => exception
           D "Conn close because of error #{exception}"
           @socket.close if @socket and not @socket.closed?
           raise exception
         end
     end
     end
     

   • 方案二：去除重试机制，删掉retry语句

5. 参考链接

   • What is the purpose of monkey patching global HTTP stack?
   • Update Net::HTTP patching for Ruby 2.5 #1756
   • AWS猴子补丁
   • 各版本Ruby http.rb源码

内存管理

堆与栈

Go语言与CPP类似，也有栈和堆的概念，栈就是函数使用的栈，函数局部变量都在栈里，而new出来的变量大部分在堆上，当然这还取决于变量是会在作用域外被使用(注：编译器通过静态分析技术Escape Analysis来确定变量的作用范围)。

堆内存管理机制

Go的内存管理是基于tcmalloc实现的，tcmalloc核心思想是多级缓存、定长分配和管理.

参考文章

Golang内存管理

垃圾回收GC

常用GC算法

Golang的三色标注-清除法

Golang 垃圾回收剖析

Unlike GHC’s stop-the-world collector, Go’s collector runs concurrently with the program to achieve short GC pauses.it means that the pause times become a scheduling problem.

In practice, the pause times of these phases to be <1ms with very large heaps. With a concurrent GC, there is also potential for running the GC in parallel on multiple processors.

Low latency has costs. The most important cost is reduced throughput. Concurrency requires extra work for synchronization and duplication, which eats into the time the program can be doing useful work. GHC’s garbage collector is optimized for throughput, but Go’s is optimized for latency. At Pusher, we care about latency, so this is an excellent tradeoff for us.

A second cost of concurrent garbage collection is unpredictable heap growth. The program can allocate arbitrary amounts of memory while the GC is running. This means the GC must be run before the heap reaches the target maximum size.

GC times tend to be proportional to the number of pointers rather than the number of bytes. we would expect pauses of around 1ms for our heap size of 200MB, according to the go team. The heap size is kept large, which is important because the heap must be traversed in order to detect which objects are still referenced. This is why GC running time is proportional to the number of live objects/pointers between them.

go tool trace observe gc phase state.

参考链接

1. ptmalloc/tcmalloc/jemalloc内存分配策略
2. Golang’s Real-time GC in Theory and Practice
3. Recycling memory buffers in Go