Horizontal or Vertical Scaling

数据库扩展的方向有两个:

垂直扩展-换更牛的机器
水平扩展-增加同样的机器

选择水平扩展必然遇到的一个问题就是,如何决定数据分布在哪台机器上? 也就是分片策略

 

分片Sharding

数据比较平坦的分布在各个节点上,可以使用数字结尾的方式或者取余运算,但是一旦增加机器就要进行大规模的数据重排

要想消除数据分布之痛,就需要更复杂的数据分布schemes来切分数据.

有些依赖于中心目录,它决定了key值对应的位置.当某个碎片增长过大的时候,
这种间接的指导允许数据在机器之间转移,这种做法的代价就是每一个操作都会去
中心目录里面去查询一下 目录信息通常非常小 也都是静态的 一般都会放在内存里面,偶尔变动一下

另外一种方案就是一致性哈希consistent hashing.这种技术使用小表把可能用到的哈希值分范围.一个碎片对应一个值

分片模型对我们的影响

大数据的处理构建在水平扩展模型上,带来的问题就是海量数据的分布式处理,会在某些方面存在妥协

Writing distributed data handling code is tricky and involves tradeoffs between speed, scalability, fault tolerance, and traditional database goals like atomicity and consistency.

不仅仅这些,还有就是数据的使用方式也会有变化:数据不一定在同一物理机器上,取数据和数据运算都会成为新问题.

NoSQL

NoSQL真的没有Schema吗?

 

 In theory, each record could contain a completely different set of named values,though in practice, the application layer often relies on an informal schema, with the client code expecting certain named values to be present.

传统的K/V缓存,缺少对复杂情况的查询,NoSQL在纯K/V的基础上做的强化,把这种常用操作的实现职责从开发者转移到数据库.

 

Hadoop is the best-known public system for running MapReduce algorithms, but many modern databases, such as MongoDB, also support it as an option. It’s worthwhile even in a fairly traditional system, since if you can write your query in a MapReduce form, you’ll be able to run it efficiently on as many machines as you have available.

 

MongoDB

 

 automatic sharding and MapReduce operations.

特点:类JOSN结构 Javascript

优势:有商业公司支持 支持自动分片 MapReduce 

 

 

CouchDB

特点:查询使用js MapReduce
使用多版本的并发控制策略(客户端需要处理写冲突并要进行周期性的垃圾回收来移除旧数据)
缺点:没有内置水平扩展的解决方案 但有外部的解决方案

 

Cassandra 

 源自Facebook内部项目,成为标准的分布式数据库方案. 值得花时间学习这样一个复杂的系统以获得强大的功能和灵活性

 Traditionally, it was a long struggle just to set up a working cluster, but as the project matures, that has become a lot easier.

 一致性哈希解决碎片问题

数据结构针对一致性写做了优化,代价是偶尔的读慢
特性:需要多少给节点一直才可以读/写
控制一致性等级,在一致性和速度之间做取舍

 

Redis

 Two features make Redis stand out: it keeps the entire database in RAM, and its values can be complex data structures.

优势:处理复杂数据结构的能力

你可以通过集群方式来处理海量数据但是目前,sharding都是通过客户端实现的. 

 

BigTable

BigTable is only available to developers outside Google as the foundation of the App Engine datastore. Despite that, as one of the pioneering alternative databases, it’s worth looking at.

 

HBase

HBase was designed as an open source clone of Google’s BigTable, so unsurprisingly it has a very similar interface, and it relies on a clone of the Google File System called HDFS.

 

Hypertable

Hypertable is another open source clone of BigTable.

  

Voldemort
An open source clone of Amazon’s Dynamo database created by LinkedIn, Voldemort has a classic three-operation key/value interface, but with a sophisticated backend architecture to handle running on large distributed clusters.

It uses consistent hashing to allow fast lookups of the storage locations for particular keys, and it has versioning control to handle inconsistent values.

 

Riak
Riak was inspired by Amazon’s Dynamo database, and it offers a key/value interface and is designed to run on large distributed clusters. 

It also uses consistent hashing and a gossip protocol to avoid the need for the kind of centralized index server that BigTable requires, along with versioning to handle update conflicts. 

 

Querying is handled using MapReduce functions written in either  Erlang or Javascript. It’s open source under an Apache license, but there’s also a closed source commercial version with some special features designed for enterprise customers. 

 

 

ZooKeeper

 

The ZooKeeper framework was originally built at Yahoo! to make it easy for the company’s applications to access configuration infor mation in a robust and easy-to-understand way, but it has since grown to offer a lot of features that help coordinate work across distributed clusters. 

 

One way to think of it is as a very specialized key/value store, with an interface that looks a lot like a filesystem and supports operations like watching callbacks, write consensus, and transaction IDs that are often needed for coordinating distributed algorithms. 
This has allowed it to act as a foundation layer for services like LinkedIn’s Norbert, a flexible framework for managing clusters of machines. ZooKeeper itself is built to run in a distributed way across a number of machines, and it’s designed to offer very fast reads, at the expense of writes that get slower the more servers are used to host the service.

Storage

 

S3

Amazon’s S3 service lets you store large chunks of data on an online service, with an interface that makes it easy to retrieve the data over the standard web protocol, HTTP.

One way of looking at it is as a file system that’s missing some features like appending,rewriting or renaming files, and true directory trees. You can also see it as a key/value database available as a web service and optimized for storing large amounts of data in each value.

  http://www.ibm.com/developerworks/cn/java/j-s3/

 

 

HDFS

 

HDFS科普内容  http://baike.baidu.com/view/3061630.htm

NoSQLfan 上关于HDFS的资料   http://blog.nosqlfan.com/tags/hdfs

  

大数据的计算

 

Getting the concise, valuable information you want from a sea of data can be challenging, but there’s been a lot of progress around systems that help you turn your datasets into something that makes sense. Because there are so many different barriers, the tools range from rapid statistical analysis systems to enlisting human helpers.

 

R   Yahoo! Pipes  Mechanical Turk  Solr/Lucene  ElasticSearch  BigSheets Tinkerpop

 

NLP

Natural language processing (NLP) is a subset of data processing that’s so crucial, it  earned its own section. Its focus is taking messy, human-created text and extracting meaningful  information.  As  you  can  imagine,  this  chaotic  problem  domain  has spawned a large variety of approaches, with each tool most useful for particular kinds of text. There’s no magic bullet that will understand written information as well as a human, but if you’re prepared to adapt your use of the results to handle some errors and don’t expect miracles, you can pull out some powerful insights.

• Natural Language Toolkit
• OpenNLP
• Boilerpipe
• OpenCalais

 

Map Reduce 

The approach pioneered by Google, and adopted by many other web companies, is to instead create a pipeline that reads and writes to arbitrary file formats, with intermediate results being passed between stages as files,

with the computation spread across many machines.

Hadoop Hive Pig Cascading Cascalog mrjob Caffeine S4 MapR Acunu Flume Kafka Azkaban Oozie Greenplum  

 

Machine Learning

 

WEKA

WEKA is a Java-based framework and GUI for machine learning algorithms. It provides a plug-in architecture for researchers to add their own techniques, with a command-
line and window interface that makes it easy to apply them to your own data.

 

Mahout
Mahout is an open source framework that can run common machine learning algorithms on massive datasets. 

 

 

scikits.learn
It’s hard to find good off-the-shelf tools for practical machine learning.It’s a beautifully documented and easy-to-use Python package offering a high-level interface to many standard machine learning techniques.This makes it a very fruitful sandbox for experimentation and rapid prototyping, with a very easy path to using the same code in production once it’s working well.

 

卓越亚马逊地址: http://www.amazon.cn/Big-Data-Glossary-Warden-Pete/dp/1449314597/qid=1333609610&sr=8-1#

 

 

2012-8-18更新,下面是回复同事邮件,解答Nosql的几个疑问:

 

  周末我把手头的Nosql资料梳理了一下,尝试回答一下关于Nosql大家比较关心的几个问题,由于每一个点展开都有很多内容,我首先给出一个简单的回答,后面有详细的梳理;

 

简单回答:

1. Q: Why Nosql?既然有关系型数据库为什么要用Nosql?
   A:存储多对多的关系,数据膨胀速度非常快;使用关系型数据库,需要使用分库,分表的方式解决存储问题;
   如果要对关系进行进一步的运算,将是一个大运算量的任务;在Nosql中可以使用MapReduce的方案来实现;
   
   
2. Q:既然我们已经使用了Redis,为什么还要搞一个MongoDB的方案出来?
   A:redis本质上是一个Key-数据结构的内存数据库,不支持对复杂条件的查询,不支持MapReduce;
   而且Redis是产品定位是内存数据库,如果我们把用户行为数据全放在内存,这样就有显著的问题:为冷数据买单
   虽然内存已经很便宜,还是把热数据放在内存,冷数据放磁盘
   
   
3. Q: 据说MongoDB性能很牛,怎么做到的?
   A: 这种观点往往是和关系型数据库比较出来的;本质原因是两者背后的理论不同;
   
   关系型数据库要支持复杂的SQL,严格的关系模型,ACID级别的强事务;
   Nosql在关系型数据库的基础上大刀阔斧的做减法,支持SQL仅仅是可选,不支持强事务;指导其设计的理论是分布式系统的CAP理论
   
   弱化了复杂的系统和强事务性换来了可观的性能提升!可以说这是一个不公平的比赛:一个穿着鲨鱼皮泳衣选手和一个穿着棉衣的选手比赛游泳;
   
   
4. Q: 立志比较纠结分片,在我们的项目里面如何实践分片?
   A: 分片会大大增加现在系统复杂度,我不建议在上线之初就搞分片;如果要读写分离可以使用主从复制集群,如果只是想备份数据避免单点,可以配置"副本集"集群;如果仅仅是想减轻MongoDB的压力,可以前面使用内存缓存;
   
   引入分片的信号:
   (1) 机器磁盘不够用 (2)单节点不能支撑写需求
   
   MongoDB的自动分片目前还是一个"看上去很美"的功能,强烈反对在生产环境中使用;
   
   
5. Q: 你认为捧腹的架构应该如何设计?
   
   A: 捧腹走的是UGC路线,并会增强用户之间的关系;各种复杂的关系存储和运算,是不适合使用Redis和SQL Server的.所以我建议底层使用sql server等关系型数据库储原始数据,中间使用MongoDB存储关系数据和资源冗余数据,上层使用Redis做内存缓存;

详细分析:

 

 

  我们平时使用最多的关系型数据库实际上包含两个重要的组成部分:基于集合理论的SQL和关系型数据模型;其特点是:

1. 支持SQL需要提供一个复杂的系统,即使你仅仅使用最简单的功能;这种成本投入很像我们购买带宽,虽然绝大部分时候带宽不多,但是带宽的购买还是要按照峰值进行;我们仅仅使用主键存取数据,但是关系型数据库依然要按照完全支持SQL理论提供底层支持;
2. 关系型数据模型是非常严格的,在OOP盛行的情况下,这种严格的约束还会有一点便利:开发者可以把业务实体直接映射到DB表
3. 关系型数据库在单机容量达到上限的时候,做扩展是非常难的,往往要要根据主键进行分表;其实可以想到一旦分表之后,就已经开始违反关系型数据库的范式了,因为"同一个集合的数据被拆分到多个表"
4. 关系型数据库一般支持ACID强事务,即:A原子性-要么都全部执行要么不执行 C一致性:事务执行过程中数据一致 I隔离:两个事务互不影响 D持久化:一旦事务完成就应把结果持久化到磁盘

  关系型数据库到Nosql的转折点其实就在第3点,当数据开始分布存储的时候,关系型数据库逐渐演变成依赖主键的查询系统,这几乎是所有Nosql产品共同的特征;总结一下大部分Nosql产品的共同点:

1.  支持SQL不再是必选项,取而代之的是简单的Key-Value存取模型
2.  在关系型数据库的基础上大刀阔斧的做减法,比如不支持事务;Nosql产品对性能的关注远远超过ACID,往往只提供行级别的原子性操作,即对同一个key的操作操作会是串行执行,保证数据不会损坏;这样的策略可以应对大多数场景,关键的是它可以带来非常可观的执行效率提升!
3.  Nosql产品在设计上比较收敛,一般比较克制增加新功能的加入,避免回到关系型数据库的老路上

 

Nosql产品的设计依据的是分布式系统的CAP理论:

C 一致性:在同一时刻,分布式系统中所有节点的数据副本是否一致

A 可用性:集群中一个节点出现问题的时候,是否还可以正常对外服务

P 分区容忍性:当集群中的某个节点失去联系的时候,是否还可以正常对外服务

 

而且所有的分布式系统只可能支持上面的两条,由于网络延迟等问题,P是必须要支持的;所以就要在一致性和可用性上做选择;显然要保持所有节点数据一致就要在检查所有节点数据一致之后才可以判定操作成功,这样显然在一个节点宕掉之后就无法保证可用性;

 

 

Nosql产品大致可以分成下面几类:

1. Key-Value型 value值类型随意类型,比如Voldemort
2. Key-数据结构型 value可以是更为丰富的数据结构,比如Redis
3. Key-document型 value是文档,一般使用类似于Json的结构存储,比如MongoDB CouchDB

 

 

 分片解决的是什么问题?

分片技术实际上就是将数据和读写请求在多个机器(或节点)上分配的技术.

 

同一条数据会存储在多个节点上,存在数据冗余,分片策略追求的目标就是当节点增减的时候,数据填充和迁移的成本最小;

常见的分片策略有:(1) 一致性哈希 (2)想对数据有一个显示的控制,利用控制模块+路由表

分片会导致系统的复杂性大大增加,在数据量不大的情况下,通过增加内存缓存层或通过简单的读写分离即可应对.