• Feeds

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

    今天讨论了一个传统的问题,问题本身比较简单,就是针对key-list类型的数据,如何优化方案做到性能与成本的tradeoff。Key-list在用户类型的产品中非常普遍,如一个用户的好友关系 {“uid”:{1,2,3,4,5}},表示uid包含有5个好友;一条微博下面的评论id列表{“weibo_id”: {comment_id1, comment_id2……}},一个用户发表的微博id列表等。

    在list长度较少时候,我们可以直接的使用数据库的翻页功能,如

    SELECT * FROM LIST_TABLE LIMIT offset, row_count;
    

    根据经验,在大部分场景下,单个业务的list数据长度99%在1000条以下,在数据规模较小时候,上面的方法非常适合。但剩下的1%的数据可能多达100万条,我们把这种单个列表记录数非常大的数据集合称为超长列表。在超长列表中,当访问offset较大的数据,上述方法非常低效(可参看Why does MYSQL higher LIMIT offset slow the query down?),但在实现方案的时候不能忽视这些超长列表的问题,因此要实现一个适合各种变长list的翻页方案,考虑到数据的长尾问题,并没有简单高效的方案。这也体现了常说的80%的时间在优化20%的功能。

    List数据访问模型常见的有两种方式

    1. 扶梯方式
    扶梯方式在导航上通常只提供上一页/下一页这两种模式,部分产品甚至不提供上一页功能,只提供一种“更多/more”的方式,也有下拉自动加载更多的方式,在技术上都可以归纳成扶梯方式。
    navbar
    (图:blogspot的导航条)


    (图:很多瀑布流式的产品只提供一个more的导航条)

    扶梯方式在技术实现上比较简单及高效,根据当前页最后一条的偏移往后获取一页即可,在MySQL可使用以下方法实现。

    SELECT * FROM LIST_TABLE WHERE id > offset_id LIMIT n;
    

    由于where条件中指定了位置,因此算法复杂度是O(log n)

    2. 电梯方式
    另外一种数据获取方式在产品上体现成精确的翻页方式,如1,2,3……n,同时在导航上也可以由用户输入直达n页。国内大部分产品经理对电梯方式有特殊的喜好,如图
    pagination by page
    (图:timyang.net 网站的导航条)

    但电梯方式在技术实现上相对成本较高,当使用以下SQL时

    SELECT * FROM LIST_TABLE LIMIT offset, row_count;
    

    我们可以使用MySQL explain来分析,从下文可以看到,当offset=10000时候,实际上MySQL也扫描了10000行记录。
    explain limit

    为什么会这样?在MySQL中,索引通常是b-tree方式(但存储引擎如InnoDB实际是b+tree),如图
    b+tree
    从图中可以看到,使用电梯方式时候,当用户指定翻到第n页时候,并没有直接方法寻址到该位置,而是需要从第一楼逐个count,scan到count*page时候,获取数据才真正开始,所以导致效率不高。对应的算法复杂度是O(n),n指offset,也就是page*count。

    另外Offset并不能有效的缓存,这是由于
    1、在数据存在新增及删除的情况下,只要有一条变化,原先的楼层可能会全部发生变化。在一个用户并发访问的场景,频繁变化的场景比较常见。
    2、电梯使用比较离散,可能一个20万条的list,用户使用了一次电梯直达100楼之后就走了,这样即使缓存100楼之下全部数据也不能得到有效利用。

    以上描述的场景属于单机版本,在数据规模较大时候,互联网系统通常使用分库的方式来保存,实现方法更为复杂。
    在面向用户的产品中,数据分片通常会将同一用户的数据存在相同的分区,以便更有效率的获取当前用户的数据。如下图所示
    shard uid
    (图:数据按用户uid进行hash拆分)

    图中的不同年份的数据的格子是逻辑概念,实际上同一用户的数据是保存在一张表中。因此方案在常见的使用场景中存在很大不足,大部分产品用户只访问最近产生的数据,历史的数据只有极小的概率被访问到,因此同一个区域内部的数据访问是非常不均匀,如图中2014年生成的属于热数据,2012年以前的属于冷数据,只有极低的概率被访问到。但为了承担红色部分的访问,数据库通常需要高速昂贵的设备如SSD,因此上面方案所有的数据都需要存在SSD设备中,即使这些数据已经不被访问。

    简单的解决方案是按时间远近将数据进行进一步分区,如图。
    shard time

    注意在上图中使用时间方式sharding之后,在一个时间分区内,也需要用前一种方案将数据进行sharding,因为一个时间片区通常也无法用一台服务器容纳。

    上面的方案较好的解决了具体场景对于key list访问性能及成本的tradeoff,但是它存在以下不足

    • 数据按时间进行滚动无法全自动,需要较多人为介入或干预
    • 数据时间维度需要根据访问数据及模型进行精巧的设计,如果希望实现一个公用的key-list服务来存储所有业务的数据,这个公用服务可能很难实现
    • 为了实现电梯直达功能,需要增加额外的二级索引,比如2013年某用户总共有多少条记录

    由于以上问题,尤其是二级索引的引入,显然它不是理想中的key list实现,后文继续介绍适合超长列表翻页key list设计的一些思路及尝试。

    Kubernetes – Google分布式容器技术初体验

    Kubernetes是Google开源的容器集群管理系统。前几天写的 分布式服务框架的4项特性 中提到一个良好的分布式服务框架需要实现

    服务的配置管理。包括服务发现、负载均衡及服务依赖管理。
    服务之间的调度及生命周期管理。

    由于Kubernetes包含了上述部分特性,加上最近Google新推出的Container Engine也是基于Kubernetes基础上实现,因此最近对Kubernetes进行了一些尝试与体验。

    运行环境

    Kubernetes目前处于一个快速迭代的阶段,同时它的相关生态圈(比如docker,etcd)也在快速发展,这也意味没有适合新手使用非常顺畅的版本,网上的各种文档(也包括官方文档)和当前最新的发布版会有不同程度滞后或不适用的情况,因此在使用时可能会碰到各种细节的障碍,而且这些新版本碰到的问题,很有可能在网上也搜索不到解决方案。

    Kubernetes设计上并未绑定Google Cloud平台,但由于以上原因,为了减少不必要的障碍,初次尝试建议使用GCE作为运行环境(尽管GCE是一个需要收费的环境)。默认的cluster启动脚本会创建5个GCE instance,测试完需要自己及时主动删除。为了避免浪费,可以将minions减少,同时instance类型选择f1-micro。费用方面一个f1-micro instance运行1个月大约50元人民币,因此用GCE来测试Kubernetes,如果仅是测试时候开启的话,并不会产生太多费用。

    Pods及Replication Controller

    Kubernetes的基本单元是pods,用来定义一组相关的container。Kubernetes的优点是可以通过定义一个replicationController来将同一个模块部署到任意多个容器中,并且由Kubernetes自动管理。比如定义了一个apache pod,通过replicationController设置启动100个replicas,系统就会在pod创建后自动在所有可用的minions中启动100个apache container。并且轻松的是,当container或者是所在的服务器不可用时,Kubernetes会自动通过启动新的container来保持100个总数不变,这样管理一个大型系统变得轻松和简单。

    kubernetes

    Service 微服务

    在解决部署问题之后,分布式服务中存在的一大难题是服务发现(或者叫寻址),用户访问的前端模块需要访问系统内部的后端资源或者其他各种内部的服务,当一个内部服务通过replicationController动态部署到不同的节点后,而且还存在前文提到的动态切换的功能,前端应用如何来发现并访问这些服务?Kubernetes的另外一个亮点功能就是service,service是一个pod服务池的代理抽象,目前的实现方法是通过一个固定的虚拟IP及端口来定义,并且通过分布在所有节点上的proxy来实现内部服务对service的访问。

    Kubernetes自身的配置是保存在一个etcd(类似ZooKeeper)的分布式配置服务中。服务发现为什么不通过etcd来实现?Tim的判断更多的是为了Kubernetes上的系统和具体的配置服务解耦。由于服务发现属于各个系统内部的业务逻辑,因此如果使用etcd将会出现业务代码的逻辑中耦合了etcd,这样可能会让很多架构师望而却步。

    尽管没有耦合etcd,部署在Kubernetes中的服务需要通过container中的环境变量来获得service的地址。环境变量虽然简单,但它也存在很多弊端,如存在不方便动态更改等问题。另外service目前的实现是将虚拟IP通过iptables重定向到最终的pod上,作者也提到iptables定向的局限性,不适合作为大型服务(比如上千个内部service一起运作时)的实现。

    services_detail

    由于service定位是系统内部服务,因此默认情况下虚拟IP无法对外提供服务,但Kubernetes当前版本并没直接提供暴露公网IP及端口的能力,需要借助云服务(比如GCE)的load balancer来实现。

    小结

    总的看来Kubernetes提供的能力非常令人激动,pod、replicationController以及service的设计非常简单实用。但如果立即将服务迁移到Kubernetes,还需要面对易变的环境。另外尽管Kubernetes提供health check的机制,但service生产环境所需的苛刻的可用性还未得到充分的验证。Service发现尽管不跟Kubernetes的内部实现解耦,但利用环境变量来实现复杂系统的服务发现也存在一些不足。

    安装说明

    Kubernetes cluster简单安装说明如下,需要尝试的朋友可参考。

    前提准备
    一个64 bit linux环境,最好在墙外的,避免访问google cloud出现超时或reset等问题;另外创建Google Cloud帐号,确保创建instances以及Cloud Storage功能可用;

    安装步骤
    1. 安装go语言环境(可选,如果需要编译代码则需要)

    2. 安装Google cloud sdk
    $ curl https://sdk.cloud.google.com | bash
    $ gcloud auth login
    按提示完成授权及登录

    3. 安装 etcd 二进制版本(V0.4.6), 解压后将其目录加入PATH

    4. 安装 kubernetes最新的relase binary版本(V0.5.1)
    修改 cluster/gce/config-default.sh,主要是修改以下字段以便节约资源。

    MASTER_SIZE=f1-micro
    MINION_SIZE=f1-micro
    NUM_MINIONS=3
    

    在kubernetes目录运行
    $ cluster/kube-up.sh

    执行成功后会显示 done

    5. 测试pod
    以上脚本启动了examples/monitoring 下面定义的service,如果尝试启动其它自己的pods,比如启动一个tomcat集群

    {
      "id": "tomcatController",
      "kind": "ReplicationController",
      "apiVersion": "v1beta1",
      "desiredState": {
        "replicas": 2,
        "replicaSelector":{"name": "tomcatCluster"},
        "podTemplate":{
      "desiredState": {
        "manifest": {
          "version": "v1beta1",
          "id": "tomcat",
          "containers": [{
            "name": "tomcat",
            "image": "tutum/tomcat",
         "ports": [
         {"containerPort":8080,"hostPort":80}
         ]
         }]
        }
      },
      "labels": {"name": "tomcatCluster"}}
      },
      "labels": {
        "name": "tomcatCluster",
      }
    }
    

    其中pod的tomcat image可以通过Docker Hub Registry https://registry.hub.docker.com/ 搜索及获取

    $ cluster/kubectl.sh create -f tomcat-pod.json

    创建成功后通过 cluster/kubectl.sh get pods 来查看它所在minion及ip,可以通过curl或浏览器来访问(请开启GCE防火墙端口设置)。

    再定义一个 service

    {
      "id": "tomcat",
      "kind": "Service",
      "apiVersion": "v1beta1",
      "port": 8080,
      "containerPort": 8080,
      "labels": {
        "name": "tomcatCluster"
      },
      "selector": {
        "name": "tomcatCluster"
      }
    }
    

    保存为 tomcat-service.json

    $ cluster/kubectl.sh create -f tomcat-service.json
    检查service启动后的ip及端口,由于service是内部ip,可以在GCE上通过curl来测试及验证。
    $ cluster/kubectl.sh get services

    6. 关闭cluster
    cluster/kube-down.sh

    当谈系统重构时,我们谈什么

    weibo team

    又一次团队沙龙,这是一个每周一期的活动,探讨技术或团队一些问题。

    首先,介绍一下本次讨论的背景,参与讨论的是一个多团队的部门,每个团队有不同的职责方向。因此,大部分跨团队的各种技术或协作问题也会碰到,典型的一些场景:

    • 需要升级一个公共库,但是通常并没有一个职能部门来负责公共库升级事项(即使成立也可能最终成为“全国假日办”之类的机构)。
    • 或者是当你负责一个被依赖的模块,当你需要升级时候,发现不少使用方对老版本的feature依赖比较严重,而他们没有精力(或兴趣)迎合升级做大的修改。
    • 团队多了之后,缺少全局的依赖管理,调用之间可能会出现循环依赖的情况(还有间接的循环依赖更复杂)
    • 引入新的第三方库,可能有些团队觉得方便就直接引入了,但又造成了内部使用方法不统一的问题。如果部署在相同的节点,还会对别的模块带来污染的问题。
    • 部分相似的功能大家重复开发,比如一些开关降级工具、发号器等。另外一个层面,A team在开关降级方面新开发了一些实用的feature,但是B team也用不上
    • 从team leader的角度,首要关心的问题是项目的进度及交付目标。因此软件结构的合理性、代码的优雅性以及系统的可扩展性等层面,可能出现优先级未得到保证的情况。“等忙过这一阵,一定要好好重构”,但由于拖延症,长期得不到实现。

    在正式展开讨论之前,介绍一下《人件》原书第三版(感谢华章)中的一个黑衣团队章节。说的是一公司,软件在客户那里出现了很多问题。但由于开发工程师是一群非常有个性也聪明的人,从来不认为自己的代码有问题。因此解决这个问题,公司引入了一群非常有才能的测试工程师,为了更加有个性,他们开始都穿上黑色的衣服,系统一旦有BUG他们就可怕地笑起来,他们的测试根本不是在支持开发人员,而是乐于将软件与工程师放到一种不是测试而是折磨的工序下面;他们还经常聚在一起研究出十分可怕的测试策略,他们一些变态的想法与测试方法让开发工程师望而生畏,欲哭无泪。由于这样一个机制,软件工程师在交付之前自己会进行各种极端的健壮性及正确性判断,最终这个团体逐渐形成自已的个性,也发展了一种渴望并期待发现产品缺陷的哲学。这个机制在不断有人离开的情况下仍然在团队内完好保存。

    但是在重构这个问题,如上面几点所说,团队找不到一种类似凯文·凯利《失控》中描述的机制,不健康的问题第一时间得到了处理。这个可能也是在不少公司同样存在。因此一些主要提出的方案观点如下。

    体检及手术式

    由于上面提到的各种问题,技术体系的健康遭到侵蚀,各个团队还承担各自业务压力,大家的人力资源宽裕程度也不一,因此第一种观点对这些不能及时消除的隐患的存在表示理解,也能意识彻底解决问题的复杂性,但隐患也不能长期不理,因此提出跨团队巡检队定期检查的思路,并将发现的问题列举出来,在约定的时间内完全解决。

    这个做法的逻辑有点类似生活在帝都的IT民工们,在糟糕的雾霾环境下承担着工作的重压,身体健康状况自然不好保证,但也无力改变现状,因此只好通过每年体检来发现身体大的隐患,并尽早排除。

    改变导向式

    这种观点的出发点是人都有惰性,即使有合理的重构理由,在系统还可以勉强运作的前提下,人是没有充足动力去做改变。即使这时候有人跳出来大声疾呼,也不能得到充分的支持与理解,造成了一种机制上的潜在障碍,让健康问题不能第一时间得到解决。

    《人件》第34章标题就是改变成为可能,其中提到,因为人们都不喜欢改变,而你想促成改变的发生,所以你就站在了人性的对立面,自然你就会受到他人的挑战。

    “People hate change…
    and that’s because people hate change…
    I want to be sure that you get my point.
    People really hate change.
    They really, really do.”
    – Steve McMenamin, The Atlantic Systems Guild, 1996

    为了避免这个情况出现,团队需要实行一种“改变为先”的共识 — 只要有人提出一种新的升级(新版本、框架、工具等),团队其他成员原则上不可以提出反对意见。尤其在公共工具库方面,倾向采用在框架配置层面强制升级,再让所有成员被动升级的做法。

    satir_change_model
    《人件》中有关改变的观点则引用萨提亚模型(Satir model),其主要观点是,改变需要至少经过4个阶段,其中的3、4阶段如果没有经历,改变不可能真正落地。因此对于软件开发这样一个以人为本的实践活动,充分意识到混乱也是新事务出现以后的一个必经之路,但混乱不是终点站,有很多团队在做改变时候,从3直接又回去2了。

    多数派决策式

    这种观点的出发点是大的系统、背后大的团队以及成员的关注点及诉求点的多元性。比如

    张三:关注点在存储的成本及效率,由于精力原因,对于公共组件库采用跟随策略,并期望最小的参与成本。
    李四:喜欢尝试新框架,如果团队引入了某个公共的开源框架,对社区每个小的升级迭代充满兴趣,希望将每个版本即时引入到公共库中,并希望所有团队调整自己的代码,跟随及时升级。

    在认可团队多元化价值观的前提下,这个问题不能简单总结成采用某种“稳健型”或者“积极参与型”的思路来决策。但为了团队重构的机制能够存在并运作,可以由各团队选出一名技术代表,每周来讨论一次公共的技术重构事项,并按照多数派的意见进行执行。

    当然上面只是部分主要观点,由于本次讨论各方参与激烈,本文章不做结论,欢迎大家留言介绍你们团队在系统重构方面的做法及机制,希望能从中找到类似上文《人件》或《失控》中描述方法类似效果。

    对微博平台技术沙龙感兴趣的朋友,可以在微博关注话题 #平台技术沙龙# 或微信搜索公众号“WeiboArch”(a.k.a 微博平台架构)来参与。