Web caching with consistent hashing 一致性哈希Web 缓存

读这篇文章源自于一致性哈希的开山之作:Consistent hashing and random trees: Distributed caching protocol for relieving hot spots on World Wide Web。在STOC 上下了原文后觉得估计得花和The part-time parliament 差不多时间来读吧,以后有必要深入学习再看吧!一致性哈希Web 缓存是与开山之作同一作者David Karger 1999年所写 。

STOC 会议上有许多经典的算法,但很多有晦涩难看懂没有引起大家的注意,直到某个采用了该算法的应用得到大家的认可,该算法才得以为大家所接受。分布式一致性Paxos 算法也是这样。(下面左图是consistent hash 开山作引用情况,右边是The part-time parliament 每年引用量,可见在这些牛文在引用量巅峰期之前都有几年的沉寂期,来自CiteSeerX)

conshashing  paxos

言归正传:

problem

congested network and swmaped servers 集中式缓存存在问题

related work

cooperating cache 将缓存复制到不同的机器,存在数据复制和副本一致性问题

hashing 缓存通过哈希保存到不同机器上,存在扩展性以及churn 问题:当一个节点失效或新增一个节点会导致大量失效和缓存的迁移,比如 7×i+4 mod 24 到 7×i+4 mod 23

our work

浏览器上添加哈希函数,将URL 资源定向到动态变化的可用缓存,无副本且减少失效率

consistent hashing

假设有n 个缓存节点,根据其哈希结果使用二叉树进行组织

our system

组成:1.actual cache system  2.user’ browsers   3.domain name server

浏览器对URL 进行哈希得到虚拟地址,返回给DNS 服务器

DNS 服务器通过客户端的虚拟地址查到到对应的缓存节点物理地址IP

缓存节点从原始Web 服务器取数据并保存一份副本,可相应浏览器请求

SSD 并行的性能影响

原文: Performance Impact and Interplay of SSD Parallelism through Advanced Commands, Allocation Strategy and Data Granularity

文章是胡杨博士在2011 ICS 上发表的,通过他的模拟软件SSDsim 对SSD 的并行和高级命令(advanced commands)的分析得出了一些SSD 设计实现上的建议.之前都苦于没有SSD 比较详细的综述,于是自己凑了和了一篇(之前写过的综述),而这篇文章则似乎更适合作SSD 的综述,讲的很清晰。

Idea

通过多层次的SSD 仿真器SSDsim 分析了SSD 内部影响性能的因素(并行)。

总结

  1. large pages 在许多情况下对SSD 有比较大的负面影响
    1. 越大的pages 更易导致数据的迁移
  2. 不同physical-page allocation 可应用于不同环境中,对任意工作负载都会有一个最优方案
    1. Static allocation 读性能在所有情况下最优
  3. 高级命令在一些情况下能够改进SSD 性能,但是用不当会适得其反
    1. 使用高级命令必须带有约束条件才能够提升性能
  4. SSD 四种并行:channel 层、chip 层、die 层和plane 层并行,它们优先级对性能有影响并和2、3中physical-page allocation 与高级命令相互作用、影响。
    1. 并行的优先顺序应该为:1、channel-level  2、chip-level  3、die-level  4、plane-level

微软云存储架构(Azure Cloud Storage)

原文:Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency

 

IDEA

A cloud storage system that provides customers the ability to store seemingly limitless amounts of data with high availablity and strong consistency. 为用户提供高可用、高一致性并近乎无限空间的云存储。

 

System characteristics 系统特点:

  1. High availablity and strong consistency 高可用性和强一致性
  2. Global and scalable namespace/storage 全局可扩展的名字空间、存储
  3. Multiple data abstractions from a single stack 支持多种类型的数据
  4. Automatic load balancing 自动负载均衡
  5. Range Partition vs Hashing 使用动态区域划分,而没采用哈希
  6. Append-only system 存储系统只有append 操作。
  7. End-to-end checksum 端到端的校验和
  8. Separate log file per RangePartition 日志文件粒度为RangePartition

高可用通过多副本策略实现(默认三个),数据写入的原子性操作保证强一致性。Azure 支持blob(数据块)、Table(structured storage)和Queues(消息队列)三类数据。所有数据都是以添加的方式写入的。

继续阅读

Scalable Consistency in Scatter

原文地址

  • idea:可扩展、一致性的分布式key-value 存储(evaluation of Scatter, a scalable and consistent distributed key-value storage system)
  • key insight:基于DHT 的一致性组
  • DHT 功能简介:传统DHT 中,应用数据和节点ID 都哈希为键值key,数值保存在先于或紧接着键值key 的那个节点
  • 为什么会发生一致性问题:1.Assignment violation 节点加入或者离开时对keyID 范围的声明的重叠。2.节点加入和离开对临近指针的影响。

Scatter Design

goal:一致性,可扩展性,自适应性

方法:用组来代替单个节点,RSM 基于paxos 一致性算法,组内使用一致性协议维持内部一致性,但是如静态指定组会存在一些问题:

  1. 当大量nodes 离开或者加入会使得该组失效
  2. 健壮性、可扩展性问题
  3. 当组内节点增多,一致性算法性能下降
  4. 热点问题

因此Scatter 允许多组操作:

  1. split       组一分为二
  2. merge   两临近组合二为一
  3. migrate 将组员从一组移动到另一组
  4. repartition 临近两组交换键值空间

强一致性在拓扑结构不是原子变化的情况下是很难保证的,因此文章引出“自创”的nested consensus 老保证原子性,但实际上nested consensus 就是组内的paxos 算法保证强一致性,组间两阶段提交保证弱一致性。

接着文章从发起方coordinator group,参与方participant group 解释了nested consensus 过程,实际上就是两阶段提交,文章也指出这样的交互过程需要大量的广播和消息,可以作为future work 进行改进。

整个Scatter 系统对外提供存储服务,每个组中会利用paxos 算法选举出一个master,组间交互只通过master,而具体数据时存在组内所有成员,存储对应数据的称为primary。文章谈到了所做的一些性能优化,lease,diskless paxos(信息不用存盘)、relaxed reads 等。

最后进行了测试并与openDHT 比较了consistency。

 

个人体会:

文章主要是提出了可扩展和一致性的key-value 存储系统,最大的创新在于把传统DHT 中单个节点的方法改成了一个组,节点的加入和退出就限制在了组内,对外这个组的状态和功能还是不变的。为了满足可扩展性,组可以进行分裂合并操作,通过形式上说明和实验组操作的OPs/sec、延时说明这个方法是可行、高效的。一致性是通过paxos 算法和两阶段提交实现,也不能说有新意。文章通过与openDHT 的比较,说明Scatter 不损失性能和可用性的情况下,一致性上比openDHT要好。但我有个小问题,组操作如果是手动的话就谈不上adaptive 了,如果是自动的话,这种组操作在节点加入和离开的时候频不频繁,虽然文章也给出了组操作的thoughput 和latency ,但我觉得这个应该同时进行读写操作才能说明问题,如果在现实情况中组操作严重干扰了用户的正常读写的话,试验中的高性能和可用性就不好说了。

HOW TO PRESENT A PAPER

Leslie Lamport

4 August 1979

原址

1.  WHAT TO SAY(说什么

    – Don’t give your paper; the audience can’t take it.  If someone
      can understand in thirty minutes what it took you weeks to
      develop, then you’re in the wrong business.

不要和别人谈论你的论文,别人不可能在短时间内理解的。如果别人能在三十分钟内理解你花了几个星期才写出的成果,那只能说明你的成果并不是很有价值。

另外分析一个句子If someone can understand in thirty minutes what it took you weeks to develop, then you’re in the wrong business.,这是一个同位语从句,what 是understand 的宾语,同时也是后面的句子的同位语。

    – Do advertise your paper.  The purpose of an automobile ad is
      to get potential customers to the showroom, not to give technical
      specifications.  The purpose of your talk is to get people who
      might be interested in your work to read the paper, not to save
      them the trouble of reading it.

要为你的文章打广告,汽车广告的目的是将潜在的客户吸引到它的showroom,而不是给出技术细节。你演讲的目的是使得可能对你论文感兴趣的文章的人去阅读你的文章,而不是节省他们阅读文章的困难。

    – Giving a good presentation is an art, requiring both practice
      and talent.  No rules can turn you into an artist, but the
      following suggestions might be helpful.

        1.  Describe simple examples rather than general results. 
            Try to make the examples much too simple — you will not
            succeed.

        2.  Don’t use formalism.  If your results cannot be described
            simply and informally, then there is no reason why anyone
            should be interested in them.

        3.  It is better to be inaccurate than incomprehensible.  The
            place for accuracy is in the paper.  (However, false
            advertising is unethical.)

2.  HOW TO SAY IT

    – Slides are effective.  Here are some suggestions for their proper
      use.
     
              1.  Don’t put too much on a slide — a picture of a thousand
            words is worthless.  For 8 x 11 slides, all letters should
            be at least 3/8 inch high, with plenty of blank space. 
            People in the back row have to read them too.

        2.  Slides should be neat and legible.  The listener isn’t
            your secretary; it’s not his job to decipher your
            handwriting.

        3.  A rapid sequence of slides has a hypnotic effect.  Unless
            you are a licensed hypnotist, don’t use more than one slide
            per minute.
           
        – Time your talk.  Running over your allotted time is a mark of
      incompetence, and displaying your incompetence is a poor way
      to get someone to read your paper.  Remember that talking to
      an audience takes longer than talking to a mirror.

3.  DA CAPO

    – You are now thinking:  “All those dull speakers I’ve listened
      to should use these rules, but I don’t need them because my talks
      are interesting.”  All those dull speakers are now thinking exactly the
      same thing.  Read the rules again with the proper humility.  They
      apply to everyone.

        “The only wisdom we can hope to acquire
        Is the wisdom of humility:  humility is endless.”

4.  CODA – For Session Chairmen

– Be utterly ruthless about enforcing time limits.  Warn the
      speaker when he has 10 minutes left and when he has 5 minutes
      left, and stop him in midsentence when his time is up. 
      The audience will be grateful.  (A loud alarm clock works quite
      well if you don’t turn it off until the speaker has finished
      talking.)
     
       – Protect the speaker and the audience from inappropriate
      questions.  Questions should be allowed during the talk only
      if the audience is small and the question is a simple request
      for clarification.  After the talk, you must be prepared
      to silence the following two kinds of questioner.

        1.  One who leads the speaker into a long discussion of an
            obscure detail which is of no interest to most of the audience.
           
               2.  One who monopolizes the time arguing with the speaker over
            unresolvable philosophical issues.

      Remember that silencing one person enables the rest of the
      audience to ask questions.

Extracting Flexible, Replayable Models from Large Block Traces

原文

文章看了三天都没有看出所以然来。

今天重新看了yangsuli 博客,发现原来文章所谈的就是我读的那么回事。至于为什么我没有看出东西来,是因为我不知道这篇文章是要干嘛的,难道只是对trace进行了压缩么?

Main idea: take standard trace, then divide them into chunks, define feature function to turn traces into a muliti-demention diagrame, to trade accuracy for size reduction.

将标准的trace 按照时间点(文章谈到了在trace可能出现的误差点或不精确点chunk 作为分隔点)或者块大小分隔大小,然后根据特征(读、写、偏移)函数将traces 转化为多维度的图,然后通过重复数据删除和benchmark plugin对数据进行压缩,以减少精确度换取size 的缩小。

我的点点想法:

  1. 重复数据删除在算法优劣的评价下并没有一个数据集合,一方面是如果真的有这个数据集合也会是非常非常大的,它的存在价值不大;另一方面更需要一个精简的方法来衡量算法的优劣,这个方法甚至可以自己创造一个数据集合对重复数据删除算法进行评估。重复数据算法实际上就是压缩算法,比较压缩算法的优劣也没有固定的数据集合,但可以通过压缩率来衡量,有人要说压缩率对不同的数据集的压缩率也是不一样的,好在就在于压缩算法更容易用数学来进行考察。这样有一个方式就是通过比较重复数据删除和固定压缩算法的压缩比,但问题又来了还是需要数据集。而且数据集合取得不好的话,可能这两者之比相差非常大,比如讲一个word 文档复制后重命名,重复数据删除这两个文档几乎没有压缩,而压缩算法对这种情况却十分有利。
  2. chrome 客户端写一个插件可以保存指点图片/链接(右键该图片/链接)、保存指定文字(选中该文字)、保存页面(页面上右键)到远程服务器(可以考虑ustor 哦)。在本地桌面安装一个快捷方式可以随时查看以上保存的文件。有人要质疑这样做的好处了,本地不都是可以做这些的么?但没有感觉本地在保存图片和页面的步骤繁琐,还需选文件夹,chrome 还要卡卡的以下,能够让远程服务器(云端)做这样的事情,我们只是单击下邮件或者按下快捷键是多么惬意的事情啊?有一个小小的问题就是如何认证所在的用户并保存它的数据到他的远程文件夹(显然是要先注册的)。