Grid съхранява голям обем данни (терабайтове)

релацията students (id,name,dept) се съхранява във файл, всеки ред завършва с \n; # - разделя записите. 42321#Георги Георгиев#ФМИ \n

Oписание на схемата: students# id(име)# INT(тип)# name # STR # dept #STR \n

SELECT * FROM students

Students

id name dept42321 Георги Георгиев ФМИ

SELECT * FROM students

WHERE id>42 000|High - записва се тук.

High #id # int…

SELECT * FROM R

WHERE

Стъпки:

1. 
   От схемата се изчита какви полета и от какъв тип има R
   
2. 
   Проверява се дали условието е синтактически вярно (семантически валидно)
   
3. 
   На екрана се извежда таблицата
   
4. 
   Четене на ред по ред - за всеки ред - проверка за удовлетворяване на условието
   

for всеки кортеж S от Students DO

for всеки кортеж D от Dept DO

if S и D удовлетворяват условието then

изведи S и D

Проблеми: ако данните или потребителите са много

1. 
   разполагането на кортежите върху диска е неадекватно (няма гъвкавост при изменение на кортежа)
   
2. 
   търсенето е скъпо - чете се целия файл
   
3. 
   обработката на заявките е на принципа на грубата сила
   
4. 
   в системата не се поддържа буфериране
   
5. 
   няма управление на конкурентния достъп - няколко потребители могат да променят един и същ файл едновременно
   
6. 
   няма надеждност - губим данните при авария или операция, завършила наполовина
   

СУБД

памет

Файлова

система

Оперативна памет (основна)

Основната памет е с произволен достъп, което означава, че може да се достигне всеки байт за едно и също време. Обикновено времето за достъп до данни в ОП с в порядъка на 10-100 наносекунди.

СУБД на ОП - всички данни са в ОП и отпадат голяма част от проблемите. Базират се на концепцията на виртуалната памет не ползват файлове. Има смисъл ако данните са малко - до 4GB. Оптичните и магнитно-оптичните дискове са по-бавни. Файловете също се прехвърлят на блокове между диска и ОП.

Операции: четене и писане на блок, част от ОП се използва за буфер на файла.

буфер

Размера на буфера се определя или от операционната система, или по програмен път. СУБД може да определи по колко блока да задели при изпълнението на заявките. СУБД не ползва операционната система, обмена на един блок - от 10 до 30 милисекунди; процесора - за 10 милисекунди - няколко милиона инструкции. При СУБД основната мерна единица е броя достъпи до диска. Вторичната памет 10 на 5-та по-бавна от ОП.

Виртуалната памет е много по-голяма от ОП, повечето компоненти от виртуалната памет всъщност се съхраняват на диска. Диска е разделен логически на блокове. Размера на блоковете на обикновен диск е между 4КВ и 56КВ. Преместените между диска и ОП цели блокове обикновено се наричат страници в ОП. Хардуера и операционната памет на компютъра позволяват страниците от виртуалната памет да се преместят във всяка част от ОП и всеки байт от този блок да може да се достигне чрез неговия адрес във виртуалната памет.

Обикновено всеки компютър има вторична памет, която е по-бавна и с по-голям капацитет отколкото основната памет, с произволен достъп и малки разлики между времето за достъп до различните данни. Използват се различни дискове за вторична памет. Обикновено дисковете са магнитни, но се използват и оптични или магнитно-оптични. Дискът е предвиден за поддръжка на виртуалната памет и файловата система. Докато някои блокове ще се използват за съхранение на страници на приложни програми на виртуалната памет, други се използват за съхранение на (части от) файлове. Файловете се местят между диска и ОП в блокове, под контрола на операционната система или СУБД. Преместването на блок от диска до ОП е четене на диск, преместването на блок от ОП към диска е писане на диск. Определени части от ОП се използват да буферират файловете, което означава да съдържат части с размер на блок от тези файлове. Например когато се отвори един файл за четене ОС резервира блок от ОП като буфер за този файл с размера на блоквете на диска. Обикновено първия блок от файла се копира в буфера. Когато приложението изразходва определения брой байтове от файла следващия блок от файла се доставя в буфера, заменяйки старото съдържание. Този процес продължава докато или се прочете целия файл или файла се затвори. СУБД поддържа блоковете на диска сама, не разчита на мениджъра на файлове на ОС да премести блоковете между основната и вторичната памет. Отнема грубо 10-30 милисекунди, за да се прочете или запише блок от/на диска. През това време компютъра може да изпълни няколко милиона инструкции. В резултат на това е нормално за времето да се пречете или запише блок от диска да доминира над времето да се направи каквото трябва със съдържанието на блока. Затова ако е възможно блоковете от диска, съдържащи данни, които желаем да достигнем трябва вече да са в буфера на ОП

Терабайтове информация – вериги магазини; петабайтове – сателити; такива обеми не се побират в компютъра и мрежите, съхраняват се в третична памет. Четенето и писането е много по-бавно от вторичната памет, но по-голям капацитет. Достъпът до отделните данни много варира, в зависимост къде е главата.

Видове:

1. 
   Ad-hoc tape storage – гореща лентова памет лентови ролки, касети, устройство, което ги чете на това устройство лентата се поставя от човек, лентата се пренавива докъдето трябва данните се четат и се прехвърлят върху диска.
   
2. 
   Шкафове с оптични дискове – optical disk juke box – шкафове, в които са поставени CD или DVD в тях се използва роботизирана ръка; взема диска и го поставя в четящото устройство.
   
3. 
   Лентови силози – Tape Silos – сравнително голямо устройство (колкото стая); в него има няколко четящи устройства; лентата се доставя с роботизирана ръка. По-бързо от първия вид, една касета с лента е около 50GB, а в един силоз се събират TB (пример IBM).
   

Друго разделение на устройствата за съхранение е дали те са променливи или не. Променливото устройство “забравя” какво е съхранено на него когато няма електрическо захранване. Непроменливото устройство от друга страна се очаква да съхрани съдържанието си дори за дълъг период когато устройството е изключено или при токов удар. Магнитния материал съхранява магнетизма си и при липсата на електричество, така че магнитни устройства като магнитни дискове и касети са непроменливи. Оптичните устройства като CD също. Всъщност при повечето от тези устройства е невъзможно да се промени каквото е написано на повърхността им. Основно всички вторични и третични устройства са съхранение са непроменливи. От друга страна основната памет е главно променлива. Една система, която е на машина с променлива ОП трябва да съхранява всяка промяна на диск, защото иначе може да се загуби информацията при токов удар. В следствие на това една заявка или модификация на базата от данни включва голям брой писане по диска, някой от които можеха да бъдат избегнати ако не бяхме задължени да съхраним цялата информация през цялото време. Алтернатива на това е да използваме ОП, която не е променлива. Това се прави по два начина:

1. 
   ОП да е flash памет, но тя е скъпа, макар че цените доста падат
   
2. 
   ОП да се ползват RAM дискове, за тях се ползват допълнителни източници на електрическа енергия, в тях не се губи информация, срещат се в сървърните системи.
   

Вторичната памет почти винаги е от магнитни дискове. Състои се от един или повече кръгли плочи, които се въртят около централна ос, покрити отгоре и отдолу с магнитен материал, върху който съхранява битовете, намагнитизирани в една посока – 0, в обратната – 1. обикновено са с 3,5 инчов диаметър има и по-малки(един инч) и по-големи(няколко фута).

Съхранението на битовете е организирано в писти (концентрични окръжности върху плочата). Тези плочи в по-голямата си част се използват за съхранение на писти, близо до оста не се използва. Пистите са организирани в сектори, разделени от празни, не намагнитизирани пространства, всеки сегмент представя един бит чрез посоката на намагнитизирането. Обикновено във външните писти – повече сектори, отколкото във вътрешните. Дискът чете/записва сектор, това значи, че ако се развали сектор то се разваля изцяло. Блокове – използват се в СУБД те са логическа единица, СУБД чете и пише блокове. Блокове се предават/получават към/от диска, главите се движат едновременно. Всички писти, на едно и също място в различни плочи образуват цилиндър, главите са много близо до повърхността но не я докосват, ако я докосне – задиране на диска, главите четат/записват информацията, която минава под тях.

Процесор

ОП

Контролер

1. 
   скорост на въртене – колко оборота прави на минута rpm (5400, 7200 и др.) 5400 rpm – за 11 ms - един оборот
   
2. 
   брой на плочите в устройството – обикновено от 5 до 10
   
3. 
   брой писти на повърхност (при дисковете – около 20 000)
   
4. 
   брой байтове на писта (около 1 млн. байта на писта) средно 500 сектора на писта, 1 сектор – няколко хиляди байта (степени на 2).
   

Как се извършва достъпа, как се манипулира с данните, в началото на СУБД – да се реализира /оптимизира достъпа до диска (програмиране на най-ниското ниво). Изчисления в ОП, по-точно в кеш, но ОП – арена на действието, по отношение на дисковете – как се прехвърлят блокове между вторичната памет и ОП, блоковете – логически единици, те са определен брой последователни сектори, така гледа СУБД - то на диска.

Действия:

1. 
   главите се позиционират върху цилиндъра, където се намира блока, който искаме да четем.
   
2. 
   да се изчакат секторите, които съдържат блока да стигнат главата (чака се началото на първия сектор от блока, но може и от произволен сектор, ако главата се намира вече върху блока).
   

1. 
   време, за което процесора и дисковия контролер обработват заявката (милисекунди - игнорираме)
   
2. 
   време за свързване с дисковия контролер(кратко – игнорираме, може по шината да има конкуренция, но пак е малко)
   
3. 
   време за търсене – позициониране на главата върху цилиндъра (ако са върху него-0, иначе първо започва движение, после спира) и времето необходимо за изминаване на разстоянието от текущата позиция до целевата времето за търсене – няколко милисекунди, максимално – 10-40 милисекунди. х-минимално време 3х-20х общо време.средно време – характеризира бързодействието на диска
   
4. 
   латентност на завъртане – времето за което диска се завърта до първия сектор на блока. 1 оборот е приблизително 10 милисекунди обикновено; средно търсения сектор – по средата, средно време за търсене – 5 милисекунди.
   
5. 
   време за трансфер – времето за което секторите на блока, включително празното пространство между тях ще преминат под главата, ако един диск има 250 000 байта на писта и прави оборот за 10 милисекунди можем да четем по 25 мегабайта на секунда. Ако един блок е 16 384 байта можем да го прехвърлим за 2/3 милисекунди. дисковите контролери – колкото повече поевтиняват компонентите толкова повече дисковите контролери се превръщат в малки компютри с процесор и памет, в паметта се пазят писти така по софтуерен път се увеличава бързодействието.
   

При модификация не става пряко върху диска първо да прочетем блока, да направим измененията в ОП и да запишем блока върху диска. Може след записът да направим проверка . време – времето за четене + времето за изменение в ОП + време за запис [+ време за верификация]. Доколкото контролера е управляем могат да се включат и изключат тези режими за верификация(той е скъп); четем-изменяме-пишем. Дискът обаче се върти, така че след изменението – отново изчакване за завъртане и дори наместване на цилиндъра.

Алгоритмите обикновено предполагат че данните са в ОП и достъпа до тях – за едно и също време. Този модел на представяне на алгоритъма – RAM-модел при СУБД се предполага, че данните не са в ОП а във вторичната или третичната най-добрите алгоритми за обработка на големи обеми от данни са различни от най-добрите алгоритми за същата задача, когато данните са в ОП. В СУБД основно разглеждаме обмена между вторичната и външната памет. Един алгоритъм е по-добър, когато осъществява по-малко достъпи до диска (този принцип се прилага между всички нива на йерархията на паметта – за оценка на алгоритъм се броят достъпите до по-високото ниво на йерархията). Ако знаем размера на кеша и проектирания алгоритъм той ще е толкова по-добър, колкото по.малко пъти се прехвърлят данни между ОП и кеш, това обаче е много фино.

Прост компютър, върху който е инсталирана СУБД, група потребители, обслужвани от СУБД - то. Достъпът по различни начини – заявки и изменение на базата. Един диск и един контролер, един процесор. Базата е достатъчно голяма, за да не се побира в ОП. В ОП се буферират важни части от базата, но при всички положения при първо обръщение към това парче то трябва да бъде прочетено и заредено. Веки потребител пуска входно-изходни заявки, контролера – опашка от заявки, като обслужват например FCFS. Всяка заявка направена от потребителя се счита за случайна – когато дойде да бъде изпълнена, главата ще е на случайно място и това е в сила дори ако потребителя чете данни само от една релация и те се съхраняват върху един цилиндър.

Ако един блок трябва да се прехвърли между вторичната и ОП то времето за четене е много по-голямо от това за обработка в ОП, така че броя достъпи до диска – най-точната апроксимация на времето за даден алгоритъм и трябва да бъде минимално.

стъпкаСписък 1Списък 2ИзходНачало1,3,4,92,5,7,813,4,92,5,7,8123,4,95,7,81,234,95,7,81,2,3495,7,81,2,3,4597,81,2,3,4,56981,2,3,4,5,779-1,2,3,4,5,7,88--1,2,3,4,5,7,8,9

Двуфазна многократна сортировка и сливане:

1. 
   извършва се сортировка на данните в ОП при тази фаза релацията се изчита на части в ОП всяка част се сортира и се записва върху диска, така че от една релация получаваме сортирани списъци върху диска.
   
2. 
   сливане на сортираните подсписъци в един сортиран списък.
   

Следния процес се повтаря колкото е необходимо:

1. 
   ОП се запълва с блокове от оригиналната релация, която ще сортираме, след това се сортират записите в основната памет и така сортираните записи се записват в нови блокове във вторичната памет. Така всеки запис ще бъде прочетен по един път и ще бъде записан един във вторичната памет в блоковете, заделени за съответния подсписък.
   

Ако размера на блока е В байта, а в основната памет имаме М байта за буфериране, а записите са по R байта. Броя на блоковете М/В един за извеждане останалите – броя подсписъци, които ще бъдат сливани. Т.е. при първата фаза могат да бъдат създадени М/В-1 списъка т.е. имаме М пъти зареждане на блокове в ОП със записи за сортировка. Всеки път когато зареждаме ОП сортираме М/R записи. Всеки запис, който може да сортираме е M/Rx(M/B-1)=M /RB.

Двуфазната сортировка е малко вероятно да превиши 0,67 терабайта и затова в СУБД се използва тя.

Ускоряване на достъпа до вторичната памет

Когато системата изпълнява голям брой заявки едновременно изборът на блокове е случаен. Ако сортировката е на голяма релация голяма част от времето се заема от релацията и може да се възползваме от начина, по който са разположени дисковете и да оптимизираме достъпа до вторичната памет. Когато 1 система е натоварена с голям брой несвързани заявки можем да се стремим да увеличим пропускателната способност на системата (да отложим някои заявки) или да бързаме да изпълним всички заявки на опашката. Прилагат се няколко стратегии:

1. 
   Поставяме блоковете, върху които едновременно се прави достъп на един цилиндър – избягваме търсенето и латентността от въртенето. Времето за търсене на цилиндър е половината от времето за достъп до блок. Има приложения, в които е смислено така да се съхраняват данните, че лесно да се прави достъп до тях – релациите да се разполагат на отделни цилиндри. Ако един цилиндър не стига за дадена релация се използват два съседни. Времето за прочитане на данните от една писта или цилиндър – игнорираме всичко, освен първото време за търсене (до придвижването до цилиндъра) и първата ротационна латентност (изчакване на първият блок да се придвижи под главата). Така можем да достигнем максимална скорост за прехвърляне на данни от диска към паметта и обратно.
   
2. 
   Разделяме данните върху няколко малки диска – разполагаме с повече блокови глави и това увеличава броя блокове, които можем да обработим за единица време. При използването на няколко диска игнорираме времето на работа на дисковият контролер, шина, ОП. Ако дисковете са 4 по-малки данните върху съседните цилиндри разпределяме върху тях. В първата фаза при зареждане в ОП всеки диск ползва по ј от буферите – времето за търсене е пренебрежимо малко, както и времето за латентност. Прочитането става за по-малко време. В първа фаза се разпределя всеки сортиран подсписък върху четирите диска. Записът също се извършва едновременно, т.е. е 4 пъти по-бърз. Във втора фаза отново няма преимущество. Може да се програмира така, че сравненията да продължат веднага след като е прочетен първият елемент, но не е препоръчително. Ако се прилага този подход има възможност във втора фаза да се съкрати времето за запис. Може да се ускори записът във втора фаза ако големият буфер се раздели на 4 и когато се пълни един от тях другите три се използват за записване. В някои случаи втора фаза се ускорява 2-3 пъти.
   
3. 
   Създаване на огледани дискове – на данните се правят копия върху два или повече диска – пак разполагаме с няколко блокови глави и при провал в някои от дисковете имаме информацията запазена. Огледалните дискове могат да се използват за ускоряване на достъпа до данните. Във втора фаза можем да уредим зареждането на 4 блока от 4 различни сортирани списъка, чиито блокове са празни. Не може да избираме от кои 4 списъка ще се четат нови блокове. Ако разполагаме с 4 копия на големия диск можем да гарантираме, че системата ще чете 4 блока едновременно. Винаги може да се определи от кой диск ще се проведе следващото четене. Не ускорява записа, но не го и намаля, ако го сравняваме със използването на един диск. Това е така, защото когато трябва да запишем блок ние го пишем на всички дискове, които имат копие. Тъй като писането може да е паралелно, времето за писане остава същото като това за писане на един диск, а има малка възможност за различа при времето за писане за различните огледални дискове, защото не можем да разчитаме на тях да се въртят абсолютно синхронно. Но тези разлики в ротационната латентност са приблизителни и ако използваме първата стратегия могат да се игнорират.
   
4. 
   Прилагане на алгоритъм за режимно използване на диска – може да се реализира в ОС, СУБД, контролера на диска. Определя реда, по който се изпълняват заявките, за да могат няколко блока да бъдат едновременно четени или писани. Този алгоритъм не е полезен, когато системата трябва да чете или пише блокове в определен ред. Но когато системата поддържа много малки процеси, всеки от които има достъп до няколко блока, може да се увеличи бързодействието като се избере кой процес да е първи. Алгоритъм на асансьора – за ускоряване на достъпа до диска. Когато главите преминават над цилиндър спират ако има една или повече заявки за блокове на този цилиндър. Тези блокове се четат или пишат , както е изискано, след това главите продължават в същата посока до следващия цилиндър, когато главите стигнат позиция, където няма повече заявки напред те обръщат посоката. В контролера са се натрупали заявки и той определя режима на изпълнението им, преподрежда ги. Не е полезно когато системата прави сортировка (пише блокове), защото има система по какъв начин да се подредени. Алгоритъм на асансьора – ефекта е, че пропускателната способност на диска се увеличава. Времето за търсене се минимизира, а времето за латентност остава същото. Бързодействието на изпълнение на заявките пада.
   

Време_за_търсене=(1+брой_писти_за_обхождане)/1000. Ако средния брой на заявките се увеличава се увеличава и пропускателната способност. Ако броя на заявките е по-голям от броя на цилиндрите за 1ms се изпълняват две заявки. Проблем –броя заявки върху един диск е много голям увеличава се пропускателната способност, но и времето за изпълняване на заявката. Използването на алгоритъма за голям брой заявки не е разумно.

1. 
   Предварително зареждане на блокове в ОП като се прогнозира тяхната по-късна употреба. Поне за известно време системата е заета с определена задача (например сортировка). Бързодействието на системата и използването на вторичната памет може да се определи по два начина: а)Какво ще се случи ако има голям брой процеси, поддържани едновременно от компютърната система б)Ако има фиксиран бюджет на компютърната система или върху нея се изпълнява смес от различни заявки. Предварително зареждане (двойно буфериране) – по-добре режимираме диска и ако ползваме алгоритъма на асансьора може да намалим времето за достъп до блоковете.
   

1. 
   когато блоковете се четат и пишат в предсказуем във времето ред от един процес. Отлична за приложения, при които има предсказуем достъп до диска.
   
2. 
   когато имаме много процеси, които са кратки и генерират случаен достъп до диска. Имаме множество дискове – и в двата случая ще се увеличи бързодействието до 2-3 пъти. За съжаление четене и писане върху един диск не могат да се извършат едновременно. Цената на няколко малки диска е по-голяма от един голям със същия капацитет.
   

При алгоритъма на асансьора се намаля средното време за четене и писане на блокове, най-ефективен е когато има много заявки, но тези процеси, които чакат четенето и писането твърде много чакат.