How to create a program to handle HUGE data?[0]

In the past few weeks, I was working on a project that need a program to "handle" millions of files. The verb, "handle", here means to download millions of html files from remote server, parse the html to find interested URLs and texts,  download images pointed by the URLs and organize all the files in a 3-level hierarchy.
In the following posts, I will discuss what I have suffered during the development, what I have applied to the system, and what I want to do but have not done yet. All the topics which gonna be covered can be classified into two categories, design philosophy and  design pattern.

... to be continued...

面向对象编程有感【2】-- Understand SRP and LSP

In this post, I will mainly talk about SRP(Single Responsibility Principle) and LSP(Liskov Substitution Principle) in Object Oriented Programming. As I want to show you something different from the traditional boring textbooks, a simple project is described. You may first examine the requirements and think about how to implement a system to get it done!
Requirement: We need to design a web spider, which could traverse all the web pages rooted from a seed link. There are a number of different types of pages, which need different operation to be performed. In addition, we may have to add more types in the future.

After you reading the simple description above, few design patterns may pop up in your mind, such as factory pattern, responsibility chain pattern, observer pattern, MVC pattern and singleton pattern. Right, all those patterns are designed to assist you in such a scenario. But, when you implement all the patterns together, there may be few mistakes happened. Let us take a look at my code first.
I defined few classes as follows:

• BaseTask and its subclasses. The base class has few virtual functions, which generalize some common operations needed by each types of page.

• pObject and its subcalsses. As the data extracted from the pages may have different saving path and preprocessing requirement. pObject opens few virtual functions, such as where to save the data and how to preprocess it. Its derivatives override those functions and properly handle/keep the data.
• The next two classes are Download_Manager and Data_Manager. Download_Manager is the observer to the Data_Manager. Once a new task, which is in form of BaseTask, is added to Data_Manager, Download_Manager will try to pop the task from the task queue and download the page needed by this task. Once the page is downloaded, it will be assigned to the task and the task will return to Data_Manager, where the analyzing is performed. Some new tasks may be initialized and append to Data_Manager during analyzing. Furthermore, Singleton pattern is applied to both managers, so only few interfaces are opened to each other.

The reason why I design like this is that, the only object transferred between managers is BaseTask. So if we want to handle other types of pages, we could just implement another derivative class and push the objects into the task queue. In addition, each task has a “pObject”, which could handle the file path, URL and analyze process.

• Inside each task object, as we need to open a constant interface to other components, I define a recursive function, called decompose(), which is used to traverse all XML blocks and allow other parts to invoke. The code segment looks like the follows:

1:  void BaseTask::Decompose( QDomElement parentElement )  
2:  {  
3:    QDomNode element = parentElement.firstChild();  
4:    //  
5:    while(!element.isNull())  
6:    {  
7:      int type = this->RightBlock( element.toElement() );  
8:      if( type!=0 )  
9:      {  
10:        Extract( element.toElement(), type );  
11:      }  
12:      Decompose( element.toElement() );  
13:      element = element.nextSibling();  
14:    }  
15:    return;  
16:  }

RightBlock() is used to determine which XML block is needed; Extract() is used to extract the information in the XML block. Each derivative class will override those two functions, and then, each object of derivative class will act in different ways. The following flow chart shows how this code works.

This is a common trick in C++ based on polymorphism. We could initialize an object with sub-class but assign it to a base class pointer. As the functions in base class are virtual, the function point in virtual function table will updated to the implementation in subclass.

So far so good, right. LSP seems applied properly. But I found a big mistake about SRP when I try to update the code. Which part violates SRP? Let us first understand what I want to update with the original architecture.

As my previous structure tries to do everything in one executable, it becomes very vulnerable, or buggy . So I want to add a simple function that could resume the previous downloading. It seems simple but it is not. Because the tasks does not follow SRP. Let us first examine what happened inside a task object from its creation to release.

Can you find which part is worry? Right, the file system and URL interface is only a variable of the task objects. When I want to recover the downloading, the program may not need to download the page, but directly start the parsing. But based on the above sequence, the tasks are initialized by other tasks during parsing; parsing begins after download is finished; we want to recover and omit the download step… Now, you see the dead loop right. If we add more if-else, the original code may work, but not elegant.

Another part looking ugly is the URL interface. As the relative paths need to be translated into global, we not only need its parent object, but also modify the format. For example, the hierarchy of a website is as follows:

• First level, front page. The URL is www.pinterest.com


• Second level, user page, which contains a number of image folders. The URL is www.pinterest.com/user_name


• Third level, image folder, which holds a number images. The URL is www.pinterest.com/user_name/pin_board


• The final level, the images. The URL is www.pinterest.com/pin/pin_id

Each task object need to perform modification respectively. If I put the modification in tasks, it is easier and straight forward, but the code is hard to maintain. Imagine such a situation, all the levels of URL are updated and what shall we do? Update all relevant code in each subclass of BaseTask? What if we have 100 different tasks? It is not possible… The pObject in also lost its meaning of existence. As SRP says, we should put one responsibility in one object! We should put all URLs and paths task in pObject. The following diagram shows what the code should look like.

My previous design of the tasks looks like the left diagram. When the URLs input to task, there are more than one object could modify it. So it undermined the scalability of the code. The right hand diagram shows a design that keeps both scalability and the same functionalities. You feel familiar with the right hand side diagram. Because it likes the responsibility chain pattern, from some point of view. If any parts updated, you could just plugin another object to filter the input, and isolate the changes to the other component.

I have written so much. As I am also a green hand of this topic, some mistakes and errors may occur. If you found any, or just want to share your idea, please leave me a comment or directly email me.

Have fun!

面向对象编程有感【1】--基本原则

在未来的几天，我会写一些有关面性对象编程的体会，并将自己的一些代码作为例子（有好有坏）！作为这个系列的第一节，主要介绍OOP的五大原则！下面的内容是转载的，作者的描述很清楚准确！愿诸位看官跟我共同学习！
在面向对象设计中，如何通过很小的设计改变就可以应对设计需求的变化，这是令设计者极为关注的问题。为此不少OO先驱提出了很多有关面向对象的设计原则用于指导OO的设计和开发。下面是几条与类设计相关的设计原则。
　　单一职责原则SRP：Single Responsibility Principle
　　开放封闭原则OCP：Open-Close Principle
　　Liskov替换原则LSP：Liskov Substitution Principle
　　依赖倒置原则DIP：Dependency Invertion Principle
　　接口隔离原则ISP：Interface Separate Principle
　　在面向对象设计中，如何通过很小的设计改变就可以应对设计需求的变化，这是令设计者极为关注的问题。为此不少OO先驱提出了很多有关面向对象的设计原则用于指导OO的设计和开发。下面是几条与类设计相关的设计原则。
1. 开闭原则(the Open Closed Principle OCP)
　　一个模块在扩展性方面应该是开放的而在更改性方面应该是封闭的。因此在进行面向对象设计时要尽量考虑接口封装机制、抽象机制和多态技术。该原则同样适合于非面向对象设计的方法，是软件工程设计方法的重要原则之一。我们以收音机的例子为例，讲述面向对象的开闭原则。我们收听节目时需要打开收音机电源，对准电台频率和进行音量调节。但是对于不同的收音机，实现这三个步骤的细节往往有所不同。比如自动收缩电台的收音机和按钮式收缩在操作细节上并不相同。因此，我们不太可能针对每种不同类型的收音机通过一个收音机类来实现(通过重载)这些不同的操作方式。但是我们可以定义一个收音机接口，提供开机、关机、增加频率、降低频率、增加音量、降低音量六个抽象方法。不同的收音机继承并实现这六个抽象方法。这样新增收音机类型不会影响其它原有的收音机类型，收音机类型扩展极为方便。此外，已存在的收音机类型在修改其操作方法时也不会影响到其它类型的收音机。
2. 替换原则 (the Liskov Substitution Principle LSP)
　　子类应当可以替换父类并出现在父类能够出现的任何地方。这个原则是Liskov于1987年提出的设计原则。它同样可以从Bertrand Meyer 的DBC (Design by Contract) 的概念推出。
　　我们以学生为例，夜校生为学生的子类，因此在任何学生可以出现的地方，夜校生均可出现。这个例子有些牵强，一个能够反映这个原则的例子时圆和椭圆，圆是椭圆的一个特殊子类。因此任何出现椭圆的地方，圆均可以出现。但反过来就可能行不通。
　　运用替换原则时，我们尽量把类B设计为抽象类或者接口，让C类继承类B(接口B)并实现操作A和操作B，运行时，类C实例替换B，这样我们即可进行新类的扩展(继承类B或接口B)，同时无须对类A进行修改。
3. 依赖原则 (the Dependency Inversion Principle DIP)
　　在进行业务设计时，与特定业务有关的依赖关系应该尽量依赖接口和抽象类，而不是依赖于具体类。具体类只负责相关业务的实现，修改具体类不影响与特定业务有关的依赖关系。
　　在结构化设计中，我们可以看到底层的模块是对高层抽象模块的实现(高层抽象模块通过调用底层模块)，这说明，抽象的模块要依赖具体实现相关的模块，底层模块的具体实现发生变动时将会严重影响高层抽象的模块，显然这是结构化方法的一个"硬伤"。
　　面向对象方法的依赖关系刚好相反，具体实现类依赖于抽象类和接口。
　　为此，我们在进行业务设计时，应尽量在接口或抽象类中定义业务方法的原型，并通过具体的实现类(子类)来实现该业务方法，业务方法内容的修改将不会影响到运行时业务方法的调用。
4. 接口分离原则(the Interface Segregation Principle ISP)
　　采用多个与特定客户类有关的接口比采用一个通用的涵盖多个业务方法的接口要好。
　　ISP原则是另外一个支持诸如COM等组件化的使能技术。缺少ISP，组件、类的可用性和移植性将大打折扣。
　　这个原则的本质相当简单。如果你拥有一个针对多个客户的类，为每一个客户创建特定业务接口，然后使该客户类继承多个特定业务接口将比直接加载客户所需所有方法有效。
　　以上四个原则是面向对象中常常用到的原则。此外，除上述四原则外，还有一些常用的经验诸如类结构层次以三到四层为宜、类的职责明确化(一个类对应一个具体职责)等可供我们在进行面向对象设计参考。但就上面的几个原则看来，我们看到这些类在几何分布上呈现树型拓扑的关系，这是一种良好、开放式的线性关系、具有较低的设计复杂度。一般说来，在软件设计中我们应当尽量避免出现带有闭包、循环的设计关系，它们反映的是较大的耦合度和设计复杂化。