最近有兴致，想看点中国经济的书，受朋友推荐知道这本书。在微信读书上用差不多一周的时间赶着读完，虽然囫囵吞枣，倒也酣畅淋漓。以前看过吴晓波《激荡三十年》的一些章节，本书算是后传，风格一致，但是读起来会更有共鸣，因为这也正是初代九零后我们的人生中的黄金十年。作为“渐有意识”的亲历者，回放感很强。
吴晓波很擅长宏大叙事和情绪铺垫，在本书中全景式的再现了 2008~2018 这十年间中国经济和企业的波澜起伏。书名“水大鱼大”乍一看很俗，看完后细想，倒也形象。市场和企业的关系，正是鱼和水的关系——水大容纳了鱼的成长厮杀，鱼大成就了水的鲜活壮阔。
这十年也是我从懵懂少年到步入青年的一个人生阶段。作为这段经济史的亲身经历者，对于其间的很多现象，有的没太留意，有的不得其解。作者以类似编年体的方式，以更高维的视角，紧扣时空二象，将各种线头有机的组织在一块，并带出了一些当时不广为人知的秘辛。通过这些冰山之下的暗线，让我们在重新审视这段历史时，隐隐然摸到了一些脉络。
西奥迪尼在影响力方面对我的影响，其他任何科学家都比不上…… 这本畅销书呈现了六至八种方法，让你古怪精灵的想法不会再阻碍你获得最佳利益。 ——查理·芒格，巴菲特黄金搭档
人类都有一些思维定势或固有模式，一经触发会使我们就像被按下了播放键，之后的行为便可能不受我们控制。其实这些都是源于人类避免思考的趋势。避免思考在人类原始时期确实给人类带来了不少好处，比如它能节省时间，减轻犹豫不决带来的危及生命的后果。但现在，避免思考的本能也恰恰成了最容易被顺从专家们利用的地方。
其实，不管是那种顺从手法，其应对的核心方法都是一个——思考。首先要从情绪中脱离出来，其次要想清楚自己真正想要的是什么，把表象和实质区分开。
Bw-tree 是 2013 年微软发表的相关论文提出的数据结构。考虑到多核机器和 SSD 日趋普及，结合两大存储引擎 B+-tree 和 LSM-tree 特点，提出了一种 latch-free、delta update、log structured 的 B族树 —— Bw-tree。
由于上述论文在实现细节上语焉不详，cmu 几个作者在 2015 年时实现了一版基于内存的 Bw-tree，然后又发表了一篇论文，补充了一些实现上的细节，并将代码开源在了 github 上，称为 open bwtree。
例行地总结下（太长不看版），Bw tree 的主要特点有：
在技术领域中，分布式系统越来越成为绕不过去的一个名词。原因在于，这个时代的数据尺度与单机存储、处理能力的不匹配。于是有两条路子：机器大型化和机器互联。前者成本高昂且不灵活，于是后者越来越受青睐。根据代价守恒定律，代价不会凭空消失，硬件成本降下来了，软件设计成本便会提升。而分布式系统理论，则是帮我们降低这个软件成本的钥匙。
分布式系统奠基者 Leslie Lamport [1] 在其最重要的论文之一 ”Time, Clocks, and the Ordering of Events in a Distributed System“ [2] 中提到：
A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process.
Lamport 是用类似相对论的思想来阐释这个问题。我们考虑两个时间尺度：进程间消息传递延迟和进程内事件间隔，如果前者相对后者不可忽略，则这组进程就是一个分布式系统。
理解这个定义，需要理解几个重要的概念（形式化的定义总是这样，摊手）：进程（process）、消息（message）和事件（event）。为了避免套娃，这里不做过多展开，仅给出一个形象的理解：进程就是一个负责干活的劳工，其干的活可以分解为多个步骤，每个步骤就是一个事件，消息便是劳工交流的方式。
这也印证了维基百科中 distributed computing [3]（分布式系统又称分布式计算）给的定义：
这里面涉及到了计算机系统中最重的几种资源：计算（computational），存储（memory），以及沟通他们的网络（network）。
总结下，我们可以从另一个角度来对分布式系统进行描述：
对外，分布式系统表现为一个整体，基于总体的存储和计算能力，提供特定功能。
对内，分布式系统表现为一组个体，基于网络消息进行通信，分工合作。
而分布式系统的设计目标是，最大化整体资源利用率的同时，处理局部错误、保持对外可用性。
Facebook TAO[1] ，即 The Associations and Objects 的缩写，点（对象，Object）和边（联结，Associations）是”图“中最基本的抽象，用来做 Facebook 图存储名字倒是恰如其分。
概括来说，TAO 是 Facebook 为了解决社交场景下，超大数据的更新与关联读取问题，其核心特点如下：
分布式系统有很多经典的套路，也即设计模式。每个设计模式可以解决经典的一类问题，积累的多了，便可以稍加变化，进行取舍，设计出贴合需求的架构组织。但似乎大家在这方面经验分享的不太多，因此之后打算总结一些工作和学习的经验，既是备忘，也希望对大家有些助益。篇幅所限、能力所囿，难以面面俱到，又或疏于精确。不当之处，欢迎指正。
每篇将以概述背景、架构模块、总结延伸来分别解析，本篇是第一篇：Master-Workers 架构。
Master-Workers 架构（粗译为主从架构）是分布式系统中常见的一种组织方式，如 GFS 中的 Master、ChunkServers；MapReduce 中的 Master、Workers。面对分布式系统中一堆分离的机器资源，主从架构是一种最自然、直白的组织方式——就像一群人，有个说了算 leader 进行组织、协调，才能最大化这群人的对外输出能力。
这也是计算机系统中常见的一种分而治之思想的体现。即将一个复杂的系统，拆解成几个相对高内聚、低耦合的子模块，定义清楚其功能边界和交互接口，使得系统易于理解、维护和扩展。对于主从架构来说，主（Master） 通常会维护集群元信息、进而依靠这些元信息进行调度，从（Workers） 通常负责具体数据切片（存储系统）的读写或者作为子任务（计算系统）的执行单元。
Paxos 是分布式系统中绕不过去的一个算法，但出了名的难以理解。因此我看到 Paxos 也是一直绕着走，但是绕的多了总感觉有些遗憾。于是过去一周闲暇时间搜集了很多资料，尝试了很多打开方式，总算初窥门径。便趁着新鲜，将脑中的理解赶到纸上，做个小结，以备后日不时之需。
Paxos 算法的发明人 Leslie Lamport 是分布式系统的奠基人之一，轶事颇多，从 Paxos 这个名字也能窥得一斑：Paxos 是 Lamport 为了引出分布式系统共识问题，所虚拟的一个古希腊城邦。在最初的相关论文 The Part-Time Parliament 发表于 1998 年后，很多人都表示理解不能。于是 Lamport 在 2001 年，又使用相对简练的语言和逻辑，将其主干思想重新阐述了一遍，便有了 Paxos made simple。
Lamport 在 Paxos made simple 论文的摘要只有一句话：
The Paxos algorithm, when presented in plain English, is very simple
然而，我却无法理解这种 simple。
本篇要介绍 Patrick Hunt 等人在 2010 年发表的、至今仍然广泛使用的、定位于分布式系统协调组件的论文 —— ZooKeeper: Wait-free coordination for Internet-scale systems。我们在多线程、多进程编程时，免不了进行同步和互斥，常见手段有共享内存、消息队列、锁、信号量等等。而在分布式系统中，不同组件间必然也需要类似的协调手段，于是 Zookeeper 应运而生。配合客户端库，Zookeeper 可以提供动态参数配置（configuration metadata）、分布式锁、共享寄存器（shared register）、服务发现、集群关系（group membership）、多节点选主（leader election）等一系列分布式系统的协调服务。
总体来看，Zookeeper 有以下特点：
时下，随着通信技术的发展、移动互联网的普及、物联网车联网人工智能的兴起，每天所产生的数据呈爆炸性的增长。这种尺度的数据不是传统单机系统可以独立处理的，而只能借助于大规模的分布式系统，因而分布式系统渐渐的变成一门“显学”。而作为一个分布式系统初学者，面对网上未加归类、浩如烟海的学习资料，很容易两眼抓瞎。
但分布式系统有其基本研究内容和独特发展脉络，比如：
因此只需要在“时空”两个维度对分布式系统进行把握，就能提纲挈领，愈学愈明。“时”表示分布式系统的演进脉络，可以通过阅读不同时期、学术界工业界的一些论文来把握。“空”表示分布式系统中所研究的基本问题的拆解，可以通过阅读一些书籍建立分布式系统的知识体系。本文将我在学习分布式系统知识过程搜集到的一些资料，按类别简单汇总，以飨诸君。资料排名没有先后，请按需采用。
注：文中推荐的资料大多为英文，如果阅读有困难，推荐使用 Chrome 浏览器，并且给 Chrome 装一个 “google 翻译”的插件，可以点击一键“翻译此页面”。
早对 LevelDB 有所耳闻，这次心血来潮结合一些资料粗略过了遍代码，果然名不虚传。如果你对存储感兴趣、如果你想优雅使用 C++、如果你想学习如何架构项目，都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看过一遍如果不输出点什么，以我的记性，定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙，但又不想走寻常路：从架构概览说起，以模块分析做合。读代码的这些天，一直在盘算从哪下笔比较好。在将将读完之时，印象最深的反而是 LevelDB 的各种精妙的数据结构：贴合场景、从头构建、剪裁得当、代码精到。不妨， LevelDB 系列就从这些边边角角的小构件开始吧。
本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构，分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第三篇，LRUCache。
LRU 是工程中多见的一个数据结构，常用于缓存场景。近年来，LRU 也是面试中一道炙手可热的考题，一来工程用的多，二来代码量较少，三来涉及的数据结构也很典型。LeetCode 中有一道相应的题目：lru-cache。相对实际场景，题目进行了简化：本质上要求维护一个按访问时间有序的 kv 集合，且 kv 皆是整数。经典解法是使用一个哈希表（unordered_map）和一个双向链表，哈希表解决索引问题，双向链表维护访问顺序。这是我当时的一个解法，特点是用了两个辅助函数，并且可以返回节点自身，以支持链式调用，从而简化了代码。
说回 LevelDB 源码，作为一个工业品，它使用 的 LRUCache 又做了哪些优化和变动呢？下面让我们一块来拆解下 LevelDB 中使用的 LRUCache，看看有什么不同。
本文首先明确 LRUCache 的使用方法，然后总览分析 LRUCache 的实现思路，最后详述相关数据结构的实现细节。
强行凑出来的五一小长假即将结束，一年一度的朋友圈晒图大赛又将起航。虽然手机自带的图片自动润色功能越来越强大，但毕竟不能满足我们程序员想掌控一切的精细化调整需求。下面就我一些浅薄的调色经验，以我在长沙游天心阁玩拍的一张图片的调色过程为例，教你一套李鬼变李逵的风景调色屠龙技。最后会给一个简单的修图原理的总结，一探图片调色背后的本质。
为了说明图片调色确实有奇效，先上一个对比图给大家直观感受下：
此图摄于老长沙制高点——天心阁。是日乌云密布，暴雨将至，从天心阁二层远眺，黄瓦蓝天，车水马龙，一动一静，似有雷霆之势。
下面分步骤讲解下调色过程和原理，尽量简洁一点，并且附上参考资料，留给有兴趣深挖的同学。
