idea's blog

我的前一篇博客文章"谈谈Facebook的聊天系统架构", 对Facebook的聊天系统架构进行了分析. 其中的有些思想和系统划分, 对即使不是做聊天系统, 如一般的网站系统, 也是很有借鉴意义的. 例如其中的在线状态服务器(Presence).

在线状态服务, 是这样的一个服务, 它维护了网站当前的在线用户列表, 接受其它模块的查询. 是实现统计网站同时在线人数, 维护在线用户列表等功能的基础服务. 在Facebook的聊天系统中, 在线状态是为聊天系统服务的, 所以在线状态是一种"强"在线, 也即用户保持着和Comet服务器的连接, 可随时接受服务器推送(push)的消息.

Continue reading »

今天看到一份 Facebook 公司 2009 年的 Slideshow, 介绍它的聊天系统架构, 其中的一张图结构非常清晰, 所以我对这张图谈谈我的看法.

Continue reading »

虽然拥有主从同步结构, 甚至是多主多从的同步结构, SSDB仍然是一个单机存储数据库系统, 所以SSDB天生适合存储1TB以内的数据. 如果数据可以静态分布, SSDB当然可以存储无限的数据量. 当然, 这样的SSDB并不是一个集群, 也不是一个严格意义上的分布式存储系统, 统一入口是集群的最基本特征.

"一致性哈希"常常被认为是分布式存储系统的一个重要概念, 事实上, 它只是一个可选的九牛一毛而已. 分布式存储要解决的重要问题不是数据如何分布, 而是如何保证数据迁移对用户不可见.

当一个区间(r1, r2)内的数据在从S1存储点向S2存储点迁移的过程, 处于这个区间的数据的读写会涉及到定位的问题. 读问题其实很好解决, 把迁移分为复制和删除两个步骤, 那么就可以保证在复制过程中还是从S1读取. 写问题也是类似, 但要复制得多, S1必须保证复制过程中的所有写操作都被同步(sync)到S2.

在区间内数据被删除后, S1再接收到读或者写请求时, 应该返回一个out-of-range(oor)错误, 并redirect到S2, 这时客户端可以更新寻址表然后重试.

另外, 迁移完成后, 应该由S1进行报告, S2无权进行报告, 而只能被动地接受通知区间的变化. 也就是说, 虽然S2知道自己已经接收了区间内的数据, 但S1仍然可以在这时取消迁移.

写硬盘

为了持久化, 必须写硬盘.

Log 文件

为了快速写入硬盘, 必须采用追加方式顺序写到 log 文件. 这导致 log 文件中的数据是无序的.

sst 文件

为了快速从硬盘中读取数据, 基于查找算法和局部性原理考虑, 必须将数据排序组织到 sst 文件中.

多个 sst 文件而不是单个

为了快速的插入数据到 sst 文件中, 必须使用多个 sst 文件, 每个 sst 文件只保存一定范围的数据. 堆.

Levels

为了减少 log 文件合并所影响的 sst 文件个数, 将 sst 按层次组织, 层次越深, 文件数量越多. 最坏的情况, 每一次合并都会修改该层次所有的 sst 文件. 而层次越深, 合并发生的概率越小. 树.

Bloom Filter

由于 LevelDB 在某一层查找不存在的数据时, 会继续在下一层进行查找, 所以对于不存在的数据的查找会速度非常慢. 所以, 需要结合 Bloom Filter, 利用 Bloom Filter 能快速地判定"不存在"的特点.

推荐阅读: Leveldb 实现原理

最近, 我在 review 组员的 Python 代码时, 发现了一个递归调用, 我立即发现了其中的问题.

先说一下编程中递归. 只有会用递归, 并且能随心应手地写出递归程序的程序员, 才是已经入门了的程序员. 不过, 许多程序员并没有发现编程中的递归的一个限制: recursion depth limit, 逻辑上的递归可以无次数限制, 但语言执行器或者程序堆栈会限制递归的次数.

例如一个 Cpy 编程语言(用 C 语法写 Python 代码)例子:

function func(i){
    if(i < 1000000){
        try{
            func(i + 1);
        }catch(Exception e){
            print 'maximum recursion depth exceeded', i;
            print e;
            return;
        }
    }
}

func(1);

因为 Python 语言有递归次数的限制, 试验结果是 997 次.

sys.setrecursionlimit( limit) 

而 C 语言的限制, 是程序堆栈的大小限制, 超过之后, 会产生 stack overflow. 比如下面这个 C 语言的例子在我的环境下只递归了 511 次:

void func(int i){
    int buf[1000];
    if(i < 100000){
        printf("depth = %d\n", i);
        func(i + 1);
    }
}

int main(int argc, char **argv){
    func(1);
    return 0;
}

再回到最先开始提到的, 我 review 发现的例子, 我为什么能一眼就发现那个递归有问题呢. 因为, 那段代码是一段按行分析文本的程序, 当发现某一行不符合条件时, 程序会递归调用分析函数递归地分析下一行. 显然, 如果连续 997 行文本不符合条件, Python 程序就会崩溃退出了.

在 360 游戏, 我们每天要产生数亿条数据, 而且这个数据量每天都在增长, 其中包括用户的充值记录, 游戏数据, 各种行为等等. 如何高效地分析和挖掘这些海量数据是一个非常大的挑战.

我们首先遇到了数据的生产问题. 如何生产所需要的数据, 同时不影响主业务流程? 我们分为前端生产和后端生产. 不敏感的数据主要由前端生产, 而敏感的数据由后端生产. 而生产的方式也有多种, Web Server 的访问日志, 各个模块和子系统的访问日志, 主动增加的业务日志等等.

第二个问题是数据的汇总. 我们的服务器不是简单的一台, 而是多个机房的服务器组, 如何及时地将所有日志汇总? 我们使用了 Linux 自带的 syslog, 由 syslog 组成一个分布式日志系统, 最终日志被汇总到中心节点组.

Continue reading »