• Feeds

  • 为什么超长列表数据的翻页技术实现复杂(二)

    上文为什么超长列表数据的翻页技术实现复杂提到了超长列表翻页技术设计上一些问题,今天讨论下部分解决思路。

    前新浪同事 @pi1ot 最近在程序员杂志发表的一篇文章《门户级UGC系统的技术进化路线》也是超长列表的一个经典案例,在正式展开思路之前,我们也不妨了解一下此文所说新浪评论系统的演进思路。

    从文中看到几个版本的列表翻页实现方案

    3.0版

    3.0系统的缓存模块设计的比较巧妙,以显示页面为单位缓存数据,因为评论页面是依照提交时间降序排列,每新增一条新评论,所有帖子都需要向下移动一位,所以缓存格式设计为每两页数据一个文件,前后相邻的两个文件有一页的数据重复,最新的缓存文件通常情况下不满两页数据。

    此方案由于每页的条数是定长的,因此主要采用缓存所有列表的方案。但为了数据更新的便利,缓存结构比较复杂。从今天多年之后的眼光来看,这种设计不利于理解、扩展及维护。因此目前大多不倾向使用这种方案。

    4.0版

    解决方案是在MySQL数据库和页面缓存模块之间,新建一个带索引的数据文件层,每条新闻的所有评论都单独保存在一个索引文件和一个数据文件中,期望通过把对数据库单一表文件的读写操作,分解为文件系统上互不干涉可并发执行的读写操作,来提高系统并发处理能力。在新的索引数据模块中,查询评论总数、追加评论、更新评论状态都是针对性优化过的高效率操作。从这时候起,MySQL数据库就降到了只提供归档备份和内部管理查询的角色,不再直接承载任何用户更新和查询请求了。

    使用自定义索引的方式,由于未与相关人员交流细节,推断应该是类似数组的结构。

    从上述案例看到,评论系统是一种典型的超长列表数据结构,如果再MySQL的基础上来做,需要设计额外的索引结构来实现高效的翻页功能

    由于超长列表的翻页实现成本高主要是由于列表索引的B-TREE结构方面原因,B-TREE结构能快速查找到某个key,但不是为叶子节点的Range访问而设计,因此主要解决思路也是围绕B-TREE的range访问而进行优化。

    首先、从原理来看,可以在B-TREE增加以下2个二级索引字段:

    • Count index 记录每个非叶子节点下的条目数,这样可以帮助快速定位到任意的offset;
    • Offset index 记录部分叶子节点的offset,比如每隔1000个id记录一个offset如下,并保存在另外一个列表中,当需要查找某个offset的时候,则可以利用附近已经记录offset的id来定位目的地位置。比如当翻页到1010时,如果offset index记录了[1000: id10345],则可以从id10345往后10个元素找到10010。
    [
    {"1000":10345},
    {"2000":13456},
    {"3000":22345},
    {"4000":56789},
    {"5000":66788}
    ]
    

    这2个字段可以同时使用,也可以只用其中一个。如图
    btree-index

    再看如何将上述方法应用到具体的实现中。由于本文主要讨论MySQL环境,MySQL要在B-TREE上额外保存一些信息需要修改MySQL源代码,修改门槛较高,因此更简单方法是将上述二级索引通过应用层保存在另外的表中。

    一种非严格意义的count index实现如下:

    CREATE TABLE IF NOT EXISTS `second_index` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `uid` int(11) NOT NULL,
      `yymm` int(11) NOT NULL,
      `index_count` int(11) NOT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB  DEFAULT CHARSET=utf8;
    
    
    INSERT INTO `second_index` (`id`, `uid`, `yymm`, `index_count`) VALUES
    (1, 1, 1409, 123),
    (2, 1, 1410, 2342),
    (3, 1, 1411, 534),
    (4, 1, 1412, 784),
    (5, 1, 1501, 845);
    

    一种offset index实现如下:
    在第一次用户翻页到某个offset位置时,在redis直接保存offset, id。当有其他请求来查找offset之后数据时,可以从offset的位置往后扫描。如果列表的数据发生了变化,需要及时将Redis保存的offset index删除。

    以上2种方法已经在生产环境使用。

    @icycrystal4对此文所提方法亦有贡献。

    我为什么选择DigitalOcean VPS来做开发

    工程师在开发过程中经常需要下载及实时访问国外各种软件及服务,比如从github下载软件及在Linux上运行docker等软件,通常会在本机创建虚拟机或者通过一些公共的测试服务器来进行,我为什么选择付费的DigitalOcean来当做自己的开发环境? 本文介绍DigitalOcean相对于自建服务器及其他VPS如Linode的优势。

    先说一个案例,一个月前某工程师说,“看了你写的kubernetes文章后,我也打算试下”。最近再碰到他时,他很惭愧的说,“试了好多次,还没跑通”。在国内运行各种常用开发软件确实存在访问国外云服务及各种软件的问题,一方面速度慢,另外也存在不少资源莫名其妙就被墙了,因此更推荐大家使用国外的VPS来进行日常的学习及测试。因此给大家介绍Tim日常使用DigitalOcean(简称DO)的一些便利之处。

    1. 虽然大家所在公司也都有公共测试服务器,但是使用这些资源通常面临多人共同使用的冲突;独占的服务器通常需要领导审批,也存在随时被业务征用走的情况。而在自己工作电脑创建虚拟机则由于占用资源较大,影响本身工作环境效率。使用云主机创建帐号开通一个虚拟机只需要几秒钟,不会出现启动的服务被人停掉的困扰。
    2. DigitalOcean是经过Tim比较后一种性价比非常高的VPS,它的特点是全SSD存储,费用低,比同类型的云服务及VPS如Linode更便宜。按小时计费,基本款每天开24小时只需要1.04元人民币。如果只开1小时,则只收费1小时,不到1毛钱。
    3. 与Linode相比,稳定性基本相当,Tim的博客从Linode迁移到DigitalOcean已经有半年以上,没碰到过稳定性方面问题。
      清华大学的梁斌博士比较了大量VPS之后也称赞digitalocean

      最近try了很多厂商的vps,一个体会,凡是没有名气的,大多比较渣。而且有个特点,只卖小机器,不卖多cpu,大内存的,很显然小机器好超卖啊。整个vps提供商比较业界良心的也就linode和digital ocean了,他们是把这事当事业在做的。

    4. DigitalOcean支持CoreOS,CoreOS是一种天生为容器而设计的Linux发行版,由于CoreOS没有包管理工具,无法直接安装各种应用,所有的功能推荐用容器来实现,因此可以帮助大家在测试Docker环境时更好理解容器化理念、更好的分清宿主机与容器的边界、更好的理解分布式的容器及服务。DigitalOcean自带了较新版本的CoreOS,利用CoreOS自带的docker,创建虚拟机后1分钟内就可以完成下载镜像及启动容器的工作。
    5. DO的网速很快,可极大提升工作效率,在DigitalOcean美国机房访问github等资源基本上一回车就下载完了,从docker registry拉一个200M的unbutu镜像只要数秒。而国内访问大部分技术资源速度比较慢,比如CoreOS默认是在线安装方式,在国内装CoreOS要2小时以上;从Docker registry下载一个ubuntu image也需要20分钟左右。
    6. 建议使用以下推荐链接 https://www.digitalocean.com/?refcode=b5d7cd2d0410 来注册用户,当你使用及付费后,Tim可以获得一杯咖啡左右的推荐费的好处,你可以获得$10的奖励费用,相当免费使用2个月。

    PS:给那些申请成功的同学:

    1、CoreOS默认的用户名不是你的 ssh-key 指定的用户或 root,而是 core,因此使用以下命令登录。
    ssh -i ssh-key-file core@ip
    2、Droplet在服务器不启动时可能也会收费,如果是测试用途,长时间不用前建议将Droplet删除,以免产生额外费用。

    3、DO美国机房从国内SSH访问会有丢包的情况,可以尝试MOSH来代替SSH,也可以选择新加坡机房。

    4、DO的文档也非常丰富,英文熟练的同学可以参看 tutorials

    一个技术从业人员眼中的2014

    年轻的同学喜欢按学习曲线来看自己过去的每一年,但是这种方式很快就会步入到瓶颈,学习曲线增长突然会变得缓慢。在2013年圣诞节时,Tim还在每天花上10-30分钟玩一款叫Clash of Clans的游戏,并邀请身边的朋友都加入了部落,当时每天的升级成长也很快。但不知道从哪一天开始,发觉升级越来越慢了,需要2周或者更长时间才能将一些对象升级,所以慢慢的对其失去了成就感、耐心与好奇心。

    工程师对于技术的关系也是如此,刚接触第一门编程语言时候,对每一个细节充满了好奇心,发现一种新的语法糖也会兴奋不已。当使用这些技能之后,慢慢的发现工作中只会重复的使用其中20%左右的领域,就这样月复一月的过着。当然学习的习惯还继续保留,工作之外的东西也会去看看其他一些东西,比如花一周学习媒体炒得火热的Swift语言。但较常见的情况是,大家学的这些新潮技术工作中一般不会立即使用,几个月之后Swift怎么写可能一点也不记得了。几次类似经历之后,当再有新的某项技术出来,如果看不到有使用的需要,你已经不打算再学了。毕竟花很大力气学会某项东西,又注定在几个月后会忘记,这种做无用功的感觉很不好。因此最终学习曲线会停滞在某个点。

    前几年在新年来临之际Tim也会去给一些技术媒体投稿,彻夜不眠写出一篇技术圈宏大的总结与展望,希望能给从业人员指出一条明路。但是这种凭借个人视野有感而写出来的东西,最终指导不了自己也指导不了别人。技术领域太广太深,即使图灵奖得主也很难去评论另外一个专业领域未来一年的发展趋势,能看到的各种预测无非是主流媒体的观点汇集而已。于是后来就不写(也不看)这种总结展望了。尽管技术领域内盲从的心理还是非常显著,很需要这种指南类的东西(比“干货”受欢迎多了)。

    在2014年日常感悟比较多的,就是对昨天文章技术团队的标准化与可复用文化所说的技术群体里面的无序感到有些悲观。当一个低级问题,第一次解决时,你会感受到成就;第二次解决时,你感受到责任,第三次解决时,你可能更多的感受到无力。当你观察一个小的团队时时,这些情况不会明显;但当你把目光聚焦在一个稍大的团队,比如50人以上时,这种问题会更容易发现。

    有人倡导自组织团队,包括各级大佬BOSS们也给我们指出这是前进的方向,但是完全具有自组织特征的团队不是很容易见到。Tim身边更多情况是靠各级管理者强有力的执行力去推动。想想如果没有领导的角色可以自运作起来,还是很有挑战的一件事情。当然挑战不包括各种技术大会的那些敏捷教练们。

    开源这个词有些滥用,我个人去评价一个项目时候更多的是看它解决的问题以及带来的价值。国内业界的问题不是开源不够,而是能创造价值的软件太少。单纯去讨论开源运动我觉得和讨论”跑步运动“或者”站立办公“没什么区别,虽然我也尝试站立办公,但是我觉得没必要天天挂在嘴上。

    运营开源最重要的是社区(指贡献你项目代码的群体),先是有了社区,然后有了你的开源project。否则你的项目最多会成为一个带源代码的一款工具软件。经常的误区是一些人觉得将内部的一堆不再维护的代码上传到github上,然后就期望一夜成名,或觉得船到桥头自然直,这就有点naive了。

    虽然大数据很热,但是我认可大部分engineering方向的工程师不适合做大数据这个观点。不是说这些人不够聪明,而是当你已经25岁左右时候,你已经用了3-5年“最好的编程语言”之后,来决定踏入大数据算法这道门,时机有些晚了。大数据的算法是稍微和计算机科学的“科学”二字最搭边的一门学科,这个算法和CS学的那些快速排序算法有很大的区别,通常这些半路进入的engineering类的工程师,最终的天花板可能是一个数据统计工程师或者是协同过滤工程师。即便如此,一代又一代工程类的技术人员义无反顾走了进去,经过半年一年狂热的学习之后,在一些大BOSS不理解的岗位上默默的发挥着作用,并坚信自己已经是迈向金矿的康庄大道上。大部分没有Critical thinking sense的工程师,习惯在因与果之间用“自然而然”推理并联系起来,比如“只要我进一步学好大数据算法,自然而然,就能挖到金矿”。

    2013年元旦时候也写了一篇谈分享、创新与开源,和目前想法也有些明显的区别。