木鸟杂记

概览

首先说下 BLOB 的意思， 英文全称是 Binary Large OBjects，可以理解为任意二进制格式的大对象；在 Facebook 的语境下，也就是用户在账户里上传的的图片，视频以及文档等数据，这些数据具有一次创建，多次读取，不会修改，偶尔删除 的特点。

之前简单翻译了 Facebook 的前驱之作 —— Haystack，随着业务量发展，数据量进一步增大，过去玩法又不转了，如果所有 BLOG 都用 Haystack 存，由于其三备份的实现，在这个量级下，性价比很低。但是完全用网络挂载+传统磁盘+Unix-like（POSIX）文件系统等冷存储，读取跟不上。于是计算机科学中最常用的分而治之的思想登场了。

他们首先统计了 BLOBs 的访问频次与创建时间的关系，然后提出了随着时间推移 BLOB 访问出现的冷热分布概念（和长尾效应差不多）。并据此提出了热、温分开的访问策略：用 HayStack 当做热存储去应对那些频繁访问的流量，然后用 F4 去响应剩下的不那么频繁访问的 BLOB流量，在此假设（F4只存储那些基本不怎么变动，访问量相对不大的数据）前提下，可以大大简化 F4 的设计。当然有个专门的路由层于两者之上进行了屏蔽，并进行决策和路由。

对于 Haystack 来说，从其论文出来时，已经过去了七年（07~14）。相对于当时，做了少许更新，比如说去掉了 Flag 位，在 data file，Index file 之外，增加了 journal file，专门用来记录被删除的 BLOB 条目。

对于 F4 来说，主要设计目的在于保证容错的前提下尽可能的减小有效冗余倍数（effective-replication-factor），以应对日益增长的温数据 存取需求。此外更加模块化，可扩展性更好，即能以加机器方式平滑扩展应对数据的不断增长。

我总结一下，本论文主要高光点就是温热分开，冗余编码，异地取或。

概览

Haystack 的基本思想就是将索引信息放在内存中，避免额外的IO。为了做到这一点，主要进行了两方面的设计：

1. 将小文件集合成大文件，减少文件数，从而减少了元信息的数目。
2. 精简文件元信息，去掉一切在 Facebook 场景中不需要的 POSIX 语义中元信息。

这样就可以将数据元信息减小到一个内存可以放的下的量级，基本上每次每次数据访问同一个一次 IO 就可以完成，而非以前的好几次。

绪论

使用 Logging 前可以先捋一下我们常见的日志输出需求，俗话说，不管需求的设计就是耍流氓。

1. 能够定位事件（Event）的产生位置（代码文件&行数）和生成时间，用于调试和跟踪。
2. 一份日志可以同时送到多个目标输出。
3. 可以通过不同级别或者更精细条件筛选日志输出。
4. 可以方便的控制第三方模块的日志输出。
5. 实现上面的一切的前提下，配置/设置 尽量简单。

Python 的 Logging 模块通过神奇的模块化设计，树形的方式组织完美的实现了以上五点。

引言

某次在用到 Python 的 socketserver 时，看到了 ForkingMixIn 和 ThreadingMixIn。当时就对这种插件式语法糖感觉很神奇。最近自己写代码，也想写一些这种即插即用的插件代码，于是对 python 的 mix-in 机制探究了一番。

简单来说它是利用多继承的特性，通过插拔额外代码片段，对原类进行花样式增强的一种技术。

小引

以前学 js 的时候第一次见到闭包，当时不甚了了，还为了应付面试强行记住了一个模棱两可的“定义”：在函数中嵌套定义函数，并且在外层将内层函数返回，一同返回了外层函数的环境。当时从字面意思以及当时一个经典例子试图去理解闭包，加之”闭包”这个翻译也很不容易让人味出其中的道理，导致对其总感觉懵懵懂懂。最近工作需要，用起 python，又遇到闭包，这次看到了一些新奇有趣的资料，这才算大致把一些字面上的概念（first-class functions，bind，scope等等）贯通在一起，反过来对闭包有了更深的理解。

引用资料列在最后，十分推荐大家去读读。

hexo 博客搭建

今年新年愿望之一，督促自己每周写博客。作为一个新的开始，打扫屋子清爽一番是我的一贯风格。加上感觉jeklly 引擎不怎么好使，就想换个新的引擎 hexo。去年注意到越来越多的博客开始用这个引擎，于是关注了下，感觉的确不错（主题，模式等等），说干就干。想着作为科班出身，看别人教程多low，于是直接看官方文档开搞，当然了，坑是不可避免的，下面来聊一下。

前言

上一次在做完 lab2a 即 raft 的 leader 选举之后，一直卡在日志同步这一块（log replication）；直到昨晚进行了一下 appendEntries 的优化（prevLog 不匹配时，一下跳过本 term 所有 logEntries），一直困扰的 TestBackup2B 竟然神奇 Passed 的了。跑了两遍还不大信，特地将其改回去，看到果然 Fail 才放心下来，看来是效率太低超时了。

趁着还新鲜，索性今晚就将这一段时间的血泪史记下来吧。

概述

记录下在实现6.824 lab2 raft 的一些想法和经验，聊以备忘。

实验概述

6.824是MIT的一门分布式课程，我跟的是2018 spring 。在第二个实验中要求简单实现一个分布式一致性协议–raft。

这是一个专为方便教学和工程实现所设计的协议，它将协议拆解为几个相对独立的模块–leader选举，log复制，安全保证。论文里图二基本给出了Raft的所有实现细节，可谓字字珠玑。但也因为太微言大义了，导致有些状态转换分散在不同描述中，假如你真只照着这幅图实现，很容易遗漏些细节。

概述

以前对二分查找的认识只停留在有序数组查找给定整数上，后来发现一类问题都可以用二分的思想来做，概括来说就是：如果要求的结果所在的集合（值域）和要搜索的数的集合（定义域）存在单调（映射）关系，就可以通过二分思想来解决，说起来有点抽象，后面将用几个例子来说明。

二分思想以其每次迭代将规模砍一半的效率，有着极其广阔的应用。

本文分两大部分，第一部分对二分查找的各个细节探讨；第二部分拓展二分查找为一般的二分思想。

概述

梳理一下MapReduce框架涉及到的一些基本接口和类。

概述

最近在琢磨关于树的非递归遍历的一些思路和对应的实现，写在这里，聊以备忘。

问题

在进行模块化的时候，试图将诸如SearchListener, CallManager 的模块从MainActivity中拆出来，然而在响应事件的时候，不可避免的需要改变其他资源状态，那么就需要获取其句柄。由此还需要把MainActivity作为句柄传入代码。