[SOSP-17] The Ada workshop

Starting my first system conference journey, excited! I’d say the first day and the workshop is wonderful.

Generally, I feel it is a very supportive community. Not so-much technique thing, so I could just writing some random staff and take-away.

The most impressive thing is from Kay “Your advisor will tell you to give up and don’t give up before that”. Well, I think I will pretend it to be true. I’m not good at giving up, though I am always not sure that if I could do. Stop worrying about ‘Can I do a phd’ and assumed advisors would do so to notify ‘giving up’.

I talked to a lot of intelligent and nice people. Talked with those researchers did the paper I liked (No-Paxos, Retro, Sparrow etc.) and others in the project I am not very familiar with. Asked apple guys how do they think about their new building for fun.

Some random notes:

Andrea’s talk:

talk to industry, put as much as possible work into one paper, more motivation, using old things to do new staff (tech, insight, methodology).

Kay’s talk:

— Pick up project, work on that. Depth First (Totally agree)

— “Facts preceded concepts”

— Learn as much as you can, even the boring staff.

— Use your intuition to ask questions, not to answer questions

— distrust good result

— “You are a scientist”, talk to people hate your work. Assume they are correct, try deeply understand why they say so.

Some tricks for communication:

— Do homework (From the cool night-watch guy)

— Re-introduce yourself

— Good question to ask: ‘how do you get the idea’ (From Shan Lu), ‘criticize the benchmark” (From Jenna)

To summary, owesome, the supportive community, the advice, and the dinner w/ advisor, graduated group members and their students.


Programming Quotes

Premature optimization is the root of all evil! – Donald Knuth

Walking on water and developing software from a specification are easy if both are frozen. – Edward V Berard

It always takes longer than you expect, even when you take into account Hofstadter’s Law. – Hofstadter’s Law

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems. – Jamie Zawinski

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. – Brian Kernighan

Measuring programming progress by lines of code is like measuring aircraft building progress by weight. – Bill Gates

PHP is a minor evil perpetrated and created by incompetent amateurs, whereas Perl is a great and insidious evil, perpetrated by skilled but perverted professionals. – Jon Ribbens

On two occasions I have been asked, ‘Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?’ I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.” – Charles Babbage

Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. – Rick Osborne

Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. – Rich Cook

I don’t care if it works on your machine! We are not shipping your machine! – Ovidiu Platon

I have always wished for my computer to be as easy to use as my telephone; my wish has come true because I can no longer figure out how to use my telephone. – Bjarne Stroustrup

A computer lets you make more mistakes faster than any other invention in human history, with the possible exceptions of handguns and tequila. – Mitch Ratcliffe

If debugging is the process of removing software bugs, then programming must be the process of putting them in. – E. W. Dijkstra

It is practically impossible to teach good programming style to students that have had prior exposure to BASIC. As potential programmers, they are mentally mutilated beyond hope of regeneration. – E. W. Dijkstra

In theory, theory and practice are the same. In practice, they’re not. – Unknown

Perl – The only language that looks the same before and after RSA encryption. – Keith Bostic

I love deadlines. I like the whooshing sound they make as they fly by. – Douglas Adams

XML is like violence – if it doesn’t solve your problems, you are not using enough of it. – Unknown

Einstein argued that there must be simplified explanations of nature, because God is not capricious or arbitrary. No such faith comforts the software engineer. – Fred Brooks

Books 2017

  • 计算机是怎么跑起来的 ( How computers Work) [May 21st, 2017]
    • I’m not sure whether it is appropriate to suggest it to my parents to let them know more about computer science. I have lost the ability to figure if it fit to ordinary people.
  • 拖延心理学 (Procrastination: why you do it, how to do about it) [May 22nd, 2017]
    • 这本书有点意思,细细想来自己还是有一些拖延的行为的。一直比较喜欢这种类型的书,似乎是可以让人更清晰的认识自己。很多时候过多的沉迷一些娱乐活动(比如游戏和网络小说)、甚至是看书其实也是一种拖延,利用阅读作为拖延这招可能从幼时抗拒弹琴就存在了。
    • 如果那是一件值得做的事情,那么为它犯错误也是值得的 & 当我展现出真实的自我,真正喜欢我的人会跟我坦诚相对
  • 断舍离 [May 27th, 2017]
    • 没有想象中的好吧,可能因为我还是很喜欢扔东西的,still some interesting thinking,另一方面觉得有点像传销。。。
    • 断:停止负面的思考模式;舍:顺从自己的心,割舍既有;离:松开‘多就是好’的念头
    • 主语永远都是自己,而时间轴永远都是现在
    • 断舍离的含义就是:在‘断’与‘舍’的交替里,脱离对物品的执念,达到轻松自在(离)的状态
    • 把东西送给朋友的时候,不要用“给你”这个词,因为“给你”是高高在上地俯视别人,甚至听起来像是在盛气凌人的说:“我不要了,你想要这个吧”应该这么说:“这东西在我这里没办法物尽其用,但是我觉得你会爱惜的使用它,所以能不能请你手下它呢?”  (good point)
  • 自私的基因 (Not sure how to say about it)
  • Brief History of Humankind [July 4th, 2017]
    • Since I like history for long, it is fluent to read such a book.
    • I always think that history book is skewed, but seems this book intend to skew and try to build some philosophy to model how human being evolve to this stage and show worries for the dreaded future to become the god to rule the world without any constrint
    • Contradiction of freedom vs. equality
    • Cognitive revolution, agricultural revolution, unification & scientific revolution
    • imagination build the world and the community of such large scale
  • The Power of When: Discover Your Chronotype [July 11th, 2017]
    • Not Sure I’m in which type still. I think mostly Lion but kind of dolphin.
    • The kind of book that I enjoy, very relaxing. I’m not sure if it works, at least I’m not agree with something about eating, seems I need to just eat protein…
    • Anyhow, the thing about coffee make sense.
    • No matter the conclusion or model is right or wrong, in my opinion, it make more sense to display that different people need to build different daily routine.
  • The ONE Thing: The Surprisingly Simple Truth Behind Extraordinary Result [July 15th, 2017]
    • 大部分的待办清单其实是“存活清单”,只能帮你应付日子,对迈向成功毫无帮助。
    • 自律是一个流行的谎言。其实,我们需要的不是坚持,而是习惯,要养成习惯,我们就需要自律。
    • 我们不需要追求平衡是因为奇迹不会在中间点上发生,奇迹只有在追求极致的过程中才会发生
    • 在生活中,所有的要素都不能少,都需要顾忌;而对于工作来说,取舍是常态。
    • 如果把生活想象成一场无求杂耍游戏,这五个球分别是工作、家庭、健康、朋友和诚信。(苏珊日记)
    • E–> P, Energetic –> Purposeful, avoid OK plateau
  • The Power of the Herd: A Nonpredatory Approach to Social Intelligence, Leadership, and Innovation (制怒:如何掌控自己和他人的情绪) [July 21st, 2017]
    • 这本书感觉和马有关的部分有传销的意味(调侃,宣传也是正常的),但是有的point感觉还是有点意思的,关于如何避免情绪失控和爆发,如何和他人交流一些问题的方式。有的时候感觉还是会不由自主的出口伤人,尽管我并无此意,这本书还是找到了原因,生活中管理自己的情绪其实不是一味的压抑,而是感知自己的想法和反馈。
    • 不断积累的未经处理的羞辱会侵蚀你的自尊和健康意识。而不时地感到内疚或者困窘确有着积极的自我纠正的效果
    • 外部威胁时环境中本能警告系统感受到的恐惧,内部威胁是对脆弱的恐惧,是对自我形象、信仰体系和舒适习惯的挑战
    • 我们天生的移情能力有时会让我们遵从反社会神经系统所独具的特征
    • 物化是赋予其他生物、组织和文化以愚昧、愚钝、有缺陷甚至本质上邪恶的特征。投射包括惩罚、拒绝甚至迫害那些有着我们拒绝承认自己具有的弱点和黑暗品质的人。在所有我们试图掩饰的心理中,物化和投射的组合是最具破坏性的。
    • 每个人都是土用所有的方式羞辱对方。一心一意的要证明对方是坏人,换句话说,证明对方有着无可救药的缺陷。
    • 羞辱儿不负责任的指责对情侣、家庭、组织和社区来说都是有害的。首先,当我们羞辱并责备他人的时候,就把关注点从有问题的原始行为转移到个人评价上来了。
    • How to: 感受原始的情绪;理解情绪背后的信息;根据信息作出一些改变。
  • Eating Animals by Jonathan Safran Foer (吃动物) [July 27th, 2019]
  • Whole: Rethinking the Science of Nutrition (救命饮食2:全营养与全健康从哪里来) [July 28th, 2017]
    • I’d say the translation of title is a magic …
    • I do like the philosophy of “whole” instead of “nutrition fact”, that is why I hate things like ‘Soylent’ while preferring salad (of course no cheese and no sauce).
    • Living in an era that is rich in food and at the meantime food becomes a huge business is not so easy.
  • 素心佛餐 [July 28th, 2017]
  • 穿T恤听古典音乐 [July 29th, 2017]
  • 问中医几度秋凉[August 1st, 2017]
    • 读来消遣感觉不错,这种一个家庭里面存在不同的思想碰撞和谐统一的故事,读来有一种淡淡的感觉,对于中医和西医的看法也颇有道理。
    • 中医这件事情个人来讲倒是一直挺纠结的,做不到完全的用科学的角度去看待。
  • 一个传统中医的成长历程[August 13th, 2017]
    • 消遣,感觉一般,略鸡汤,但是信念可敬
  • Same Kind of Different as Me (世界上的另一个你)[August 27th, 2017]
    • 读起来挺消遣的,两个人一人一个章节的讲故事有点意思,似乎适合拍电影
    • 似乎是比较符合灯塔国目前的一些主流价值观,关于种族、善意、爱和希望
    • 霍尔和摩尔两个人的轨迹原本不想交,却因为一个圣母型的女主角成为了亲人一般的关系。个人倒是觉得像摩尔这样的人如何能保持心底里的善意和形成了生活的信仰与智慧比较有意思。
  • Ferryman (摆渡人) [September 05th, 2017]
    • 貌似没怎么get到point,是说人要勇敢的面对内心的荒原么。。。。
    • 一般好玩的故事,Happy ending
  • 古拉格:一部历史【October 31, 2017】
    • 这本书断断续续读了很久的时间,属于我会挺喜欢的类型的书,有很多详细的史料记载,详细的描述了,从沙皇俄国末期到苏联时期,劳改营的产生,发展和终结,读来振聋发聩,耳目一新。
    • 能写出海燕的高尔基,也不过是鼓吹劳改营,向当权者谄媚的普通人,可以理解,着实可叹。
    • 难以想象,在冰天雪地中,人与人之间丧失了最基本的尊重,是如何挣扎与生活。
    • 有的感想其实很难表达,自己有幸能够做自己喜欢做的事情,追求自己的理想,能够fight for GLORY,需要怀着最大的感恩生活。
  • 所谓情商高就是会说话【佐佐木尘】[November 20, 2017]
    • 很短的书,挺好玩的
    • 投其所好:不要直接说出自己的想法
    • 突破口2:儆其所恶,能形成强大的强制力,这是措辞的最终手段
    • 突破口3:选择的自由:关键在于,要给出合适的两个选项,无论对方选择哪一个,自己都要达到目的
    • 突破口4:被认可欲,这种被认可欲,也可以解释为心理学上的“尊重需求”,即“一个人能做出与他人期待相对应的成果”
    • 突破口5:非你不可,就是告诉对方:别人不行,你才是被选中的人
    • 突破口6:团队化。喜欢和别人一起做事,本来就是人的本能。
    • 利用感谢:关键在于说谢谢的时机:应该在请求提出之后立刻说谢谢。心理学上的:互惠式好感:一个人接收到好意,就会产生向对方回报好意的心里
    • 里面有一段文字颇有意思:
      • 人是不讲理的,会做自私的事,即便如此,也请原谅
      • 你若显露善意,必会被人怀疑,即便如此,也请坚持
      • 你若获得成功,必会遭叛树敌,即便如此,也请成功
      • 你若做人正直,必会为人所骗,即便如此,也请正直
      • 你用多日所创,别人一晚即毁,即便如此,也请创造
      • 你寻安乐幸福,必会遭人嫉妒,即便如此,也请幸福
      • 今日纵然行善,明日或即被忘,即便如此,也请行善
      • 你若予人以物,必有人不知足,即便如此,也请给予
    • 总的来说是挺消遣的读物,没有什么很深入的东西。


Sparrow: Distributed, Low Latency Scheduling (SOSP13)

The two papers for one class are Sparrow paper and Coopcache paper. Generally, several (two, or even three…) papers for one class has some kind of relation, but I didn’t figure it out this time before class. Again, Prof. Remzi lights it, both of them are about a topic — decision making, i.e. how to make decision based on information (quality). Great summary, isn’t it?

The paper addresses the problem of scheduling shot-lived “jobs”, i.e. parallel jobs that complete in sub-seconds which are divided into a large number of short tasks. For short-lived jobs, it is proposed that high throughput (scheduling unit is task, so throughput must be high), low latency and high availability become requirement. Note that job is only considered as finished once all the tasks are done. Existing centralized schedulers cannot support this kind of jobs very well, because every task must be passed to one single node which chooses a machine and launches the tasks. According to this, a natural idea is to add more schedulers, they went further to the opposite extreme.They use decentralized schedulers and make scheduling decision based on the method ‘random sampling’.

Basically, the approach is picking some servers, probing them “how long is your queue” and sending tasks to shortest queue. Actually this is not a quite new idea. In this condition, a job contains many tasks, that is many scheduling decisions are made at the sometime, thus not exploiting these information together seems a waste and stupid. So The make decisions based on all the n * 2 (n is the # of tasks) queue size and send task to the shortest n of them.

Another problem is that whether sending a task to the shortest queue is a reasonable decision? Much like process scheduling in OS, it is not possible to know how long a existing job will take. Thus, they change from “push-based” approach to “pull-based” approach (late-binding in the paper). Specifically, schedulers wait to assign tasks until a worker signals that it has enough free resources to launch the task. But this approach has the issues that there can be idle time not doing task while pulling from server. And there are much more communication with the scheduler and worker than before (Even more communication  to avoid the idle problem by prefetching). This trade-off is based on the assumption that network latencies is much less than task runtime.

As this time, the reservation of tasks are put into workers, so some kind of cancellation is needed to avoid double execution. Two ways for cancellation, proactive way or sloppy way. They use proactive cancellation based on the result of simulation.

Now, for scheduling, it is also important to support for some policies, they discuss constraints over where individual tasks are launched and inter-user isolation policies. First where is the constraints from? I think it mainly from the constraint of physical resource and the constraints just try to make the scheduling more efficient or reasonable. For example, some tasks need GPU and it will be much better if every task can execute in the server that holds its data and states (co-locating task), and it will be more useful to put the task to the server that the data is cached in memory. The solution seems natural from the sparrow framework, which is just probing to the workers that satisfy the constraints. But how do the scheduler know the worker has the data? And if the task is truly put into server without input data, how can it know which worker to contact with? Well, it may need some <key, location> pair provided by other layer? As for the isolation problem, they support strict priority and weighted fair sharing. All the policy like FIFO, EDF, SJF or enforcing weighted fair shares are implemented by multiple queues in worker. For example queue for every priority or for each user which is also naturally.

Since it is related to my own research work, so I may read it some time later. Based on the subtitles in the following section, it may have some hints for the experiments I will do.

A question in class is that what difference between pisces paper and sparrow paper, I may answer this in the post of pisces paper.



CFS: Wide-area cooperative storage with CFS (SOSP2001)

Here are some questions from the professor (Helpful to understand):
1. CFS uses a block-based approach:
    How does this work?
    -- split each file system (and file) into blocks and distribute those blocks over many servers.
    How would this compare to a file-based approach (pros/cons)?
    -- pros: load balance for popular file
    -- cons: 
           -- more time to look up, more # of messages to fetch a whole file. (Can do prefetch)
           -- not as efficient as whole-file scheme for large but unpopular files
           -- not likely affect small file because of using cache
2. Immutability makes aspects of CFS much easier, which?
3. Replication is needed for reliability
    How are replicas maintained?
    -- See below
    Do replicas help with read performance?
    -- Yes, with server selection (Chord)
4. Caching is used to speed lookup?
    How well does it work? Is cache consistency an issue?
    -- cache consistency is not a problem, content-based hash
5. How to handle servers with more disk space than others?
    -- virtual node and configuration, and the administrator configures the server with a number of virtual servers in rough propotion to the server's storage and network capacity.
6. There is no-delete
    What does this make easier?
    -- no need to agree on the deleted item

CFS is a read-only (read-only from client view) Storage System on top of chord. In my understanding, it seems build a virtual disk on top of many servers and their local file system using chord to connect to each other. Thus, the client FS can use the DHash blocks and block identifiers in place of disk blocks and disk addresses. The figure below is the software architecture of CFS.cfs-2

The responsibility of DHash layer is : 1). Storing blocks. 2). Replication. 3). Cache. Each block can be either a piece of file or a piece of file system meta-data. A parent block contains the identifier of children. The published inserts the file system’s block into the CFS system using a hash of each block’s content as its identifier (like H(D), H(B1) in the figure below). Then the publisher signs the root block with his or her private key, and inserts the root block into CFS using the corresponding public key as the root block’s identifier. (Well, I think it is some kind of mount+security). The root is used to support their goal ‘many unrelated publishers may store separate file system on a single CFS system‘.


For availability, DHash places a block’s replicas at the k servers immediately after the block’s successor on the Chord ring.

DHash caches blocks to avoid overloading servers that hold popular data. Each DHash layer set aside a fixed amount of disk storage for its cache. When a CFS client looks up a block key, it performs a Chord lookup, visiting intermediate CFS servers with IDs successively closer to that of the key’s successor. At each step, the client asks the intermediate server whether it has the desired block cached. The client then sends a copy of the block to each of the servers it contacted along the lookup path for future lookup. CFS avoids most cache consistency problem because blocks are keyed by content hashes.

CFS does not support an explicit delete operation. Publishers must periodically refresh their blocks if they wish CFS to continue to store them. A CFS server may delete blocks that have not been refreshed recently.

(Still something missing about Quotas, TBD)