Wednesday, March 25, 2009
SQL 大全
Tuesday, March 24, 2009
A Publisher's Introduction to the Semantic Web
White Papers
Newsletters
A Publisher's Introduction to the Semantic Web
by Ed Stevenson
Spamoflage( 'ES', 'Email' );
May 2005
Although the concept of the Semantic Web began to surface in the early part of this century (see this early Scientific American article from Tim Berners-Lee, James Hendler, and Ora Lassila), it is now reaching buzzword status. Some publishers have been using technologies considered to be "semantic" for a few years, but it is a new topic for many others.
What do the concepts behind the Semantic Web mean for publishers? Well, first let's ask—what is the Semantic Web? The point of the Semantic Web is a richer interconnectiveness among all objects (or content), thereby allowing us to pull data from various sources to discover new meaning and present in different formats. A simpler view is that the Semantic Web makes better use of metadata. That is, all objects on the web are assigned rich data to describe themselves (in a universal and standardized format), and tools are better able to make use of that data.
Creating richer metadata
Almost all publishers use metadata in some capacity. Most also use taxonomies (a hierarchy of terms used to categorize content), although they might not call them by that name. The next step beyond that is the use of ontologies. Just as taxonomies make metadata or controlled vocabularies look "flat," ontologies do the same to taxonomies. Ontologies describe more detailed relationships among concepts and provide a higher level of richness in the metadata.
Taxonomies are just like the animal and plant kingdom taxonomies, in which every species lives in a particular branch. However other, more conceptual objects don't always have that clear lineage. If we created a taxonomy based on colors with the three primary colors—red, yellow, and blue—as the top nodes, orange would need to be related to both red and yellow. In a simple taxonomy, we would probably repeat the term "orange" under both, but in a technical sense they would really be two distinct nodes that have the same name.
In an ontology, orange can be represented as the exact same concept appearing in multiple nodes on the tree. In fact, an ontology is not a tree at all. It is a complex mapping of concepts with defined relationships between those concepts (such as "part of" or "subclass of").
In their most expanded use, ontologies can in themselves be valuable collections of information and almost become database-like in nature. Imagine an ontology that captures court "metadata" for a legal publisher. That publisher may currently have a taxonomy with branches for federal courts, district courts, state courts, etc. But in this "flat" taxonomy, there is probably no implicit relationship between the local and district courts or state courts or to geographical boundaries like state or congressional district lines. In an ontology those relationships can be established. Of course, documents are still tagged to nodes in the ontology, but even without the documents, the ontology becomes a very valuable piece of content.
RDF and OWL: expressing richer metadata with W3C standards
The W3C standard framework for expressing metadata (including taxonomies and ontologies) is RDF (Resource Description Framework).
RDF provides a standard framework for expressing information about resources (metadata) that allows for complex definition of relationships, polyheirarchal taxonomies (giving a node multiple parents), and the ability to combine taxonomies (by connecting a detailed taxonomy to a broader taxonomy through a common node). The purpose of RDF is to create a syntax to capture rich metadata and relationships and allow the processing of this data by applications.
The RDF data model expresses relationships among resources in what is called "triples." These triples define two things and the relationship between them. Each triple consists of a subject, a predicate and an object (sometimes called the resource, property, and value). The subject (or resource) is the "thing" the statement is about, the predicate (or property) specifies a characteristic or property of the subject, and the object (or value) is the value of that characteristic or property.
The following illustration is an RDF graph representing a triple that illustrates the simple metadata value of the author of this newsletter article:
Where RDF gets interesting is when you start to combine triples, such as making the author the subject of another triple describing his email address or company affiliation.
The PRISM metadata standard can often be expressed in RDF, many RSS feeds use RDF syntax, and Adobe's XMP (eXtensible Metadata Platform) for embedding metadata within media objects makes use of RDF.
But being a structured framework, RDF is more syntax (structure) than semantics (meaning). OWL (Web Ontology Language) is the W3C effort to provide a standard for the types of relationships that can be expressed in RDF. OWL provides for an XML vocabulary to express hierarchies and relationships. OWL introduces specific property vocabularies, such as "sameAs" and "intertsectionOf." OWL provides a shared meaning in the RDF syntax.
Topic Maps: expressing richer metadata with ISO standards
In semantic circles, there is often discussion about RDF vs. topic maps. In most conceptual ways topic maps are very similar to RDF with some slight and subtle distinctions. Both have different origins. Whereas RDF came through the W3C, topic maps are an ISO standard and arose to address the need to create indexes (like back of the book indexes). Topic maps prime focus is on the topics (or subjects); RDF focuses on the resources. Although both were created for somewhat different purposes, both do very similar things.
Topic maps describe topic structures and associate them with resources. Like RDF, topic maps break from the traditional hierarchal taxonomy and offer much more robust classification, indexing, and relationship descriptions. Topic maps allow for the creation of complex topical descriptions which then point out to resources. There is a separation between the topical information (the index) and the content which is associated to specific topics within it.
The topic maps "language" uses topics, occurrences, and associations in its model where the topic is the resource (the thing or the subject), the occurrence is the resource that has some association with the topic, and the association is a type of relationship. You can see from a very high level the similarities with the RDF model. Note in topic maps the association is two way, that is if my topic is this article, the association is "is authored by" and the occurrence is "Ed Stevenson," the inverse is also true - that is Ed Stevenson (topic) authored (association) this article (occurrence).
It is beyond this introductory article to fully explore the differences between the two and much work has been done in that area. Additionally, the W3C has started a RDF/Topic Maps Interoperability Task Force to look for interoperability between the two. See http://www.w3.org/2001/sw/BestPractices/RDFTM/ for more information.
First steps for publishers
So if you never knew about the Semantic Web but now have the overview, what should you do next? It can be difficult to take the intellectual concepts behind the Semantic Web and apply them to practical day-to-day use in a publishing process. But it is important to be aware of the issues and the potential they have. The following are a few suggestions on preparing your publishing organization for the Semantic Web.
Consider using RDF if you are implementing or re-engineering or enhancing any process capturing metadata. Even if the full power of RDF is not harnessed initially (which it most likely will not be), starting down the path is the first step. There will be more tools and reusable code for translating RDF.
If you are defining or building metadata (or taxonomies or ontologies) look to industry standards first. Consider Dublin Core and PRISM for basic metadata and look to industry specific standards as well (like IEEE and NISO). Borrow where you can.
Value librarians on your staff. They are important now, but are generally undervalued. They will be critical in expanding taxonomies into ontologies and managing the complex relationships.
See the links mentioned in the interview with David Wood in this issue to get some hands-on experience with Semantic Web tools.
Keep an eye on Semantic Web topics through news groups, publications, web sites, etc. Some Semantic Web experts predict the health sciences industry to be some of first adopters of semantic technologies. See the next section for good resources to learn more of the basics as well as stay on top of the latest news and trends.
Monitor the actions of publishers who are using Semantic Web technologies and how they make them worthwhile.
Further reading
In addition to the links found within the document, the following offer good information on the Semantic Web (and were consulted for this article):
W3C RDF Primer
TAO of Topic Maps
O'Reilly's XML.com offers plenty of informative articles all grouped together under a link from the main left navigation: http://www.xml.com/semweb/
Sunday, March 22, 2009
09书单
年又过年,去年在写在译的书又长出了一茬,又是时候订一份今年的读书计划。
架构师类
架构类的书从来都很少,今年又长出两本来。
- 《Beautiful Architecture》
--《Beautiful Code》的姐妹作,里面有三成的架构是自己感兴趣的,已经有国内出版社拿下了,见架构师的唐诗三百首------O'reilly新书Beautiful Architecture(InfoQ中文站)
。
- 《97 Things Every Software Architect Should Know 》
-- 一个开放的wiki
,O'Reilly 将它发布成书,不知道有没人在翻。
- 《Pattern-Oriented Software Architecture, Volume 4 - A Pattern Language forDistributed Computing》
-- 架构模式的集大成者,号称有人在翻但等了一年中文版还是没翻出来啊。
架构技术类
虽然云计算已经开始代替SOA成为新一代大词,但回顾一下整个SOA出版风潮,自己觉得值得一读不忽悠的居然只有一本《SOA in Practic - SOA实践指南-分布式系统设计的艺术》 。
在热潮彻底退却前,SOA书还在继续出着,OSGI与SCA的书开始出现:
- 《SOA Design Patterns》
-- 又是Thomas Erl的书,很奇怪的连电子版都找不到。
- 还 没出版的呀 --《SOA Patterns》、《ESB Architecture for SOA》、《SOA with Java》、《Open Source SOA》、《OSGi in Action》、《SpringSource dm Server in Action》、《Modular Java: Creating Flexible Applications with OSGi and Spring》、《Understanding SCA》、《Apache Tuscany in Action》
编程匠师类
立志做一个匠师的人,今年会比较幸福。
- 《Beautiful Code - 代码之美》
-- 很有经典潜质的一本,去年没有读完今年继续。
- 《Produtive Programmer - 卓有成效的程序员》
-- Thoughtworks中国翻译的,看了下样章,熊节(透明)的翻译依然是这么好,见《卓有成效的程序员》推荐序:做一个懒人(InfoQ中文站)
。
- 《Clean Code: A Handbook of Agile Software Craftsmanship》
-- Rober。C大叔的书,不知道谁在翻,应该很容易翻啊,到后面大段大段都是代码。
- 《Effective Java中文版(第2版)》
-- 特别感谢俞黎敏同学送的书,这里推荐一把了。
bash编程
bash编程
bash脚本编写教程 说明,这部教程是我在网上找到比较经典的BASH中文教程,对新手学习bash脚本,bash编程的好文章。 建立一个脚本 |
The Stony Brook Algorithm Repository
Algorithm Implementations in Java
-
JGraphT: Java graph library (Library) NEW
- Connected Components
(9) , Drawing Graphs Nicely(9) , Graph Data Structures(7) , Shortest Path(9) , Topological Sorting(8) , Traveling Salesman Problem(5) , Vertex Cover(9) -
Java Collections (Library) NEW
- Calendrical Calculations
(9) , Dictionaries(8) , Median and Selection(9) , Priority Queues(8) , Searching(9) , Set Data Structures(9) , Sorting(9) -
Weisses Data Structure (Application)
- Dictionaries
(9) , Kd-Trees(5) , Priority Queues(9) , Searching(8) , Set Data Structures(5) -
JDSL: Java Data Structures Libary (Library) NEW
- Connected Components
(8) , Dictionaries(9) , Graph Data Structures(8) , Minimum Spanning Tree(8) , Priority Queues(9) , Topological Sorting(8) -
GNU Classpath: an GNU Java API Library (Library) NEW
- Dictionaries
(7) , Priority Queues(8) , Set Data Structures(8) - JUNG: Java graph data structure (Library) NEW
- Connected Components
(9) , Graph Data Structures(9) - JScience: comprehensive Java library for the scientific community. (Library) NEW
- Determinants and Permanents
(9) , Solving Linear Equations(9) - JAMA : A Java Matrix Package (Library) NEW
- Determinants and Permanents
(9) , Solving Linear Equations(8) , Matrix Multiplication(5) - Samest Spatial Index Demos (Animation) NEW
- Kd-Trees
(9) , Nearest Neighbor Search(7) - JGraphEd: Java Graph Editing application (Application) NEW
- Planarity Detection and Embedding
(9) - Prof Harold Thimbleby's The Chinese Postman Problem (Application) NEW
- Eulerian Cycle / Chinese Postman
(9) - Biojava: A Java framework for processing biological data. (Embedded) NEW
- Suffix Trees and Arrays
(9) - Parallel Random Number Generation (Application) NEW
- Random Number Generation
(8) - JGraph: Java Graph Visualization and Layout (Library) NEW
- Graph Data Structures
(8) - JGAP: Java Genetic Algorithms Package (Library) NEW
- Constrained and Unconstrained Optimization
(8) - Scott Cotton's graphlib (Library) NEW
- Transitive Closure and Reduction
(8) - Colt Project (Library) NEW
- Determinants and Permanents
(5) , Solving Linear Equations(7) , Matrix Multiplication(5) - Bruno R. Preiss's books with source (Application) NEW
- Graph Data Structures
(5) , Priority Queues(5) , Set Data Structures(6) - JFLAP: Formal Languages and Automata Theory (Application) NEW
- Finite State Machine Minimization
(7) - Bioalgorithms' Longest Common Subsequence (Application) NEW
- Longest Common Substring
(7) - QOCA Project (Library) no updates since 2001 NEW
- Linear Programming
(7) - 3D Convex Hull algorithm in Java (Application) no updates since 1999
- Convex Hull
(4) , Voronoi Diagrams(5) - GA Playground (Library)
- Traveling Salesman Problem
(3) , Constrained and Unconstrained Optimization(4) - Java Compatible Toolkit (Application) no updates since 1998
- Finite State Machine Minimization
(3)
Go to Main Page This page last modified on 2008-07-10 . www.algorist.com
Wednesday, March 18, 2009
[转]常用校验码
计算机系统运行时,各个部之间要进行数据交换. 为确保数据在传送过程正确无误,常使用检验码. 我们常使用的检验码有三种. 分别是奇偶校验码、海明校验码和循环冗余校验码(CRC) 。
奇偶校验码
奇偶校验码最简单,但只能检测出奇数位出错. 如果发生偶数位错误就无法检测. 但经研究是奇数位发生错误的概率大很多. 而且奇偶校验码无法检测出哪位出错.所以属于无法矫正错误的校验码。奇偶校验码是奇校验码和偶校验码的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是奇校验加上校验位后,编码中1的个数为奇数个。如果是偶校验加上校验位后,编码中1的个数为偶数个。
例:
原编码 奇校验 偶校验
0000 0000 1 0000 0
0010 0010 0 0010 1
1100 1100 1 1100 0
1010 1010 1 1010 0
如果发生奇数个位传输出错,那么编码中1的个数就会发生变化. 从而校验出错误,要求从新传输数据。目前应用的奇偶校验码有3种.
水平奇偶校验码对每一个数据的编码添加校验位,使信息位与校验位处于同一行.
垂直奇偶校验码把数据分成若干组,一组数据排成一行,再加一行校验码. 针对每一行列采用奇校验 或 偶校验
例: 有32位数据10100101 00110110 11001100 10101011
垂直奇校验 垂直偶校验
数据10100101 10100101
00110110 00110110
11001100 11001100
10101011 10101011
校验00001011 11110100
水平垂直奇偶校验码就是同时用水平校验和垂直校验
例:
奇校验 奇水平 偶校验 偶水平
数据 10100101 1 10100101 0
00110110 1 00110110 0
11001100 1 11001100 0
10101011 0 10101011 1
校验 00001011 0 11110100 1
海明码也是利用奇偶性来校验数据的. 它是一种多重奇偶校验检错系统,它通过在数据位之间插入k个校验位,来扩大码距,从而实现检错和纠错.
设原来数据有n位,要加入k位校验码.怎么确定k的大小呢? k个校验位可以有pow(2,k) (代表2的k次方) 个编码,其中有一个代表是否出错. 剩下pow(2,k)-1个编码则用来表示到底是哪一位出错. 因为n个数据位和k个校验位都可能出错,所以k满足pow(2,k)-1 >= n+k。
①海明校验的基本思想
将有效信息按某种规律分成若干组,每组安排一个校验位,做奇偶测试,就能提供多位检错信息,以指出最大可能是哪位出错,从而将其纠正。实质上,海明校验是一种多重校验。
②海明校验的特点
它不仅具有检测错误的能力,同时还具有给出错误所在准确位置的能力。
一.校验位的位数 校验位的位数与有效信息的长度有关
设:N--为校验码的位数 K--是有效信息位 r--校验位(分成r组作奇偶校验,能产生r位检错信息)
海明码应满足 N=K+r≤2r-1 若r=3 则N=K+r≤7 所以K≤4
二.分组原则`
在海明码中, 位号数(1、2、3、……、n)为2的权值的那些位,即:
1(20)、2(21)、4(22)、8(23)、…2r-1位,作为奇偶校验位
并记作: P1、P2、P3 、P4、…Pr,余下各位则为有效信息位。
例如: N=11 K=7 r=4 相应海明码可示意为
位号 1 2 3 4 5 6 7 8 9 10 11
P占位 P1 P2 × P3 × × × P4 × × ×
其中×均为有效信息,海明码中的每一位分别被P1P2P3P4… Pr 中的一至若干位所校验,其规律是:
第i位由校验位位号之和等于i的那些校验位所校验
如:海明码的位号为3,它被P1P2(位号分别为1,2)所校验
海明码的位号为5,它被P1P3(位号分别为1,4)所校验
归并起来: 形成了4个小组,每个小组一个校验位,校验位的取值,仍采用奇偶校验方式确定。
如表 2·6 、表2·7所示:
三.编码、查错、纠错原理
以4位有效信息(b1、b2、b3、b4)和3位校验位(P1、P2、P3)为例: K=4 r=3
海明序号 1 2 3 4 5 6 7
海明码 P1 P2 b1 P3 b2 b3 b4
根据表2-8可以看到
(1)每个小组只有一位校验位,第一组是P1、第二组是P2、第三组是P3。
(2)每个校验位校验着它本身和它后面的一些确定位。
1.编码原理(采用偶校验)
1)若有效信息b1b2b3b4=1011 先将它们分别填入第3、5、6、7位
2)再分组进行奇偶统计,分别填入校验位P1、P2、P3的值
如:第一组有:P1b1b2b4 因b1b2b4含偶数个1,故P1应取值为0
第二组有:P2b1b3b4 因b1b3b4含奇数个1,故P2应取值为1
第三组有:P3b2b3b4 因b2b3b4含偶数个1,故P3应取值为0
海明编码为:P1P2b1P3b2b3b4=0110011
2.查错与纠错
因为分三组校验,每组产生一位检错信息、3组共3位检错信息,便构成一个指误字,上例指误字由G1G2G3组成。
其中:
G3=P3⊕b2⊕b3⊕b4 P3b2b3b4=0011
G2=P2⊕b1⊕b3⊕b4 P2b1b3b4=1111
G1=P1⊕b1⊕b2⊕b4 P1b1b2b4=0101
采用偶校验,在没有出错情况下G1G2G3=000。由于在分组时,就确定了每一位参加校验的组别,所以指误字能准确地指出错误所在位。
如:若第3位b1出错,由于b1参加了第一组和第二组的校验,必然破坏了第一组和第二组的偶性,从而使G1和G2为1。 因为b1未参加第三组校验,故G3=0,所以构成的指误字G3G2G1=011它指出第3位出错。
反之:若G3G2G1=111 则说明海明码第7位b4出错。因为只有第7位b4参加了3个小组的校验,破坏了三个小组的偶性。
假定:
源部件发送海明码为:0110011 接收端接收海明码为:0110011
则: 三个小组都满足偶校验要求,这时G3G2G1=000,表明收到信息正确,可以从中提出有效信息1011参与运算处理。
纠错:若接收端收到的海明码为0110111,分组检测后指误字G3G2G1=101,它指出第5位出错,则只须将第5位变反,就可还原成正确的数码0110011。
循环冗余校验码
CRC码利用生成多项式为k个数据位产生r个校验位进行编码,其编码长度为n=k+r所以又称 (n,k)码. CRC码广泛应用于数据通信领域和磁介质存储系统中. CRC理论非常复杂,一般书就给个例题,讲讲方法.现在简单介绍下它的原理:
在k位信息码后接r位校验码,对于一个给定的(n,k)码。可以证明(数学高手自己琢磨证明过程)存在一个最高次幂为 n-k=r 的多项式g(x),根据g(x)可以生成k位信息的校验码,g(x)被称为 生成多项式
用C(x)=C(k-1)C(k-2)...C0表示k个信息位,把C(x)左移r位,就是相当于 C(x)*pow(2,r) 给校验位空出r个位来了.给定一个 生成多项式g(x),可以求出一个校验位表达式r(x) 。C(x)*pow(2,r) / g(x) = q(x) + r(x)/g(x) 用C(x)*pow(2,r)去除生成多项式g(x)商为q(x)余数是r(x)。所以有C(x)*pow(2,r) = q(x)*g(x) + r(x)
C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是生成多项式g(x)的倍式.所以如果用得到的n位CRC码去除g(x)如果余数是0,就证明数据正确. 否则可以根据余数知道出错位.
在CRC运算过程中,四则运算采用 mod 2运算(后面介绍),即不考虑进位和借位. 所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x)
继续前先说下基本概念吧.
1.多项式和二进制编码
x的最高次幂位对应二进制数的最高位.以下各位对应多项式的各幂次. 有此幂次项为1,无为0. x的最高幂次为r时, 对应的二进制数有r+1位 例如g(x)=pow(x,4) + pow(x,3) + x + 1 对应二进制编码是 11011
2.生成多项式 是发送方和接受方的一个约定,也是一个二进制数,在整个传输过程中,这个数不会变.
在发送方利用 生成多项式 对信息多项式做 模2运算 生成校验码.
在接受方利用 生成多项式 对收到的 编码多项式 做 模2运算 校验和纠错.
生成多项式应满足:
a.生成多项式的最高位和最低位必须为1
b.当信息任何一位发生错误时,被生成多项式模2运算后应该使余数不为0
c.不同位发生错误时,应该使余数不同.
d.对余数继续做模2除,应使余数循环.
生成多项式很复杂,不过不用我们生成。
下面给出一些常用的生成多项式表
n k 二进制码(自己根据 多项式和二进制编码 的介绍转)
7 4 1011 或 1101
7 3 11011 或 10111
15 11 1011
31 26 100101
3.模2运算
a.加减法法则
0 +/- 0 = 0
0 +/- 1 = 1
1 +/- 0 = 1
1 +/- 1 = 0
注意:没有进位和借位
b.乘法法则
利用模2加求部分积之和,没有进位
c.除法法则
利用模2减求部分余数,没有借位,每商1位则部分余数减1位,余数最高位是1就商1,不是就商0, 当部分余数的位数小于余数时,该余数就是最后余数.
例 1110
1011)1100000
1011
1110
1011
1010
1011
0010(每商1位则部分余数减1位,所以前两个0写出)
0000
010(当部分余数的位数小于余数时,该余数就是最后余数)
最后商是1110余数是010
好了说了那么多没用的理论.下面讲下CRC的实际应用.例: 给定的生成多项式g(x)=1011, 用(7,4)CRC码对C(x)=1010进行编码.
由题目可以知道下列的信息:
C(x)=1010,n=7,k=4,r=3,g(x)=1011 C(x)*pow(2,3)=1010000 C(x)*pow(2,3) / g(x) = 1001 + 11/1011 所以r(x)=011.所以要求的编码为1010011
例2: 上题中,数据传输后变为1000011,试用纠错机制纠错. 1000011 / g(x) = 1011 + 110/1011
不能整除,所以出错了. 因为余数是110.查1011出错位表可以知道是第5位出错.对其求反即可.
Redundant Array of Independent Disks
http://en.wikipedia.org/wiki/Redundant_array_of_independent_disks
独立冗余磁盘阵列Principles
RAID combines two or more physical hard disks into a single logical unit by using either special hardware or software. Hardware solutions often are designed to present themselves to the attached system as a single hard drive, so that the operating system would be unaware of the technical workings. For example, you might configure a 1TB RAID 5 array using three 500GB hard drives in hardware RAID, the operating system would simply be presented with a "single" 1TB disk. Software solutions are typically implemented in the operating system and would present the RAID drive as a single drive to applications running upon the operating system.
There are three key concepts in RAID: mirroring, the copying of data to more than one disk; striping, the splitting of data across more than one disk; and error correction, where redundant data is stored to allow problems to be detected and possibly fixed (known as fault tolerance). Different RAID levels use one or more of these techniques, depending on the system requirements. RAID's main aim can be either to improve reliability and availability of data, ensuring that important data is available more often than not (e.g. a database of customer orders), or merely to improve the access speed to files (e.g. for a system that delivers video on demand TV programs to many viewers).
The configuration affects reliability and performance in different ways. The problem with using more disks is that it is more likely that one will go wrong, but by using error checking the total system can be made more reliable by being able to survive and repair the failure. Basic mirroring can speed up reading data as a system can read different data from both the disks, but it may be slow for writing if the configuration requires that both disks must confirm that the data is correctly written. Striping is often used for performance, where it allows sequences of data to be read from multiple disks at the same time. Error checking typically will slow the system down as data needs to be read from several places and compared. The design of RAID systems is therefore a compromise and understanding the requirements of a system is important. Modern disk arrays typically provide the facility to select the appropriate RAID configuration.
Standard levels
A number of standard schemes have evolved which are referred to as levels. There were five RAID levels originally conceived, but many more variations have evolved, notably several nested levels and many non-standard levels (mostly proprietary).
Following is a brief summary of the most commonly used RAID levels.[3] Space efficiency is given as amount of storage space available in an array of n disks, in multiples of the capacity of a single drive. For example if an array holds n=5 drives of 250GB and efficiency is n-1 then available space is 4 times 250GB or roughly 1TB.
| Level | Description | Minimum # of disks | Space Efficiency | Image |
|---|---|---|---|---|
| RAID 0 | "Striped set without parity" or "Striping". Provides improved performance and additional storage but no fault tolerance. Any disk failure destroys the array, which becomes more likely with more disks in the array. A single disk failure destroys the entire array because when data is written to a RAID 0 drive, the data is broken into fragments. The number of fragments is dictated by the number of disks in the array. The fragments are written to their respective disks simultaneously on the same sector. This allows smaller sections of the entire chunk of data to be read off the drive in parallel, giving this type of arrangement huge bandwidth. RAID 0 does not implement error checking so any error is unrecoverable. More disks in the array means higher bandwidth, but greater risk of data loss. | 2 | n | |
| RAID 1 | 'Mirrored set without parity' or 'Mirroring'. Provides fault tolerance from disk errors and failure of all but one of the drives. Increased read performance occurs when using a multi-threaded operating system that supports split seeks, very small performance reduction when writing. Array continues to operate so long as at least one drive is functioning. Using RAID 1 with a separate controller for each disk is sometimes called duplexing. | 2 | 1 | |
| RAID 2 | Hamming code parity. Disks are synchronised and striped in very small stripes, often in single bytes/words. Hamming codes error correction is calculated across corresponding bits on disks, and is stored on multiple parity disks. | 3 | ||
| RAID 3 | Striped set with dedicated parity or bit interleaved parity or byte level parity. This mechanism provides an improved performance and fault tolerance similar to RAID 5, but with a dedicated parity disk rather than rotated parity stripes. The single parity disk is a bottle-neck for writing since every write requires updating the parity data. One minor benefit is the dedicated parity disk allows the parity drive to fail and operation will continue without parity or performance penalty. | 3 | n-1 | |
| RAID 4 | Block level parity. Identical to RAID 3, but does block-level striping instead of byte-level striping. In this setup, files can be distributed between multiple disks. Each disk operates independently which allows I/O requests to be performed in parallel, though data transfer speeds can suffer due to the type of parity. The error detection is achieved through dedicated parity and is stored in a separate, single disk unit. | 3 | n-1 | |
| RAID 5 | Striped set with distributed parity or interleave parity. Distributed parity requires all drives but one to be present to operate; drive failure requires replacement, but the array is not destroyed by a single drive failure. Upon drive failure, any subsequent reads can be calculated from the distributed parity such that the drive failure is masked from the end user. The array will have data loss in the event of a second drive failure and is vulnerable until the data that was on the failed drive is rebuilt onto a replacement drive. A single drive failure in the set will result in reduced performance of the entire set until the failed drive has been replaced and rebuilt. | 3 | n-1 | |
| RAID 6 | Striped set with dual distributed parity. Provides fault tolerance from two drive failures; array continues to operate with up to two failed drives. This makes larger RAID groups more practical, especially for high availability systems. This becomes increasingly important because large-capacity drives lengthen the time needed to recover from the failure of a single drive. Single parity RAID levels are vulnerable to data loss until the failed drive is rebuilt: the larger the drive, the longer the rebuild will take. Dual parity gives time to rebuild the array without the data being at risk if one drive, but no more, fails before the rebuild is complete. RAID 6 is sometimes referred to as Advanced Data Guarding (ADG). | 4 | n-2 |
Load Balance
针对此情况而衍生出来的一种廉价有效透明的方法以扩展现有网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的来实现的,在DNS中为多个地址配置同一个名字,因而查询这个名字的客户机将得到其中一个地址,从而使得不同的客户访问不同的服务器,达到负载均衡的目的。DNS负载均衡是一种简单而有效的方法,但是它不能区分服务器的差异,也不能反映服务器的当前运行状态。
2、代理服务器负载均衡 使用代理服务器,可以将请求转发给内部的服务器,使用这种加速模式显然可以提升静态网页的访问速度。然而,也可以考虑这样一种技术,使用代理服务器将请求均匀转发给多台服务器,从而达到负载均衡的目的。
3、地址转换网关负载均衡 支持负载均衡的地址转换网关,可以将一个外部IP地址映射为多个内部IP地址,对每次TCP连接请求动态使用其中一个内部地址,达到负载均衡的目的。
4、协议内部支持负载均衡 除了这三种负载均衡方式之外,有的协议内部支持与负载均衡相关的功能,例如HTTP协议中的重定向能力等,HTTP运行于TCP连接的最高层。
5、NAT负载均衡 NAT(Network Address Translation 网络地址转换)简单地说就是将一个IP地址转换为另一个IP地址,一般用于未经注册的内部地址与合法的、已获注册的Internet IP地址间进行转换。适用于解决Internet IP地址紧张、不想让网络外部知道内部网络结构等的场合下。
此种负载均衡是当前多WAN口路由器的带宽汇聚技术基础,以欣向路由器为例:
欣向的多WAN路由器实现的是业界先进的动态负载平衡机制,我们独立研发的多WAN口动态负载平衡技术,使得在使用多条线路的情况下动态分配内网的数据流量,动态的实现带宽汇聚的功能,采用特有的三种负载平衡机制:
a.Session:所有启用的WAN口,采用均分session的方式工作。
如第一个连接session通过WAN1口流出,则下一个session自动选择WAN2流出,第三个session选择WAN3口流出(假设所有WAN口都启用)
这种方式适用于多条相同带宽的线路捆绑时使用。
b.Round robin:同样是根据session数目调整负载,但比例可调。
如将比例设为1:2:3:4,则按如下规则处理:
第1个session选择WAN1口(session数=1);
第2,3个 session选择WAN2口(session数=2);
第4 ~ 6个 session 选择WAN3口(session数=3);
第7 ~ 10个session选择WAN4口(session数=4);
这种方式适用于多条不同带宽的线路能够更好的协同工作。例如:WAN1口接一条512K的ADSL,WAN2口接
c.Traffic:按数据流量分配负载,系统自动选择流量最小的WAN口作为出口。
此种方式适用于线路不稳定时的多条线路混用的情况。在某一条线路暂时不通或者线路不稳定的情况下会把流量自动分配到另一条稳定的线路上。但在多条线路稳定的情况下不建议使用这种方式。
有了这三种负载平衡使得路由器可以灵活的应对多种线路混用的复杂情况,支持多种线路混接,支持多种协议,能够满足多种复杂应用。
6、反向代理负载均衡 普通代理方式是代理内部网络用户访问internet上服务器的连接请求,客户端必须指定代理服务器,并将本来要直接发送到internet上服务器的连接请求发送给代理服务器处理。反向代理(Reverse Proxy)方式是指以代理服务器来接受internet上的连接请求,然后将请求转发给内部网络上的服务器,并将从服务器上得到的结果返回给internet上请求连接的客户端,此时代理服务器对外就表现为一个服务器。反向代理负载均衡技术是把将来自internet上的连接请求以反向代理的方式动态地转发给内部网络上的多台服务器进行处理,从而达到负载均衡的目的。
7、 混合型负载均衡 在有些大型网络,由于多个服务器群内硬件设备、各自的规模、提供的服务等的差异,我们可以考虑给每个服务器群采用最合适的负载均衡方式,然后又在这多个服 务器群间再一次负载均衡或群集起来以一个整体向外界提供服务(即把这多个服务器群当做一个新的服务器群),从而达到最佳的性能。我们将这种方式称之为混合 型负载均衡。此种方式有时也用于单台均衡设备的性能不能满足大量连接请求的情况下。
Thursday, February 19, 2009
route 笔记(续)
Active Routes:活动的路由
network destination 目的网段
netmask 子网掩码
gateway 下一跳路由器入口的ip
interface 到达该目的地的本路由器的出口ip
路由器通过interface和gateway定义一条到下一个路由器的链路,通常情况下,interface和gateway是同一网段的,特殊情况下gateway可以不在当前interface的网段上,比如配置递归寻路的情况下metric 跳数,该条路由记录的质量,一般情况下,如果有多条到达相同目的地的路由记录,路由器会采用metric值小的那条路由,如果同时连接了有线和无线网络,一般有线是20,无线是30 Persistent Routes:手工配置的静态固化路由,即时重启也不会消失
第一条:
Network destinationNetmask Gateway Interface Metric
0.0.0.0 0.0.0.0 192.168.2.1 192.168.2.6 20
缺省路由:意思就是说,当一个数据包的目的网段不在你的路由记录中,那么,你的路由器该把那个数据包发送到那里!缺省路由的网关是由你的连接上的default gateway决定的.
该路由记录的意思是:当我接收到一个数据包的目的网段不在我的路由记录中,我会将该数据包通
过 192.168.2.6 这个接口发送到 192.168.2.1 这个地址,这个地址是下一个路由器的一个接口,这
样这个数据包就可以交付给下一个路由器处理,与我无关。该路由记录的线路质量: 20.
第二条
Network destination Netmask Gateway Interface Metric
127.0.0.1 255.0.0.0 127.0.0.1 127.0.0.1 1
本地环路:127.0.0.0这个网段内所有地址都指向自己机器,如果收到这样一个数据,应该
发向哪里 该路由记录的线路质量 1
第三条
Network destination Netmask Gateway Interface Metric
192.168.2.0 255.255.255.0 192.168.2.6 192.168.2.6 20
直联网段的路由记录:当路由器收到发往直联网段的数据包时该如何处理,这种情况,
路由记录的 Interface 和 Gateway 是同一个。
当我接收到一个数据包的目的网段是 192.168.2.0 时,我会将该数据包通过
192.168.2.6 这个接口直接发送出去,因为这个端口直接连接着192.168.2.0这个网段,
该路由记录的线路质量 20
第四条
Network destination Netmask Gateway Interface Metric
192.168.2.6 255.255.255.255 127.0.0.1 127.0.0.1 20
本地主机路由:当路由器收到发送给自己的数据包时将如何处理。
当我接收到一个数据包的目的网段是 192.168.2.6 时,我会将该数据包收下,因为这个数
据包是发送给我自己的,该路由记录的线路质量 20
第五条
Network destination Netmask Gateway Interface Metric
192.168.2.255 255.255.255.255 192.168.2.6 192.168.2.6 20
本地广播路由:当路由器收到发送给直联网段的本地广播时如何处理。
当我接收到广播数据包的目的网段是 192.168.2.255 时,我会将该数据从
192.168.2.6 接口以广播的形势发送出去,该路由记录的线路质量 20
第六条
Network destination Netmask Gateway Interface Metric
224.0.0.0 224.0.0.0 192.168.2.6 192.168.2.6 20
组播路由:当路由器收到一个组播数据包时该如何处理。
当我接收到组播数据包时,我会将该数据从 192.168.2.6 接口以组播的形势发送出去,
该路由记录的线路质量 20。
第七条
Network destination Netmask Gateway Interface Metric
255.255.255.255 255.255.255.255 192.168.2.6 192.168.2.6 1
广播路由:当路由器收到一个绝对广播时该如何处理。
当我接收到绝对广播数据包时,将该数据包通过 192.168.2.6 发出去
