• 2013-01-14

    LevelDB 的原理和动机

    Views: 23079 | 1 Comment

    写硬盘

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

    Log 文件

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

    sst 文件

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

    多个 sst 文件而不是单个

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

    Levels

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

    Bloom Filter

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

    推荐阅读: Leveldb 实现原理

    Posted by ideawu at 2013-01-14 08:39:29 Tags: ,
  • 2012-08-11

    小心递归次数限制

    Views: 16746 | 3 Comments

    最近, 我在 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 程序就会崩溃退出了.

    Posted by ideawu at 2012-08-11 13:51:36 Tags:
  • 2012-07-29

    海量游戏数据的即时分析和挖掘

    Views: 8875 | 2 Comments

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

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

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

    Continue reading »

    Posted by ideawu at 2012-07-29 18:00:15
  • 2012-07-29

    动态语言应该有多动态?

    Views: 19434 | 12 Comments

    一加一等于几, 这是个问题

    某些所谓的动态语言是名不副实的 - 我称之为伪动态语言. 这些伪动态语言之所以是伪的, 是因为它们只是在代码层面的变量是动态的, 而它们的类型系统并不是真正动态的, 一个简单的例子, 考虑字符串能否直接和整数进行拼接成为一个新的字符串.

    当然, 语言维护者用另一个名词"类型强度(type strength)"来表示这种行为, 然后把这种本质上不动态的行为称为"强类型(strong typing)", 把真正的动态称为"弱类型(weak typing)".

    但我认为, "动态语言"的概念应该重新定义, "动态"应该脱离字面的意义, 去探究真正本质的动态.

    Continue reading »

    Posted by ideawu at 01:00:33
  • 2012-07-26

    流式数据的模型设计

    Views: 8743 | No Comments

    流式数据是指带有时间点参数的数值数据. 例如在某个网站的 PV 统计中, 有整个网站的 PV 统计, 也有分不同子域名的统计, 而这个统计数据可能每小时统计一次, 同时每天统计一次. 而在不同的子域名下, 又有不同的功能模块的统计, 如论坛子域名下的发贴 PV, 回复 PV, 等等.

    显然, 这类的数据还有至少一个维度, 表明这条数据的产生条件(或者说产生地点), 这样, 数据才有了实际意义. 维度是有序的, 子域名维度必须在网站维度之下, 因为要先有了网站, 子域名才有意义. 每一条数据的维度可以这样表示: /dim1=v1/dim2=v2/... 表示该条数据在 dim1 维度下的值是 v1, 在 dim2 维度下的值是 v2, ...

    数据还要有一个统计方法, 如pv, uv.

    Posted by ideawu at 2012-07-26 22:37:53
  • 2012-07-17

    Redis 导数据的 PHP 脚本

    Views: 12983 | 2 Comments

    Redis 本身没提供方便的导数据工具, 比如从某个 db 导数据到另一个 db, 只能自己写脚本了. redis copy.

    <?php
    
    $from = '127.0.0.1:6200/6';
    $to = '127.0.0.1:6200/8';
    
    $from_redis = redis_init($from);
    $to_redis = redis_init($to);
    
    
    $keys = $from_redis->keys('*');
    $count = 0;
    $total = count($keys);
    foreach($keys as $key){
        if(++$count % 100 == 1){
            echo "$count/$total\n";
        }
        $type = $from_redis->type($key);
        switch($type){
            case Redis::REDIS_STRING:
                $val = $from_redis->get($key);
                $to_redis->set($key, $val);
                break;
            case Redis::REDIS_LIST:
                $list = $from_redis->lRange($key, 0, -1);
                foreach($list as $val){
                    $to_redis->rPush($key, $val);
                }
                break;
            case Redis::REDIS_HASH:
                $hash = $from_redis->hGetAll($key);
                $to_redis->hMSet($key, $hash);
                break;
            case Redis::REDIS_ZSET:
                $zset = $from_redis->zRange($key, 0, -1, true);
                foreach($zset as $val=>$score){
                    $to_redis->zAdd($key, $score, $val);
                }
                break;
        }
    }
    
    
    function redis_init($conf){
        $redis = new Redis();
        preg_match('/^([^:]+)(:[0-9]+)?\\/(.+)?/', $conf, $ms);
        $host = $ms[1];
        $port = trim($ms[2], ':');
        $db = $ms[3];
        $redis->connect($host, $port, 1000);
        $redis->select($db);
        return $redis;
    }
    
    Posted by ideawu at 2012-07-17 12:10:52 Tags:
|<<<123456789>>>| 4/11 Pages, 61 Results.