101.Stocks Versus Other Investments

102.The Magic of Compounding 

103.Investing for the Long Run

104.What Matters and What Doesn’t 

105.The Purpose of a Company 

106.Gathering Relevant Information 

107.Introduction to [...]]]>

Part I – Foundations of Investment and Stock

Portfolio Management
- diversification: don’t put your eggs in one basket
- if you own about 12 to 18 stocks, you have obtained more than 90% of the benefits of diversification, assuming you own an equally weighted
portfolio
- don’t weight each stock equally in your portfolio if you want to outperform market index
- consider including mutual fund to cover area that you are not familiar with

Options
- option is the right (but you can choose to exercise it or not at will when it expires) to sell (put option) or buy (call option) some thing (it’s stock for stock option) at a specific price (stated in the option contract)
- option makes shorting possible

Investing Tips
- Keep It Simple
- Have the Proper Expectations
- Be Prepared to Hold for a Long Time
- Tune Out the Noise
- Behave Like an Owner
- Buy Low, Sell High
- Watch Where You Anchor
- Remember that Economics Usually Trumps Management Competence
- Be Careful of Snakes
- Bear in Mind that Past Trends Often Continue
- Prepare for the Situation to Proceed Faster than You Think
- Expect Surprises to Repeat
- Don’t Be Stubborn (Stubborn VS Patient)
- Listen to Your Gut
- Know Your Friends, and Your Enemies
- Recognize the Signs of a Top
- Look for Quality
- Don’t Buy Without Value
- Always Have a Margin of Safety
- Think Independently

One Sentence Summary

- Invest in long term basing on quantitative and qualitative analysis, don’t speculate if you don’t want to rely on luck.

Luis is a well known computer scientist who focuses on so called human computation technologies. He is famous for his previous projects CAPTCHA and reCAPTCHA. In fact, the word CAPTCHA is coined [...]]]> There is a popular presentation on ted Titled as massive scale online collaboration given by Luis von Ahn.

Luis is a well known computer scientist who focuses on so called human computation technologies. He is famous for his previous projects CAPTCHA and reCAPTCHA. In fact, the word CAPTCHA is coined by him for “Completely Automated Public Turing test to tell Computers and Humans Apart”  in the paper: CAPTCHA: Using Hard AI Problems for Security .

CAPTCHA is publicly well known since we should already encountered them many times in our daily web life. But reCAPTCHA is not so well known but in fact we should also had faced it many times and this technology is solving some hard AI problems every day.

The motivation behind reCAPTCHA is that, there is about 200M CAPTCHA inputs per day and each input spends a people 10 seconds around. This is really a huge time and intelligence waste, so Luis want to leverage such kind of resource to accomplish some useful work – solving AI problems that can be divided into 10 seconds small chunks.

Fortunately, there do be one such problem – book digitizing: scan real books and turn scanned pictures into text. There are already many OCR (optical character recognition) technologies to do this automatically. But they are not good enough, it’s said that for books older than 50 years ago, OCR can’t handle +30% of them. So we can divide those OCR task into small pieces (usually, one word per piece) and let people solve them while they are doing CAPTCHA on Internet, which is called reCAPTCHA.

How it works? Each time a CAPTCHA is requested, the system send two pictures to people. One picture contains word that the system already knows but the other are not, and the unknown one comes from books that need to be OCRed. When receiving feedback from human, the system check whether the first picture/text matches, if yes, it has some confidence that the second picture/text also matches. To handle those cases that the second pair failed to match, the system will send the same picture multiple times and use the most popular answer as the final result.

This works very well and the reCAPTCHA is acquired by Google in 2009.

But Luis didn’t stop there, now he is introducing another great ideas called Duolingo.

The problem Duolingo wants to solve is translate the web into different languages and the challenges for this are:
- Lack of bilinguals
- Lack of motivation

The way to solve this problem is： learning by doing for language learners.

When doing language translation exercises, the learners are given real world sentences that come from the web translation problem. This solution is pretty good because it can solve the web translation problem because there are so many language learner in this world, and it also has positive feedback look to solve the motivation challenge:
- Learn with real content, thus learners has good exercise to improve their skills
- Fair business model for language education, thus learners can learn for free since he had contributed some valuable stuff while learning

Luis called his problem as duolingo and I think this project is very promising and super attractive.

But there are two common problems:

1. Authentication

Sharepoint system usually adopt NTLM authentication system, which wget doesn’t support as of 1.11.4 for windows.

The solution is using a [...]]]> WGet is a great tool to automate the work of downloading documents when you work in a team whose shared resources are managed by sharepoint system.

But there are two common problems:

1. Authentication

Sharepoint system usually adopt NTLM authentication system, which wget doesn’t support as of 1.11.4 for windows.

The solution is using a NTLM supported proxy server:
- NTLMaps is a good NTLM enabled proxy server http://ntlmaps.sourceforge.net/
- Edit server.cfg under NTLMaps install folder, each section is self explained
- You need python before using it

To let wget connect to resource using proxy server rather than direct connection, you need to set environment variable http_proxy to http://localhost:5865 (the default NTLMaps port).

2. Restrict downloading documents

Sharepoint usually manages large amount of documents for different projects, so you need to restrict the type and folder path of the document you are going to download.

For document type, the –accept option works, for example: –accept=docx;pptx;doc;ppt;vsd;txt

For folder path, wget didn’t support specifying include folder and its subfolder, but an alternative is using -np option instead.

One of my full wget command line looks like:

wget -c -N -nH -r -np –accept=docx,pptx,doc,ppt,vsd,txt,aspx http://sharepoint/sites/xxx/yyy/xxx

NOTE: even if you just want to download *.ppt file, you also need to specify aspx file as accept file type, because wget needs these files to traverse other page and seek targeted files.

[Reference]
1. http://gnuwin32.sourceforge.net/packages/wget.htm
2. http://ntlmaps.sourceforge.net/

(Disclaimer: due to long paper list and lacking of strong DB background, it may contain misunderstandings and [...]]]> I attended VLDB 2011 during 29/08 ~ 01/09 in Seattle. Here are some brief observations and reports for this conference. Due to broad area coverage of VLDB, I just focus on System, Search and Transaction related materials.

(Disclaimer: due to long paper list and lacking of strong DB background, it may contain misunderstandings and personal biases, feel free to follow up and comment.)

=Basic Info=

VLDB is one of the top conferences in DB community (others are SIGMOD and ICDE) which focus on managing data and system for data management. For VLDB 2011, there are:

- 30 research sessions with 104 papers presented and 4 industrial sessions with 12 papers presented in 5 parallel tracks
- 8 out of 104 research papers are contributed by Microsoft people
- 31 out of 104 research papers are first authored by Chinese people (Domestic + Oversea)

o Mainland: 4
o Hong Kong: 4
o Singapore: 6
o Oversea: 17

Industrial Participation:
- Microsoft hosted the reception dinner on 30/08
- Google/Facebook/EMC had their recruiting/advertising booths at the conference site

Best Paper:
- RemusDB: Transparent High Availability for Database Systems

=Topics and Trends=

Hot Topics:
- Graph and Social Data Management: 5 sessions (17 papers), 2 tutorials
- Big Data Analyzing and Infrastructure: 3+ sessions (12+ papers), 1 tutorial
- Streaming and Realtime data analyzing

Traditional system topics for DBMS:

- Query Processing session covers:

o Partition the storage and querying processing of native XML database
o Use a new GroupJoin operator to speed up GroupBy and Join query
o Optimize Similarity Join using sensitive hashing

- Transaction Processing session covers:

o Scale OLTP system on shared-everything architecture using logical + physical partitioning
o Recovery algorithm implementation and optimization in DBMS where data management and transactional functionalities are separated
o New transaction semantic and isolation level definition for cooperated traditional transactions
o Hyder’s optimistic concurrency control algorithm in fast network and storage settings

It’s amazing that we found there were several (distributed) systems related sessions, where several papers are highly related to some on-going projects in our group:
- New Hardware Architecture, it covers

o Main memory based, column/row hybrid storage engine driven by application trace
o Compiling query statement directly into binary native code rather than iterator based execution plan
o Parallel B+ tree algorithm for many core processor

- Cloud Computing and High Availability, it covers

o Database storage live migration
o High available Database based on reliable Virtual Machine

- Distributed System (2 sessions), it covers

o Selectively partial replicating large-scale web databases
o Paxos based high available datastore
o DBMS like indexing on overlay network

- MapReduce and Hadoop, it covers

o Adding data co-location optimization in Hadoop for column-oriented storage application
o Automatic optimize Hadoop program using code analyzing

- GPU-based Architectures and Column-Store Indexing, it covers

o Sparse matrix-vector multiplication by leveraging GPU
o Transaction execution on GPU
o List intersection and index compressing using GPU

So 13 out of 104 research papers in VLDB are in system style. It’s also amazing that all system related sessions are crowded with audiences and there are active Q/A after the presentation. While in other sessions that I happened to attend, there are relatively small numbers of attendees and the session is also pretty quiet. System related publication institutes cover CMU, IBM Research, Intel Research and Yahoo!.

=Notable Papers=

Here I only focus on system, search and transaction related papers.

- RemusDB: Transparent High Availability for Database Systems
Umar Farooq Minhas, Shriram Rajagopalan, Brendan Cully, Ashraf Aboulnaga, Kenneth Salem, Andrew Warfield

This work was rewarded as best paper in VLDB2011 and came from Waterloo University.

The paper proposed the idea of making DBMS high available by leveraging VM HA technology called Remus and doing some DBMS specific performance optimizations for it. The paper first explained why Remus can be used to do DBMS HA without breaking ACID properties and then discussed 4 (3 memory related, 1 network related) DBMS specific optimizations.

To reduce the size of checkpoint synced from active to standby node, they put page content diff, not the whole original page content to checkpoint since most modifications between consecutive checkpoint touch only part of a page.

To avoid checkpointing pages that can be read from disk, they also track disk read operations and put some metadata into checkpoint data and standby server can use these small size metadata to reconstruct those memory pages.

They also implemented an interface to let application developer mark pages not replicated explicitly but didn’t use it in this paper since it has negative performance impact for DBMS software.

The previous optimizations seem not very DBMS specific and are pretty general. Other applications can also benefit from it, so I think it should be optimization work for Remus.

Yet another optimization is DBMS specific: it leverage transaction semantic to avoid Remus’s TCP packet level protecting. In this optimization, the underlying VM only need to protect Transaction related message such as acknowledge to ABORT and COMMIT message from client. This will reduce the latency a lot for irrelevant messages, such as those that comprising the transaction itself.

The ideas seem simple and easy to understand, the results seem very good and the work is done in real world code base: XEN, MySQL and PostgreSQL. These are probably the reasons why it is voted as best paper, although the innovation and technical challenge are not that big in system guy’s eyes.

There are some obvious drawbacks for this work:

o First, it only works with VM, which has some overhead especially for DBMS like applications since it is very I/O sensitive. The paper didn’t mention the overhead of running DBMS inside VM
o It only compare performance with raw Remus, not with other HA technologies, such as MySQL HA cluster. Building HA DBMS using VM may not be the correct way compared with other alternatives.
o Remus’s checkpoint technology don’t have knowledge about the transaction running inside it, so the standby server is consistent with active server in system level, but not transaction level. I.E., the latest state of standby server may not be consistent in terms of ACID, so it can’t be used to serve reading requests under specific isolation level.

- PLP: Page Latch-free Shared everything OLTP
Ippokratis Pandis, Pınar Tozun, Ryan Johnson, Anastasia Ailamaki

This paper aims to improve the salability OLTP system on many core system by combining existing logical (shared everything) and physical (shared nothing) partitioning technologies. The idea seems pretty elegant and the work seems to be very solid in both system’s perspective and DBMS’s perspective.

The meanings of “shared everything” and “shared nothing” in this paper are not the same as in distributed/parallel DBMS settings. They are the technologies used to eliminating the contention bottleneck of OLTP system on many-core platform: the former term refers to the technology of assigning different range of the same shared table to different thread to avoid high level locking among OLTP threads and the later one refers to the technology of partitioning the underlying data pages of one table and assigning each partition to different database instance.

PLP combines these two technologies by a new design called Multi-Rooted B+ Tree:

o Each logical partition has its own sub B+ tree as index, which is similar to shared nothing design
o The underlying data pages are shared among all logical partitions, which is similar to shared everything design
o Transaction manager will divide each transaction into a DAG of tasks, each task is within partition boundary and assigned to dedicated thread for that partition

Thus, this new design remains the benefit of contention free among transaction threads, low cost of repartitioning/rebalancing and eliminated the need for distributed transaction for cross-partition transactions.

But the work is based on a research prototype called Shore-MT which is built by WISC/EPFL, if it’s on top of popular open source DBMS such as MySQL or PostgreSQL, the work will be more convincing and making bigger real world impact.

- Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore
Jun Rao (LinkedIn), Eugene Shekita (IBM Research – Almaden), Sandeep Tata (IBM Research – Almaden)

There was a paper talks about using Paxos to build reliable data store in NSDI 2011 and here comes the similar story for DB. But it’s not a transactional storage, just a key/value style structured storage. And also, the system architecture and the protocol are very similar to that of PacificA.

The system, which is called Spinnaker, is a replicated range partitioned reliable structured storage that providing put/get like operations. The master is based on Apache Zookeeper.

The replication protocol is essentially a combination of two phase commit, majority consensus and group commit. It differs with PacificA on that it only requires majority members’ ack before doing the real commit at partition leader node. Follower recovery is simple and straight forward – learning to catch up with leader state. As for leader recovery, it uses Zookeeper to choose the follower that has the highest prepare number as new leader.

And another trivial difference with PacificA is that it allows reading at follower nodes by providing so called time line consistency semantic.

Replication and consistency is always a hot topic in DB conferences, both VLDB and SIGMOD has dedicated session.

- Column Oriented Storage Techniques for MapReduce
Avrilia Floratou (University of Wisconsin-Madison), Jignesh Patel (University of Wisconsin-Madison), Eugene Shekita (IBM Research – Almaden), Sandeep Tata (IBM Research – Almaden)

This paper presented several techniques to build column oriented structured storage and analyze engine on top of Hapood.

One is for storage enhancement:
o One column is stored as one file in HDFS
o Multiple related columns’ files are collated together by adding a new data placement policy for HDFS

Second technology is lazy record deserialization. The author argued that modern analytical applications are processing more and more complex data types, deserializing them from byte stream is pretty expensive. But most applications only need to process part of the whole records. So they proposed an idea:
o Deserialize only small part of a complex object to determine whether the object is needed to be processed
o Fully deserialize objects that need to be processed

Another optimization is using some specific technology to compress record, for example dictionary based schema to compress text string.

These works seems very trivial and incremental improvement for Hadoop system.

- CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop
Mohamed Eltabakh (IBM Research – Almaden), Yuanyuan Tian (IBM Research – Almaden), Fatma Ozcan (IBM Research – Almaden), Rainer Gemulla (Max-Planck-Institut für Informatik), Aljoscha Krettek (IBM Germany), John McPherson (IBM Research – Almaden)

This paper adds a new data placement policy for HDFS in Hadoop and uses it to speed up Join and Sessionized query like log processing tasks.

They observed that many log processing jobs need to process data partitions from different HDFS files, so placing correlated data partitions from different files will speed up the processing since it eliminate many data shuffle and remote I/O.

And also, although it starts from different angle, this paper convers only part of the work in previous paper.

- Automatic Optimization for MapReduce Programs
Eaman Jahani (University of Michigan), Michael Cafarella (University of Michigan), Christopher Ré (University of Wisconsin-Madison)

This paper proposed the idea of using static code analyzing to improve the performance of unmodified Hadoop jobs.

But this work only uses analyzing result to do storage related optimization:

o Using index to pre-prune useless record for mapping function by selection analyzing
o Pruning useless field for map/reduce by projection analyzing
o Application level compression optimization

They didn’t do any query plan wide optimization using code analyzing result, there seems to be a lot of promising future works here.

- Where in the World is My Data?
Sudarshan Kadambi (Bloomberg), Jianjun Chen (Yahoo!), Brian Cooper (Google), David Lomax (Yahoo!), Raghu Ramakrishnan (Yahoo!), Adam Silberstein (Yahoo!), Erwin Tam (Yahoo!), Hector Garcia-Molina (Stanford University)

This paper proposed an idea to replicate structured data table at record level rather than traditionally table/partition level. The basic reasoning behind this idea is that: most popular website contains global data, but access at different geographical sites have different focus of the global data. They call this idea as selective replication.

In their design, record replicas are divided into 3 types:
- Master, where write/update operation can be executed, asynchronously notify full replicas about the update/write
- Full, where read operation can be executed
- Stub, where only primary key is stored and R/W operations are forwarded to proper other replica

Given this setting, the paper focus on the placement of the 3 types of replicas and optimize it for bandwidth (forwarding/replicating) savings. They introduced static/dynamic placement policy and defined a language to specify replica placement constraints (for example, total replica, forced full replica sites etc)

The major difference between static and dynamic placement policies are that dynamic method can leverage historical access pattern data to adjust the placement and make better bandwidth cost. To reduce the bookkeeping cost of store/analyze historical access data, the dynamic policy is simplified as: promoting to a full replica when we see a read at a stub replica; demoting to a stub replica when full replica is notified to update but not read for a period of time.

Their experiment shows that in a 10% remote friend setting, bandwidth used can be improved by 2x.

The value of stub is that it can reduce one message round trip and avoid master hot spot in case that the placement is not optimal.

Drawbacks:
- Cross row transaction is not supported
- Require a primary key for each record

- Fast Set Intersection in Memory
Bolin Ding University of Illinois at UrbanaChampaign, Arnd Christian K¨onig Microsoft Research

This paper described a fast intersection algorithm for in memory set. The basic idea is: use machine word to encode set elements and use bitwise-AND to accomplish intersection. The author reported about 3x performance gain compared with inverted index based set intersection.

The main problems of this work are:
o it requires complicated and costly preprocessing and dynamically updating the set is also not easy
o it’s only applicable for in-memory big/small set intersection and the result scale should be small

- Efficiently Compiling Efficient Query Plan for Modern Hardware
Thomas Neumann (Technische Universität München)

This paper described a new DB query processing architecture that compiles query statement into machine code directly using LLVM. Current DB query processing is based on iterator model and the advantage of this model is the flexibility and pipelining. But the disadvantages are: 1, it will call next() for each record for each iterator, which results lots of function calls; 2, usually, the next() function calls are virtual functions, this makes the function call cost more expensive; 3, poor code locality for one query execution. So the author tried compiling query plan directly into machine code and the previous 3 drawbacks are eliminated.

But the problems of this approach are that the compiling cost, whether is LLVM code optimizer is good enough for DB query and how to adopt existing query optimization technologies in this method.

- Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units
Naiyong Ao, Fan Zhang, Di Wu, Douglas S. Stones, Gang Wang, Xiaoguang Liu, Jing Liu, Sheng Lin

This work comes from Baidu-Nankai joint lab and it aims speeding up index encode/decode and serving by leveraging GPU. I am not familiar with GPU programming, so skip the content here.

Industrial Sessions:

- Inspector Gadget: A Framework for Custom Monitoring and Debugging of Distributed Dataflows

o Yahoo! Reported a tool used to monitor and debug query processing dataflow.

- Jaql: A Scripting Language for Large Scale Semistructured Data Analysis

o IBM reported a script language over hadoop called Jaql to do large scale semi-structured data analyze which is used in its InfoShpere product.

- Tenzing – A SQL Implementation on the MapReduce Framework

o Google reported their HIVE copycat called Tenzing, which extended standard SQL with support for advance analysis. The paper also contains some MapReduce enhancement.
o This is probably the hottest paper in VLDB2011 and many famous DBMS gurus are crowded in the meeting room, probably due to the hot debate on Map/Reduce VS Parallel DBMS several years ago.
o Google adopted many technologies learned from Parallel DBMS and Dryad to improve Map/Reduce in order to build a low latency SQL compatible query analyzing engine, which “partially answered the previous debate” (Google presenter’s words).

- Citrusleaf: A Real-Time NoSQL DB which Preserves ACID

o A company called Citrusleaf reported their real-time NoSQL DB that supports ACID, which is called Citrusleaf and is also widely used in some of the world’s largest real-time bidding networks.

Here are some notes on this speech:

1. Not just simple plain forum, [...]]]> An architect of Baidu, who is being in charge  of the technology of Tieba product, gave a brief introduction on the back end technologies of this famous web application in the June activity of Baidu Salon.

Here are some notes on this speech:

Part I – Application Scale

1. Not just simple plain forum, but also photo/video/gaming
2. Includes front end, storage, anti-spamming, searching and mining
3. Numeric facts
- Bs of topics
- 10Bs of posts
- 10Ms of posts for single hot topic
- Ps of video data
- 100K+ QPS from client web browser
- 10K+ per second update message forwarding (I doubt this number)
- 100s service

Part II – Backend Technology: lightweight framework

For 80% common situations

1 MySQL
- prefer InnoDB than MyIASM with some modification (on disk writing pattern, with 10x perf gain)
- application optimization:
* avoid joining (by break normalization?)
* auxiliary index
* data locality
- single node numbers
* Ks of QPS
* 100Gs of Data
- mySql clustering
* master/slave for write/read separation
* home brewed request dispatcher (for easier programming and load balancing)

2 Cache
- hit ratio around 80%
- 10k ~ 100k QPS
- multiple granularity (page, picture, data item etc.)
- challenge: cache updating, writing request pressure

3 Flash Disk
- 5x – 10x perf gain without extra effort
- huge improve on random access
- size limitation: 500G (SSD) vs 10T (HDD)

Part III – Backend Technology: Heavyweight Infrastructure

For 20% rare scenarios

1. Partitioning
- Virtual, partitioned by application
** topic and post are separated
** relationship(list) and content are separated
- Horizontal, partitioned by key

2. Message Queue
- Reliable multicast communication system
- Handling mutation requests (I guess)
- Peak tps:100K+ (really?)
- It can only solve updating reliability problem, but seems that the speaker claims it also solves the scalability problem

3. In house storage node
- speedup by transforming random write to batch/append write
- memory patch: (background merge [mem + disk] in my understanding)
- write ahead logging for reliability
- highly optimized for application

4. In house distributed KV store
- for video storage
- replication (driven by MQ) for reliability
- append only
- Peta bytes scale

Part IV Backend Technology – Clustering Management

1. Most website are basically SOA architecture
- 100+ standalone small services
- service orchestration for single user request

2. Challenges in this architecture
- service/data upgrading
- failure handling
- performance variation

3. Service Management
- service metadata center management
- service registration and notification
- hide service cluster from application caller
- auto failure handling and load balancing
- (why service notification but not just try and ask registry if failed?)

Part V – Summary

It seems that there is nothing new in the presentation, all related technologies are well known. But its value lies in the fact that it gave us a high level overview of how today’s various famous web service is implemented and many numeric facts about this product.

[Reference]

0. Baidu Salon site
1. Speaker introduction and video
2. Speech ppt

Basically, Google+ [...]]]> The Wired magazine recently published a great story on the origination and development of Google+. The author has many inside information about Google and the Google+ product, so the story contains many useful and insightful information about　Google’s people-centric movement. I noted some of my understanding and comments here:

1. What’s Google+ ?

Basically, Google+ is Google’s social networking initiative to turn this algorithm-centric giant to be more people-centric. Currently, it consists of the following major components:
- Stream: Stuffs that are shared by people you care about (circled by you in G+ world), very similar to what twitter/facebook provide.
- Spark: Stuffs that pushed to you by Google according to your specified interesting.
- Hangout: Web based multi-user video chat service.
- Circle: A multi-dimensional way to organize your online social networks.

But this is just the very basic introduction, Google+ is more than just those even in today’s service. More detail follows.

2. Why Google+ ?

The Google+ is big product (or product umbrella) mainly driven by Vic Gundotra, SVP of Google Social Division, a former general manager at Microsoft in charging .Net/Live developer ecosystem.

The major driving forces of Google’s social efforts come from:

- Challenges from other pioneers such as Facebook. Facebook refused to open its content and connection data to Google while it gets more and more popular. People in Google worry that Facebook may use those valuable user contributed data to build a even better people-centric search engine that beats Google.

- Internet paradigm shift. The Internet and application in it become more and more people centric, which is not the same as when Google’s founded:

“The internet is nothing but software fabric that connects the interactions of human beings, every piece of software is going to transformed by this primacy of people and this shift.”  -Gundotra, SVP of Google social

3. The History of Google’s Social Efforts

January, 2004, Google launched it’s social networking service – Orkut, developed as spare time project by Orkut Büyükkökten while working at Google.

2007, Google start a initiative called Open Social to establish a open standard for social applications and platforms.

2009, a social networking based communication tool called Wave was introduced during Google I/O.

2009, a twitter like product called Buzz is integrated into Gmail.

Non of them had been considered as a successful product, but Google’s social networking efforts continues.

March 2010, only a month after the Buzz debacle, Google’s head of operations, Urs Hölzle, sent out  an e-mail evoking Bill Gates’s legendary 1995 Internet Tidal Wave missive to Microsofties. Hölzle acknowledged that fundamental way people use the internet has changed. He did started some social networking related projects within Google and his memo became known as the Urs-Quake.

May 2010, 50 of Google’s top people gathered together to discuss the challenges faced by the search giant. Amit Singhal, one of the company’s most respected search engineers, urged that Google dramatically expand its focus to create a hub of personalization and social activity.

The Google leadership team adopted Singhal’s suggestion and code named the projects as: Emerald Sea. Gundotra made a pitch to lead the Emerald Sea project, and got the nod. Bradley Horowitz became his co-leader and collaborator.

Google VP of product management Bradley Horowitz (L) and Vic Gundotra, Senior vice president of social for Google. (from [1])

4. The Birth of Google+

- It got started just after the May meeting, and covered 18 current Google products, with almost 30 teams working in concert.

- It produced a working prototype 100 days after the May meeting (August 2010).

- It became ready for dogfood around October 2010.

- It got its first 50 users by email invitation, 600+ in around one hour, 90% of Google employe within one day during dogfood.

- The first round of dogfood feedback is not very positive due to lacking of tutorial and feature complication – hard to comprehend and hard to use .

- It is refactored and re-conceptualized according to feedback: some features are delayed to future release, some are separated out as other standalone features, such as the +1 button.

- It rolled out the second round dogfood with selected people within Google in Spring, 2011 and got positive feedback.

- It started its field test @ June 28, 2011, where external users can experience this product in invite-only way.

5. Feature Drill down and Insights

Stream – ordered shared items from you social graph. It’s a pretty typical social networking feature that is provided by twitter, facebook and weibo. But it has its uniqueness:
- It has no limitation on the word count of item, while Twitter/Weibo limits it to 140
- It has +1 button and can be commented with instant update to online readers
- It can be filtered by author groups, which is a very handy feature when you follow large amount of people

Spark – streamed items from Google according to the topics you explicitly specified. Sounds like a normal search query result page but Google had adjusted the filtering and ranking policy to make it more suitable for sharing in Google+ world. It favors more on fresh, social popular and visual items discovered from the web.

spark is the way Google try to understand your unique interests and feed you with related information. But it may also be the cover that hide the facts that Google is using the privacy related information from Gmail content and your search history to know more about your interests.

Circle/Sharing – offers a simple means of organizing one’s social network so that your sharing is micro-targeted: you organize your social network into various (maybe overlapped) circles and share items to specific circles. It may be the most important and also most controversial feature in Google+.

Some people said that it help them control who will see shared items but others said that it makes sharing action very complicated and the whole social network become very hard to manage and understand.

In my personal experience, it’s a over designed feature. I am forced to think/select what’s the target audience when I want to share something online, which break the famous UX design rule: DON’T MAKE ME THINK. And also, it’s very hard for a user to understand thoroughly exactly who will ultimately see the item I am going to share.

Here is the exact Google+ share visibility workflow: (sorry, it’s in Chinese, but you can get the idea)

(digram from william feng)

How many people on this planet has enough patient to fully understand this logic and exercise it each time when he want to share an interesting item?

The idea of circle and multiple social network is said to be the result of the following research result:

Google claims that it create the idea and concept of circle because it behaves exactly the same way as our real social experience. Let’s assume that it does behave exactly as real social activity, but will it better to behave the same as reality? I don’t think so. We spend more and more time on online social activities because it’s different (in positive way) from the boring real society. For me, I use various online social service because it’s more convenient for me to keep in touch with real friends and it’s more open and easier for me to get know more friends, especially those that aren’t available in real life. If the online society is the same as the real one, what’s the attractiveness of the online social service? I feel Google’s circle concept is making the online social more enclosed, more complicated to understand and master.

There are some other critics said “SNS just do what virtual world should do, let some other stuff happen in real world” and “in real life, the circle is not chosen when you want to convey some message, rather, you choose what to say when you are in different situation and different circle”.

I do admit that there are some situations that I didn’t want my message to be visible to some one in my social network. But it’s better to be fulfilled by a feature: selecting what’s the target user you want to hide your message/status from, I.E., you need to do minus rather than addition. Here, the minus operation is easier to understand and involves less thinking.

But circle is a good idea for streaming stuff filtering especially when you follow many people and they have different message updating cycle.

6. Misc

- “There are only a few emotions that can effect change at a large organization,” he (Gundotra) explains. “One is greed and another powerful one is fear.” Outright greed is gauche in the Googleplex, so Gundotra prepared a slide deck that mocked up challenges from Google’s competitors (notably, Facebook), illustrating how each company could turn Google upside down.

- Emerald Sea has been the rare initiative in Google where the company was not breaking ground but defensively responding to a competitor’s success. (One engineer has described this process as “chasing taillights,” noting that me-too-ism has never been a strength for Google.) It’s also, claims Gundotra, the most extensive companywide initiative in Google’s history.

- “We put the product to [dog food] before it was fully baked, before we hardened the system and polished it and knew what we were doing,” says Horowitz. “We had no getting-started screen, no intro video. It was hard for people to get their hands around what it is and how to begin interacting with it. It was as if Facebook had been in stealth mode for seven years and then launched in its entirety at once today — it would have been an overwhelming, hard-to-comprehend, hard-to-understand system. The feedback we was got was: Simplify.”

- No one expects an instant success. But even if this week’s launch evokes snark or yawns, Google will keep at it. Google+ is not a product like Buzz or Wave where the company’s leaders can chalk off a failure to laudable ambition and then move on. “We’re in this for the long run,” says Ben-Yair. “This isn’t like an experiment. We’re betting on this, so if obstacles arise, we’ll adapt.”

- Because of the pressure the stakes and the scale, Gundota insisted that Emerald Sea should be an exception to Google’s usual consensus-based management style.

- “This is a top-down mandate where a clear vision is set out, and then the mode of moving forward is that you answer to Vic,” Rick Klau told me last year. “If Vic says ‘That looks good,’ then it looks good.”

[Reference]

[1] Inside Google+ — How the Search Giant Plans to Go Social
[2] The Real Life Social Network V2
[3] Google Plus Wiki
[4] 40 Google Plus Tips
[5] Google Plus Tutorial

1. How to get SSH service?

- Register and web hosting or virtual private [...]]]> There is a well known wall called GFW (功夫网) in Chinese Internet and there are also many ways to cross over it. Private proxying using SSH may be the most reliable, available and cheapest way to accomplish this crossing over.

1. How to get SSH service?

- Register and web hosting or virtual private server service from outside China mainland

- For web hosting, I recommend bluehost, for vps, I recommend linode

2. How to proxying over SSH

- Create sock5 proxy over SSH using plink or Bitvise Tunnelier

- Config you browser wisely. I recommend: FireFox + AutoProxy

Now make a deep breath and feel the fresh air of freedom!

1. auto_ptr
- RAII and transfer-of-ownership semantics based, but no shared-ownership
- Managed heap object will be owned by one and only one
- Assignment/Copy Construction will transfer ownership
- Can be compiled with STL containers, but wrong semantic

2. scoped_ptr
- RAII semantic based, [...]]]> Part I – Brief Summary for Various Smart Pointers

1. auto_ptr
- RAII and transfer-of-ownership semantics based, but no shared-ownership
- Managed heap object will be owned by one and only one
- Assignment/Copy Construction will transfer ownership
- Can be compiled with STL containers, but wrong semantic

2. scoped_ptr
- RAII semantic based, but no shared-ownership, nor transfer-of-ownership semantics
- Managed heap object will be owned by one and only one pointer
- Assignment/Copy Construction are forbidden
- Can’t be compiled with STL containers

3. shared_ptr
- Reference count based
- Managed heap object could be owned by multiple smart pointers
- Assignment/Copy Construction will add ownership
- To avoid memory leak, don’t construct temporary shared_ptr object on function call parameter
- Can’t construct a shared_ptr object from this pointer (Causes double deletion) 

4. intrusive_ptr
- Basically the same as shared_ptr
- Shared ownership of objects with an embedded reference count
- Can be constructed from an arbitrary raw pointer of type T *
- Try shared_ptr first, if  it isn’t obvious whether intrusive_ptr better fits your needs

5. weak_ptr
- Just reference, no ownership, no RAII, no shared-ownership, no transfer of ownership
- Linked to a shared_ptr object and known by it
- Shared_ptr will reset weak_ptr when it decides to destroy the dynamic object owned by it
- It’s a safe(no need to worry the dangling reference) way to reference a dynamic object but don’t own it
- A nice feature of weak_ptr is that, it can access the internal state of corresponding shared_ptr object 

6. unique_ptr
- C++0x  introduced a new scoped_ptr like pointer: unique_ptr to replace auto_ptr.
- It hide assignment operator and copy constructor
- Transfer-of-ownership can be done using std::move() explicitly

These smart points are only suitable for single dynamic object, for object array, use other smart pointers whose name ended as “_array”.
 
Part II – Tips for shared_ptr

1. shared_ptr VS weak_ptr
- shared_ptr owns some heap object
- weak_ptr points some heap object 

2. Handling this Pointer

It’s safe to construct a shared_ptr object from a newly created heap object since it’s not managed by any other shared_ptr object yet. But when you want to pass this pointer to a function that expects a shared_ptr object, you will encounter a tricky problem because most likely, the heap object is already created and managed by other shared_ptr objects.

The problem is that, in general, you can’t create a shared_ptr from an existing raw pointer – the new shared_ptr you create won’t “know” about the other instances that refer to the same object and you’ll get multiple-deletes.

2.1. Use enable_shared_from_this from boost library

You can derive from enable_shared_from_this and then you can use “shared_from_this()” instead of “this” to spawn a shared pointer to your own self object.

How it’s implemented?
- Add a weak_ptr member to point to an existing shared_ptr object that manages this object
- When shared_ptr object get constructed from raw pointer to a this kind of object, it will properly set the weak_ptr inside that object
-  shared_from_this() will construct a safe shared_ptr object from the weak_ptr member
- In boost shared_ptr implementation, the “sp_enable_shared_from_this()” function will get called in shared_ptr’s constructor. In this function, if the passed in dynamic object derives from enable_shared_from_this, it will set the weak_ptr member using itself.

If you adopt this method, you should be careful not creating such object on stack. Because when creating object on stack, the object is not managed by any shared_ptr, so no shared_ptr’s constructor gets called and the corresponding weak_ptr member won’t get set properly.

2.2 If you know that your object is long lived, you can do the following:

struct null_deleter
{
template void operator()(T *) {}
}

Then in your code, just return a shared_ptr(this, null_deleter()).

3. Handling Null Valued shared_ptr Object.

When you are using shared_ptr in your code, sometimes you need a NULL equivalent stuff to represent a pointer that didn’t point anything meaningful.

Generally speaking, you have the following choices:

• Return iterators and the end iterator if not found
• Boost::optional
• Silly return codes

Out of all the options boost::optional & exceptions (when there really are exceptional circumstances) are the best methods, if you are dealing with containers return an iterator to end and test for the end iterator.

Returning Zero/Null for smart pointers is acceptable in some cases too, when the other alternatives don’t make sense. Consider the following code:

class some_class_name{
public:    
template<typename T> operator shared_ptr<T>() { return shared_ptr<T>(); }
} nullPtr;

Use this template function when any boost::shared_ptr<> typed null pointer is needed.

[Reference]

smart pointers overview
http://en.wikipedia.org/wiki/Smart_pointer
http://www.informit.com/articles/article.aspx?p=25264
http://www.drdobbs.com/184401507
http://dlugosz.com/Repertoire/refman/Classics/Smart%20Pointers%20Overview.html
http://ootips.org/yonat/4dev/smart-pointers.htm

unique_ptr
http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=401 

shared_ptr
http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=239

weak_ptr
http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=300
http://www.drdobbs.com/184402026;jsessionid=X2T3WUC5FRMSDQE1GHPSKHWATMY32JVN

shared_ptr for this pointer
http://stackoverflow.com/questions/142391/getting-a-boostshared-ptr-for-this

1.1 Parallel Database for OLAP (Shared-Nothing/MPP)

TeraData
- TeraData Home
Just a survey article on materials on parallel database products and technologies for OLTP/OLAP applications. It mainly covers major commercial/academic efforts on developing parallel dbms to solve the ever growing large amount of relational data processing problem.
 
Part I – Parallel DBMSs

1.1 Parallel Database for OLAP (Shared-Nothing/MPP)

TeraData
- TeraData Home
- Teradata DBC/1012 Paper
- NCR Teradata VS Oracle Exadata

Vertica
- Vertica Home
- The original research project: C-Strore

Paraccel
- Paraccel Home
- MPP Based Architecture
- Columnar Based Storage
- Flash Based Storage

DataLlegro(now MS Madison)
- Design Choices in MPP Data Warehousing Lessons from DATAllegro V3
- Microsoft SQL Server Parallel Data Warehousing

Netezza
- Netezza Home
- Acquired by IBM
- Hadoop & Netezza: Synergy in Data Analytics (Part 1, Part 2) 
- Netezza Twinfin VS Oracle Exadata (eBook, Blog)

GreenPlum:
- GreenPlum Home
- Combined: PostGreSQL/ZFS/MapReduce
- Acquired by EMC

Oracle ExaData:
- ExaData Home
- OLTP & OLAP Hybrid Orientation
- 1 * RAC + N * Exadata Cells (Storage Node) + Infiniband Network
- Exadata Cell: Flash Cache + Disk Array + Data Filtering Logic (partial SQL execution)
- Exadata – the Sequel is a great Exadata study article

IBM DB2 Data Partitioning Feature (can work with both OLAP/OLTP)
- formerly known as DB2 Parallel Edition (An Shorter Overview)
- DB2 At a Glance – Data Partitioning Feature
- Simulating Massively Parallel Database Processing on Linux

AsterData:
- Supercharging Analytics with SQL-MapReduce
- Aster Data brings Applications inside an MPP Database 

Misc Articles:
- What’s MPP?
- Comparison of Oracle to IBM DB2 UDB and NCR Teradata for Data Warehousing
- SMP or MPP for Data Warehouse
- Dividing the data Warehousing work among MPP Nodes
- SANs vs. DAS in MPP data Warehousing
- Three ways Oracle or Microsoft could go MPP

1.2 Parallel Database for OLTP (Shared-Disk/SMP)

Oracle Real Application Cluster
- Oracle RAC Concepts
- Oracle Parallel Database Server Concepts
- Oracle RAC Case Study on 16-Node Linux Cluster

IBM DB2 for z/OS (with Sysplex Technology)
- Share Disk and Share Nothing for IBM DB2
- What’s DB2 Data Sharing?

IBM DB2 for LUW (with pureScale Technology)
- IBM DB2 pureScale: The Next Big Thing or a Solution Looking for a Problem?
- What is DB2 pureScale?
- DB2 pureScale Scalability (section 1, section 2)

Part II – Academic Readings

2.1 Overview
1). Parallel Database System: The Future of High Performance Database Processing
2). Survey of Architecture of Parallel Database System
3). The Case for Shared Nothing
4). Much Ado About Shared-Nothing 

2.2 Research System
1). XPS: A High Performance Parallel Database Server
2). The Design of XPRS
3). Prototyping Buuba, H High Parallel Database System
4). The Gamma Database Machine Project
5). NonStop SQL, A Distributed, High-Performance, High-Availability Implementation of SQL
6). Parallel Query Processing in Shared Disk Database System
7). Architecture of SDC, the Super Database Computer

2.3 Commercial System
1). A Study of A Parallel Database Machine and Its Performance – The NCR/TERADATA DBC/1012
2). A Practical Implementation of the Database Machine – Teradata DBC/1012
3). DB2 Parallel Edition
4). Parallel SQL Execution in Oracle 10g
6). Shared Cache – The Future of Parallel Database
7). Cache Fusion: Extending Shared-Disk Clusters with Shared Caches

The presentation video can be [...]]]> 01/18/2000, Michael Burrows gave a technical presentation  at UW. In this video, he talked about the design of the AltaVista indexing system and the search engine site. The presentation is short and brief, but covers many core design and concepts which are used in today’s commercial search engine systems.

The presentation video can be found at uwtv: http://uwtv.org/programs/displayevent.aspx?rid=2123

And I had recreated the PPT used in his video for further use. I tried my best to record the text and redraw the diagrams, but there may be many errors during this process. The copyright is of Mike.

I think the most interesting design is the Location Space and ISR abstraction. The first one enables store any information using inverted index mechanism and the second one solve the problem of interpreting complicated search query semantic.

But it’s not easy to fully understand how the whole ISR system works to serve various query semantic.

And in the second part of his presentation, Mike mentioned many aspects of AltaVista search engine web site. Many of the experiences and designs are still good reference for today’s Internet web application.


[Reference]
1. http://www.searchenginehistory.com/
2. http://en.wikipedia.org/wiki/Search_engine
3. http://en.wikipedia.org/wiki/AltaVista

2. Add new language support Option -> Preferences -> Languages -> Import/Add

3. Associate new file type to some language
Options -> Document Options -> Document Type -> Add Type

4. [...]]]> 1. Specify file types to add in a project
Option -> Document Options -> Document Type -> Include when adding to projects

What about the ANSI C standard regarding this problem?

The standard defines 5 standard integer types:
- [...]]]> While writing codes for multiple platform (in terms of both OS and CPU Arch), making the code independent of the exact byte size of each integer type in c/c++ on each specific platform becomes a typical challenging problem.

What about the ANSI C standard regarding this problem?

The standard defines 5 standard integer types:
- unsigned char - short int - int - long int - long long int

It also defines some limitations on these types in limits.h

But it didn’t say explicitly on the exact byte size of each type.

Common understanding on the standard is that it requires:

sizeof(short int) <= sizeof(int) <= sizeof(long int)  sizeof(long long int)

So how about popular compiler’s documentation on this?

Visual Studio 10 has an article on MSDN describes the exact size of each integer type.

From that article we can see:
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 4
sizeof(long long int) = 8

And these constrains are true on both 32/64 bit platforms.

To help programmer aware of the exact size of integer types they are using, vs 10 introduces some other integer types:
__int8, __int16, __int32, __int64 and their unsigned counter parts.

In fact, ANSI c99 also defined those fixed width integer types in stdint.h
uint8_t/int8_t
uint16_t/int16_t
uint32_t/int32_t
uint64_t/int64_t

To scanf() and printf()? The format string for these types are defined in the standard header – inttypes.h. For example, this is inttypes.h for visual studio.

And here is a good summary on how to use format strings to deal with integer types in c/c++

[Reference]
1. stdint.h in C99
2. Integer Types in VS10
3. ANSI C99 Spec
4. Integers in C99

It’s good to know source of referenced data but what’s the confidence of these data source?

I had a look that website to learn how the ranking list [...]]]> I recently read some material talking about the page view ranking of some web sites. It said that the source of the ranking data is alexa.com.

It’s good to know source of referenced data but what’s the confidence of these data source?

I had a look that website to learn how the ranking list is generated. Here is my understanding:

1. Alexa’s traffic rankings are based on data collected from Alexa Toolbar and other, diverse sources over a rolling 3 month period.

2. A site’s ranking is based on a combined measure of Reach and PageViews.
- Reach is determined by the number of unique Alexa users who visit a site on a given day.
- PageViews are the total number of Alexa user URL requests for a site. However, multiple requests for the same URL on the same day by the same user are counted as a single pageview.

3. Sites with relatively low traffic will not be accurately ranked by Alexa. Traffic rankings of 100,000+ should be regarded as not reliable. Conversely, the closer a site gets to #1, the more reliable its rank. Since Alexa only uses sampled data from all Alexa Toolbar and Alexa Toolbar in fact is just a small portion of the whole Internet user.

So it seems that the ranking list should not be so authoritative as very few people uses its toolbar. But why it gets so popular and important for many VCs? I guess it’s mainly due to the lack of other better solutions.

The better data provider should be web browser vendors like Microsoft, Mozilla and Google. But obviously, they are not willing to share with community the data they collected for privacy concerns and potential legal issues.

[Reference]
1. How Reliable Are Your Traffic Ranking?
http://www.alexa.com/faqs/?p=139

2. How are Alexa’s traffic rankings determined?
http://www.alexa.com/faqs/?p=134

3. About the Alexa Traffic Rankings
http://www.alexa.com/help/traffic_learn_more

The following content is copied from a MSDN blog post named- Product Development Disciplines at Microsoft, I just [...]]]> I really want this blog to be a place to express my own ideas and thoughts, but I don’t refuse reference other people’s great ideas, especially when they are really helpful for me or potential readers.

The following content is copied from a MSDN blog post named- Product Development Disciplines at Microsoft, I just highlighted some lines.

“Over the last several months in my role here in China, I have given talks at several leading universities and met with many of the leading faculty and students working on technologies related to the Data Platform. I’ve also spoken at several industry conferences, meeting with customers, partners, analysts and other industry folks. There are many topics that come up at these meetings – changing technology trends, distributed development, the tremendous growth of Asia etc. But one topic that seems to come up more than almost any other is the question of how we organize and conduct our product development in Microsoft. I suppose this is only natural – Microsoft is one of the most successful software companies in the world, and the software industry here in this region is poised for tremendous growth, so it makes sense that people in the industry are eager to learn from the our experience over the last quarter century.

This is actually a very big topic and within Microsoft we have an Engineering Excellence group that actually runs courses that can span several days and provide an overview of Microsoft’s software development methodology, our engineering system, organizational structures, best practices, tools and technologies we use internally ensure quality, reliability, security etc and a variety of related topic. By no means would we claim that we have all this figured out perfectly and have a perfect system, but there is indeed a lot of accumulated knowledge and experience that we can share. And we do actually share this information, in appropriate form, with others in our industry, worldwide and also in this region.

As this is indeed a large topic, I don’t want to get too deep into this here, but I do want to address one aspect of our engineering system – the core disciplines that we organize our R&D teams around and the particular roles that each of these disciplines plays. I want to discuss this because I believe Microsoft does this a little bit differently from the rest of the industry even in the US, and especially here in China there is not a good understanding of these core disciplines and what role each of them plays.

Traditionally, the Microsoft engineering system has consisted of 3 “core” disciplines: “Development”, “Test”, and “Program Management”, also known as Dev/Test/PM for short. I’m going to touch on each of these briefly here, but I like to introduce them in a different order:

PM: When we think of engineering disciplines, most people start with “Dev”. For me however, things really start with the Program Management discipline. At Microsoft, “PM” means many different things, but for me the core essence of the PM role is two things:

1. The first part of the PM’s job is to understand the customer’s requirements and translate that into a functional specification of what we should build. This is where it all begins. If we don’t understand the customer, it is not very likely that we’ll end up building the right thing.

2. The second part of the PM’s job is to work with Dev and Test to translate the initial specification into a living, breathing product.

I find that many people, especially here in China, think “Project Management” when they hear PM. Indeed, Project Management is part of a PM’s job (under #2 above), but it is only a part of the PM’s job. The real skill that a PM brings is the expertise to listen to customers, understand the world from their point of view, and then to design a solution for their problem. This does not just mean giving customers what they ask for literally, but to truly understand them and design a solution that solves their problems even if the customers could never imagine the solution – as the famous saying goes, if we had only listened to customers, we would have looked for a faster horse, not come up with the automobile.

Dev: Of all the engineering disciplines, this one is probably the one people think about the most commonly. Dev is short-hand for “Development”, the folks who responsibility it is to actually design and build the software that we ship. The essential job of Dev is to take the functional specification produced by PM and translate that into an actual implementation. In the world of mission-critical system-level software, this implementation better be extremely reliable, secure, manageable, scalable and high-performance. And the designs and implementations Dev produces better stand the test of time and last for several versions and years to come.

Test: The test discipline in Microsoft is much misunderstood, certainly externally, but sometimes internally as well. When I first came to Microsoft many years ago, I was (pleasantly) surprised to find that Microsoft had almost as many, if not more, testers as developers. Coming from a company that had a much less developed testing discipline (and where as a result, quality assurance was considerably weak), it took a little while to get used to what the essence of the Test discipline really is. The reality is that, in Microsoft, how fast we can ship software depends on not how quickly we can design and implement it but rather on how quickly we can test it. This is because every piece of software we ship, especially on the systems-software side, has to pass an extremely high quality bar. The Test discipline is really an complex area, and one where have learned a lot over the years in terms of different types of testing that we employ – unit tests, functional test, integration tests, stress and long-haul tests, performance tests, security tests, localization tests, etc. The set of tools and techniques we employ in test is truly some of the most impressive and complex – automated test harnesses, automated test generators, automated test failure analyzers, automated security “fuzzers”, fail-point and state-machine based testing.

The three “core” engineering disciplines described above are like the 3 legs of a chair – you need all three of them, and in a balance, to have a proper engineering organization. No one leg can dominate the other – otherwise, you get an organization that may not be in touch with customers needs or one that does not pay enough attention to quality. Indeed, the three disciplines are a little bit like the branches of government – they form a system of checks and balances that ensures we understand what customers want, we design and build that with high quality, and we ensure that we deliver a product that meets customer expectations in every regard.

It is also important to emphasize that we aim to attract the best talent to all three core disciplines – the bar is equally high for all the disciplines, it just happens to be that the passion and skill-set for each is a little different:

- PMs usually have a passion for working with customers, conceptualizing what the product should do, and then working with their Dev and Test peers to coordinate all the work to make sure we deliver exactly that.

- Developers have a passion for building top-quality software – software that is innovative, simple, reliable, secure, scalable, high-performance and stands the test of time.

- Testers are passionate about finding all kinds of ways to break software and making sure making sure we find all the issues and bugs before we ship it to customers.

When we interview candidates, a very important part of what we do is find out which discipline the person’s talent and passion really lie in and directs them accordingly. Of course, over the course of one’s career, one’s passion and talent may change, and the person may change disciplines as a result – I myself started in the Dev discipline before switching to PM. This is only natural and we actually encourage that as a way to build better teams.

Other disciplines

It is also important to point out that although the three disciplines mentioned above are what have traditionally been considered the “core” disciplines at Microsoft, there are several other disciplines that are also becoming increasingly important. For example, User Experience (UX) professionals are essential to ensuring that products are intuitive and natural for users to use. A great user experience can make the difference a product that customers love versus one they merely tolerate. UX is certainly very important for products aimed at end consumers, but it is also important for all our audiences – Developers, IT Professionals, Information Workers.

As we move into the Software+Services era, a variety of disciplines related to architecting, building and running extremely large-scale infrastructure becomes increasingly important. Again, while this has been true for some time for our consumer facing web properties such as MSN and Live, it is now becoming increasingly important for all our product groups as more and more of them take steps to evolve their products along the Software+Services model.

Many candidates I talk to often want to discuss what role at Microsoft would be the best fit for them and how they can grow their careers. The best advice I can think of is to work on a technology and a role that they are really passionate about.

As I mentioned above, we value all the disciplines equally and a well-balanced organization needs great people in all the different roles. While different disciplines appeal to people with different passions and skill-sets, all the disciplines offer opportunities for innovation and great work. And all of them offer opportunities for advancement and leadership. Indeed if you look across the senior levels of Microsoft, there are leaders who emerged from various disciplines – what they shared was a passion for what the work they were doing.

I hope this discussion of the different engineering disciplines at Microsoft and the approach we take to them shall be useful for the many people who seem to be interested in this topic. If you have any questions or comments, feel free to post a reply to his entry.”

To design and implement a IR system that has high relevance quality, we must have some methods to measure the quality of relevance.

Generally speaking, a [...]]]> One of the challenges Information Retrieval system faces is Relevance Quality. It’s the main factor that determines end end user’s happiness. (The other two are latency and corpus size)

To design and implement a IR system that has high relevance quality, we must have some methods to measure the quality of relevance.

Generally speaking, a measuring system consists of three components:
- Test Corpus (Document Collection for Test purpose)
- Test Query Set (Set of Queries for Test)
- Measuring Parameter (usually a function, used to measure the retrieval result of an IR system for some query in the query set, using the test corpus)

Test Corpus/Query is another story and we only focus on measuring parameter/function here.

1. Precision/Recall for un-ranked retrieval result

Precision = #Relevant Documents Retrieved / #Retrieved Documents, it’s the percentage of the returned documents that are really relevant to the user query. (查准率)

Recall = #Relevant Documents Retrieved / #Total Relevant Document, it’s the percentage of the relevant document in the corpus that is retrieved in the query result. (查全率)

2. NDCG for ranked retrieval result

NDCG stands for Normalized Discounted Cumulative Gain, which is a human rating based measuring system.

Gain – user will assign a numeric value (which is a score gained) to represent the goodness of a returned document for some specific query request.

Cumulative Gain – user will assign gain value for each document in the top K returned results, the values is assigned individually and independently.

Discounted Cumulative Gain – when assigning relevance score to the returned document, there is a weight related to the order of the document in the retrieval result.

Normalized Discounted Cumulative Gain – it’s easy to understand: make the final value to be [0, 1]. Usually, the DCG score of the ideally ordered (ordered using Gain score) document list is used as the normalizing factor. So

For concrete example of how to compute the NDCG value of a query result, please see wiki on NDCG

NDCG is widely used in today’s commercial search engine evaluation, but the problem is that, if the returned document is ordered in the same way as the decreasing order of gain score, the NDCG value will be the max:1.

This means that, NDCG is only used for the measuring the ranking algorithm of a search engine and can’t tell whether the returned document is highly related to the user intention or not. But in end user’s perspective, the perfect return result should be highly related document ordered properly.

More technically, a typical query serving sub-system of an IR system has two phases, one is matching (find highly related document), and the other is ranking (order the matched documents). NDCG may be a proper tool to measure the ranking phase, but definitely not the matching phase. So I think is not an ideal measuring mechanism for IR system.

So, tuning the whole system against NDCG score only may not be a correct direction for search engine improving.

Update@07/09
- The ideal set, which is used to calculate the normalization factor, is the highly scored documents list ordered properly, not the proper order of the returned documents. So the problem I mentioned above doesn’t exist.
- But the final effect of this measuring method depends on what test corpus, what test query, what the predefined gain score for each query.

Part I – Overview of Search Engine Evolution: 1999 VS 2009

Factors to Consider when Designing [...]]]> Jeff Dean gave a keynote Building Large Scale Information Retrieval Systems at WSDM 2009. It’s actually a presentation on how Google search engine evolves during the past 10 years. Here are my notes for this lecture.

Part I – Overview of Search Engine Evolution: 1999 VS 2009

Factors to Consider when Designing a Information Retrieval System:
1. Corpus Size(# docs to be indexed)
2. QPS(Query Per Second)
3. Freshness/Update Rate
4. Query Latency
5. Complexity/Cost of Scoring/Retrieval Algorithm

Parameter Change 1999 -> 2009:
1. Corpus Size: 70M -> *B ~100X
2. QPS: ~1000X
3. Refresh: Months -> Minutes ~10000X
4. Latency: <1s> <02.s style="font-weight: bold; font-style: italic;">~5X
5. Machine Scale: ~1000X

Consider 10x Growth when designing, Rewrite for 100x Growth!

Part II - Evolution of Google Search Engine

~1997 – Circa, Research Prototype

- Simple Architecture and Focus on System Distributing/Partitioning
- Term vs Doc based Partition: Doc based Win
- Disk Based Index, DocID+Posting List with Position Attributes, Byte Aligned Encoding

~1999 – Circa, Production

- Introduced Cache
– hit rate is low 30~60% due to index refresh and long tail query
– very beneficial, reduce large disk i/o
– hot term first priority to cache, hot and costy request

- Replica Index Data
– better performance
– better availability

Some Summary in late 1990′s:

Crawler is simple batch system
- start with very few urls
- queue it when found new urls
- stop when have enough docs

Index Serving using cheap machine
- no failure handling
- added record/chunk checksum

Index Update
- once/month
- wait traffic to low -> take replica offline -> do update -> start serving

~2000 – Dealing with Growth

Situation:

- doc size:50m -> 1000m
- ~20% query traffic increase/month
- Yahoo! deal

Solution:

add machines constantly
- more index shards for larger index size
- more index replica for bigger query capacity

And improve software constantly
- better disk scheduling
- better index encoding

~2001 – Adding In-Memory Index

- enough machine memory: holding all index in mem
- machine function: replica -> micro shard holding
- balancer: cordinator
- availability: replicate important docs

~2004 – Adding Infrastructure

- Generalize tree structured query flow
- Generalize balancer concept
- New index encoding: group varint encoding
- GFS appear in production

~2007 – Universal Search

- Universal search: combine results from multiple vertical corpus
- Realtime search: fast url finding -> crawling -> indexing -> serving cycle
- Experiment supporting: have idea -> try it on real data offline and tune -> live experiment on small piece -> roll out and launch

Part III – Future Trends

- Cross Language Information Retrieval
- ACL in large IR system with huge amount of user and dynamic requirement
- Automatic Construction of Efficient IR system (one bin for realtime and regular web index with different parameter configuration)
- Info extraction from semi-structured data

[Reference]

1. Challenges in Building Large Scale Information Retrieval Systems[PDF, Video]
2. Notes by Another Blogger – http://www.searchenginecaffe.com/2009/02/jeffrey-dean-wsdm-keynote-building.html

The review is written using Chinese since I read the Chinese version of this book. To keep the pure English characteristic of this blog, I moved the book review to another place: Book Notes – The Long Tail. Please follow [...]]]>

Just a book review for the famous book about Internet economics:

The review is written using Chinese since I read the Chinese version of this book. To keep the pure English characteristic of this blog, I moved the book review to another place: Book Notes – The Long Tail. Please follow the link if you can read Chinese.