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

Advertisements

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

Sparrow

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

 

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‘.

cfs-1

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)

Chord

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (SIGCOMM 01)


In brief, chord solves the problem of ‘how to build consistent hashing at scale‘(a good summary pointed by the professor). Chord achieves scalability with some trade-off, that is, maintaining O(logN) of other nodes’ information to be able to take O(log N) for lookup.

The consistent hashing function assigns each node and key a m-bit identifier using a base hash function such as SHA-1. The good thing of consistent hashing is that it forms a ring circle and seems to minimize the cost to add or remove a node. Because only keys in one node are influenced in this condition.

When choosing node identifier, some elements need to be taken into account, including a). we do not want two nodes have same ID, b). we  want to spread node ID ‘evenly’, c). Considering replication, it should have geographic diversity for the sake of failure.

Chord maintains O(logN) information of m=logN nodes in the ring called finger table. The ith entry of node contains the identity of the first node that succeeds n by at least 2^(i-1) on the circle. This will result in two properties. a). each node stores information about only a small number of other nodes and knows more about nodes closely following it on the identifier circle than about nodes farther away. b). a node’s finger table generally does not contain enough information to determine the successor of an arbitrary key k.

consist-hash

So, if the key k‘s successor is not known by node n. To find the correct successor, it just keep trying to find the node that may know more about current node and the files. (Like the figure above). Such a nice way that utilize the property of exponential function to reduce the space of searching~~

If one node just maintains the k successors, it would be nightmare that a new node joins and will hold the partition that exactly ahead of the node n’ that it contacts with in the ring. So, they keep each node maintaining a predecessor pointer. Thus, when a new node n joins the network, chord will: 1). Initialize the predecessor and fingers of node n. 2). Update the fingers and predecessors of existing nodes to reflect the addition of n. 3). Notify that higher layer software so that it can transfer keys and values. A problem is that how the new node find one node in the ring to start the joining? Well, the paper says it depends on some external mechanism. The new node n learns its predecessor and fingers by asking n’ to look them up.

After node n has its own finger table, its predecessors need to update their finger table, so chord will walk counter-clock-wise to fulfill this requirement. The process of updating finger tables will take O((logN)^2). Finally, node n only needs to contact with one node that will reduce its key space to a half and finish the value transfer.

Because the P2P system may have concurrently nodes joining, failing and leaving, they modify the basic chord described above and incorporate a basic ‘stabilization’ protocol which is used to keep nodes’ successor pointers up to date. It aims to preserve reachability of existing nodes when adding nodes to the ring. To think about this problem, especially figure out the difference between this ‘stabilization’ from above ‘lookup’, it is in need to think the world concurrently. For example, when several node join concurrently, to each node, after lookup, the node in lookup path may be in three conditions, including all the things correct, successor pointers correct but finger table not, incorrect successor pointers.

Every node runs stabilize periodically, the process seems like insertion to a linked-list which can be seen in the figure below. Note here that it is eventual consistency, at some time after the last join all successor pointers will be correct. For the failure, the key step in  failure recovery is maintaining correct successor pointers for the worst case that finger table provide no optimization.

chord2


BTW: I think I need to write something to make myself more deeply understand the paper I read. So, start from today !