Многие базы данных хранят географическую информацию, такую как расположение городов или многоугольников, описывающих государственные границы. Транспортным приложениям, возможно, потребуется схема соединений автотрасс, железных дорог и станций. Бюро переписи населения нужно хранить в картографической форме тысячи переписных районов вместе с данными переписи по каждому из них.
Что интересно в таких базах данных, так это выполнение запросов в отношении пространственной информации. Например, если вы руководите службой скорой помощи, то вам нужна база данных с расположением больниц в районе. Ваша СУБД должна уметь быстро выдавать ближайшую больницу относительно любого заданного местоположения.
Такие приложения ознаменовали разработку специальных СУБД, которые называются географическими информационными системами (ГИС). Они содержат поля, специально предназначенные для географических данных: PointField (точка), LineField (прямая), PolygonField (многоугольник) и т. д. И они способны выполнять пространственные запросы в этих полях. По ГИС рек и городов вы можете непосредственно делать запросы такого рода: «Города в пределах 10 миль от реки Миссисипи, упорядоченные по численности населения». ГИС использует пространственные индексы, и поэтому поисковые запросы по пространственной близости осуществляются очень эффективно.
Рис. 6.12. Медианный возраст в США[66]
Эти системы даже позволяют определять пространственные ограничения. Например, в таблице, хранящей информацию по земельным участкам, можно установить ограничение, что никакие два участка не должны перекрываться. Это оградит агентства по земельному кадастру от колоссального количества проблем.
Многие общецелевые СУБД предоставляют ГИС-расширения. Всегда, когда вам приходится иметь дело с географическими данными, убедитесь, что вы используете ядро базы данных с поддержкой ГИС, и применяйте ее функционал для создания более умных запросов. ГИС-приложения часто используются в ежедневной жизни, например, в GPS-навигаторах вроде Google Maps или Waze.
6.5. Форматы сериализации
Как хранить данные за пределами БД в формате, совместимом с разными системами? Например, мы можем захотеть продублировать данные либо экспортировать их в другую систему. С этой целью данные должны пройти процесс сериализации, в ходе которого они будут преобразованы согласно формату кодирования. Получившийся файл прочитает любая система, поддерживающая этот формат. Давайте кратко пройдемся по нескольким форматам, которые широко используются для сериализации данных.
SQL — наиболее распространенный формат сериализации реляционных баз данных. Мы пишем серию команд SQL, которые воспроизводят базу данных и все ее детали. Большинство реляционных систем баз данных содержат команду DUMP для создания SQL-сериализированного дампа базы данных. Они также содержат команду RESTORE для загрузки такого файла дампа назад в СУБД.
XML — это еще один способ представить структурированные данные, но он не зависит от реляционной модели или реализации СУБД. Формат XML создавался для совместимости с разнообразными вычислительными системами и описания структуры и сложности данных. Некоторые говорят, что XML был разработан учеными, не понимавшими, что их творение не очень практично.
JSON — это формат сериализации, к которому все больше сходятся разработчики во всем мире. Он может представлять реляционные и нереляционные данные интуитивно понятным для программистов образом. Существует много расширений JSON: BSON (двоичный JSON) дает максимальную эффективность обработки данных; JSON-LD привносит в JSON мощь XML-структуры.
CSV, или файл с разделением значений запятыми, — это, возможно, самый простой формат обмена данными. Данные здесь хранятся в виде текста, по одной записи на строку. Поля в записи разделяются запятой или каким-либо другим символом, не встречающимся в данных. Формат CSV полезен для создания дампов простых БД, но он не годится для представления сложных данных.
Подведем итоги
В этой главе мы узнали, что структурирование информации в базе данных имеет чрезвычайно важное значение для того, чтобы сделать данные полезными. Мы изучили различные способы того, как это делается. Мы увидели, как реляционная модель разделяет данные на таблицы и как они связываются вместе при помощи отношений.
Большинство программистов учатся работать только с реляционной моделью, но мы вышли за эти рамки. Мы увидели альтернативные, нереляционные способы структурирования данных. Мы обсудили проблемы непротиворечивости данных и как их смягчить при помощи транзакций. Мы рассмотрели способы масштабирования СУБД для обработки интенсивных нагрузок при помощи распределенной базы данных. Мы также узнали о ГИС и о функционале, который они предлагают для работы с географическими данными. А еще мы узнали распространенные способы обмена данными между различными приложениями.
И, наконец (если только вы не экспериментируете), остановите свой выбор на широко используемой СУБД. Она производительнее и содержит меньше ошибок. Идеальной системы управления базами данных не существует. Ни одна СУБД не подходит для любых, без исключения, сценариев. Прочитав эту главу, вы теперь лучше разбираетесь в различных типах СУБД и их особенностях, и потому сможете сделать обоснованный выбор, какую из них использовать.
Полезные материалы
• Концепции систем баз данных (Database System Concepts, Silberschatz, см. https://code.energy/silber).
• Садаладж П. Дж., Фаулер М. NoSQL. Новая методология разработки нереляционных баз данных.
• Принципы систем распределенных баз данных (Principles of Distributed Database Systems, Özsu, см. https://code.energy/ozsu)
Глава 7. Компьютеры
Любая достаточно развитая технология неотличима от магии.
Бесчисленные и разнообразные машины были изобретены для решения задач. Существует много типов компьютеров: от встроенных в роботов, которые бродят по Марсу, до тех, что управляют навигационными системами атомных подводных лодок. Почти все компьютеры, включая наши ноутбуки и телефоны, имеют тот же самый принцип работы, что и первая вычислительная машина, изобретенная фон Нейманом в 1945 году. А вы знаете, как устроены компьютеры? В этой главе вы научитесь:
понимать основы компьютерной архитектуры;
выбирать компилятор для трансляции вашего исходного кода на язык компьютеров;
разменивать память на быстродействие при помощи иерархии памяти.
В конце концов, программирование должно выглядеть как волшебство только для непрограммистов — но не для нас с вами.
7.1. Архитектура
Компьютер — машина, которая подчиняется командам, управляющим данными. Он имеет два главных компонента: процессор и память. Память, она же ОЗУ[67], — это то место, где мы пишем команды. Она также хранит данные, которыми компьютер оперирует. Процессор, или ЦП[68], получает команды и данные из памяти и выполняет соответствующие вычисления. Давайте разберемся, как работают эти два компонента.
Память
Память поделена на множество ячеек. Каждая хранит крошечный объем данных и имеет числовой адрес. Чтение или запись данных в памяти выполняется посредством операций, которые воздействуют на одну ячейку за раз. Чтобы прочитать ячейку памяти или произвести запись в нее, мы должны передать ее числовой адрес (рис. 7.1).
Рис. 7.1. Сообщение для ОЗУ выполнить операцию в ячейке № 210 (11010010)
Поскольку память является электрической схемой, мы передаем адреса ячеек по проводам в виде двоичных чисел[69]. Каждый провод передает двоичную цифру. Высокое напряжение соответствует сигналу «единица», низкое — сигналу «ноль».
Рис. 7.2. Память может работать в режиме чтения или записи
Память способна выполнить с адресом ячейки две операции: получить хранящееся в ней значение или записать новое. Память имеет специальный входной контакт для установки ее рабочего режима (рис. 7.2).
Каждая ячейка памяти хранит 8-разрядное двоичное число, которое называется байтом. В режиме чтения память получает хранящийся в ячейке байт и выводит его по восьми проводам, которые передают данные (рис. 7.3).
Когда память находится в режиме записи, она получает байт по этим проводам и записывает его в указанную ячейку (рис. 7.4).
Группа проводов, используемых для передачи одинаковых данных, называется шиной. Восемь проводов для передачи адресов формируют адресную шину. Другие восемь, используемых для передачи информации в ячейки памяти и обратно, формируют шину данных. Адресная шина является однонаправленной (используется только для получения данных), а шина данных — двунаправленной (используется для отправки и для получения данных).
Рис. 7.3. Чтение числа 32 из ячейки с адресом 211
Рис. 7.4. Запись числа 33 в ячейку с адресом 212
В любом компьютере ЦП и ОЗУ постоянно обмениваются данными: процессор выбирает команды и данные из памяти и иногда сохраняет туда данные для вывода и промежуточные результаты вычислений (рис. 7.5).
Рис. 7.5. ЦП подключен проводами к ОЗУ
Процессор
Центральный процессор имеет несколько ячеек внутренней памяти, которые называются регистрами. Он может выполнять простые математические операции с числами, хранящимися в этих регистрах. Он также может перемещать данные между регистрами и ОЗУ. Вот примеры типичных операций, которые приходится исполнять центральному процессору:
• скопировать данные из ячейки памяти № 220 в регистр № 3;
• сложить число в регистре № 3 с числом в регистре № 1.
Набор всех операций, которые может выполнять ЦП, называется его набором команд. Каждой операции в наборе команд присвоено число. Машинный код по существу — последовательность чисел, представляющих операции центрального процессора. Они хранятся в виде чисел в ОЗУ. Мы сохраняем входные/выходные данные, промежуточные результаты и машинный код — все вперемешку — в ОЗУ[70].
Рис. 7.6 показывает, как некоторым процессорным командам ставятся в соответствие числа в том виде, в котором они приводятся в руководствах по ЦП. По мере совершенствования технологии производства процессоры стали поддерживать дополнительные операции. Набор команд современных ЦП огромен. Однако самые важные операции существовали уже несколько десятилетий назад.
Рис. 7.6. Часть технического описания Intel 4004, показывающая, как операциям ставятся в соответствие числа. Это был первый в мире ЦП, выпущенный в 1971 году
ЦП работает в бесконечном цикле, постоянно выбирая и исполняя команды из памяти. В ядре цикла находится регистр PC, или счетчик команд[71]. Это специальный регистр, который хранит адрес памяти следующей исполняемой команды. Вот что делает ЦП:
1) выбирает команду в адресе памяти, заданном регистром PC;
2) увеличивает PC на 1;
3) выполняет команду;
4) возвращается к шагу 1.
Когда ЦП включается, PC присваивается значение по умолчанию, то есть адрес первой команды, выполняемой машиной. Это обычно неизменяемая встроенная программа, ответственная за загрузку основных функций компьютера[72].
После включения ЦП начинает выполнять этот бесконечный цикл выборки и исполнения, пока вы не выключите компьютер. Однако если бы ЦП мог выполнять только упорядоченный, последовательный список операций, то компьютер был бы не более чем продвинутым калькулятором. ЦП удивителен, потому что ему можно поручить записать новое значение в регистр PC, заставив процесс исполнения команд выполнить переход — «перепрыгнуть» куда-то в другое место в памяти. Такое ветвление может быть условным выражением. Например, команда ЦП может сообщить: «Записать в PC адрес № 200, если регистр № 1 хранит ноль». Это позволяет компьютерам выполнять операторы, подобные следующему:
if x = 0····compute_this()····# вычислить этоelse····compute_that()····# вычислить тоВот и все, что вам надо знать. Открываете ли вы сайт, играете ли в компьютерную игру или редактируете электронную таблицу, вычисления всегда одинаковы: это серия простых операций, которые могут лишь суммировать, сравнивать или перемещать данные в памяти.
При помощи множества этих простых операций можно выражать запутанные процедуры. Например, код классической игры Space Invaders (рис. 7.7) включает порядка 3000 машинных команд.
Рис. 7.7. Игру Space Invaders, выпущенную в 1978 году, многие называют самой влиятельной за всю историю
Тактовая частота ЦП. В 1980-х годах чрезвычайно популярной стала игра Space Invaders. Люди играли в нее на игровых автоматах, оборудованных процессорами с тактовой частотой 2 МГц. Этот показатель — число базовых операций, которые процессор выполняет в секунду. Процессор с тактовой частотой 2 МГц выполняет примерно 2 млн базовых операций в секунду. Для выполнения машинной команды требуется от пяти до десяти базовых операций. Следовательно, винтажные игровые автоматы выполняли сотни тысяч машинных команд каждую секунду.
В условиях современного технологического прогресса обычные настольные компьютеры и смартфоны обычно имеют процессоры с тактовой частотой 2 ГГц. Они способны выполнять сотни миллионов машинных команд каждую секунду. А с недавних пор массовое применение получили многоядерные ЦП. Четырехъядерный процессор с тактовой частотой 2 ГГц может выполнять почти миллиард машинных команд в секунду. И, похоже, в перспективе у наших процессоров будет все больше ядер[73].
Архитектуры ЦП. Вы когда-нибудь задавались вопросом, почему нельзя вставить компакт-диск для Sony PlayStation в настольный компьютер и начать играть? Или почему приложения для iPhone не запускаются на Mac? Причина проста: разные архитектуры ЦП.
В наше время архитектура x86 является довольно стандартной, и потому одинаковый код может выполняться на большинстве персональных компьютеров. Однако сотовые телефоны, например, имеют процессоры с другой, более энергоэффективной архитектурой. Разные архитектуры означают разные наборы процессорных команд и, следовательно, разные способы их кодирования числами. Числа, которые транслируются как команды для ЦП вашего настольного компьютера, не являются допустимыми командами для ЦП в вашем сотовом телефоне, и наоборот.
32-разрядная архитектура против 64-разрядной. Первый ЦП под названием Intel 4004 был основан на 4-разрядной архитектуре. Это означает, что он мог оперировать двоичными числами (суммировать, сравнивать, перемещать их) до 4 разрядов в одной машинной команде. Шина данных и шина адресов на Intel 4004 состояли всего из четырех проводов каждая.
Вскоре после этого широкое распространение получили 8-разрядные ЦП. Они использовались в ранних персональных компьютерах, работавших под DOS[74]. Game Boy, популярный в 1980–1990-х годах переносной игровой компьютер, тоже имел 8-разрядный процессор. Одиночная команда в таких ЦП может оперировать 8-разрядными двоичными числами.
Быстрый технологический прогресс позволил занять доминирующее положение 16-разрядной, а затем — 32-разрядной архитектуре. Емкость регистров ЦП была увеличена до 32 разрядов. Для более емких регистров естественно потребовалось расширить шины данных и адресов. Адресная шина с 32 проводами позволяет адресовать 232 байт (4 Гб) памяти.
А затем наша жажда вычислительной мощи стала просто неудержимой. Компьютерные программы быстро усложнялись и использовали все больше памяти. 4Гб ОЗУ оказалось слишком мало. И обращение к памяти большего объема с числовыми адресами, которые укладываются в 32-разрядные регистры, превратилась в непростой процесс. Это ознаменовало появление доминирующей сегодня 64-разрядной архитектуры. 64-разрядные процессоры могут оперировать в одной команде чрезвычайно большими числами. При этом 64-разрядные регистры хранят адреса в огромном пространстве памяти — 264 байт, что составляет более 17 млрд гигабайт.
Прямой порядок байтов против обратного. Некоторые разработчики компьютеров посчитали, что в ОЗУ и ЦП целесообразно хранить числа слева направо (от младших разрядов к старшим), способом, известным как обратный порядок байтов. Другие предпочли записывать данные справа налево, способом, который называется прямым порядком байтов. Двоичная последовательность 1-0-0-0-0-0-1-1 может представлять разные числа в зависимости от порядка байтов:
• прямой порядок байтов: 27 + 21 + 20 = 131;
• обратный порядок байтов: 20 + 26 + 27 = 193.
Большинство ЦП сегодня имеют обратный порядок байтов, вместе с тем существует много компьютеров с прямым порядком. Если данные, сгенерированные ЦП с обратным порядком байтов, должны интерпретироваться процессором с прямым порядком, то необходимо принять меры, чтобы избежать несоответствия порядка байтов. Программисты, манипулирующие двоичными числами напрямую, в особенности во время разбора данных, выходящих из сетевых коммутаторов, должны об этом помнить. Несмотря на то что большинство компьютеров сегодня имеет обратный порядок байтов, интернет-трафик стандартизировал прямой порядок, потому что большинство ранних сетевых маршрутизаторов имели соответствующие ЦП. Данные с прямым порядком окажутся искажены, если их прочитать так, как если бы порядок в них был обратным, и наоборот.
Эмуляторы. Иногда бывает полезно на своем компьютере выполнить некоторый программный код, разработанный для другого ЦП. Это позволяет протестировать приложение для iPhone без iPhone или сыграть в вашу любимую старинную игру для Super Nintendo. Для этих задач существуют компоненты программного обеспечения, которые называются эмуляторами.
Эмулятор имитирует целевую машину: компьютер притворяется, что имеет тот же ЦП, ОЗУ и другие аппаратные средства. Команды декодируются программой эмулятора и выполняются в эмулированной машине. Как вы понимаете, очень сложно эмулировать одну машину внутри другой, когда у них разная архитектура. Но поскольку наши компьютеры намного быстрее старых, это стало возможным. Если вы раздобудете эмулятор Game Boy и позволите своему компьютеру создать виртуальную игровую приставку, то сможете играть в игры точно так же, как если бы вы играли на настоящем Game Boy.
7.2. Компиляторы