Вордовские лекции (1121814), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Личный опыт лектора показывает, что вот на этом уровне – единственно возможный способ поиска тупиков – поиск циклов, то на системном уровне можно обойтись таймаутами.

Тупик возникает как правило, если выполняется операция чтения и обновление. Подходы:

1. Блокировать корень до конца микрооперации. Дерево ильно ветвистое, и вероятность того, что две операции пойдут по одному пути, маленькая, а мы накладываем ограничения,Ю которые позволяют работать с ними последовательно. Это плохой способ. А хорошего сопособа нет.

2. Блокировать поддерево. Как узнать уровень, с какого блокировать? Ничего путного от статей, посвящённых подобной блакировке, не было. Лектор сотоварищи придумали собственный метод, котороым он гордистся.ю До начала блокировок выполняется игра:напирмер, длч Вставки ключ, tid Идём оп дереву, пока не дойдём до нужного листа. По этому пути все блоки сохраняются в буфера. Начинаем играть – проигрываем оп вставки без работы с внеш память. Потом блокируем нужный блок в режиме опбновления, и проигрываем операцию ещё раз. Если выше не поднимается, то проигрываем начисто. Если же поднимается, то все блокировки снимаем и начинаем сначала. Если пут поменялся, то начимнаем совсем сначала.

Другой метод организации индексов:

Про б-деревья лектор будет спрашивать всё, даже то, что не рассказывал.

Хеширование

В понедельник лектор расскзаыыал хеширование физтеху и понял, что 10-15 минут достаточно.

Есть большой блок вснеш памяти, кот орый используется для размещ нек массика. Элементы – ключ/запись. Есть спецфункция, которая выбир для орг таблиц – хэш-функция. Она вырабатывает ключ, разрядность которого меньше, чем адреса. По-русски это называют хэширование рандомизацией или перемешивание. Нужно уметь выбирать такую хэшфункцию, которая равномерно разбрасыввает ключи по пространству. С тем, чтобы вероятность попадания нового ключа на занятое место мнимальна. В результате поняли, что лучше всего работает деление на число и взятие остатка. Для маленьких таблиц - 7, потом 13, потом 43. На ВМК не очень хорошо дело с математикой, но лектор надеется, что нам успели внушить, что простые числа хорошие.

Известно, это некоторый факт, который никто никогда не доказывал, но все считают, что он верный, что хэшьаблицы хорошо работают при заполненности менее 70-75 процентов. Подход:

1. Если возникает первая коллизия, и если хэш-функция, берётся новое простое число, перераскидываются все ключи – называется перестройка хэш-таблиц.

2. Создание списков в каждой ячейке таблицы. Этот подход ломает идею хеширования. За что хеширование любят: если всё хорошо, то мы попадаем в нужный элемент за 2 операции (вычисление, переход). Как только возн области переполнения, все вырождается. Ещё неприятный момент – таблица статическая, а кускочи возникают в динамике.

3. Как только нарываемся на коллизию, начинаем искать вниз первый свободный элемент, и если свободен, то пишем туда ключ. При поиске ещё страньше. Пока нет коллизий, поиск работает замечательно. Но, как только возникают коллизии, начинается хождение по кругу.

Когда идёт работа, таблица перестаёт быть хорошо перемешанной. В этом случае применяем вторичное хэширование. Лектор не знакти, есть ли какая-нибудь теория, для вторичного хэширования – тот адрес, вниз от которого нужно искать свободное место. Берётся ключ и делится на квадрат. Если применяыть такой подход, то штучки, связанные с перепонением, достаточно хорошо раскидываются по всей таблице.

//педедыв

Ричард Столлман определил облик 20 века

У Столлмена дефект – слишком коммунист.

Лектору не нравится, что он на них слишком влияет в этом отношении.

С чего он начал в 85 году. Он очень обидился на мир, потому что должен подписывать NDA. У него давно есть программочка, которая по заданному набору ключей умеет подсчитать совершенную хэш-функцию.

Б-деревья хорошая структура индексации, но нужно пройти от корня до личста, а это 2-3 обмена с внеш памятью. А тут за один обмен.

Один из прогрессивных методов выполн методов соединения – hashjoin.

Широко известный в узких кругах человек – vitold li(t)vwin

С сасмого начала происходит работа с 2^n блоками. И в них помещаются ключи со ссылками на строки. Поддерживается такая шкала: 2^n бит. Как только возникает коллизия, Заводится его двойник, и хэшфункция тоже становится 2^(n+1). Как происходит работа: берётся поиск, делается поиск по ключ, делим его на 2^n, а какого размера у нас шкала. Если шкала 2 в степени (н+1), и смотрим, есть ли у него напарник, и применяем новую хэшфункцию, если нет – тсарую.

У нас она настолько популярна, что у лектора есть специальная папочка с его статьями.

Человек интересен. Живёт в Европе. Жил в Англии, потом обиделся на англичан, перебрался во Францию .В опследник годы занимается вебом.

Ещё один человек – альтернативный канадец, у него идеи, как сблизить б-деревья и хэш-таблицы. Хранить небольшое б=дерево, которое заменяет хэшфункцию. Но засчёт б-деревянных особенностей позволяет сделать линейнвй порядок. Связывают ключи, для которых одна ссылк на блок. Для лектора единственный пример метода б-деревьев в основной памяти.

все. про индексы закончил.

походите на курс Фомичёва про индексы.

Индексы хороши, когда их можно объяснять жестами.

Можно было бы двигаться в соотв с ист правдой и расскзать, как относились к транзакции 31 год назад. Лектор начнёт с тогоЮ что сегодня считают транзакцией, а потом из современной картинки лектр будет рассказывать, каак это делалось в систем р.

ACID-транзакции

Atomicity – атомарность – свойство транзакции «всё или ничего». Транзакция – последовательность операций. Либо результат транзакции успешен и её результат остаётся в БД, либо после неё не остаётся ничего. Атмарность – важное свойство. В ряде случаев, хотя с этим не согласен Дейта, если смотреть на СКЛ, в ряде случаев с помощью отлельной операции изменения БД перевести из одного согласованного состояния в другое, использовав одну операцию .Пример: те же самые таблицы отделов, в таблице отделов хранится количество служащих, и хоть ты тресни, надо выполнить две операции, причё если выполнится только одна операция, то БД будет неправильная, поэтому эти операции будут выполняться в транзакции

Consitensy – целостность – значит, мы с васми уже говорили, что целостное состояние бд – главная особенность набора файлов, который считается бд. Для того, чтобы хранить сложную инфцию, файлы должны быть связаны, и что такое связь, не всегда просто определть. На саомм деле, ни одна БД не знает, когда она целостна, а когда нет. Для того, чтобы СУБД могла поддерживать целостность бд, надо сказать, при каких условиях пользователи согластны считать БД целостной. Значитт, эээ, уоль сокоро мы говрим, что, эээ, нельзя гарантировать, вообще говоря, что оно сумеет перевести БД из одного целост состояния, в другое, поэтому свойство транзакции – любая транзакция должна начинаться, когда БД находится в логичесик целостном состоянии (это состояние, коиорое удовл некоему логическому условию, которое на неё навешано),и любая транзакция обязана оставить после себя БД в целостном состоянии. Любая транзакция может оканчиваться commit (зафиксировать – этот пользователь или приложение просят проверить СУБД всё ли в порядке, и сделать так, чтобы эти изменения были видны всем остальным. Пока они не проверены,Ю они не должны влиять на работу пользователей.) или rollback (откатить – по каким-то причинам поняли, что всё, что было сделано в пределах транзакции, не верно, и нужно из бд всё это убрать. В этом случае транзакция, rollback – возврат в исходную точку, commit – проверка всех изменений и произведение некрых действий, который делают изменинея видимыми. Если коммит обламывается с проверкой, то делается rollback, и при таком подходе БД останется в целостном состоянии). Что такое проверка целостности – не надо думать, что если администратор напихал 33000 проверки целостности. На самом деле, работает компилятор, он знает смысл операций, но знает, над какими объектами БД будут они выполняться, посему знает, какие ограничения целостности могут быть нарушены, и именно они проверяются в конце транзакции. Понитие транзакции - идеальное для изоляции пользователей.

1. Isolation Изоляция – обеспечение такого режима работы, когда он не чувствует присутствия других пользователей. Когда лектор быдет это рассказывать подробно, то мы увидим, что это туфта, и пользователь во время работы видит чудеса, которые можно списать на Господа Бога, но это не Он, это Иванов, это Иванов через субд.

2. Durability – долговечность – после коммита что бы не произошло на этом свете: злостный партнё р поделил его на ноль, сумасшедший взорвал машину, весь мир может погибнуть, а транзакция может остаться целой. База данных остаётся вечной и бесконечной. В принципе, результат транзакции должен пережить Апокалипсис.

Младшие поколения начинают называть consistency консистентностью, лектор это не любит.

БД

Будет ещё 4 лекции, закончится всё в след пятницу.

Досрочный экзамен.

Лектор хочет провести один или два экзамена до зачётной сессии. Формально он мог бы ограничить количество народа теми, кого переписали. Есди нахалов придёт слишком много, то их отсеят.

В след четверг лектор даст вопросы, но досрок – экзамен-экспромт, и никакой подготовки нет. Экзамен стремительный, лектор относится крайне разко к ответам, которые его не устраивают. Как правило, когда там ставятся тройки, в том случае, если удасться доказать, что нужно человек получить тройку досрочно. Первый досрок – 19 числа. Возможно, ещё 20. Можно провести ещё экзамен после зачётной, до НГ, если наберётся достаточно народа. Третий курс разросся до безобразия. Процент успеха – 25 процентов.

Был случай, когда человек приходил к лектору 4 раза и получил в итоге пятёрку, с каждым разом чуть-чуть продвигался. Экзамен будет принимать не только лектор, у каждого своя манера приёма экзамена.

Траннзакции

begin trans

...

commit / rollback

Понятно, что если внутри транзакции возникает непредвиденное, то СУБД получает соотв образом информацию (в Систем Р, которая была менйфреймовской, всё запускалось в пределах сервера, и отлавливалось легко) м неявно считает, что в этой точке выполняется rollback. Это действительно атомарная последовательность действий, потому что либо она успешно завершается, либо её следов вообще не остаётся. свойство атомарности соблюдается за счёт скобок.

В Систем Р определялись два огрничения целостности – immediate, которые выполняются сразу после каждой операции, например, то, что зарплата должна повышаться не более чем на 20 процентов. Если не проходит, то транзакции не обрываются, но операция отвергается. А бывают ограничения, которые нельзя проверить сразу, и их отодвигают в конец транзакции.

Идея Дей та и Дарвина – идея здравая и полезная. Лбюбая операция изменения БД – операция присваивания. Нвапример, если добавляете строку в таблицу отношений, то в действиетльности это присваивание переменной отношение, которая соотв этой таблице, нового значения, в которое входит эта строка. То же про удаление. Главная идея Дейта и Дарвина – разрешается делать множественные присваивания. Это требуется,к когда нанимается на работу новый служащий, и требуется обновление двух переменных отношения. При старорежимном подходе это отложенное огранич целостности по Д. и Д. это обновить вот это, обновить вот это, проверить, и если плохо, то изменние отвергается, трпанзакция проболжается. Фактически, это маленькая транзакция внутри транзакции.

Гречушкин выпендривается – спрашивает про реализацию множественного присваивания, например, для этого нужно применять теневые операции, а лектор ему говорит, что это прекрасно делается с помощью журнала.

Из-за чего возн проблемы с изоляцией транзакций? Когда выполн смесь транзакций, concurrently, которые конкурируют за нечто. Concurrency без вреда – не concurrency. Очень часто это переводят как параллельно, но они не обязательно реально параллельны. При этом одна транзакции начинает чувствовать другую.

Могут возникнуть конфликты трёх сортов:

1. write-write – если допустить наличие конфликтов, то наблюдаются феномены 1. феномен потерянных изменнией. Решение – монопольные (exclusive) блокировки. /* ен называть эксклюзивными */

2. read-write (dirty read – грязное чткние). т1.писать, т2.читать, т1.ролбек, т2.коммит

Решение: вводится ещё один механизм блокировок – совместные блокировки (s., shared). Читать можно вместе сколько угодно.

Таблица совместимости:

След таблицу совместимости лектор рисовать не будет.

s – Кратковрем блокировка до конца чтения.

Эффект фантомов

Сценарий очень похож. Вот транзакция т1 по некоторому условию, например, столобец а больше 5 меньше 25, а транзакция т2 в момент т2 записываем строки, у которых значение атрибута a равно 20. Понятно, что конфликта read-write нет, но при втором чтении возникнет кортеж-фантом. Как мы видим, в действительности, мы сделали всё, что было можно, потому что работают длинные блокировки по чтению-записи, и они не спасают. Есть один способ, очень грубый, и которым пользуются в непродуманных системах. Когда в стандарте СКЛ есть три режима выполн транзакции – грязное чтение, неповт чтение, допуск наличие фантомов, и режим, при котором транзакции работают абсолютно изолированно. В непродуманых системах, если выборка не по первичному ключу, тоблокируется таблица целиком до конца транзакции. Конечно, это достаточно грубый способ, рпотому что читается 10 строк из 5 миллионов, а мы блокируем 5 миллионов, чтобы не возникла 11. В Систем Р поняли, что природа фантома заключ в следующем. Блокируем мы физ объект, а условие логическое. Противоречие в том, что блок физ объекты, а выборка по логич усл, И рпидумали механизм предикатных синхронизированных блокировок. То есть я гворю системе, что хочу заблокировать все строки, которые удовлетворяют этому условию. И тогда они будут блокировать не свю таблицу, которую лектор стёр и вот от неё следы остались, а: если у нас блокировка по чтению по такому условию S(5<a<25), и X(26<a<27), то всё нормально, а если X(6<a<18), то происходит пересечение, и блокировка не выполнится.

Лектор интересуетсчя, понятно ли нам, что это для разных транзакций, в пределах транзакций всё пройдёт.

В данном случае это проблему решает. Первая транзакция делает S()5<a<25, вторая X(a=20) и затормозится, пока первая не выполнится. Но это толдько в теории, и они долго изголялись, но таки сделали, тобы у них не было фантомов, но не так красиво. Дело в том, что они опирались на SQL, у которого условия могут быть очень сложные, и не смогли придумать способ проверки, когда эти условия совместимы. На самом деле, в течение долгого времени эта идея висела, и лучше всего эту идею реализовали мы в своём СКЛ-сервере. У нас в группе работали очень опытные программисты, и ни один не допёр. И был один неопытный программист и хороший алгебраист, и он до идеи допёр.

Характеристики

Список файлов лекций