Hadoop Isn’t Silver Bullet

2013-12-05

Hadoop

Hadoop is a great framework for distributed large data computing. But Hadoop is not the silver bullet. Hadoop fits not very well in such cases as follow:

1. Low-latency Data Access

Applications that require real-time query, and low-latency access to data in tens of milliseconds will not work well with Hadoop.
Hadoop is not a substitute for a database. Database index records that will gains low-latency and fast response.
But if you really want to replace the database for real time needs, try HBase, which is a column-oriented database for random and real time read/write.[more…]

2. Structured Data

Hadoop is not fit for structured data with strong relationship. Hadoop works well for semi-structured and unstructured data. It stores data in files, doesn’t index them like RDBMS. Therefore, each ad hoc query for Hadoop is processed by MapReduce job which will bring the latency cost.

3. When data isn’t that big

How big the data is big enough for Hadoop? The answer is TB or PB. When your analytics data is only tens of GB, Hadoop is heavy. Don’t follow the fashion and use Hadoop, just follow your requirements.

4. Too many small files

When there are too many small files, the NameNode will hit its memory limit where the block map and the metadata are hosted. And to handle the NameNode bottleneck, Hadoop introduces HDFS Federation.

5. Too many writers and too much file updates

HDFS is in write-once-and-read-many-times way. When there is too much files update needs, Hadoop won’t support that.

6. MapReduce may not the best choice

MapReduce is a simple programming model in parallel. But for MapReduce parallelism, you need to make sure each MR job and the data where the job runs on is independent from all the others. Every MR shouldn’t have dependencies.
But if you want to do some data sharing during MR, you can do like this:

Iteration: run multiple MR jobs, with the output of one being the input of the next MR.
Shared state information. But don’t share information in memory, since each MR job is run on single JVM.

Resources:
Part 0 Hadoop Overview
Part 1 Hadoop HDFS Review
Part 2 Hadoop HDFS Federation
Part 3 Hadoop HDFS High Availability(HA)
Part 4 Hadoop MapReduce Overview
Part 5 Hadoop MapReduce 1 Framework
Part 6 Hadoop MapReduce 2 (YARN)
Part 7 Hadoop isn’t Silver Bullet

Hadoop MapReduce 2 (YARN)

2013-12-05

Hadoop

For large clusters with more than 4000 nodes, the classic MapReduce framework hit the scalability problems.
Therefore, a group in Yahoo began to design the next generation MapReduce in 2010, and in 2013 Hadoop 2.x releases MapReduce 2, Yet Another Resource Negotiator (YARN) to remedy the sociability shortcoming.
The fundamental idea of YARN is to split up the two major functionalities of the JobTracker: resource management (job scheduling) and job monitoring into separate daemons. YARN has a global Resource Manager (RM) and per-application Application Master(AM).[more…]

YARN High-level Overview

hd7.1 Figure1 YARN High-level Overview
As shown in Figure1, the YARN involves more entities than classic MapReduce 1 :

Client, the same as classic MapReduce which submits the MapReduce job.
Resource Manager, which has the ultimate authority that arbitrates resources among all the applications in the cluster, it coordinates the allocation of compute resources on the cluster.
Node Manager, which is in charge of resource containers, monitoring resource usage (cpu, memory, disk , network) on the node , and reporting to the Resource Manager.
Application Master, which is in charge of the life cycle an application, like a MapReduce Job. It will negotiates with the Resource Manager of cluster resources—in YARN called containers. The Application Master and the MapReduce task in the containers are scheduled by the Resource Manager. And both of them are managed by the Node Manager. Application Mater is also responsible for keeping track of task progress and status.
HDFS, the same as classic MapReduce, for files sharing between different entities.

Resource Manager consists of two components: Scheduler and ApplicationsManager.

Scheduler is in charge of allocating resources. The resource Container incorporates elements such as memory, cup, disk, network etc. Scheduler just has the resource allocation function, has no responsible for job status monitoring. And the scheduler is pluggable, can be replaced by other scheduler plugin-in.

The ApplicationsManager is responsible for accepting job-submissions, negotiating the first container for executing the application specific Application Master, and it provides restart service when the container fails.
The MapReduce job is just one type of application in YARN. Different application can run on the same cluster with YARN framework. That’s the beauty of YARN.

YARN MapReduce

hd7.2 Figure2 MapReduce with YARN
As shown in Figure2, it is the MapReduce process with YARN, there are 11 steps, and we will explain it in 6 steps the same as the MapReduce 1 framework. They are Job Submission, Job Initialization, Task Assignment, Task Execution, Progress and Status Updates, and Job Completion.

Job Submission

Clients can submit jobs with the same API as MapReduce 1 in YARN. YARN implements its ClientProtocol, the submission process is similar to MapReduce 1.

The client calls the submit() method, which will initiate the JobSubmmitter object and call submitJobInternel().
Resource Manager will allocate a new application ID and response it to client.
The job client checks the output specification of the job
The job client computes the input splits
The job client copies resources, including the splits data, configuration information, the job JAR into HDFS
Finally, the job client notify Resource Manager it is ready by calling submitApplication() on the Resource Manager.

Job Initialization

When the Resource Manager(RM) receives the call submitApplication(), RM will hands off the job to its scheduler. The job initialization is as follows:

The scheduler allocates a resource container for the job,
The RM launches the Application Master under the Node Manager’s management.
Application Master initialize the job. Application Master is a Java class named MRAppMaster, which initializes the job by creating a number of bookkeeping objects to keep track of the job progress. It will receive the progress and the completion reports from the tasks.
Application Master retrieves the input splits from HDFS, and creates a map task object for each split. It will create a number of reduce task objects determined by the mapreduce.job.reduces configuration property.
Application Master then decides how to run the job.

For small job, called uber job, which is the one has less than 10 mappers and only one reducer, or the input split size is smaller than a HDFS block, the Application Manager will run the job on its own JVM sequentially. This policy is different from MapReduce 1 which will ignore the small jobs on a single TaskTracker.

For large job, the Application Master will launches a new node with new NodeManager and new container, in which run the task. This can run job in parallel and gain more performance.

Application Master calls the job setup method to create the job’s output directory. That’s different from MapReduce 1, where the setup task is called by each task’s TaskTracker.

Task Assignment

When the job is very large so that it can’t be run on the same node as the Application Master. The Application Master will make request to the Resource Manager to negotiate more resource container which is in piggybacked on heartbeat calls. The task assignment is as follows:

The Application Master make request to the Resource Manager in heartbeat call. The request includes the data locality information, like hosts and corresponding racks that the input splits resides on.
The Recourse Manager hand over the request to the Scheduler. The Scheduler makes decisions based on these information. It attempts to place the task as close the data as possible. The data-local nodes is great, if this is not possible , the rack-local the preferred to nolocal node.
The request also specific the memory requirements, which is between the minimum allocation (1GB by default) and the maximum allocation (10GB). The Scheduler will schedule a container with multiples of 1GB memory to the task, based on the mapreduce.map.memory.mb and mapreduce.reduce.memory.mb property set by the task.

This way is more flexible than MapReduce 1. In MapReduce 1, the TaskTrackers have a fixed number of slots and each task runs in a slot. Each slot has fixed memory allowance which results in two problems. For small task, it will waste of memory, and for large task which need more memeory, it will lack of memory.
In YARN, the memory allocation is more fine-grained, which is also the beauty of YARE resides in.

Task Execution

After the task has been assigned the container by the Resource Manger’s scheduler, the Application Master will contact the NodeManger which will launch the task JVM.
The task execution is as follows:

The Java Application whose class name is YarnChild localizes the resources that the task needs. YarnChild retrieves job resources including the job jar, configuration file, and any needed files from the HDFS and the distributed cache on the local disk.
YarnChild run the map or the reduce task
Each YarnChild runs on a dedicated JVM, which isolates user code from the long running system daemons like NodeManager and the Application Master. Different from MapReduce 1, YARN doesn’t support JVM reuse, hence each task must run on new JVM.
The streaming and the pipeline processs and communication in the same as MapReduce 1.

Progress and Status Updates

When the job is running under YARN, the mapper or reducer will report its status and progress to its Application Master every 3 seconds over the umbilical interface. The Application Master will aggregate these status reports into a view of the task status and progress. While in MapReduce 1, the TaskTracker reports status to JobTracker which is responsible for aggregating status into a global view.
Moreover, the Node Manger will send heartbeats to the Resource Manager every few seconds. The Node Manager will monitoring the Application Master and the recourse container usage like cpu, memeory and network, and make reports to the Resource Manager. When the Node Manager fails and stops heartbeat the Resource Manager, the Resource Manager will remove the node from its available resource nodes pool.
The client pulls the status by calling getStatus() every 1 second to receive the progress updates, which are printed on the user console. User can also check the status from the web UI. The Resource Manager web UI will display all the running applications with links to the web UI where displays task status and progress in detail.
hd7.3 Figure 3 YARN Progress and Status Updates

Job Completion

Every 5 second the client will check the job completion over the HTTP ClientProtocol by calling waitForCompletion(). When the job is done, the Application Master and the task containers clean up their working state and the outputCommitter’s job cleanup method is called. And the job information is archived as history for later interrogation by user.

Hadoop MapReduce 1 Framework

2013-12-05

Hadoop

For MapReduce programming, a developer can run a MapReduce job by simply calling submit() or waitForCompletion() on a job object. This method abstracts the job processing details away from developer. But there is a great of job processing behind the scene that we will consider in this section.
Hadoop 2.x has released new MapReduce framework implementation called YARN or MapReduce 2, for traditional MapReduce is the classic framework which is also called MapReduce 1. YARN is compatible with MapReduce 1. [more…]

MapReduce 1 high level overview

hd6.2 Figure1 Classic MapReduce Framework
As shown in Figure 1, there are four independent entities in the framework:

Client, which submits the MapReduce Job
JobTracker, which coordinates and controls the job run. It is a Java class called JobTracker.
TaskerTrackers, which run the task that is split job, control the specific map or reduce task, and make reports to JobTracker. They are Java class as well.
HDFS, which provides distributed data storage and is used to share job files between other entities.

As the Figure 1 show, a MapReduce processing including 10 steps, and in short, that is:

The clients submit MapReduce jobs to the JobTracker.
The JobTracker assigns Map and Reduce tasks to other nodes in the cluser
These nodes each run a software daemon TaskTracker on separate JVM.
Each TaskTracker actually initiates the Map or Reduce tasks and reports progress back to the JobTracker

Job Submission

When the client call submit() on job object. An internal JobSubmmitter Java Object is initiated and submitJobInternal() is called. If the clients calls the waiForCompletion(), the job progresss will begin and it will response to the client with process results to clients until the job completion.
JobSubmmiter do the following work:

Ask the JobTracker for a new job ID.
Checks the output specification of the job.
Computes the input splits for the job.
Copy the resources needed to run the job. Resources include the job jar file, the configuration file and the computed input splits. These resources will be copied to HDFS in a directory named after the job id. The job jar will be copied more than 3 times across the cluster so that TaskTrackers can access it quickly.
Tell the JobTracker that the job is ready for execution by calling submitJob() on JobTracker.

Job Initialization

When the JobTracker receives the call submitJob(), it will put the call into an internal queue from where the job scheduler will pick it up and initialize it. The initialization is done as follow:

An job object is created to represent the job being run. It encapsulates its tasks and bookkeeping information so as to keep track the task progress and status.
Retrieves the input splits from HDFS and create the list of tasks, each of which has task ID. JobTracker creates one map task for each split, and the number of reduce tasks according to configuration.
JobTracker will create the setup task and cleanup task. Setup task is to create the final output directory for the job and the temporary working space for the task output. Cleanup task is to delete the temporary working space for the task ouput.
JobTracker will assign tasks to free TaskTrackers

Task Assignment

TaskTrackers send heartbeat periodically to JobTracker Node to tell it if it is alive or ready to get a new task. The JobTracker will allocate a new task to the ready TaskTracker. Task assignment is as follows:

The JobTracker will choose a job to select the task from according to scheduling algorithm, a simple way is chosen on a priority list of job. After chose the job, the JobTracker will choose a task from the job.
TaskTrackers has a fixed number of slots for map tasks and for reduces tasks which are set independently, the scheduler will fits the empty map task slots before reduce task slots.
To choose a reduce task, the JobTracker simply takes next in its list of yet-to-be-run reduce task, because there is no data locality consideration. But map task chosen depends on the data locality and TaskTracker’s network location.

Task Execution

When the TaskTracker has been assigned a task. The task execution will be run as follows:

Copy jar file from HDFS, copy needed files from the distributed cache on the local disk.
Creates a local working directory for the task and ‘un-jars’ the jar file contents to the direcoty
Creates a TaskRunner to run the task. The TaskRunner will lauch a new JVM to run each task.. TaskRunner fails by bugs will not affect TaskTracker. And multiple tasks on the node can reuse the JVM created by TaskRunner.
Each task on the same JVM created by TaskRunner will run setup task and cleanup task.
The child process created by TaskRunner will informs the parent process of the task’s progress every few seconds until the task is complete.

Progress and Status Updates

hd6.3 Figure 2 Classic MapReduce Framework Progress and Status Updates
After clients submit a job. The MapReduce job is a long time batching job. Hence the job progress report is important. What consists of the Hadoop task progress is as follows:

Reading an input record in a mapper or reducer
Writing an output record in a mapper or a reducer
Setting the status description on a reporter, using the Reporter’s setStatus() method
Incrementing a counter
Calling Reporter’s progress()

As shown in Figure 2, when a task is running, the TaskTracker will notify the JobTracker its task progress by heartbeat every 5 seconds.

And mapper and reducer on the child JVM will report to TaskTracker with it’s progress status every few seconds. The mapper or reducers will set a flag to indicate the status change that should be sent to the TaskTracker. The flag is checked in a separated thread every 3 seconds. If the flag sets, it will notify the TaskTracker of current task status.
The JobTracker combines all of the updates to produce a global view, and the Client can use getStatus() to get the job progress status.

Job Completion

When the JobTracker receives a report that the last task for a job is complete, it will change its status to successful. Then the JobTracker will send a HTTP notification to the client which calls the waitForCompletion(). The job statistics and the counter information will be printed to the client console. Finally the JobTracker and the TaskTracker will do clean up action for the job.

Hadoop MapReduce Overview

2013-12-05

Hadoop

MapReduce Introduction

MapReduce is a parallel programming model and an associated implementation for processing and generating large data sets. The MapReduce model consists of two phrases: map and reduce. A map task is to process a key/value pair to generate a set of intermediate key/value pairs, and a reduce task is to merge all intermediate values associated with the same intermediated key.[more…]

Hadoop MapReduce is based on the MapReduce paper in 2006. This processing model is automatic parallelization and distribution. It provides a clean abstraction for programmers. MapReduce programs are usually written in java, and can be written in any scripting language like Ruby, Python, PHP using Hadoop Streaming, or in C++ using Hadoop Pipes. MapReduce abstracts all the ‘housekeeping’ away from the developer. Developer can concentrate simply on writing the Map and Reduce functions.

MapReduce Data Flow

hd6.1 Figure1 MapReduce Data Flow
As shown in Figure1, A MapReduce process consists of two phrases: map phrase and the reduce phrase. Let’s consider them in detail.

The Mapper

A MapReduce job is a unit of work that the client wants to be run, including the input data, the MapReduce program and the configuration information. Hadoop runs the job by dividing it into tasks: map tasks and reduce tasks.
Hadoop divides the input data into fixed-size pieces call input splits or splits. Each map task runs on each split, which runs the user-defined map function. All of the map tasks runs in parallel. Usually, the split size is a HDFS block, 64MB or 128MB.
If the file is less than 64MB or 128MB, it will not be split. And the file will occupy one block, results in a waste of storage.
Map tasks usually runs on its local HDFS data, or the data near the node that runs the map task. Data Locality saves bandwidth and decreases dependencies.
The input value for map task is key/value pair. For example, in the WordCount example by Hadoop, the input value for map task: the key is the line offset whining the file, which we can ignore in our map function, the value is the line in the file.
In the map function, developers will process the value of each line, make sure the output is key/value pair, WorkCount again, the output for map function is like ‘<apple, 1>, <pear, 1>…’, key is the word, value is 1.
Map tasks output is written to the local disk, not to HDFS, then the reduce task will use these intermediate output to do merge work. Because storing these intermediate data to HDFS with replication would be overkill. And if the map task fails before the reduce task consume the output, Hadoop will automatically start another map task on another node that will re-create the output.

The Reducer

After map tasks done, the job tracker will start the reduce task. The reducer input is the intermediate mapper output.
Between the map task and the reduce task is the well known shuffle and sort. Hadoop will sort the intermediate map output by key. And each reduce task will run on map output with the same key. In WordCount example, the same key means the same word, like ‘<apple, 1> … <apple, 1>’, will be assigned to a reduce task, the reduce function just sum up the value and calculate the word count for ‘apple’.
Reduce tasks don’t have the advantage of data locality, the sorted map output have to be transferred across the network to the node where the reduce task is running.
Then the reduce task will merge the data with the user-defined reduce function. The reduce output is normally stored in HDFS for reliability. For each reduce output block, the first replica is stored on the local node, while the other two replicas are stored on off-rack nodes.
We can see that no reduce task can start until every map task has finished. Will the mapper become a bottleneck? Hadoop uses the ‘Speculative execution’ to mitigate against this:

If a Mapper appears to be running significantly more slowly than the others, a new instance of the Mapper will be started on another node, operating on the same data.
The results of the first Mapper to finish will be used
Hadoop will kill off the Mapper which is still running

The Combiner

Often, Mappers produce large amounts of intermediate data, which have to be transferred to Reducers that will result in a lot of network traffic.
To minimize the data transferred between Mapper and Reducer, Hadoop introduces the combiner function to be run on the map output, and combine the Mapper output and generate the Reducer Input.
Combiner is like a ‘Mini-Reducer’, runs locally on a the same node as Mapper. The output from the combiner is sent to the Reducers. Combiners decrease the amount of the network traffic required during the shuffle and sort phase.

Hadoop HDFS High Availability(HA)

2013-12-05

Hadoop

Reliability, Scalability and Availability are the most important three features for a distributed file system. In HDFS, persistent metadata, using the Secondary NameNode to create checkpoint against data loss, using block replication across the cluster against DataNode failure, all of these brings HDFS high reliability. And the master slave architecture wins HDFS great scalability. [more…]
However, HDFS has always had a well-known Single Point of Failure (SPOF) which impacts HDFS’s availability. HDFS fits well for ETL or batch-processing workflows, but in the past few years HDFS begin to be used for real time job, such as HBase. To recover a single NameNode, an administrator starts a new primary NameNode with FsImage and replays its EditLog, waits for Blockreport from DataNodes to leave safe mode. On large clusters with many files and blocks, it will take 30 minutes or more time to recovery. Long time recovery will impact the productivity of internal users and perhaps results in downtime visible to external users.
For these reasons, Hadoop community began a new feature for HDFS called High Availability Name Node (HA Name Node) in 2011. The HA makes use of an active and a standby NameNode. When the active NameNode fails, the hot standby NameNode will take over serving the role of an active NameNode without a significant interruption.

HA Architecture

hd5.1 Figure1 HDFS High Availability Architecture
As shown in Figure 1, HA architecture has several changes

The NameNodes must use highly available shared storage to share EditLog, such as Network File System (NFS), or BookKeeper. The active NameNode will write its EditLog on the Shared dir, and the Standby NameNode polls the shared log frequently and then applies to its in-memory so as to has the most complete and up-to-date file system state in memory.
DataNodes must send Blockreports with block locations to both active and standy NameNodes. Because the block mappings are stored in a NameNode’s memory and not on a disk to increase data access performance.
Clients must be configured to handle NameNode failover, using a mechanism that is transparent to users.
The HA guarantees if the active NameNode fails, the standby one will take over quickly in tens of seconds, since it has the latest state available in memory: the latest EditLog entries and an up-to-date block mapping.

Failover

The transition from the active NameNode to the standby NameNode is controlled by the failover controller. Each NameNode runs a failover controller to monitor its namenode failure, which is a heartbeating mechanism. Failover is triggered when a NameNode fails.

After NameNode failover, the Client must be informed which is active NameNode now. Client Failover is handled transparently by the client library. The HDFS client supports the configuration for multiple network addresses, one for each NameNode. The NameNode is identified by a single logical URI which is mapped the two network addresses of the HA Name Nodes via client-side configuration. The client will retry the two addresses until the active NameNode is found.

Fencing

After Failover, HDFS makes use of the fencing technique to make sure that the previous died active NameNode is prevented from doing any damage and causing corruption. These mechanisms includes killing the NameNode’s process, revoking its access to the shared storage directory and disabling its network port via a remote management command. If these techniques fail, HDFS will use STONITH, that is “shoot the other node in the head”, which uses a specialized power distribution unit to forcibly power down the host machine.

Hadoop HDFS Federation

2013-12-05

Hadoop

In traditional HDFS architecture, there is only one NameNode in a cluster, which maintains all of the namespace and block map. Regarding that Hadoop cluster is becoming larger and larger one enterprise platform and every file and block information is in NameNode RAM, when there are more than 4000 nodes with many files, the NameNode memory will reach its limit and it becomes the limiting factor for cluster scaling. In Hadoop 2.x release series, Hadoop introduces HDFS Federation, which allows a cluster to scale by adding NameNodes, each of which manages a portion of the filesystem namespace.[more…]
hd4.1 Figure1 HDFS Federation
As shown in Figure1, there are many federated NameNodes which manages its own namespace. The NameNodes are independent and don’t require coordination with each other. The DataNodes are used as common storage for blocks. Each DataNode registers with all the NameNodes in the cluster and send periodic heartbeats and block report and handles commands from the NameNodes.
Each NameNode is responsible for two tasks: Namespace management and Block Management. For the two tasks, mange NameNode manages its own Namespace Volume, which consists of two parts:

Namespace: the metadata for each file and block
Block Pool: it is a set of blocks that belong to a single namespace. The Block Pool is in charge of block management task, including processing block reports and maintaining location of blocks.
Block pool storage is not partitioned , so DataNodes register with each NameNode in the cluster and store blocks from multiple block pools. The NameNode namespace must to generate block ID for new blocks.
A NameSpace Volume is a self-contained uinit . Each NameNode has no need to contact other NameNode and it’s failure will not influence other NameNode.
To access a federated HDFS, clients use client-side mount tables to map file paths to NameNodes. A new identifier ClusterID is added to all the nodes in the cluser. Federated NameNodes is configured by ViewFileSystem and the viewfs://URIs.
The HDFS Federation brings several benefits:

NameSpace Scalability: It will support large clusters with many files, just add more NameNode to scale namespace.
Performance: Break the limitation of single node, more NameNodes means more read/write operations and the throughput is improved.
Isolation: A single NameNode has no isolation in multi user environment. While multiple NameNodes can provide isolated NameSpace for both production and experiment application.

Hadoop HDFS Review

2013-12-05

Hadoop

HDFS Basic Concepts

Hadoop Distributed File System, know as HDFS, is a distributed file system designed to store large data sets and streaming data sets on commodity hardware with high scalability, reliability and availability.

HDFS is written in Java based on the Google File System (GFS). HDFS has many advantages compared with other distributed file systems:

1. Highly fault-tolerant

Fault-tolerant is the core architecture for HDFS. Since HDFS can run on low-cost and unreliable hardware, the hardware has a non-trivial probability of failures. HDFS is designed to carry on working without a noticeable interruption to the user in the face of such failure. HDFS provides redundant storage for massive amounts of data and Heartbeat for failure detection.
When one node fails, the master will detect it and re-assign the work to a different node. Restarting a node doesn’t need communicating with other data node. When failed node restart it will be added the system automatically. If a node appears to run slowly, the master can redundantly execute another instance of the same task, know as ‘speculative execution’.[more…]

2. Streaming Data Access

HDFS is designed with the most efficient data processing pattern: a write once, read-many times pattern. HDFS split large files into blocks, usually 64MB or 128MB. HDFS performs best with a modest number of large files. It prefers millions, rather than billions of files, and each of which is 100MB or more. No random writes to files is allowed. Also HDFS is optimized for large, steaming reads of files. No Random reads is allowed.

A data set is generated and copied from source and replicated spread the HDFS system. It is efficient to load data from HDFS for big data analysis.

3. Large data sets

Large data means files that are MB, GB or TB in size. There are Hadoop clusters today that store PB data. HDFS support high aggregate data bandwidth and scale to hundreds of nodes in a single cluster. It also supports tens of millions of files processing.

HDFS NameNode and DataNodes Architecture

HDFS has a master/slave architecture. As shown in Figure1.

The master node is the NameNode, which managers the file system namespace, file metadata and regulates the access interface for files by clients. A cluster has only one NameNode, which maintain the map of file metadata and the location of blocks.

The slave nodes are the DataNodes. A cluster has many DataNodes, which holds the actual data blocks.

hd3.1 Figure1 HDFS Architecture

NameNode

NameNode maintains the namespace tree, which is logical location and the mapping of file blocks to DataNodes, which is the physical location.

The NameNode executes file system namespace operations like opening, closing, and renaming files and directories. It provides POSIX interface for client, so that user can access HDFS data with Unix like commands and no need to know about the function of NameNode and DataNodes. It is kind of abstraction which decrease the complexity for data access.

The NameNode is the pivot in a cluster. A single NameNode greatly simplifies the architecture of HDFS. NameNode holds all of its metadata in RAM for fast access. It keeps a record of change on disk for crash recovery.

However, once the NameNode fails, the cluster fails. The Single Point of Failure, known as SPOF is really a bottleneck for NameNode. Hadoop 2.0 introduces NameNode Federation and High Availability to solve the problem. We will discuss these in later section.

NameNode Data Persistent

In case of NameNode crash, the namespace information and metadata updates are stored persistently on the local disk in the form of two files: the namespace image called FsImage and the EditLog.

FsImage is an image file persistently stores the file system namespace, including the file system tree and the metadata for all the files and the directories in the tree, the mapping of blocks to files and file system properties.

EditLog is a transaction log to persistently record every change that occurs to file system metadata.

However, we have to know there is one thing that is not persistent. The block locations we can call it Blockmap, which is stored in NameNode in-memory, not persistent on the local disk. Blockmap is reconstructed from DataNodes when the system starts by the Blockreport of DataNodes.

When the system starts up, NameNode will load FsImage and EditLog from the local disk, applies the transactions from the EditLog to the in-memory representation of the FsImage, and flushes out the new version of FsImage on disk. Then it truncates the old EditLog since its transactions has been applied to the FsImage. This process is called a checkpoint.

Secondary NameNode

To increase the reliability and availability of the NameNode, a separate daemon known as the Secondary NameNode takes care of some housekeeping tasks for the NameNode. Be careful that the Secondary NameNode is not a backup or a hot standby NameNode.

The housekeeping wok is to periodically merge the namespace image FsImage with the EditLog to prevent the EditLog becoming to large. The Secondary NameNode runs on a single Node, which is a separate physical machine with as much memory and CPU requirements as the NameNode.

The Secondary NameNode keeps a copy of the merged namespace image in case of the NameNode fails. But the time lags will result in data loss certainly. And during the NameNode recovery, the reconstruction of the Blockmap will cost too much time. So Hadoop works out the problem with Hadoop High Availability solution.

DataNodes

The DataNodes holds all the actual data blocks. In sum up, it has three functions:

Serves read and requests from the file system clients.
Provides block operations, like creation, deletion and replication upon instruction from the NameNode.
Make data Blockreport to NameNode periodically with lists of blocks that they are storing.

In enterprise Hadoop deployment, each DataNode is a java program run on a separate JVM, and one instance of DataNode on one machine.

In addition, NameNode is a java program run on a single machine. Written in java provides Hadoop good portability.

The Communication Protocols

HDFS client, NameNode and DataNodes communication protocols are TCP/IP. Client Protocol is TCP connection between a client and NameNode. The DataNode Protocol is the connection between the NameNode and the DataNodes. HDFS makes an abstraction wraps for the Client Protocol and the DataNode Protocol, which called Remote Procedure Call (RPC). NameNode never initiates any RPCs, only responds to RPC requests from clients or DataNodes.

HDFS Files Organization

In traditional concepts, a disk has a block size, which is the minimum amount of data that it can read or write. Disk blocks are normally 512 bytes. While HDFS has the concept of block as well, which is a much larger unit – 64MB by default.

HDFS large files are chopped up into 64MB or 128MB blocks. This brings several benefits:

It can take advantage of any of the disks in the cluster, when the file is larger than any single disk.
Making the unit of abstraction of a block simplifies the storage subsystem. HDFS will deal with blocks, rather than a file. Since blocks are a fixed size, it’s easy to calculate how many can be stored on a give disk and eliminate metadata concerns.
Normally, a map task will operate on one local block at a time. Bocks spare the complexity of dealing with files.
It’s easy to do data replication with blocks for providing fault tolerance and availability. Each block is replicated multiple times. Default is to replicate each block 3 times. Replicas are stored on different nodes.
Block data fits well for streaming data. Files are written once and read many times. Blocks minimize the cost of seeking files.

Although files are split into 64MB or 128MB blocks ， if a file is smaller than this full 64MB/128MB will not be split.

HDFS Data Replication

HDFS each data block has a replica factor, which indicates how many times it should be replicated. Normally, the replica factor is three. Each block is replicated three times and spread on three different machines across the cluster. This provides efficient MapReduce processing because of good data locality.
hd3.2 Figure2 Block Replication
As shown in Figure2, the NameNode holds the metadata for each map of file and blocks, including filename, replica factor and block-id etc. Block data are spread on different DataNodes.

Data Replica Placement

Block replica placement is not random. Regarding of the reliability and the performance, HDFS policy is to put one replica on one node in the local rack, the second one on a node in a different remote rack and the third one on a different node in the same remote rack.
hd3.3 Figure 3 HDFS Racks
As shown in Figure 3, different DataNodes on different racks, Rack 0 and Rack1. Large HDFS instance run on a cluster of machines that commonly spread across many racks. Network bandwidth for intra-racks is greater than inter-racks. So the HDFS replica policy cuts the inter-rack write traffic and improves write performance. One third of replicas are on one node, two third of replicas are on one rack, the other third are distributed across the remaining racks. This policy guarantees the reliability.

Data Replication Pipeline

hd3.4 Figure 4 Data Replication Pipeline
As shown in Figure 4, it is the data flow of writing data to HDFS. A client request to request a file does not reach the NameNode immediately. It will follow the steps:
Step 1, the HDFS client caches the file data into a temporary local file until the local file accumulates data worth over one HDFS block size.
Step 2, the client contacts the NameNode, requests add a File.
Step 3, the NameNode inserts the file name into the file system tree and allocates a data block for it. Then responds to the client request with the identity of the DataNodes and the destination data block.
Step 4, suppose the HDFS file has a replication factor of three. The client retrieves a list of DataNodes, which contains that will host a replica of that block. The clients flushes the block of data from the local temporary file to the first DataNode.
Step 5,.the first DataNode starts receiving the data in small portions like 4KB, writes each portion to its local repository and transfers that portion to the second DataNode. Then the second DataNode retrieves the data portion, stores it and transfers to the third DataNode. Data is pipelined from the first DataNode to the third one.
Step 6, when a file is closed, the remaining un-flushed data in temporary local file is transferred to the DataNode. Then the client tells the NameNode that the file is closed.
Step 7, the NameNode commits the file creation operation into a persistent one. Be careful if the NameNode dies before the file is closed, the file is lost.
So far, we can see that file caching policy improves the writing performance. HDFS is write-once-read-many-times. When a client wants to read a file: It should contacts the NameNode to retrieves the file block map, including block id, block physical location. Then it communicates directly with the DataNodes to read data. The NameNode will not be a bottleneck for data transfer.

Hadoop Overview

2013-12-05

Hadoop

The motivation for Hadoop

Apache Hadoop is an open source distributed computing framework for large-scale data sets processing. Doug Cutting, who is the creator of Apache Lucene Project, creates it.

The name of Hadoop is a made-up name, which is the nickname of a stuffed yellow elephant of the kid of Doug. Hadoop has its origins in Apache Nutch, an open source web search engine, and it is built based on work done by Google in early 2000s, specifically on Google papers describing the Google File System (GFS) published in 2003, and MapReduce published in 2004.

Hadoop moved out of Nutch to form an independent in Feb. 2006. Up to now, Hadoop has been powered by many companies, such as Yahoo who claims it has the biggest Hadoop cluster in the world with more than 42000 nodes, LinkedIn who has 4100 nodes, Facebook who has 1400 nodes, Taobao who has the biggest cluster in China with more than 2000 nodes. [more…]

The problems for traditional big data processing

Why these companies adopt Hadoop? The reason is simple, that we live in a big data age. We are flooded with big data every day on the Internet. Consider that: Facebook hosts approximately 10 billion photos, taken up on PB storage. Every second on eBay, a total merchandise value of 1400 dollars is traded and 10 million new items are listed on eBay every day. Ancestry.com, the genealogy site, store around 2.5 PB of Data.

How to make use of these big data to make analysis? For traditional methods, use only one machine to process computation, which needs faster processor and RAM. Even though the CPU power doubles every 18 months according to Moores’s Law, it hasn’t meet the big data analysis needs. Yet distributed system evolved to allow developers to use multiple machines for a single job, like MPI, PVM and Condor. However, programing for these traditional distributed systems is complex, you have to deal with these problems:

It’s difficult to deal with partial failures of the system. Developers spend more time designing for failure than they do actually working on the problem itself.
Finite and precious bandwidth must be available to combine data from different disks and transfer time is very slow for big data volume.
Data exchange requires synchronization.
Temporal dependencies are complicated.

How can Hadoop save big data analysis

What really counts is big data. Traditional distributed computing can’t handle big data in a decent way, but Hadoop can. Lets see what Hadoop brings to us:

Hadoop provide partial failure support. Hadoop Distributed File System (HDFS) can store large data sets with high reliability and scalability.
HDFS provide great fault tolerance. Partial Failure will not result in the failure of the entire system. And HDFS provide data recoverability for partial failure.
Hadoop introduce MapReduce, which spares programmers from low-level details, like partial failure. The MapReduce framework will detect failed tasks and reschedule them automatically.
Hadoop provide data locality. The MapReduce framework tries to collocate data with the compute nodes. Data is local, and tasks are separated with no dependence on each other. So the shared-nothing and data locality architecture can save more bandwidth and solve the complicated dependence problem

In summary, Hadoop is a great big data processing tool.

Hadoop Basic Concepts and Core Concepts

The core concepts for Hadoop are to distribute the data as it is initially stored in the system. That is data locality, individual nodes can work on data local to these nodes, and no data transfer over the network is required for initial processing.
Here are the basic concepts for Hadoop:

Applications are written in high-level code. Developers don’t worry about network programming, temporal dependencies etc.
Nodes talk to each other as little as possible. Developers should not write code which communicates between nodes, that is ‘Shared-Nothing’ architecture.
Data is spread among machines in advance. Computation happens where the data is stored, wherever possible, just as near the node as possible. Data is replicated multiple times on the system for increased availability and reliability.

Hadoop High-Level Overview

Hadoop consists of two important components: HDFS and MapReduce.
HDFS is Hadoop Distributed File System, which is a distributed file system designed to store large data sets and streaming data sets on commodity hardware with high scalability, reliability and availability.

MapReduce is a distributed processing framework designed to operate on large data stored on HDFS, which provides a clean interface for developers.

A set of machines running HDFS and MapReduce is known as a Hadoop Cluster. An individual machine in a cluster is known as nodes. The nodes play different roles. There are two kind important nodes: Master Nodes and Slave Nodes.

There are 5 important daemons on these nodes.

hd2.1 Figure1 Hadoop High-Level Architecture

As shown in Figure, Hadoop is comprised of 5 separate daemons:

NameNode, which holds the metadata for HDFS.
Secondary NameNode, which performs housekeeping functions for NameNode, and isn’t a backup or hot standby for the NameNode.
DataNode, which stores actual HDFS data blocks. In Hadoop, a large file is split into 64M or 128M blocks.
JobTracker, which manages MapReduce jobs, distributes individual tasks to machines running.
TaskTracker, which initiates and monitors each individual Map and Reduce tasks.

Each daemon runs on its own Java Virtual Machine (JVM), no Nodes can run 5 daemons at the same time.

Master Nodes runs the NameNode, Secondary NameNode, JobTracker daemons. And only one of each of these daemons runs on the cluster.
Slave Nodes run the DataNode and TaskTracker daemons. A slave node will run both of these daemons. All of these Slave Nodes run in parallel, each on their own part of the overall dataset locally.

Just for very small clusters, the NameNode, JobTracker and the Secondary NameNode run on a single machine. However, when there are beyond 20-30 nodes. It’s better to run each of them on individual nodes.

Hadoop Ecosystem

Hadoop has a family of related projects based on the infrastructure for distributed computing and large-scale data processing. The core projects are apache open source projects. Except for HDFS and MapReduce, some hadoop related projects are:

Ambari, a Hadoop management and cluster monitoring system.
Avro, a serialization system for efficient, cross-language RPC and persistent data storage.
Pig, a data flow language and execution environment for exploring very large datasets, which runs on HDFS and MapReduce clusters.
HBase, provide random, realtime read/write access to BigData. The project built a column-oriented database, host very large tables —- billions of rows X millions of columns. The project is based on Google’s paper BigTable: A Distributed Storage System for Structured Data.
Hive, which is distributed data warehouse. Hive manages data stored in HDFS and provides a query language based on SQL, which is translated by runtime engine to MapReduce Job.
Zookeeper, a distributed, highly available coordination service. It provides centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services, which make build distributed applications more efficient.
Oozie, a service for running and scheduling workflows of Hadoop jobs, which includes MapReduce, Pig, Hive and sqoop jobs.
Mahout, a scalable machine learning libraries based on Hadoop HDFS and MapReduce.

Graph DFS and BFS

2013-12-02

Algorithm

图论是一个重要的部分，以前数据结构课上过，没有作为考试要求，所以很不太熟悉，尤其是没有实现。考完试，无聊中重新看了看，想起以前在eBay，某帅哥突然开玩笑说DFS和BFS嘛，当然要会呀，Cyanny你会的吧，我说忘了，其实细细想起来，还真没有写过代码。In my view，没有实现过，就等于不会，今天实现了BFS和DFS，深深赞一个算导，说得明白和透彻，现在的算法书太多，这算是一本很不错的经典，厚了点，但要是能厚着脸皮看完确实受益匪浅。

广度优先搜索BFS

其算法思想简介：
1. 利用队列
2. 每一个Vertex引入三个变量
color：WHITE 表示没有访问过，GREY 表示发现，BLACK 表示完成访问
parent: 父亲
d: 表示从root到该顶点的长度
3. 为了实现方便，我采用int来标识每一个顶点，采用邻接表来表示graph
深度优先搜索可以生成深度优先树，生成单源最短路径，即从root到每一个顶点的长度是最短路径。[more…]
BFS可以采用邻接矩阵表示，其复杂度较高为O(n^2)
如果采用邻接表表示，其复杂度为O(E+V),即顶点个数+边的个数
[java]
public void BFS(int root) {
vertexes = new Vertex[n];
// Initialize each vertex,
// Each vertex has three segment: parent, d, color
for (int i = 0; i < n; i++) {
vertexes[i] = new Vertex(i);
}

Vertex rootv = vertexes[root];
rootv.d = 0;
rootv.color = Color.GREY;
queue.add(rootv);

while (!queue.isEmpty()) {
    Vertex u = queue.remove(0);
    ArrayList&lt;Integer&gt; list = graph.get(u.vertex);
    for (int i = 0; i &lt; list.size(); i++) {
        Vertex temp = vertexes[list.get(i)];
        // Make sure each vertex enqueue only once
        if (temp.color == Color.WHITE) {
            temp.parent = u;
            temp.d = u.d + 1;
            temp.color = Color.GREY;
            queue.add(temp);
        }                
    }
        u.color = Color.BLACK;
    res.add(u);
}

}
[/java]
BFS Source Code

深度优先搜索DFS

广度优先搜索DFS，基本算法思想
1. 采用递归，或stack来实现
2. 每一个Vertex引入四个变量
color：WHITE 表示没有访问过，GREY 表示发现，BLACK 表示完成访问
parent: 父亲
timestamp1: 表示第一次访问该顶点的时间戳
timestamp2:表示访问结束时的时间戳
3. 为了实现方便，我采用int来标识每一个顶点，采用邻接表来表示graph

DFS采用邻接表表示Graph来实现，复杂度O(V+E), 矩阵复杂度依然不好，为O（n^2）
DFS是从多个源开始，最终会生成由多个源作为root的森林，即深度优先树（深度优先森林）。
同时引入时间戳，是为了获得DFS的进展情况，如果不需要时间戳，只是想简单地打印每一个顶点，可以不用。

以下是递归的实现方法：
[java]
public void DFS() {
int i = 0;
for (i = 0; i < n; i++) {
vertexes[i] = new Vertex(i);
}
for (i = 0; i < n; i++) {
Vertex u = vertexes[i];
if (u.color == Color.WHITE) {
visitDFS(u);
}
}
}

private void visitDFS(Vertex u) {
    res.add(u);
    u.color = Color.GREY;
    timer++;
    u.timestamp1 = timer;
    ArrayList&lt;Integer&gt; adjList = graph.get(u.vertex);
    for (int i = 0; i &lt; adjList.size(); i++) {
        Vertex v = vertexes[adjList.get(i)];
        if (v.color == Color.WHITE) {
            v.parent = u;
            visitDFS(v);
        }
    }
    u.color = Color.BLACK;
    timer++;
    u.timestamp2 = timer;
}

[/java]

以下是采用栈的实现方法改写 “visitDFS”：
[java]
/**
* DFS with iterative method
* Make use of stack
* @param u
*/
private void visitDFSIterative(Vertex u) {
res.add(u);
u.color = Color.GREY;
timer++;
u.timestamp1 = timer;
stack.add(u);
while(!stack.isEmpty()) {
Vertex v = stack.remove(stack.size() - 1);
ArrayList<Integer> adjList = graph.get(v.vertex);
for (int i = 0; i < adjList.size(); i++) {
Vertex temp = vertexes[adjList.get(i)];
if (temp.color == Color.WHITE) {
temp.parent = v;
temp.color = Color.GREY;
timer++;
temp.timestamp1 = timer;
res.add(temp);
stack.add(temp);
}
}
v.color = Color.BLACK;
timer++;
v.timestamp2 = timer;
}
u.color = Color.BLACK;
timer++;
u.timestamp2 = timer;
}
[/java]

DFS Source Code

最终发现，起始实现起来代码不多，重在想法。

System Analysis and Design (Kenneth Kendall) Review Part4

2013-11-27

System Analysis and Design

9. 数据库设计

9.1.基本概念

1.数据库与文件系统的区别
传统的文件系统：是扁平文件，无结构的文件，存储简单地数据，读取速度快，存储形式单一；存在数据冗余，更新时间长，不一致性，安全性的问题，冗余会带来插入、更新、删除异常。
数据库系统：是堆文件，采用数据表存储，数据存放随机且没有特定的顺序，每一个表需要提供主键；数据库提供索引功能；可以通过范式来保证数据的一致性；有事务处理功能,ACID；可以避免插入、更新、和删除异常；提供安全功能。[more…]

2.数据库设计的目标：
a)能向用户提供数据
b)准确性，一致性，完整性
c)有效的存储数据以及有效的更新和检索
d)有目的的检索数据，获取的数据要有利于管理和决策。

3.有效性目标
a)保证数据能被各种应用程序的用户共享。
b)维护数据的准确性，一致性，完整性
c)确保当前的和未来的应用程序所需的所有数据能立即可用
d)允许数据库随用户需求的增加而不断演进。
e)允许用户建立自己的数据视图，而不用关心数据的实际存储方式。

4.ERD图,要会画，可以看书中的例子
实体：任何由某人为手机数据而选择的对象或事件叫做实体。包括：一般实体，关联实体，属性实体。
关系：1对1，1对多，多对多
属性：实体的特征
ERD图

5.键的类型：基于模式而不基于实例
a)主键：唯一标识一条记录
b)候选键：一个或一组可当作主键使用的键
c)辅助键：不能唯一标识一条记录，可以唯一，也可以标识多重记录
d)链接键(组合键)：可以选择两个或多个数据组成一个键
e)外键：一个属性，它是另外一个表的键

9.2.规范化

合理规范化的模型可应对需求变更，规范化数据重复降至最少.
1.第一范式1NF：数据原子性，每一列只有单值属性

2.第二范式2NF：没有部分依赖，每一个属性不能依赖主键的部分
如 (学号, 课程名称) → (姓名, 年龄, 成绩, 学分) ，不符合2NF
因为 (课程名称) –> (学分)，(学号)->(姓名，年龄)，存在部分依赖
此时存在数据冗余，插入异常，删除异常，更新异常

分解为：学生：Student(学号, 姓名, 年龄)；
Course(课程名称, 学分)
SelectCourse(学号, 课程名称, 成绩)

3.第三范式3NF：没有传递依赖，不存在非主属性依赖于非主属性
例如： (学号) → (姓名, 年龄, 所在学院, 学院地点, 学院电话),符合2NF，但不符合3NF，因为 (所在学院) -> (学院地点, 学院电话)是传递依赖，分解为：
(学号) → (姓名, 年龄, 所在学院)
(所在学院) -> (学院地点, 学院电话)

4.BCNF(Boyce-Codd Normaml Form): nothing but the key, 首先要满足3NF，在此基础上在候选键之间不能有传递依赖。
如：(仓库ID, 存储物品ID) →(管理员ID, 数量)
　　 (管理员ID, 存储物品ID) → (仓库ID, 数量)
(仓库ID, 存储物品ID)和(管理员ID, 存储物品ID)都是候选关键字，表中的唯一非关键字段为数量，符合3NF。但是，由于存在如下决定关系：
　　 (仓库ID) → (管理员ID) 　 (管理员ID) → (仓库ID)
候选键之间有依赖，不符合BCNF。

分解为：
(仓库ID) –> (存储物品ID，数量)
(仓库ID) -> (管理员ID)
BCNF分解过细，导致查询连接性能低，所以一般3NF就可以了。

数据库范式详解

9.3.3NF无损连接分解方法

分解要做到无损连接，依赖保持。
考虑关系 R= {ABCDEFGHI}
H -> GD E->D HD->CE BD -> A
1. Right reduced
H -> G
H->D
E->D
HD->C
HD->E
BD->A

2. Left reduced
H->G
H->D
E->D
H->C
H->E
BD->A

3. Find minimal cover
尝试删除一个依赖，然后验证是否无损和依赖保持，直到不能再删除
可以删除H->D,就不能再删了
H->G
E->D
H->C
H->E
BD->A
Minimal cover R’={H->GCE, E-D, BD->A}

4. 补充没有的依赖
我们发现I还没有在R’中，因此，提取出R’中的键HB构造关系HB->I

5. 最终结果
R = { H->GCE, E-D, BD->A , HB->I}

9.4.主文件/数据库关系设计指导原则

1. 指导原则
每个单独的数据实体应创建一个主数据表。
一个特定的数据字段只应出现在一个主文件中。
每个数据表支持CRUD操作

2. 完整性约束
实体完整性：主键不能有空值，唯一键可以有空值
引用完整性：一对多关系中，“一端”是父表，“多端”是子表，子表的外键必须在父表中有匹配记录；父表记录只在没有子表记录关联时才能删除；父表主键更新，要进行级联更新，即对应的子表外键要更新。
域完整性：对数据进行有效性检验，如数据必须大于0

3. 异常
数据冗余：可以通过3NF解决
插入异常：如果主键重复，或未知，导致插入异常，因为违反实体完整性。
删除异常：删除导致相关数据丢失导致
更新异常：更新导致不一致性。

4. 检索和显示数据的步骤
1)从数据库中选择一个关系

2)连接两个关系: join(inner join, outer join, left join, right join)
a)inner join： A join B 只有交集会出现在结果中
b)left (outer) join: A 中与B没有匹配的记录会保留
c)right(outer) join: B中与A没有匹配的会保留
d)outer join, 又叫full outer join = left join 与right join的并集，所有匹配和未匹配的记录都有

3)从关系中投影出列
4)从关系中选择所需的行
5)导出新的属性
6)行索引或排序
7)计算总计值和进行性能测量
8)显示数据

9.5.反规范化

1. 原因
规范化的方式可以减少数据冗余，但查询速度会下降，一定的冗余，可以提升查询响应速度，避免重复引用检查表。
2. 反规范化的6种方法
1)合并1：1关系
2)部分合并1：关系，不复制外关键字而复制非key的常用的字段
3)在1：关系中复制FK（外关键字），减少join的表数量，将另一个表的主键复制变成外键。
4)在：关系中复制属性，避免3表join
5)引入重复组，将多值属性写在主表里：例如user表中多个电话号码的列，常用地址和常用电话
6)为了避免查询和更新这两个不可调和的矛盾，可以将更新和查询放在两张表中，从工作表提取出查询表，专门用于查询。这个方法演化成了数据仓库。这个方法只适用于查询的实时性要求不高的情况

10. 设计准确的数据输入规程

数据输入准确性的目标：
•为数据创建有意义的代码
•设计有效的数据获取方法
•保证数据的完整性和有效性
•通过有效性检查确保数据的质量

10.1 有效的编码

10.1.1.基本概念

1.优点：
a)提高数据处理效率
b)有助于数据的排序
c)节约内存和存储空间
d)提高数据输入的准确性和效率
e)特定类型的编码允许我们按特定的方式处理数据

2.目的
a)记录某些事物
b)分类信息
c)隐蔽信息
d)展示信息
e)请求相应地处理

3.编码的一般指导原则
a)保持代码简洁，短代码比长代码更容易输入和记忆
b)保持代码稳定，不应虽每次接收新数据而变化
c)代码要独一无二
d)允许排序代码
e)避免使人迷惑的代码
f)保持代码统一
g)允许修改代码
h)代码要有意义

10.1.2.编码的类型

1.记录某些事物
a)简单地顺序码
•优点：减少指派重复数字的可能性；让使用者估计出订单合适收到
•适用于：作业按顺序处理，需要知道数据项输入系统的顺序，需要知道事件的发生顺序。
•缺点：容易泄露商业信息，泄露当前已经指派了多少编码

b)字母衍生码
•例如：名字的编码：取前2个辅音字母+名字长度+一个随机数
•例如编码女装：考虑品牌，类别，产地，生产日期，款号，尺码，颜色，价格
•常用于标识一个账号，邮寄地址标签
•注意：避免重复，分布要均匀
•缺点：如果采用名字的前三个辅音字母，当辅音字母少于3个，就会生成“RXX”这样的类型；如果一些数据发生变化，如名字或地址变化，就会改变字母衍生码，而改变文件中的主键

2.分类信息
a)分类码
•目的：将一组具有特殊信息的数据从其他数据中区分出来，可以由单个字母或数字组成。是描述人物、位置、事物或事件的一种简写形式
•例如：计算所得税，分类有支付利息，医药费，税，捐款，应付款，生活用品支出，给每一个分类指派一个字母；
•使用单个字母标识分类可能会存在扩展瓶颈，可使用两个以上的字母，如计算机中的快捷键。

b)块顺序码
•是顺序码的扩展，对数据分类，对每一个分类分配一个编码范围，在该类别的项目按顺序编码
•例如浏览器分配100~~999，数据库 200~~299
•优点：根据普通的特征对数据分类，还能简单地为下一个需要标识的项目（在同一块）指派一个可用的数字代码

3.隐藏信息
密码，隐藏信息，如医药处方，凯撒密码对称加密，Hash密码单向加密

4.展示信息：为用户展示信息，使数据输入更有意义
a)有效数字集编码
•例如衣服采用有效数字集描述产品信息，“414-219-19-12:表示浅褐色冬季外套，款式219，尺码12”
•优点：让员工方便的定位产品类别；查询效率高；有助于销售

b)助记码
•帮助记忆，结合字母和符号，醒目而又清晰的编码产品，例如国家简称
c)Unicode：显示我们不能输入和看到的字符，国际标准组织ISO定义Unicode字符集，包括所有标准语言字符，还有65535个空位

5.请求相应的处理
a)功能码：用简短的数字或字母来标识一个计算机对数据执行的功能，通常采用顺序码或助记码的形式
优点：执行功能只需输入功能码，提高输入效率

10.2.快速而高效的数据获取

1.决定要获取什么样的数据
如果输入无用，输出也会无用
输入的数据分类：随每个事务而改变的数据；能简明的将正在处理的项目与所有其他项目区分出来的数据

2.让计算机完成数据处理：处理重复的任务，如记录事务时间，根据输入计算新值，随时保存和检索数据

3.减少瓶颈和减少额外输入步骤：步骤越少，引入错误的机会就越少

4.选择有效的数据输入方法
a)键盘
b)扫描仪
c)视频，音频
d)磁性墨水
e)标记识别表单：如答题纸，但缺点是用户可能会一时大意填图出错
f)条形码：准确度高
g)RFID：射频识别技术

两个好用的Chrome插件，小伙伴们看完复习资料支持一下吧： [剪影截图：好用的网页截图，一键人人分享工具，快捷键ctrl+shift+z, 双击确定!](https://chrome.google.com/webstore/detail/剪影截图/gkloklemhahnoipikedmafefilidffko "剪影截图") [TSS下载助手：让你方便一键批量下载](https://chrome.google.com/webstore/detail/tss下载助手/odhkpoplnhfnhhhkgphckabboemiifle "TSS下载助手")

资源：
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4