🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: cn.bbs.comp.database
Article #152

Re: BigTable

#152
From: Galaxy��VOLUNTEERS��Database
Date: Tue, 07 Jul 2009 05:54
218 lines
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

�� ��Դ:����ˮ˼Դ bbs.sjtu.edu.cn��[FROM: 207.46.55.30]

�� �޸ı���:��Dem �� 07��07��13:54:31 �޸ı��ġ�[FROM: 207.46.55.30]
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!SJTU

Show 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