宇宙湾

如何将 Mac 这个生产工具的效能发挥到极致呢（如何省出一个小长假）？本文将从 Mac 的基础环境配置、Java、Maven、高级命令、工具、快捷键和预先整理相关资源等方面，来阐述如何提升工作效率的。

LeetCode 组队刷题活动

介绍

代码仓库

　代码仓库的坐标：asdf2014 / algorithm

报名途径

　只需要在《Algorithm》文末的评论区，或者在 issues#40 中留言，即可随时参与

参与方式

　每位参与的小伙伴，都会获得代码仓库的 Collaborator 权限，可以自由地提交代码（不限制语种）。在 /Codes/${你的 Github 账号名} 目录下，每人都将拥有一个自己的代码库。留下 Github 名称后，将很快会收到邀请函，大家可以在 asdf2014 - algorithm - invitations 链接中认领（当然，也欢迎直接通过提交 Pull Request 参与进来）。随后，可以在任意目录下（不需要是空目录），使用如下命令，一键完成您的第一次代码提交：

1

bash -c "$(curl -L https://raw.githubusercontent.com/asdf2014/algorithm/master/first_commit.sh)"

刷题频率

　考虑到可能大家的闲暇时间并不多，我们暂定刷题频率为“一周一题”

选题策略

　选题机器人会在每周五晚八点，自动地随机选定一个题目，当前题目点击这里查看。

其他

　操作 Git 时遇到问题的话，可以参考我的一篇博客《Git 高级玩法》

　同时，为了大家更加方便地交流，也欢迎加入算法 QQ 群 或者 Gitter 聊天室

　另外，因为大部分算法都会有很多实现思路，我们会尽可能地展现所有可能的解题方法。但为了文章的排版更加地紧凑，我们会将同一算法的不同实现，通过选项卡的形式展现。且默认展示的选项卡将会是最优解。这样的话，如果您想要快速阅读本文，则可以不用翻看其他的选项卡。实际效果如下：

1
2
3
4
5
6
7
8
9
10
11

def solution(n):
    if n <= 1:
        return n
    a = 0
    b = 1
    while n > 1:
        n = n - 1
        sum_ = a + b
        a = b
        b = sum_
    return b

1
2
3
4
5

def solution(n):
    if n <= 1:
        return n
    else:
        return solution(n - 1) + solution(n - 2)

1
2
3
4
5
6
7
8

def solution(n):
    if n <= 1:
        return n
    cache = [x for x in range(0, n + 1)]
    cache[1] = 1
    for i in range(2, n + 1):
        cache[i] = cache[i - 1] + cache[i - 2]
    return cache[n]

ZooKeeper 是什么？

　ZooKeeper 是一个基于 Google Chubby 论文实现的一款解决分布式数据一致性问题的开源实现，方便了依赖 ZooKeeper 的应用实现 数据发布 / 订阅、负载均衡、服务注册与发现、分布式协调、事件通知、集群管理、Leader 选举、 分布式锁和队列 等功能

基本概念

集群角色

　一般的，在分布式系统中，构成集群的每一台机器都有自己的角色，最为典型的集群模式就是 Master / Slave 主备模式。在该模式中，我们把能够处理所有写操作的机器称为 Master 节点，并把所有通过异步复制方式获取最新数据、提供读服务的机器称为 Slave 节点

　而 ZooKeeper 中，则是引入了 领导者（Leader）、跟随者（Follower）、观察者（Observer） 三种角色 和 领导（Leading）、跟随（Following）、观察（Observing）、寻找（Looking） 等相应的状态。在 ZooKeeper 集群中的通过一种 Leader 选举的过程，来选定某个节点作为 Leader 节点，该节点为客户端提供读和写服务。而 Follower 和 Observer 节点，则都能提供读服务，唯一的区别在于，Observer 机器不参与 Leader 选举过程 和 写操作的"过半写成功"策略，Observer 只会被告知已经 commit 的 proposal。因此 Observer 可以在不影响写性能的情况下提升集群的读性能（详见下文 “性能优化 - 优化策略 - Observer 模式” 部分）

介绍 Apache HBase 的基本概念、环境部署、常用命令、实战技巧、架构设计和性能优化，并记录了一些踩过的坑，及其解决方案。

大数据生态圈中，保证一致性的方式举不胜举

• Hadoop 用 ZooKeeper（Zab，即支持事务顺序的 Paxos）
• ElasticSearch 用 Hash 路由算法（而非一致性 Hash）
• Cassandra 用 Gossip 闲话算法
• Redis 用 Raft 选举算法

他们各有什么区别，为什么会如此选型？

Paxos 选举算法

　Paxos 是最先解决拜占庭将军问题的算法，利用过半选举的机制，保证了集群数据副本的一致性（微服务中服务注册与发现的场景，其实已经不再适用了）

Raft 选举算法

　Redis 使用 Raft 实现了自己的分布式一致性。Raft 本身和 Paxos 并没有场景上的区别。更多的是，协议上的简化、Term 概念的强化、Log 只会从 Leader 到 Follower 单向同步，使得实现起来会很方便

Zab 原子广播协议

　Hadoop 偏向于离线的海量数据处理，利用 ZooKeeper 来保证数据副本的一致性，是最为合适的

Hash 路由算法

　ElasticSearch 集群接收到为文档创建索引的请求时，需要选择在哪一个 shard（完整且独立的 Lucene 索引实例）上对文档进行索引。ElasticSearch 采用的是 djb2 哈希算法（俗称 times33），对要索引文档默认或指定的 key 进行哈希 hash(key)，然后再对 ElasticSearch 集群中 shard 的数量 n 进行取模，即 $hash(key) \, mod \, n$

一致性 Hash

　用于对数据存储进行负载均衡的算法。最新的进展，是在去年 Google 发表的一篇 有界负载的一致性 Hash 算法的论文。该算法保证了负载均衡一致性和稳定性的同时，在均匀性方面做出了实质性地改进。同时，Consistent Hashing with Bounded Loads 算法 也在 HaProxy 开源项目中得以应用，有效减少了其 8 倍的缓存带宽

Gossip 闲话算法

　Gossip 主要被 Cassandra 用于实现其分布式一致性。因为 Cassandra 框架，更看重 去中心化 和 容错 的特性，在不违背 CAP 定理的情况下，能够接受 最终一致性