jimmy lin's talk

observation:
the more data, the better performance u get.

problem (why is this different):
impl. issues: concurrency.

should have a simple programming model, and large scale resources available to the masses.

PS:
break down into two problems
On y axis, you have XXX

in reference to: YouTube - Research and Education in the Clouds: Experience at the Univ (view on Google Sidewiki)

百度面试 C/C++

-C和C++的区别
-操作符？类型转换的种类
:实参到形参的类型转换有四种，有一些优先顺序。有四种exact match, promotion, standard conversion, class-type conversion, 见7.8.4

-文件声明中的__cdecl, __pascal, __stdcall是干什么的
:简单而言，这些是关键字。在函数声明的时候用在函数名前而返回值之后，如extern Region __cdecl XCreateRegion。
:__cdecl用于标准的C函数调用，__stdcall是C++调用，__pascal则是WINAPI的函数调用。具体意义见网上参考，如下：
http://hi.baidu.com/tendollor/blog/item/1584f20facefe6226059f383.html
http://hi.baidu.com/aniu_home/blog/item/0e595ad8ba8a513432fa1c6d.html

-template的偏特化
:特化specialization：使用template的函数对某些类型有特殊的实现，使用特化。template<>
?重载和特化的区别：重载的调用对实参有类型转换，特化的函数调用没有
:偏特化是对部分形参进行特化

Install VS 2008 on a Windows server (Sever 2003)

VS 2008 is to be installed on a 64-bit Windows Server 2003. Yet the VS Web Authoring Component continues to report problems (of HRESULT "-2147023293")...

As in [2], no use to look at the log in "dd_error_vs_vstscore_90.txt", which is quite high level. Yet what is useful is in %temp%SetupExe(***).log. The log says "Error: failed MsiEnumProducts ErrorCode: 2(0x2)."

A solution [1] can be located by googling the error, which perfectly solves the problem...

references:
1.http://support.microsoft.com/kb/954361
2.http://blog.mediawhole.com/2008/07/installing-visual-studio-2008.html

多线程编程-共享变量的一致性

线程存储模型和变量映射
本质上，每个线程有自己完全独立的寄存器，但每个线程被允许共享进程的所有存储器空间。具体而言，读写区域（存储global variable, local static variable）和堆都是直接可以在thread routine里访问的（堆而言，只要指针能传进去）。栈而言(存储local variable)，一般线程独立访问，但每个线程栈之间不设防：如也可以通过全局变量的方式让其他线程访问local variable.

共享变量的一致性：
当有多个线程访问一个变量实例（一个变量可能在不同的上下文（如方程，线程）有多个实例），可能导致不一致的现象。（系统对不同thread routine的汇编代码做interleaving的，且寄存器是完全独立的）

问题解决：通过信号量/互斥锁来同步线程，使得在临界区内只有一个线程。关键是对信号量的更新操作是原子的，不可中断的（应该是系统级别实现的）。

对于共享资源（如thread pool），如生产者/消费者模型，其本质和共享变量是相同的（相当于两个write操作）。

PS:
小细节：线程detach和joinable

Pip:detecting the unexpected in distributed systems.

title: Pip:detecting the unexpected in distributed systems
venue: nsdi 2006
authors: ucsd

Given a running distributed system, how to determine whether or not there is unexpected behavior so far and if yes, where it is? For pip, the basic idea is to capture necessary system behavior online and to run a offline algorithm to check them against user's expectation. (Of coz, there are some options in making such choice, like why not check the unexpected online? why not check all-possible behaviors?)

In such a framework, several detailed issues are posed:
- how to describe behavior of of a distributed system?
- how to express user's expectation for a distributed system?
- how to capture system behavior? what need to capture and what not? (This is left to users and automatic analysis tools (say, mace), by an annotation lib to indicate the PathId for an event.)

1. Behavior model - How to describe behavior of a distributed system?
System behavior is described by a series of path instances, each of which is raised by an outside input (say, a request). Each path instance portraits the internal procedure in the system to answer or to finish the task. It consists of a series of events, organized by their natural causality, (thereby forming a DAG). In a distributed setting, an event could be a task which resides on a single thread (thus on a single host), or a message which help communicate between threads or hosts.

2. Expressing expectation and checking algo.
Given a bunch of path instances and a set of user expectation, Pip checks whether each path could satisfy any of user expectations.

2.1)
Each expectation is a path-validator/invalidator. Each validator consists of several thread patterns, each indicating how a desired thread should run. Within a thread pattern, there are statements and some flexible descriptions of statement flow. A statement is the basic unit of user expectation, including tasks, messages, and notices. Those descriptions include xor and future primitives, flexible enough to capture various program/runtime flows.

The whole technical point is how to model distributed behavior and how to describe it by an expressive language. The difficulty is how to express the prevalent parallelism in every aspect of distributed systems. In essence, how to model a DAG in a language. In this respect, the expectation language is in natural parallel--- no particular order is imposed between thread patterns; within a thread, there are flexible primitives allowing expression of various runtime flow.

2.2) the checking algo.
Given a path instance and an expectation (expressed by a code snippet), checking algo. is to determine whether the path instance follows the expectation. The point here is that the expectation language is design to be expressive and flexible enough, making the matching difficulty. Specifically, the ...

Networked DHTs - Network Background

Today, various networks/protocols are in existence. Different classification methods/viewpoints are essential in understanding them.

Routing principles(for routing protocol only):

There are generally three kinds of routing protocols: the link-state and the distance-vector (including path-vector).
LS: advertise each link info. to all other nodes. (flooding, msg per router: O(n*d))
-essentially, many small messages
DV: advertise its whole routing table to only neighbors. (rummer, msg per router: O(d))
-essentially, relatively few large messages
Note the number of advertisement is meant to be before the computation.
While link-state involves global flooding of each link to update "indexed" route info., distance-vector is to disseminate local distance-vector through neighbors. The computation of LS is after flooding, whereas DV embeds the computation within the dissemination process (ie., in a round-to-round manner). Specifically, the link-state is to flood every link state to every node in the network, in a way to construct a global view of network topology known by every node. The flooding is always loop-free by indicating a sequence number. The routing table is then constructured by computing the Shortest-Paths locally by the Dijkstra. The distance-vector is a every-node-run-it and round-to-round version of the Bellman-ford algorithm; Every node maintains a distance vector to every other node in the network (note, not the global network topology), and update it by disseminate it through all neighbors to keep other's DV up-to-date. ^2

Exterior Gateway Protocol is BGP which is kind of DV (actually path-vector, and at application layer). Examples of Interior Gateway Protocol (for LAN) may be RIP, a distance-vector protocol (application/network layer), or OSPF, a typical link-state protocol (link layer).

Protocol Layering Overview:
Each kind of network has/is a suit of protocols, with each belonging to a/some specific layer in the protocol stack. For example, the Ethernet widely used in enterprise internal networks mainly focus on layer-1 and layer-2, while the Internet protocols are scattered in 4 layers (which can be essentially mapped to all 7 layers of the OSI model). The Internet Protocols has a waist model?...
PS: Internet could also refer to the set of all existing networks.

Network topological/protocol hierarchy:
host -> bridges and segments (Ethernet) -> routers and subnets -> ASes (hierarchical)
Network topology is truly hierarchical in nature: At the toppest level (application layer), AS is hierarchical; Each lowest-Tier AS could then contain several subnets and routers (a subnet could be an Ethernet); Again, each modern Ethernet could consist of several Ethernet segments connected by switches or bridges. An Ethernet segment is shared-bus structure of several hosts.

Above network layer, the Internet is really a set of subnets and routers between subnets. Subnets are identified by a single network ip, which means network ip appears in routing table's entries. By such means, router store per-subnet routing info, rather than per-host. At network layer, the internal structure of LAN is simly full-connected; every host can contact its attach router in one hop.
As to the host IP address within one subnet, there are two forms; the host is connected to the router, directly, or by NAT. The former implies each host is directly on the Internet (在公网上), having a public IP address. In the latter case, the LAN's network identifier is a complete IP, yet each host is identified on the Internet by its public identifier, namely LAN's IP+port, dynamically. From internal view, each host is configured with a reserved IP, which is transformed to its public identifier by NAT. This solution is to resolve the scarcity of public IP on the Internet.

On application layer, certain set of subnets and routers could form an Autonomous System (AS). The hierarchy of ASes could be recursive; set of some ASes could form a high-level AS. Each ISP corresponds to ISP who administrates this AS and has right in designating routing pollicy within this AS. The hierarchy of ASes can be modeled as a DAG (not the tree). The provider-customer relationship forms a tree, while multihoming, peering could be other links in the DAG besides the tree. Routing at application layer could be divided as inter-domain and intra-domain routings.

Link layer takes a closer look than network and explains how a single hop in network is performed. Specifically, link layer focuses on the internal structure of LAN and the link between routers (ie., point-to-point link). The core technical issue of link layer (including data-link and physical layers) is how to route (covered by data-link layer) following the topology of physical layer. The data-link layer focuses on Media Access Control and Logic Link Control, the form requiring to identify a host (whether it is the host of destination) and the latter providing some routing quality guarantee. Thus, a major distinct of data-link layer is to route on MAC, which introduces problems involving translation of IP to MAC (ARP) and automatically assigning IP (DHCP).
Ethernet is a typical LAN with protocols on link layer. The network topology is bridging (or switching) several segments each of which is a shared bus accessed by CSMA/CD, (note all these are at physical layer). The routing involves flooding and source-learning. The flooding (partially in unicast and always in broadcast) could form a loop, which Ethernet resolves by computing the spanning tree.

How each frame corresponds to a data packet?
Why IGMP should be a layer-3 protocol, rather than a layer-2 one, since it actually works between router and end-hosts?(because it doesn't run on switches!)

References:
1. Ion's lecture: http://www-inst.eecs.berkeley.edu/~ee122/fa08/

2. Berkeley's old lecture: http://www.cs.berkeley.edu/~kfall/EE122/lec15/sld009.htm
3. LS vs DV: http://books.google.com/books?...

Networked DHTs - Schemes and Ideas

From my own perspective, the VRR and SEATTLE build DHTs on network layer of generic networks and of Ethernet, respectively. The ROFL paper focuses on the support of DHT routing (ID-based routing) by adapt a hierarchical DHT onto the AS-based Internet structure.

Specifically, VRR essentially transforms each single leafset entry in conventional DHT's routing table into a series of network-layer routing entries (along the virtual path from endpoint to endpoint). As such, the network layer could support key-based routing; by a greedy routing approach, VRR can quickly resolve the key-to-peerID mapping (rather than a series of virtual hops as in conventional DHT) and then follow a single virtual hop to the destination. While VRR focuses on generic layer-3 network, SEATTLE is based on the Ethernet where a Link-State protocol is assumed to exist underlyingly. SEATTLE can support one-hop DHT functionality in the switch-level network, because the key-to-peerID can be resolved locally due to the globally known Link-State map. The host-level routing info. is "indexed" by the MAC and the IP in the switch-level DHT. Thus, I am prone to think that SEATTLE use the DHT more as a kind of storage/index mechanism than as a routing infrastructure (after all, the routing simply follows the shortest path bestowed by the link-state protocol). The ROFL is an ambitious paper, which radically builds an Internet equivalency from scratch and aims at supporting scalable routing on semantic-free and thus flat identifiers. Technically, the specific design of ROFL borrows heavily from that of DHTs; the intradomain ROFL is essentially a VRR, and the interdomain ROFL is orgainized in a hierarchy as in Canon DHT. The ROFL hierarchy is in accordance to the AS's provider-customer hierarchy, enabling policy-aware routing.

Overview
Recently, having read a series of Prof. Matt's SigComm papers, I found a common topic in his research that really arouses my interest, that is, how to borrow the idea of DHT in designing an Internet from scratch (on the network layer and application layer). The VRR and SEATTLE build DHTs on network layer of generic networks and of Ethernet, respectively. The ROFL paper focuses on support of DHT routing (ID-based routing) and how to do so to enable policy-based routing on the Internet (which is such an AS-based network). VRR essentially transforms a leafset entry in DHT's routing table into several network-level routing/forwarding entries (along the virtual path from endpoint to endpoint), and by this way, both support identifier-based routing and accelerates the discovery of the destination identifier (ie., the node id closest to the one requested by the route). Rather than using DHT as a routing infrastructure, SEATTLE is actually using DHT as a directory service (or kind of distributed storage mechanism to store/index per-host routing info.). The routing in SEATTLE follows the shortest path between switches, which is bestowed by the underlying link-state protocol (so it's called one-hop DHT, with the id-to-switch mapping broadcasted and resolved locally). The ROFL paper leverages the hierarchical overlay in Canon DHT and applies it in the Internet where there is an analogy of hierarchy (ie., the AS hierarchy).

Detailed Schemes
I believe a crux in designing a networked DHT is how to make finger table aware of the network layer connectivity/topology.

The VRR essentially materializes the DHT finger table in the network layer; on peer a, a finger entry pointed to peer b would now be materialized to a series of entries distributed in the nodes' forwarding table along the path from a to b. By this means, a node x in networked DHT can view several virtual nodes which are close in their identifier, and the virtual nodes whose path of their virtual neighbors run through this node. These virtual nodes collectively form a partial/local view of the global identifier space for node x (similar to DHT), which helps determines which entry to go for incoming messages. Yet, still in accordance with network layer, x only forwards the message to its direct physical neighbor. As for how to route based on identifier, it's done by a two-phase process. First, the message is forwarded greedily to discover the node whose virtual neighbor is exactly the destination. Then a virtual path (essentially, a one-hop on overlay) can reach the destination. (The SEATTLE differs from VRR in that the discovery phase is locally resolved, thus is one-hop DHT.)

By contrast, the SEATTLE takes advantage of underlying link-state protocol (which essentially makes every node know all other nodes, globally) and by this means, achieves the one-hop network DHT. Specifically, the broadcasted link-state map enables a global view for every participating node (here, every switch), so each node can resolve the consistence hashing locally. That is, for a given key k, the switch to which the requested key k is consistently hashed to, namely the switch with identifier rk the most close to H(k), can be locally known (since every switch, along with their identifier, and the hash function are known). Because rk actually corresponds to the switch's MAC_ID (i.e., the location for switcher), the lookup can be resolved by a single physical route.

Since SEATTLE is built over the packet-switch network using link-state protocol, I am also wondering if a DHT can be materialized over networks using other kinds of protocols, say distance-vector routing protocol?

References:
1. Mathew Caesar, et al. "Virtual Ring Routing: Network Routing Inspired by DHTs." SigComm'06
2. Changhoon Kim, et al. "Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Ethernet." SigComm'08
3. Matthew Caesar, et al. "ROFL: Routing on Flat Label." SigComm'06

Google architecture - highly parallel computation on large cluster of commodity machines

Three core questions:
Q1. Why based on commodity PCs?
Q2. What's penalty?

Q3. What's the benefit? (Maybe it can be answered by posing another question "Why is Google so fast?")

A1. the basic observation is that commodity PCs has advantages in performance-price ratio. The money to buy a high-end multiprocessor server could be used to buy commodity PCs with typically much more total capacity in computation(CPU and memory) and in storage. This advantage is even substantial, when it comes to serving highly paralleled applications, like Google.

A2. apparently, the performance-price advantage wouldn't come free. There are several issues that should be addressed by a large cluster of commodity PCs, (which are not typical in a cluster of high-end servers).
- power problem: typically, the commodity PC can't meet the power consumption requirement at the Google's scale. Thus, explicit cooling mechanism is in need.
- failure: Since the hardware isn't designed for massive usage/computation like in Google's cluster, machine failure should be taken normal. To tackle this, Google's philosophy is "provide software reliability over unreliable hardware." Replication is typically used.
- administrative efforts: It comes with heterogeneity in both machine's hardware and software. Due to frequent machine updates (new machines cheaper and stronger come and old depreciated ones go), there are generally a variety of types of machines in the cluster. Overhead like manual configuration and software updates is not negligible, (though Google is a relative homogeneous application in which only few software is in require).

A3. the gain by using commodity PCs is that one can buy a great number of PCs. As such, high parallelism could be utilized. To see how it is done here, we need to take a closer look at how Google resolves huge query traffic from the world wide.
- Google has a number of cluster geographically distributed over the world. When user's browser issues a DNS lookup for "www. google.com," a deployed system would direct the query to a cluster that is geographically proximate and lightly loaded at that time (a cluster is identified by a IP, not a URL).
- Each cluster has a google web server which coordinates the query execution within this cluster. The query execution is really a two-phase procedure, with first querying index servers followed by retrieval from document servers (say, to extract the keyword-in-context snippet). In both phases, parallelism is used; the overall index/documents(copy of entire Web) are partitioned into shards, each served by a pool of machines. Within each pool, replication of shards is utilized to achieve higher throughput. (Note that since machines are really low-end, shards should be small enough.)

Hadoop运行日记

搞了几天，第一个cluster总算是起来了，如下：



第一个Hadoop Job，计算PI值。

Map-Reduce and its Applications

MapReduce Features and Architectures
Features: interface:
- simplified, abstracted and powerful
- restricted
hardware:
- commodity(low-cost, unreliable) machines
system:
- extremely scalable RAIN cluster
- high performance (parallel,)
- fault-tolerance and simple administration

Architecture: Shared-nothing computing and disk-shared storage
There are a global file system (say, GFS) and a cluster of computing nodes each of which has a local processor, memory and hard drive. To run a job with a dataset, mapreduce starts with reading splitted dataset from GFS and assigning each trunk to a node in the cluster. A comstomable map function is then called for each trunk, which outputs an immediate file containing a series of key-value pairs (with duplicated and sporadic keys). Then, a partition-sort-group operation is performed to generate inputs for reduce operations, which essentially aggragates all values associated with the same key. In the end, a series of key-value pairs (with distinct keys or values) are generated as the final results. The procedure could be illustrated as follows.

read (k1, v1) from FS and schedule them to a cluster of nodes
map: (k1, v1) -> list(k2, v2) {duplicated and sporadic k2}
partition-sort-group: list(k2, v2) -> (k2, list(v2)) {distinct k2}
reduce: (k2, list(v2)) -> list(v3) {distinct v3}

Note the initial schedule and manipulation of intermediate files (partition-sort-group operation) are performed by general MapReduce framework.

Observation & Motivation
What programmer want for data analysis?
- procedural programming: so pure sql is out.
- high-level declarative primitives (say, sql): so Map-Reduce interface is out, so we have Pig Latin.

What is present now?
- Map-Reduce framework:
-- the interface is rigid, thereby limiting programming power, (say fail to support n-stage data flow functions, like join).
-- too low level. programmers need to build tasks from scratch, even for the common tasks.

Technical Problems
Map-Reduce fails to support sql primitives, mainly join (over heterogeneous data sets).


FQ:
why shared-nothing means scalability?
why simply map-reduce can't treat well with data-join?
what is differences between P2P and cloud computing?(control in cloud computing is centralized)

About spaces in path in cygwin

标准流程是三步走：

设置
$ export JAVA_HOME=/cygdrive/c/program\ files/java/jdk1.6.0_02

cygwin中存储
$ echo $JAVA_HOME
/cygdrive/c/program files/java/jdk1.6.0_02

规范使用
"$JAVA_HOME/bin/java"

PS:
~转换为home目录。而这发生在从cygwin输入命令的过程中。

Distributed and Parallel Computing Systems

Why parallel & distributed computing?

In general, parallel and distributed computing is the area in which computation(CPU cycles) occurs in several far-away processors. Specifically, parallel computing is more "professional"; it refers to the computation pattern that aims at reducing response time and taking place on those systems that are specifically designed to support it. That is, the network/system in parallel computing is regular and controllable. For distributed computing systems, things are a bit different; the systems are built for some other purposes rather than computation time efficiency, like sensor networks, and the primary goal of distributed computing is result correctness and feasibility on existing systems (probably with limited resources and changing networks), although the computation efficiency is also a concern. We mainly focus on parallel computing, since it's more "pure."

Architectural Overview

1.Underlying Systems

Traditional parallel computing systems are divided into two main category, the shared-memory and the message-passing. In the former system, there is a global memory every processor can access. By this means, processors can communicate each other, thereby forming a clique network. The problem is memory access contention, when different processors want to access the memory simultaneously. A switching system is the solution which maps/connects processors to separate parts of the global memory in a non-blocked way.

The message-passing systems posses a number of processors, each with one own local memory. The inter-processor communications are done by network connections. Though without bus contention problem, the systems of this kind comes with how to design the network topology; excessive links/separate buses come with overly costs, yet less links increase communication latency.

Other methods for classification are also in use, like the number of processors, (a)synchronous operations, and global control granularity, etc.

2.Distributed Computation Model
-problem, algorithm, model(DAG), schedule,

A computation problem has a variety of serial algorithms. Each algorithm is actually a series of basic and dependent operations, generally represented by a DAG, with each vertex (non-input vertex) being a basic operation and each arc/edge being a computation dependence. To fully represent a parallel algorithm, the schedule is in requirement, which essentially is a mapping from the p processors vertexes in the DAG (non-input vertexes). More formally, a schedule is to assign processor Pi to the operation/vertex i at time ti, represented as {(i, Pi, ti) | i \in DAG}.

For a computation problem, our goal is to design a "good" parallel algorithm. The measure is in three terms: the number of processor p, the total executing time and the number of messages transmitted. A secondary measure would be the efficiency, E, measuring how much potential of current computation power is utilized and which may has to do with the economical costs. The definition is the fraction of time a typical processor is employed, as E = T1//p*Tp.

To design a parallel algorithm, the first thing to do is to design a good/optimal serial algorithm, with no duplicated computation/operations. In other words, the DAG is optimal in that it has no unnecessary vertex within it. For the given DAG (actually, the vertex set of DAG), the next is to find a good schedule, mainly involving how many processors are in need to achieve the "good" goal stated as above. The observation below is crucial for determining a good parallel system.

Observation: For a serial algorithm, we denote its serial computing time as T0, its minimal parallel computing time with unlimited processors as T:, the minimal parallel computing time with p processors as Tp. Then,
for p>T1/T:, Tp<2T:
for p<T1/T:, T1//p<Tp<2T1//p
Generally, Tp<T:+T1//p

The implication is the T1/T: is a special value for p at which the time complexity is 2T: and efficiency is 1//2 approximately. It is actually quite a good choice in selecting p: For p bigger than T1/T:, increasing p comes little or no benefit in shortening execution time-the time is at the best reduced by only a half, from 2T: to T:, while the efficiency approach 0 for large n, say O(1/logn); For p smaller than T1/T:, Tp could jump at another complexity level O(Tp/p), although efficiency could remain at o(1). Note that Tp, T1, T: and p are all a function to n (the problem size).

design over heterogeneous processors?
about finding optimal DAG?

Iterative method.
Jacobi iteration could build a dependency graph, based on which a DAG is constructed describing the procedure of how iteration should run, (see Figs in the book.) A straightforward solution could be assigning exactly the number of parameters as p. This strategy comes with excessive processors and unnecessary updates/communications. An improvement is the Gauss-Seidel iteration, which in essence makes part of updates involved in Jacobi method. The reduced updates lead to less processors in need, the same time efficiency and less communication costs. Finding DAG of gauss-seidel iteration could be modeled as Graph coloring problem.

New Advances

?Shared-nothing?
-Peer-to-Peer
-MapReduce

-Data Center Network, MultiCore,