存储中的文件合并策略优化

系统中的所有数据以block 存放, 2个block中可能包含大量的重复文件, 这时我们需要找出这2个block, 将其合并,

问题: 如何高效的(在时间上和空间上) 找出具有大量重复文件的block对.

假设:

  • 每个block的文件数 n = 1000万
  • 单个文件名长度: l = 512 字节
  • hash-bitmap 大小 64 * 10^6 = 8MB
  • min-hash bucket数量 b = 128

各种算法的开销如下

算法\开销 空间开销 实际空间 时间开销
fn-list O(n x l) 5GB O(n x l)
hash-bitmap O(n) 8MB O(n)
min-hash O(1) 1KB O(1)
continue reading>>

伽罗

好吧, 我承认考试期间没有好好复习, 偷懒去画画了. 估计会挂.

continue reading>>

小龙女

李若彤版的小龙女, 美到不真实.

从中学开始在课桌上画她;

就像喜欢的歌会要唱出来, 想用心情去控制每个音符;

像喜欢的人要说出来, 想把每一点滴的爱慕用最贴切的字词表达出来;

喜欢的人的颜色, 一定要用自己的画笔, 拿捏它的每个细节, 才会觉得她完全属于了自己.

continue reading>>

软件工程是个面包机

我们平时印象中的面包机是这个样子的:

烤面包机属于加热电器。其功能是在面包片附近生成足够的热量,以便对面包进行烘烤

面包机的原理非常的简单, 有个开关控制通电, 通过电热来加热, 这些基本的原理普通的中学生都知道, 也都能在wikipedia上找到. 这么简单的东西…

如果我们要亲手制作一个面包机, 需要花费多久呢?

话说, 英国有个叫Thomas Thwaites 的艺术家, 几年前, 花了9个月的时间做了一个面包机.

恩…没错, 9个月!

如果依赖现代社会的完善体系, 这件事情是很简单的,

之所以花费了这么久, 是因为他没有使用现成的零件, 一切都是从头开始制作的!

我们看看他到底怎么完成的:

continue reading>>

程序员必须知道的事情, 一般人我不告诉他

  • 软件开发里所有的东西都已经发明出来了! 人们总是在做重复的事情, 假装在发明新的东西. 如果有个东西让你觉得很酷很新, 那它肯定是从Smalltalk, HAKMEM, Ivan Sutherland, Douglas Engelbart, 早期的IBM, 或者Bell 实验室其中之一抄来的.
continue reading>>

cgexec 无法继承 LD_PRELOAD 环境变量

continue reading>>

mysql group replication实践记录: 步骤, 问题和注意事项

continue reading>>

枚举所有整勾股数

勾股数可以写成 $ x^2 - y^2, 2xy, x^2 + y^2 $ 的形式, 因为 $ (x^2 - y^2)^2 + (2xy)^2 = (x^2 + y^2)^2 $

结论1: 如果x, y是互质整数, 则一组 x, y 对应一组互质整勾股数 a, b, c.

continue reading>>

ansible中的include, include_tasks 和 import_tasks 的差别

include 被deprecated了. 建议使用include_tasksimport_tasks.

  • include_tasks 是动态的: 在运行时展开. when只应用一次. 被include的文件名可以使用变量.

  • import_tasks 是静态的: 在加载时展开. when在被import的文件里的每个task, 都会重新检查一次. 因为是加载时展开的, 文件名的变量不能是动态设定的.

    When using static includes, ensure that any variables used in their names are defined in vars/vars_files or extra-vars passed in from the command line. Static includes cannot use variables from inventory sources like group or host vars.

continue reading>>

python 并发subprocess.Popen的坑

一个父进程里多个线程并发地调用subprocess.Popen来创建子进程的时候, 会有几率出现Popen长时间不返回的情况.

这个问题是由于fd被多个子进程同时继承导致的.

重现问题的代码

下面这个小程序启动2个线程, 每个线程各自(通过subprocess.Popen)启动一个子进程, 一个子进程执行echo 1后就直接返回; 另一个子进程启动后, sleep 0.03秒后返回.

程序里统计了2个调用Popen花的时间, 运行后可以发现, echo的进程有时启动很快(小于预期的0.01秒, 仅仅是启动, 不包括执行时间), 有时会很慢(超过0.03秒), 刚好和另一个sleep的进程执行时间吻合. 调大sleep子进程的时间可以看到echo也会同样有几率返回慢.

continue reading>>

程序员必读: 摸清hash表的脾性

hash表中key的分布规律

当hash表中key和bucket数量一样时(n/b=1):

  • 37% 的桶是空的.
  • 37% 的桶里只有1个key.
  • 26% 的桶里有1个以上的key(hash冲突).

下面这个图更直观的展示了当n=b=20的时候, hash表中每个bucket中key的个数的分布, (我们按照key的数量对bucket做了排序):

continue reading>>

python 进程内存增长问题, 解决方法和工具

表现

运行环境:

# uname -a
Linux ** 3.10.0-327.el7.x86_64 #1 SMP Thu Nov 19 22:10:57 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

# python2 --version
Python 2.7.5

# cat /etc/*-release
CentOS Linux release 7.2.1511 (Core)
continue reading>>

xp的分布式系统系列教程之: Erasure-Code: 工作原理, 数学解释, 实践和分析.

文字版: Erasure-Code: 工作原理, 数学解释, 实践和分析

continue reading>>

xp的分布式系统系列教程之: Erasure-Code: 工作原理, 数学解释, 实践和分析.

内容简介

Erasure-Code, 简称 EC, 也叫做 擦除码纠删码, 指使用 范德蒙(Vandermonde) 矩阵的 里德-所罗门码(Reed-Solomon) 擦除码算法.

EC 本身是1组数据冗余和恢复的算法的统称.

本文以 Vandermonde 矩阵的 Reed-Solomon 来解释 EC 的原理.

术语定义:

  • $d_j$ 表示数据块.
  • $y_i$ 表示通过数据块计算得来的, 作为数据冗余的校验块.
  • $u_j$ 表示丢失的, 需要恢复的数据块.
  • k 表示数据块的数量.
  • m 表示校验块的数量.
continue reading>>

可靠分布式系统基础 Paxos 的直观解释

Paxos 已经逐渐被承认是分布式系统中不可缺少的核心算法, 越来越多的分布式系统都是以paxos或其变种来达到强一致性的.

本文是一篇paxos入门教程, 从基本的分布式中的问题: 主从复制,quorum-rw等算法出发, 通过逐步解决和完善这几个问题, 最后推导出paxos的算法.

本文分为2个部分:

  • 前1部分是分布式一致性问题的讨论和解决方案的逐步完善, 用比较通俗的语言得出paxos算法的过程. 如果你只希望理解paxos而不打算花太多时间深入细节, 只阅读这1部分就可以啦.

  • 第2部分是paxos算法和协议的严格描述. 这部分可以作为paxos原paper的实现部分的概括. 如果你打算实现自己的paxos或类似协议, 需要仔细了解协议细节, 希望这部分内容可以帮你节省阅读原paper的时间.

continue reading>>

socket关闭: close()和shutdown()的差异

对于一个tcp连接,在c语言里一般有2种方法可以将其关闭:

close(sock_fd);

或者

shutdown(sock_fd, ...);
continue reading>>

随手改变世界之 git-auto-squash

使用git的同学是不是经常纠结于在开发过程中是应该频繁提交, 还是仔细构造提交点之后再提交?

  • 前者可以让开发更流畅,不必打断思路,但会造成提交历史无法浏览;
  • 后者可以构造漂亮易懂的提交历史,但码码时停下来考虑commit message 怎么造句是不是太影响情绪了。

一般的做法是先做很多小的fixup,之后再将fixup合并到一起。

这个工具 git-auto-squash 可以将提交历史中连续的fixup 合并到它之前最早的1个正式提交点上,类似不需要交互的rebase --interactive

continue reading>>

Numbers Programmers Should Know About Hash

There is a hash table:

  • It has b buckets.
  • It has n keys stored in it.
  • We assume that the hash function distributes keys uniformly.
  • A bucket can contain more than 1 keys.

If n b, the hash table would look like this:

  • 37% buckets are empty.
  • 37% buckets contain 1 key.
  • 26% buckets contain more than 1 key, which means collision occurs.

The following chart created by program simulation shows distribution of 20 keys over 20 buckets.

continue reading>>

Vim-tabbar: Simple, stupid and fast tab-bar for VIM

Simple, stupid and fast tab-bar for VIM.

continue reading>>

1% 慢请求优化

1个客户端同时向服务器发出100个请求,等待所有的请求都返回才算成功。
99%的请求10ms返回,1%的请求1000ms返回.

假设慢请求的概率是 ,请求总数是 . 能快速(10ms)返回的概率有多少?如何优化?

continue reading>>