Article View: cn.bbs.comp.database
Article #152Re: BigTable
From: Galaxy��VOLUNTEERS��Database
Date: Tue, 07 Jul 2009 05:54
Date: Tue, 07 Jul 2009 05:54
218 lines
21402 bytes
21402 bytes
���(Bigtable):�ṹ����ݵķֲ��洢ϵͳ
http://labs.google.com/papers/bigtable-osdi06.pdf
��������������,��������
{���ĵķ�������в�ȷ�ĵط�,��ϸ������ο�ԭ��.}
ժҪ
bigtable��������ֲ��洢���ģ�ṹ����ݵģ���������������չ���ϣ�^50�ֽڣ�
�ֲ��洢�ڼ�ǧ����ͨ�������ϣ���oogle�ĺܶ���Ŀʹ�ã£����洢��ݣ�������ҳ��
ѯ��google earth��google���ڣ���ЩӦ�ó���ԣ£Ե�Ҫ�������ͬ����ݴ�С����U
RL����ҳ������ͼ��ͬ����Ӧ�ٶȲ�ͬ���Ӻ�˵Ĵ����?ʵʱ��ݷ�����
�ڲ�ͬ��Ҫ�£Զ��ɹ����ṩ������Ч�ķ����ڱ����У����ǽ������£Ե���
��ģ�ͣ�������ģ�����û���̬�Ŀ�����ݵķֲ��ͽṹ�����ǻ��������£Ե����
��ʵ�֣�
��������
�ڹ�ȥ������������ƣ�ʵ�ֲ������ˣ£ԣ��£��������ֲ��洢����ṹ����
�ݵģ��£Ե����ʹ���ܹ�����2^50 bytes(petabytes)��ݣ������Բ�����ǧ̨����
�ϣ��£����������Ŀ�꣺Ӧ�ù㷺������չ�������ܺ߿����ԣ�high availability
��. ����google analytics, google finance, orkut, personalized search, writely
��google earth���ڵ�60�����Ŀ��ʹ��BT.��ЩӦ�öԣ£Ե�Ҫ�������ͬ���е���Ҫ
�������������?�е���Ҫ���ٷ�Ӧ���û���ݣ�����ʹ�õģ£Լ�ȺҲ������ͬ��
�е�ֻ�м�̨�������е�����ǧ̨���ܹ��洢2^40�ֽ�(terabytes)��ݣ�
�£��ںܶ�ط�����ݿ�����ƣ���ʹ���˺ܶ���ݿ��ʵ�ֲ��ԣ�������ݿ�ۣ���
�ݺ��ڴ���ݿ�ۣ������п���չ�Ժ����ܣ����ǣ£ԵĽ��治ͬ���£Բ�֧����ȫ
�Ĺ�ϵ���ģ�ͣ�����Ϊ�ͻ��ṩ�˼����ģ�ͣ��ÿͻ�����̬������ݵķֲ���
��ʽ{����ֻ�洢�ִ�����ʽ�ɿͻ�������}��������ͻ��ƶϵײ�洢��ݵľֲ��ԣ�
����߷����ٶȣ�����±����к��е����֣���ݱ���������κ��ִ����£Ե����
���ִ���û�н��ͣ����͵ȣ�ͻ����ڰѸ��ֽṹ���߰�ṹ������ݴ��л������
˵���ڴ�������У�ͨ����ϸѡ����ݱ�ʾ���ͻ����Կ�����ݵľֲ��������
��ʹ�ã£�ģʽ����������Ƿ����ڴ��ﻹ����Ӳ���ϣ������˵��ģʽ���������
�ݷ�����Ӧ�����ĵط����Ͼ�������һ��ʱ��ֻ�õ�һ����ݣ�����ϵ�ṹ�����
��locality, locality, locality��
�ڶ����������ģ��ϸ�ڣ�����ڹ��ڿͻ����Уɸ��������Ľڼ��£�������google
��ܣ�����������£Ե�ʵ�ֹؼ�֣���6��������ߣ£����ܵ�һЩ�����7����
���£����ܵ���ݣ��ڵ�8�ڣ������ṩ�£Եļ���ʹ�����ӣ���9���Ǿ����ѵ���ڵ�1
0�ڣ������г�����о�����������ǵĽ��ۣ�
��������
�£���һ��ϡ��ģ����ڴ洢�ģ����Ӳ���ϣ��ά�ȵģ������ӳ��?���ű��
�������йؼ��֣��йؼ��ֺ�ʱ�����ÿ��ֵ��һ�������͵��ַ����飮����ݶ�����
��û���ͣ��ͻ�Ҫ���;���������ɣ�
(row:string, column:string,time:int64)->string {�ܱ����Ķ��ܶ�������������}
//�˰�����ĵڶ���
������ϸ�鿴���Щ����bigtable��ϵͳ֮������������ģ�͡���һ���������ӣ�
���ʹ��������ijЩ��ƾ������� ����������Ҫ�洢������ҳ�������Ϣ�������ںܶ�
��ͬ����Ŀ�����ǹ��ҽ���Webtable����Webtable����ǽ���URL��Ϊ�йؼ��֣�����
ҳ��ijЩ������Ϊ�������ҳ���ݴ���contents:���в��û�ȡ����ҳ��ʱ�����Ϊ��
ʶ����ͼһ��ʾ��
http://i106.photobucket.com/albums/m261/beyond-the-sea/Bigtable_Figure1.jpg
ͼһ��һ���洢Web��ҳ�ķ����б�Ƭ�ϡ�������һ������URL��com.cnn.www��cont
ents�����ԭ���� family����Ϊ�壬������������ҳ���ݣ�anchor���������ø�
��ҳ��ê�����ı���CNN����ҳ��Sports Illustrater����νSI��CNN�����������Ŀ
���MY-look����ҳ���ã���˸��а�����С�anchor:cnnsi.com���� ��anchhor:my.
look.ca�����С�ÿ��ê����ֻ��һ���汾����ʱ�����ʶ����t9��t8���contents��
��������汾���ֱ���ʱ�� ��t3��t5����t6��ʶ��
��
���е��йؼ��ֿ����������ַ�Ŀǰ֧�����64KB�����������10��100�ֽ��㹻��
������һ���йؼ����µ�ÿһ����д��������ԭ�Ӳ��������ܶ�д��һ������ٸ���ͬ
�У�������һ����ƾ����������ڶ�ͬһ�н��в�������ʱ���û�����ϵͳ��Ϊ������
�����ƿء�
Bigtableͨ���йؼ��ֵ��ֵ�����ά����ݡ�һ�ű���Զ�̬���ֳɶ�������С�����
��������������ӱ?��tablet������ݷֲ����ؾ��ĵ�λ������һ����������
�������оͱȽ���Ч�ʣ�ͨ��ֻ��Ҫ���ٻ���֮���ͨ�ż��ɡ��û����������������
��ѡ���йؼ��֣��Ӷ�ﵽ�Ϻ���ݷ��ʵ����ԣ�locality�������˵����Webtable
�ͨ��תURL��������ķ�ʽ������ͬһ�������µ���ҳ��֯�������С�������˵
������maps.google.com/index.html�е���ݴ���ڹؼ���com.google.maps/index.h
tml�¡�������ͬ���������������������ҳ�����û�������ͻ�������ķ��������
��
����
һ���йؼ�������ˡ����塱�����Ƿ��ʿ��ƵĻ�λ��ͬһ�����´�ŵ��������
ͨ������ͬһ���ͣ�ͬһ�����µ���ݿ�ѹ����һ�𣩡���������ȴ�����Ȼ��������
���е��йؼ����´����ݣ����崴���������κ�һ���йؼ��־��ʹ�á�����ϣ��
��һ�ű��еIJ�ͬ���岻��̫�ࣨ��༸�ٸ��������������������о��ٸı䡣��Ϊ��
�ȣ�һ�ű�����������С�
�йؼ�����������������壺���ʡ� ����������ǿ��ö���printable����ִ�
�������ʿ����������ַ����磬Webtable�����и������language�����д��
ҳ�����ԡ�������language������ֻ��һ���йؼ��֣��������ÿ����ҳ�����Ա�ʶ��
���ñ����һ�����õ�������anchor���������ÿһ���йؼ��ִ��һ��ê���ӣ���ͼ
һ��ʾ��������������������ø���ҳ��վ�������һ�������ŵ��������ı���
���ʿ��ƣ�����ʹ��ͳ�ƣ��ڴ�ʹ��ͳ�ƣ�������������������С���Webtable����
�У����ǿ�������Щ���������?ͬӦ�ã��е�Ӧ������µĻ���ݣ��еĶ�ȡ��
��ݲ�������������壬�е���ֻ�������ݣ�����������Ϊ��˽Ȩԭ�����������
��ݣ���
ʱ���
Bigtable����ÿһ���������ͬһ��ݵĶ���汾����ʱ���������Bigtable
��ʱ�����64λ���͡�������Bigtable����ֵ����ʾȷ������ġ�ʵʱ������������
��Ӧ�ó�������ֵ����Ҫ�����ͻ��Ӧ�ó�������Լ��������Ψһ�Ե�ʱ�������ͬ
�汾�ı������ݰ�ʱ����������У������µ�����ǰ�档
Ϊ�˼��ڲ�ͬ��ݰ汾����ݵĹ��?���Ƕ�ÿһ������֧�������趨���Ա���Big
table�Ա���İ汾�Զ�������������û�����ָ��ֻ������������n���汾������
ֻ�����㹻�µİ汾�����磬ֻ�������7������ݣ���
��Webtable�����У�������contents:���д��ȷ������һ����ҳ��ʱ���������������
���������ƿ���������ֻ����ÿ����ҳ���������汾��
//�ҿ�ʼ����3,4��
3.API
BT�ģ��У��ṩ�˽�����ɾ��������ĺ����ṩ�˺������ļ�Ⱥ����������
Ԫ��ݣ�����˵����Ȩ�ޣ�
// Open the table
Table *T = OpenOrDie(��/bigtable/web/webtable��);
// Write a new anchor and delete an old anchor
RowMutation r1(T, ��com.cnn.www��);
r1.Set(��anchor:www.c-span.org��, ��CNN��);
r1.Delete(��anchor:www.abc.com��);
Operation op;
Apply(&op, &r1);
ͼ 2: д��Bigtable.
�ڣ£��У��ͻ�Ӧ�ÿ���д����ɾ��ֵ����ÿ��������ֵ�����߱���һ�����е������
����ͼ2�ģã���������ʹ��RowMutation�����ʾ������һϵ�еĸ��£�Ϊ��֤���뾫
��û�а����ص�ϸ�ڣ�������Apply����Ͷԣ�ebtable������һ��ԭ���ģ���
Ϊhttp://www.cnn.com/������һ��ê�㣬��ɾ��������һ��ê�㣮
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily(��anchor��);
stream->SetReturnAllVersions();
scanner.Lookup(��com.cnn.www��);
for (; !stream->Done(); stream->Next()) {
printf(��%s %s %lld %s\n��,
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
ͼ3: ��Bigtable�����.
ͼ3�ģã���������ʹ��Scanner����������һ�����ڵ�����ê�㣮�ͻ����Ա�������
�壮�кܶ����������һ��ɨ���в�����У��к�ʱ��������磬���ǿ�����������
��ɨ�裬����ֻ�ҵ���Щƥ��������ʽ*.cnn.com��ê�㣬������Щʱ����ڵ�ǰʱ��
ǰ10���ê�㣮
�£Ի�֧������һЩ���ӵĴ�����ݵĹ��ܣ����ȣ��£�֧�ֵ��д��?������ܿ�
�������Դ洢��һ���йؼ����µ���ݽ���ԭ�ӵĶ�-��-д�������£�Ŀǰ��֧�ֿ�
�йؼ��ֵĴ��?��������һ�����棬���������ÿͻ����������Ŀ��йؼ��ִ������
����Σ��£������ÿ�����������������������£�֧���ڷ������ĵ�ַ�ռ���
ִ�пͻ����ṩ�Ľű����ű������������google������Sawzall[28]��ݴ�������
��Ŀǰ�����ǻ��ڵ�Sawzall�ģ��Уɻ�������ͻ��ű�������£���д��ݣ���������
�������ʽ����ݱ任�������κα��ʽ�Ĺ��˺�ͨ����ֲ������ժҪ��
�£Կ��Ժ�MapReduce[12]һ��ʹ�ã�MapReduce��google�����Ĵ��ģ���м����ܣ�
����Ϊ��д��һ��������ʹ�£Կ�����ΪMapReduce��������Դͷ��������
4.�����£ԵĻ�Ԫ
�£��ǽ������������google��ܵ�Ԫ�ϵģ��£�ʹ��google�ֲ�ʽ�ļ�ϵͳ(GFS)[17]
���洢��־������ļ�{yeah, right, what else can it use, FAT32?}��һ���£Լ�Ⱥ
ͨ����һ������Ļ������й��������еĻ�������������ķֲ�ʽӦ��{��Ȼ�������˵�
��ײ��Ƶģ�����һ��Ҫ���ж������������С�ײ�}���£Ժ���������������
�£Ե�ƿ���ǣɣ�/�ڴ棬���Ժ�CPUҪ��ߵij����£�������Ⱥ����ϵͳ����
�Ź������ڹ���Ļ����Ϲ�����Դ������ʧЧ���������ӻ���״̬����͵�server farm
�ṹ���£��������Ӧ��֮һ��
�£��ڲ��洢��ݵĸ�ʽ��google SSTable��ʽ��һ��SSTable�ṩһ���ӹؼ��ֵ�ֵ��
ӳ�䣬�ؼ��ֺ�ֵ�������������ַ�ӳ��������ģ��洢�ģ����Ϊ�����ʧ
��ɸ�д�ģ����Խ������²�������ѯ��һ���ؼ�����ص�ֵ�����߸�ݸ���Ĺ�
���ַ�Χ�������еĹؼ��ֺ�ֵ�����ڲ���ÿ��SSTable��һ����ݿ飨ͨ��ÿ�����
��С��64KB,���Ǵ�С�ǿ������õģ������С��16 bits��Ӧ���DZȽϺõ�һ�����
��������洢��SSTable�����������λ��ݿ飻����SSTable��ʱ�������
���ڴ�����ܣ�ÿ�β��Ҷ�������һ��Ӳ��������ɣ����������������ĸ�����
��һ����Ӧ�ò������������û��Ҫʡ��ô��ռ���������ڴ��е���������ж���
�����ҵ���ݿ��λ�ã�Ȼ���ٴ�Ӳ�̶�ȥ��ݿ飮�������ǣ����SSTable���Ա���
���ڴ������һ���Ͳ��ط���Ӳ���ˣ����������ǰ����˭�ڿ�����˵Ҫ����˹���
�������ţ�����ڴ�ռ���˱�������˯ȥ����
�£Ի�����һ���߶ȿ��õģ��洢�ķֲ�ʽ��������Chubby[8]������ô�����high
performance��˵Բඣ�һ��Chubby������5����ı��ݣ������ɣ�����һ������
Щ����ѡ�������ݣ����Ҵ��������������ֻ���ڴ����ݶ����Ų��һ���ͨ�ŵ�
ʱ����ǻ�ģ��ƿ��ȥ��ԭ�İɣ������г����ǰ���µ������㷨���л���ʧ
Ч��ʱ��Chubbyʹ��Paxos�㷨[9,23]����֤���ݵ�һ���ԣ��������DZȽϸ��ӵ�
������ȥ�������˽�һ�����Ȿ���Chubby�ṩ��һ�����ֿռ䣬���������Ŀ¼��
С�ļ�����䲻�����ڣ�ÿ��Ŀ¼�����ļ����Ե���һ�������ã���д�ļ���������
ԭ�ӻ��ģ�Chubby�ͻ��˵ij�����ṩ�˶�Chubby�ļ���һ���Ի�������������
���ǽ������ܣ��������Ƿֲ��ģ�����������ܣ�ÿ��Chubby�ͻ�ά��һ����Chubb
y����ĻỰ�����һ���ͻ�������һ��ʱ���ڸ�����ĻỰ������Ự����ʧЧ�ˣ�
������Դ�server farm�����ʧЧ��Ƶ����Ƶģ�һ���ỰʧЧʱ����ӵ�е����
���ļ����ʧЧ������ԭ��ʧЧʱ�ص���ȫ״̬��Chubby�ͻ���������
����Ŀ¼�ϵǼǻص������Ի�øı���Ự���ڵ�֪ͨ���������û������
��java��ζ���ˣ���
�£�ʹ��Chubby�������¼�������֤�κ�ʱ�����ֻ��һ����Ծ�������ݣ����洢
�£���ݵ�����λ�ã��ο�5.1�ڣ�������С�?tablet���������������tablet������
�������ƺ�5.2�ڣ����洢�£���ݵ�ģʽ��Ϣ��ÿ�ű������Ϣ�����Լ��洢����Ȩ
���б?������൱����ʱ��Chubby���ܷ��ʣ��£Ծ�Ҳ���ܷ����ˣ��κ�ϵͳ������
��������������ʹ��11��Chubby����ʵ���14���£Լ�Ⱥ�ж��������Ч������C
hubby���ܷ��ʶ���BT�в�����ݲ��ܷ��ʵ�ƽ��ٷֱ���0.0047%,����Chubby���ܷ�
�ʵ�ԭ����Chubby����ʧЧ�����������⣮������Ⱥ���Ӱ�����İٷֱ���0.0326%
������ļ�ϵͳ��Chubby���Ǻ��ȶ��ģ�.
--
Welcome to Database Board
��ӭ������ݿ��
http://bbs.sjtu.edu.cn/bbsdoc?board=database
[m[1;37m�� ��Դ:����ˮ˼Դ bbs.sjtu.edu.cn��[FROM: 207.46.55.30][m
[1;36m�� �ı���:��Dem �� 07��07��13:54:31 �ı��ġ�[FROM: 207.46.55.30][m
Technical Details
Message-ID:
<4gh9A8$bCh@bbs.sjtu.edu.cn>Path:
arc1-ca.pugleaf.net!g2news2.google.com!news1.google.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!news.glorb.com!news2.glorb.com!news.neu.edu.cn!news.shec6.edu.cn!SJTUShow Full Headers
Complete Article Headers
X-Google-Thread: 4df683fd51,aecfe36239f3fb2f,start X-Google-Attributes: gid4df683fd51,public,usenet X-Google-NewGroupId: yes X-Google-Language: Chinese,GB Path: arc1-ca.pugleaf.net!g2news2.google.com!news1.google.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!news.glorb.com!news2.glorb.com!news.neu.edu.cn!news.shec6.edu.cn!SJTU From: Dem.bbs@bbs.sjtu.edu.cn (Galaxy��VOLUNTEERS��Database) Newsgroups: cn.bbs.comp.database Subject: Re: BigTable Date: 07 Jul 2009 05:54:31 GMT Organization: ��ˮ˼Դ Message-ID: <4gh9A8$bCh@bbs.sjtu.edu.cn> Mime-Version: 1.0 Content-Type: text/plain; charset="gb2312" Content-Transfer-Encoding: 8bit X-Filename: database/M.1246946024.A