# Noob Coding
This is the repo of my notes. Now live on !
## Goal
* **Teach:** Try to develop a fast-learning process to help others grasp programming as quickly as possible. Focuses on speedrun so it does not guarantee insightful knowledge and is by no means comprehensive. However, some interesting stuff would be provided marked optional.
* **Teach Myself:** Should be able to review or preview many important topics in our industry.
* **Improve:** Since we are working in a fast-changing industry, the ability of fast-learning, or revolutionizing ourselves, is the most valuable asset in ourselves. Hopefully, a system of fast-learning could be established within this project.
## Method
Pick any topic you want. But I would recommend (with bias):
* For data scientists or anyone who wishes to learn AI (Trending): `Python` -> `Big Data` -> `Machine Learning`
* For those who want to build a website: `LNMP`
* For those who want to have some fun and see immediate feedback: `Frontend`
* For students or those who wish to find jobs: `Java` -> `LeetCode`
* For architects: `PowerPoint`
* For architects who want to write some real code besides PowerPoints: `C++`/`Java` -> `Search Engine`/`Distributed Systems`
## Basic
### Effectiveness
A few tips and tools to boost development effectiveness.
* Environment: Instead of working as root with too much privilege and too many folders, I prefer creating several linux users to seperately manage projects when I get my hands on a new machine.
```bash
sudo adduser ocean
sudo passwd ocean
# Then add line `ocean ALL=(ALL) ALL` in `/etc/sudoers` to enable `sudo` command
```
Next time log in as 'ocean' and start messing around.
* Command Line: The simplest way to improve command line usability is to modify the `~/.bashrc` file. Always add your working directory as aliases or use [bashmarks](https://github.com/huyng/bashmarks).
[.bashrc PS1 generator](http://bashrcgenerator.com) is a good site to create useful bash prompt style. My favourite:
```bash
function git-branch-name {
git symbolic-ref HEAD 2>/dev/null | cut -d"/" -f 3
}
function git-branch-prompt {
local branch=`git-branch-name`
if [ $branch ]; then printf " [%s]" $branch; fi
}
export PS1="\[\033[38;5;11m\]\u\[$(tput sgr0)\]\[\033[38;5;15m\]@\h:\[$(tput sgr0)\]\[\033[38;5;6m\]\w\[$(tput sgr0)\]\[\033[38;5;2m\]\$(git-branch-prompt)\[$(tput sgr0)\]\[\033[38;5;14m\]:\[$(tput sgr0)\]\[\033[38;5;15m\] \[$(tput sgr0)\]"
```
And some useful aliases:
```bash
alias psgrep='ps -eo pid,lstart,cmd | grep -v grep | grep --color'
alias grep='grep --color'
alias zhcn='export LANG=zh_CN.GBK;export LC_ALL=zh_CN.GBK;export LC_CTYPE=zh_CN.GBK'
alias enus='export LANG=en_US.UTF-8;export LC_ALL=en_US.UTF-8;export LC_CTYPE=en_US.UTF-8'
alias ..='cd ..'
alias ...='cd ..; cd ..'
alias ....='cd ..; cd ..; cd ..'
alias l.='ls -d .* --color=auto'
alias ll='ls -l --color=auto'
alias ls='ls --color=auto'
# This pull or push from master branch. You might need to change this.
alias pull='git pull origin master'
alias push='git push origin master'
alias cm='git commit -m '
```
* Vim: I use [The Ultimate vimrc](https://github.com/amix/vimrc) with some personal settings in `~/.vim_runtime/vimrcs/my_configs.vim`:
```bash
set gcr=a:blinkon0
set cursorline
set cuc
```
* Samba/FTP
* Useful Commands
```bash
df -h # Machine overall disk usage
du -sh * # File and folder size at current folder
```
### Version Control
* Install git: `sudo yum install git` If you are using CentOS, other checkout [git download page](https://git-scm.com/downloads)
* Setting up git:
```bash
# remove --global if you are configuring different user for different project.
git config --global user.name "Your Name"
git config --global user.email "you@example.com"
git config --list
```
* Github user: There are two kinds of url to clone your project: HTTPS and SSH. I recommend (the SSH way)\[] since it helps you type your Github password less in the future:
* Get your local SSH keys:
```bash
ls -al ~/.ssh # check if you already have one
# if not:
ssh-keygen -t rsa -b 4096 -C "your_github_email@example.com" # and hit enter all the way
```
* Add your private SSH key to the ssh-agent:
```bash
eval "$(ssh-agent -s)"
ssh-add ~/.ssh/id_rsa
```
* Add your public SSH key to your Github account:
```bash
cat ~/.ssh/id_rsa.pub
# Then copy the content
# and add to Github: Settings -> SSH and GPG keys -> click New SSH key -> put in the 'key' field->click Add SSH key
```
* For each project, use a `.gitignore` file to avoid submitting sensitive/large/unwanted files to git:
### Github
* How to insert equation on github:
* ,
*
### Java
Grasp Java Programming in a few days with [a simple online tutorial](https://beginnersbook.com/java-tutorial-for-beginners-with-examples/).
* Installation
Download JDK (I would recommend Java SE Development Kit 8) from the Oracle website.
* [Fundamentals](https://beginnersbook.com/2013/05/jvm/)
Java Development Kit > Java Runtime Environment > Java Virtual Machine
.java -> `$javac` -> .class -> `$java`
* [Data types](https://beginnersbook.com/2017/08/data-types-in-java/)
* `byte`, `short`, `int`, `long`: 1, 2, 4, 8 byte(s) length integer
* `float` and `double`: 4, 8 byte(s) length decimal(6/7 decimal digits, 15 decimal digits). Always suffix float value with the "f" else compiler will consider it as double
```java
double num1 = 22.4;
float num2 = 22.4f;
```
* `char`: 2 bytes length
* `boolean`: `true` and `false` with lowercase initials
* Non-primitive: Arrays and Strings
* "Unique" Grammer
* Enhanced for loop:
```java
String arr[]={"hi","hello","bye"};
for (String str : arr) {
System.out.println(str);
}
```
* do-while loop
* Object-Oriented Programming
* `this.`
* Inheritance: With `extends`. **Multiple inheritance is not allowed** in Java.
```java
class A extends B
{
}
```
* Polymorphism: Apart from **method overriding**, Java allowed **method overloading** within a class using different method signature (same method name, different parameters).
```java
class DisplayOverloading
{
public void disp(char c)
{
System.out.println(c);
}
public void disp(char c, int num)
{
System.out.println(c + " "+num);
}
}
```
* Abstract Method: Method with only signature no body (declared but not defined) or declared using the abstract keyword.
```java
abstract public void playInstrument();
```
* The class that inherits **must provide the implementation of all the abstract methods of parent class else declare the subclass as abstract**.
* These methods cannot be abstract: Constructors, Static methods, Private methods, Methods that are declared "final".
* Abstract Class: An abstract class outlines the methods but not necessarily implements all the methods.
```java
abstract class A{
abstract void myMethod();
void anotherMethod(){
//Does something
}
}
```
* **Cannot be instantiated.**
* A class derived from the abstract base class must implement those methods that are not implemented(means they are abstract) in the abstract class.
* Interface: With `interface`.
```java
Interface Interface1
{
String a;
void b();
}
//...
class ClassName extends Superclass implements Interface1, Interface2
```
* Can contain only constants and abstract methods.
* Cannot be instantiated.
* Can only be implemented by classes or extended by other interfaces.
* Java does not support Multiple Inheritance, however a class can implement more than one interfaces.
* All methods in an interface are implicitly public and abstract. Using the keyword abstract before each method is optional.
* An interface may contain final variables.
* When a class implements an interface it has to give the definition of all the abstract methods of interface, else it can be declared as abstract class.
* An interface reference can point to objects of its implementing classes.
* Access Specifiers: `public`/`private`/`protected`/Default(Package Level scope)
## C++
Also, start with any tutorial [like this one from cplusplus.com](http://www.cplusplus.com/doc/tutorial/). But you should realize that C++ IS HARD, because it's both old and powerful.
* Useful tips:
* string null terminated:
* Many ways to loop on every character of a string:
* Various way to init a 2D array:
* String to int: ,
* There is no empty char:
## Full Stack Dev
* Limit on url length (that affects the lengths of your GET uri and parameters unless you know what you are doing): unbounded. But being less than 2000 char would be most compatible. [source](https://stackoverflow.com/questions/417142/what-is-the-maximum-length-of-a-url-in-different-browsers).
# PHP (Laravel)
Hope this article saves you from all those irritating Laravel jargons when developing for the first time.
## Server Setup
## Install Laravel
### Environmental Variables
There is a `.env` (or `.env.example` if not using Composer to install Laravel) file at the project root. Configuration files like `config/app.php` would look for configuration value in this `.env` file.
To make your modifications work, use `php artisan config:cache` to recache it.
## Developing for Laravel
Like many other web frameworks, Laravel renders a page or API with four main modules: The first one (jargon: **route**) matches the url to a handler module. The handler module (jargon: **controller**) is where you write the core business logic for the page or API. It could call a data module (jargon: **model**) for data from databases or other storages. Finally it sends the processed data to the last module (jargon: **view**) which formats and generates a response. Of course there are many other modules, classes and libraries supporting these four. But we'll focus on these first.
### Develop Web Pages
* Show your page: First we define the url and the corresponding handler class/method at `routes/web.php`:
```php
Route::get('test', 'TestController@index');
// Laravel also supports adding a function instead of handling class
// This one returns a view module without any logic.
Route::get('/', function () {
return view('welcome');
});
```
Now for our `TestController`:
```bash
# Generate controller file using this command
php artisan make:controller TestController
vi app/Http/Controllers/TestController.php
```
```php
class TestController extends Controller
{
//Router TestController@index goes here
public function index()
{
// Simply return a view module
return view('test');
}
}
```
Finally we write our new view module `test`:
```bash
# Create test view file
vi resources/views/test.blade.php
```
And just put in any valid HTML code.
```php
Hello
Testing.
```
You can run the Laravel built-in server locally using command `php artisan serve`. If you are developing on your local machine with a browser, you can go to `http://127.0.0.1:8000/test` and see your page. Otherwise using command `curl http://127.0.0.1:8000/test` to see your server output.
* Insert your data: First we create our database table and a corresponding data module (model) to manipulate the table. Then we call this model from controller to insert data. The model of Laravel provides us with a lot of conveient APIs to manipulate data tables without writing SQL.
1. To post data to a url, simply add this to `routes/web.php`:
```php
Route::post('note', 'NoteController@store');
```
1. Create our controller:
```bash
# Generate controller file using this command
php artisan make:controller NoteController
vi app/Http/Controllers/NoteController.php
```
```php
public function store(Request $request) {
// We are using model Note.
// This create API is provided by Laravel.
$note = Note::create([
'title' => $request->title,
'author' => $request->author,
'content' => $request->content,
]);
// Assume the request is ajax, we respond with a JSON.
return response()->json([
'status' => 0,
'msg' => '',
'data' => $note
], 201);
// If it is a form submit, we can also redirect user to a page.
// Below we direct the user back to where he/she came from.
// return back()->withInput();
}
```
1. Create our table and model. Laravel provide scripts (jargon:**migration**) to create tables for us.
```bash
# -m tells Laravel to create model for us at the same time
php artisan make:migration Note -m
vi database/migrations/DATETIME_create_notes_table.php
```
```php
public function up()
{
Schema::create('notes', function (Blueprint $table) {
$table->bigIncrements('id');
$table->string('title', 100)->default('');
$table->string('author', 100)->default('');
$table->string('content', 800)->default('');
$table->timestamps();
});
}
public function down()
{
Schema::dropIfExists('notes');
}
```
```bash
# Run your scripts (all of them) to create the table
php artisan migrate
# Now edit our model file
vi app/Note.php
```
```php
// Add the column names that were used in Note::create at our controller
// Otherwise Laravel won't let us insert like that
protected $fillable = ['title', 'author', 'content'];
```
Now if we post something to our url, you can see the result.
```bash
```
* Retrieve your data: Similarly, we edit our route and controller file:
```php
// routes/web.php
// In case your url path is long, we can give it a name like this.
// So we can easily get this url string anywhere in our app.
Route::get('note', 'NoteController@showNotes')->name('note');
```
```php
// app/Http/Controllers/NoteController.php
```
* Update your data: The only difference from create and retrieve process is the model API we use in our controller:
```php
```
* Front end: It's going to take a long time introducing the modern front end technology stack. If not interested, you can use old-fashion HTML/CSS/JS in Laravel like this:
```php
```
If you do have the patience to learn, Laravel has the most popular front end frameworks (Bootstrap, Vue, React) and module bundler (Webpack) builtin for us. So you can easily reap the benefit:
```bash
# Install the front end package prepared by Laravel
# This command sometimes takes up to a few minuts
composer require laravel/ui --dev
# Generate basic scaffolding. Choose one.
php artisan ui bootstrap
php artisan ui vue
php artisan ui react
# Install the scaffolding
npm install
```
Every time you modifies JS or SASS, run `npm run dev` to generate final JS and SASS assets.
* Pagination:
* Handling user: Usually if you are letting user posting content on your site, you need to implement register, login, verification, password reset, session and logout the whole package. How to implement all of these is beyond the scope of this article. Luckily Laravel has these all built-in for us. Using the command below will generate all the code, including route, view, controller and model, for us:
```bash
# If you haven't already
composer require laravel/ui --dev
# Generate login / registration scaffolding. Choose one.
php artisan ui bootstrap --auth
php artisan ui vue --auth
php artisan ui react --auth
# Install the scaffolding
npm install
# Generate final assets
npm run dev
```
If you are curious about how they are implemented, you can show all the routes in your app now using command `php artisan route:list`. (They hid them behind a `Auth::routes();` function call so you won't see them at `routes/web.php`). Their controller code are at
You can control where your app jumps to after login at `app/Http/Providers/RouteServiceProvider.php` `public const HOME = '/home';`.
### Develop APIs
* Request validation: create a request class and put our validation code there:
```bash
# Create a request class
php artisan make:request StoreNote
vi app/Http/Requests/StoreNote.php
```
```php
// Authorization check code here. You can access $this->user(), $this->{PARAMETER_NAME},
// $this->route, your model class, etc. to check user privilege.
public function authorize()
{
return $this->user()->name == $this->author;
}
// Request parameter check rules here.
// Validation rules provided by Laravel should be enough: https://laravel.com/docs/master/validation#available-validation-rules
public function rules()
{
return [
'title' => 'required|max:100',
'author' => 'required|max:100',
'content' => 'required|max:800',
]
}
// Customize validation error messages here.
public function messages()
{
return [
'content.required' => 'Content is required!',
]
}
```
Finally, put it to work by replacing the request class in your controller `app/Http/Controllers/NoteController.php`:
```php
headers->set('Accept', 'application/json'); // Add this line
return $next($request);
}
}
```
1. Register this middleware to Laravel by modifying `app/Http/Kernel.php` file:
```php
// Register it and give it a name
protected $routeMiddleware = [
'auth' => \App\Http\Middleware\Authenticate::class,
'auth.basic' => \Illuminate\Auth\Middleware\AuthenticateWithBasicAuth::class,
// ...
'throttle' => \Illuminate\Routing\Middleware\ThrottleRequests::class,
'verified' => \Illuminate\Auth\Middleware\EnsureEmailIsVerified::class,
'request_json' => \App\Http\Middleware\RequestJson::class, // Add this line
];
// Because we should set header before any other process, we give it the highest priority
protected $middlewarePriority = [
\App\Http\Middleware\RequestJson::class, // Add this line here
\Illuminate\Session\Middleware\StartSession::class,
// ...
\Illuminate\Auth\Middleware\Authorize::class,
];
```
1. Put it to work. Add `request_json` middleware to `routes/api.php` file:
```php
Route::group(['middleware' => ['request_json', 'auth:api']], function(){
Route::post('note', 'NoteController@store');
});
```
1. Modify all the exception handling code in one place `app/Exceptions/Handler.php`:
```php
public function render($request, Exception $exception)
{
// Add this part of code
if ($request->wantsJson()) { // This checks if the request has the specified header
$status = 1;
$msg = 'Unknown error';
$http_code = 500;
if ($exception instanceof \Illuminate\Validation\ValidationException) {
$msg = $exception->getMessage();
$http_code = 422;
} else if ($exception instanceof \Illuminate\Auth\Access\AuthorizationException
|| $exception instanceof \Illuminate\Auth\AuthenticationException) {
$msg = $exception->getMessage();
$http_code = 403;
} else if ($exception instanceof \PDOException) {
$msg = 'Database error';
} else if ($exception instanceof \Illuminate\Database\Eloquent\ModelNotFoundException) {
$msg = 'Resource not found';
$http_code = 404;
}
return response()->json([
'status' => $status,
'msg' => $msg,
'data' => []
], $http_code);
}
return parent::render($request, $exception);
}
```
### Log
* Laravel supports eight logging levels defined in the RFC 5424 specification: emergency, alert, critical, error, warning, notice, info and debug:
```php
use Illuminate\Support\Facades\Log;
// eg. log an exception
$err_class = get_class($exception);
Log::error("err_class[\\{$err_class}] err_code[{$exception->getCode()}] err_msg[{$exception->getMessage()}]", [ 'key'=>'value' ]);
```
### Query your database
* Create your tables in database
Laravel provides us with a fancy command to generate a PHP script that create or modify table schemas for you. The idea behind this is to keep track of all the database modifications in a series of PHP files. So it is kind of like version control of your database schemas:
```bash
# In your project root folder:
php artisan make:migration DB_OPERATION_SCRIPT_NAME # this is part of the name of the generated script
# Then add your modification code here
vi database/migrations/DATETIME_DB_OPERATION_SCRIPT_NAME.php
```
This script grammar is listed here: . Remember it is best to implement the `down` method in case you need to rollback your modification in the future.
```bash
# Run your scripts (all of them)
php artisan migrate
# If you regret your last modification
php artisan migrate:rollback --step=1
```
# Python
## Dictionary
* Check key exists in dictionary `dict`: `if key in dict:`
* How to iterate: [a good tutorial](https://realpython.com/iterate-through-dictionary-python/).
## String
* Trimming:
```python
s = s.strip()
s = s.lstrip()
s = s.rstrip()
```
* Replace:
```python
s = s.replace('\t', ' ')
```
## Debug
* `str` vs `repr`: , .
# Fluent Python
My notes when reading Luciano Ramalho's Fluent Python.
## The Python Data Model
By implementing special methods (A.K.A. magic methods, like `__len__`, `__getitem__`, `__repr__` etc.. Often pronounced *dunder xx*), your objects can utilize built-in functions and syntax like `len()`, `[]`, `for ... in ...` and thus be considered Pythonic.
Understanding the Pythonic `len(xx)` over `xx.len()`: Think of these functions as unary operators.
## An Array of Sequences
* List Comprehension vs Generator Expression
* List Comprehension: `list_a = [i + j for i in ... for j in ...]`
This is a cartesian products example. `for i in ...` part is the outer loop.
* Generator Expression: `xx(i + j for i in ... for j in ...)`
The syntactic difference is `()` vs `[]`. But under the hood it saves space by yielding item one by one so a full list is never constructed. Also it can be used to build many other containers.
* Tuples
* Tuples (Iterable) Unpacking
* Use case: parallel assignment (can be nested), swap, `%` string formatting `print('%s %s' % tup)`, passing function parameter `f(*tup)`.
* Works for any iterable as long as the iterable yields exactly one item per variable in the receiving end. The only exception is using `*` dicussed below.
* `a, *b, c = range(5)` and `b` is `[1, 2, 3]`. Only one `*` prefix variable is allowed.
* Named Tuples `collections.namedtuple`
* Construction: Passing construct parameters by name or position. `NamedTup._make(iterable)`. `NamedTup(*iterable)`.
* Accessing field by name or position.
* `._asdict()` return a `collections.OrderedDict`
* Methods and attributes as an "immutable list": No appending/poping/inserting nor any inplace ops.
* Slicing
* `[:3]` exclude the last item.
* Slice object.
```
s = slice(begin, end, stride)
line[s]
```
* Under the hood:
```
# v[a]
v.__getitem__(a)
# v[a, b]. Multidimensional. Used in Numpy.
v.__getitem__((a, b))
```
* Ellipsis object: function parameters `f(a, ..., z)` and slice `a[i:...]`. If `a` is four dimentional, this is a shortcut for `a[i, :, :, :]`. It is mostly used in Numpy.
* Assignment using slices. Some interesting example from the book:
```
>>> l = list(range(10))
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[2:5] = [20, 30]
>>> l
[0, 1, 20, 30, 5, 6, 7, 8, 9]
>>> del l[5:7]
>>> l
[0, 1, 20, 30, 5, 8, 9]
>>> l[3::2] = [11, 22]
>>> l
[0, 1, 20, 11, 5, 22, 9]
>>> l[2:5] = 100
Traceback (most recent call last):
File "", line 1, in
TypeError: can only assign an iterable
>>> l[2:5] = [100]
>>> l
[0, 1, 100, 22, 9]
```
* `+` and `*` and augmented assignment on sequences
* `my_list = [[]] * 3` will result in a list with three references to the same inner list. List comprehension avoids this problem. `[[] for i in range(3)]`.
* `+=` and `*=` will first try to use `__iadd__` and fall back to `__add__` and create a new object.
* `list.sort` and `sorted`
* `list.sort` sorts inplace and returns `None`.
* `sorted` library function accepts any iterable object.
* Both accept two parameters: `reverse` bool and `key` for the name of a function that produces sorting keys.
## Misc
* [Online Python Tutor](http://www.pythontutor.com/)
# Computer Networks
My summary notes from Avi and Gabe's JHU CS 414/614 Computer Networks course 2020 spring.
## Wireless
### Basics
* Infrastructure: Base station (access to the wired net for clients) or ad-hoc net (among clients)
* Standards:
* Short range: 802.15 (Bluetooth), 802.11 (WiFi)
* Long range: 2G - 5G
* Wireless characteristics compared to wired: All kinds of interference and hidden terminal problem (hard to sense if the medium is busy) caused by obstacle between senders and signal fading
* CDMA (Code Division Multiple Access): Recovers original data from one of the senders using its assigned code by Linear Algebra magic.
### 802.11 (WiFi)
* Infrastructure: Base station (aka Access Point). Take 802.11 b/g for example, there are 11 channels (only 1, 6, 11 channel has no overlap with each other). AP admin must assign one channel number to an AP. Each host must associate with one AP.
* CSMA/CA: No collision detection compared to wired version (CSMA/CD).
* Because the stength of received signal is usually small compared to transmitted signal, it is costly to build hardware that can detect a collision. CSMA/CA consists of sensing channel availability, random backoff, **wait for a certain time** (Because there is no collision detection, waiting is needed in case others are starting to send at the same time), transmit an entire frame (no collision detection so no abortion), **wait for ACK** (Also because there is no collision detection).
* Reserving channel (optional): handling the hidden terminal problem.
* Frame:
* 4 MAC addresses: receiver host or AP, sender host or AP, router interface to AP, address in ad-hoc mode. Compared to switch, AP is not transparent (Has MAC address).
### 802.15 (Bluetooth)
* Infrastructure: Ad-hoc net. Master/slaves/parked(inactive) devices within a local net.
### Cellular Net
* Infrastructure: Cell (Base station + mobile users), mobile switching center, etc.
* Combined FDMA/TDMA/CDMA to support more users
* 2G (Voice), 3G (Voice + data), 4G (All IP)
### Handling Mobility
* How:
* Do nothing and let routing handle it: not scalable, too many losses.
* Indirect routing (often used): Inform home agent about host's new address when host move to another network and let the home agent and foreign agent forward data to it. Longer delay.
* Direct routing: Correspondent agent get the new address of a host from home agent and directly connect to it. Shorter delay but 'unfair' (too much work) to the correspondent agent.
* Mobile IP: Implements indirect routing above.
* Cellular net (GSM): Also indirect routing. Roaming address is acquired by querying the cellular net provider.
* Handoff: Base stations, host and cellular net provider coordinate to serve a moving host.
# Designing Data-Intensive Applications
## 1. Reliable, Scalable, and Maintainable Applications
## 2. Data Models and Query Languages
## 3. Storage and Retrieval
## 4. Encoding and Evolution
A note on B-tree lightweight lock for concurrency control: My intuition is that we can use a R/W lock on the nodes we visited.
## 5. Replication
## 6. Partitioning
### Consistent hashing
A hashing strategy for easier rebalancing. Used both in data partitioning and request load balancing.
Map nodes and keys into a same space using a same hash function. A key would be stored on the node with a successor hashed value. Concatenate the begin and the end of this hashed space so every key has a node successor.
### Other view of paritioning
#### From the Grokking the System Design Interview course in my words
* Layers of paritioning:
* Partition by key. Lowest level. This is often what we talk about when discussing partitioning.
* Partition by feature. Different service storages could be considered to be partitions of one large system.
* Partition query layer. The level closest to the application. At this level we can add a service to abstracts away the detail of partitioning methods and make life easier for application writers.
* Partitioning Criteria
* Hash (+ mod N round robin)
* Key range
* Compound: hash + key range
* Common problems
* Joins are usually not supported because of inefficiency: may be solved by denormalization (keep redundant information).
* Foreign key constraints not supported: implement in the application
* Rebalancing
## 7. Transactions
## 8. The Trouble with Distributed Systems
# Information Retrieval
This note mainly focuses on text information retrieval. It is mainly based on JHU's, [ETHzurich's](https://www.systems.ethz.ch/courses/spring2018/informationretrieval) and [Stanford's](http://web.stanford.edu/class/cs276/) information retrieval course.
## Overview
Data -> Search -> User
More detail:
* Data: Getting documents and preprocessing documents
* Crawler
* Text preprocessing, Clustering, Information Extraction (Named Entity, Relation, Topic Models, etc.)
* Forward Index, Inverted Index
* Search: Querying content (Search engine) or filtering content (Recommendation system). Not different that much.
* Querying: Boolean Retrieval, Vector Space Model, Probabilistic Model, Learning to Rank
* Filtering: Content Filtering, Collaborative Filtering, Also use Querying methods
* Ranking: Scoring, Link Analysis
* User: Content presentation
## Retrieval In General
* The way user accessing data: Push mode (Recommendation system like news feed) -> filtering content and Pull model (Search engine) -> querying content.
* Retrieval compared to Database: Database usually holds structured data, with well-defined query semantics.
* Know that user information need is almost always larger than the given query.
* Search core methods: Selection (binary decision) or Ranking (Continous scoring and thresholding). If we assume the utility of a document to a user is independent of any other document and the usesr browse the results sequentially, we could rank documents in descending order of the probability that a document is relevant to the query.
* Search results evaluation: Precision and Recall.
## General Text Preprocessing
* Tokenization
* Normalization: Map term variant to the same form.
* Stemming: Extract root word.
* Stop words: Omit common words
## Main Topics
* [Ad Hoc Retrieval](/topics/informationretrieval/ad_hoc_retrieval)
* [Classification and Clustering](/topics/informationretrieval/classification_and_clustering)
# Ad Hoc Retrieval
This part we dicuss the fundamental techniques of retrieval when the system is presented with a user query.
## Boolean Retrieval
1. First we need to scan each document and extract (docId, term) pairs from each document. Now we need a efficient way to lookup docId given terms.
2. Intuition: Build a Term-Document incidence matrix
| | documents | | | | |
| --------- | --------- | ------------------- | -------- | --------------------------- | - |
| doc0 | doc1 | ... | doc\|d\| | | |
| terms | term0 | is\_in(term0, doc0) | | | |
| term1 | | ... | | | |
| ... | | | ... | | |
| term\|V\| | | | | is\_in(term\|V\|, doc\|d\|) | |
Each cell in the table body is a binary weight describing if a document contains a term. Eg:
But this table will be massive if |V|\*|d| is large.
3. Instead, we use Inverted Index.
Notice that the documents are ordered by docId. This allows us to do quick intersection.
4. Do boolean operations on terms with AND, OR, NOT operators. Eg: {doc result} = f(term0 OR (term1 AND NOT term2)).
Small optimization: Reorder terms of boolean operation in increasing document frequency (how many document this term appears in) to reduce unneccessary works.
## Index Construction
* Hash Table, B+ Tree
* First step is to scan each document and extract (docId, term) pairs from each document. But the number of pairs may be too large to fit into memory or to sort in disk. So how to build large inverted index efficiently?
* Block sort-based Indexing:
* Keep a termId-term table on the fly or in batch, to reduce (docId, term) pair size
* Divide documents into chunks. Chunk by chunk, pull from disk into memory. Extract t pair of (docId, termId). T in total. Time complexity is O(T).
* Sort the pairs by termId\_docId and merge them with termId as the key. Then write merged termId-docIds back into disk. O(TlogT) in total.
* Open all chunks on disk simultaneously. Read line by line and merge and write to final inverted index. O(T) in total. Because it is disk operation so O(T) becomes dominant.
* Single-pass in memory Indexing:
* Divide documents into chunks. Chunk by chunk, read each document and build term-docIds map on the fly. Still we assume t pair of (docId, termId). T in total. D documents. Time complexity is O(T) because docId is already in order.
* Sort the map by term. Then write back into disk. O(DlogD) in total.
* Same as Block sort-based Indexing. O(T) still dominates.
* Distributed indexing: Use MapReduce.
* mapper: Extract pairs from document
* reducer: Get all pairs of one (or more) term(s). Sort by docId and write merged term-docIds into disk.
* Dynamic indexing: To efficiently get incremental changes.
* Main index plus a incremental auxiliary index, which is periodically merged into main index. The cost of merge is associated with the number of indexes. The more the better. In reality we often choose a compromise between the two extreme. For example logarithmic merge indexes (detail omitted here).
* Dual main index switching.
## Index Compression
* Dictionary Compression: Focusing on compressing term string
* Dictionary as a string: Instead of giving fixed-width length to terms, we first concat terms into a single long string in order of inverted index and record only the position of each term.
* Blocked Storage: Instead of recording all the positions of terms, we record every *k*th term position and keep each term length in front of each term in the concated string. When walking down the B+ tree in search of a term, we found the *k* length section the term is in and then do a linear scan.
* Front coding: When concatenating terms in order, omit same prefixes and use some special symbols and numbers representing suffixes length.
* Postings Compression: TODO
## Ranked Retrieval
* Find documents based on score and we can control the number of most relevent documents to show in the end.
* Jaccard Coefficient: |query terms AND doc terms| / |query terms OR doc terms|. But it does not consider term frequency, rarity (informative) and document length.
* Term-Document frequency matrix: Recall the Term-Document incidence matrix. Instead of putting binary number in the cell, we count how many times a term appears in a document.
* Bag of words model: A document is represented by a vector of word counts. It does not consider order of words.
* Notice that relevance does not increase proportionally with term frequency. So we could use some transformation to discount the effect of term frequency:
Sublinear Transformation:
BM25 Transformation:
* Query document scoring: Considering term frequency.
Define log frequency weight of term t in d:
!\[\text{Score} = \sum*{t \in q \cap d} (1+\log{tf*{t,d}})]\([https://render.githubusercontent.com/render/math?math=%5Ctext%7BScore%7D %3D %5Csum\_%7Bt %5Cin q %5Ccap d%7D (1%2B%5Clog%7Btf\_%7Bt%2Cd%7D%7D](https://render.githubusercontent.com/render/math?math=%5Ctext%7BScore%7D%20%3D%20%5Csum_%7Bt%20%5Cin%20q%20%5Ccap%20d%7D%20\(1%2B%5Clog%7Btf_%7Bt%2Cd%7D%7D)))
* idf: Considering rarity (informative). It only starts working when there are two or more terms in a query.
 is the number of document that contain t. Minimum set to 1.
!\[idf\_t=\log{(N/df\_t)}]\()
Use log to dampen the effect of idf.
Summing up, we have tf-idf model:
TODO
Score =
### Vector Space Model
* Intuition: tf-idf weight matrix. Each cell is now a tf-idf score.
| | documents | | | | |
| --------- | --------- | -------------------- | -------- | ---------------------------- | - |
| doc0 | doc1 | ... | doc\|d\| | | |
| terms | term0 | tf\_idf(term0, doc0) | | | |
| term1 | | ... | | | |
| ... | | | ... | | |
| term\|V\| | | | | tf\_idf(term\|V\|, doc\|d\|) | |
Each document can now be represented by a high dimentional vector (a column). In boolean retrieval model, each vector is filled with binary values. In naive bag of words model, each vector is filled with term frequency as values. In tf-idf model, each vector is filled with tf-idf values.
* Scoring method: Now we can represent query as a same kind of vector, then give each document a score based on the similarity between the query vector and the document vector. Because we care more about the distribution of terms than raw value in the vector, we use cosine similarity instead of Euclidean distance.
* Implementation: The naive implement is to compute a score between the query and each document. But that would be too slow (same reason as in Boolean Retrieval). We actually do not use table but use inverted index. So to calculate cosine similarity between the query and documents, we iterate postings of each query term and accumulate a score for each document. The terms not presented in the query are not traversed at all since they would be 0 anyway. Then we noramlize the scores by dividing the length of query vector and the corresponding document vector length. Finally we extract the top scoring documents we needed.
This algorithm is described in detail below:
If we loop through query terms one-by-one to accumulate document scores, it is called term-at-a-time algorithm. Else we could open all terms postings together like the intersection algorithm in boolean retrieval and iterate postings by the order of docIds. Then we are accumulating scores document by document. This is called document-at-a-time algorithm.
Note sometimes in practice, VSM is only used in the providing a score for ranking instead of actual retrieval. In Lucene, other models like boolean retrieval is used to retrieve a subset of documents before VSM is applied. (In this way, you may be able choose the naive VSM implementation if dev time is limited to you.)
* Optimization:
* Tf-idf is a floating point number which takes up a lot of space. Since all idf values of a term is the same, we can actually store the idf value at the postings list head and only keep the tf values in the postings.
* All scores are normalized by the length of query vector, so we can just omit this part.
* We only need to compute the length of documents query terms appear in.
* To find the top documents, we either use QuickSelect, or use Min Heap to only keep the number of the documents we wanted on the fly.
* Variants of tf-idf:
Also you can use different weighting schemes on query and document.
* Furthur Optimization, with approximation:
* Query terms tf are usually 1, so we can omit them.
* Idf are the same for query term and document term, we can change the scoring scheme and leaves only document term idf.
Summing up, we have the following:
### Optimization and Other Scoring Methods
From exact top k document retrieval to inexact top k.
* Index elimination
* Leave only postings lists with high idf.
* Leave only documents which contain a large number of terms.
* Champion lists: For each postings list, leave only corresponding r documents with high tf value. Each term could contribute different number of 'champion' document according to our custom settings. In the end we could compute scores for documents in the union of all champion lists.
One potential problem here is that the postings would be sorted by tf values instead of docIds. This should make our quick intersection or document-at-a-time algorithm impossible. So we could keep a separate inverted index ordered by docIds.
* Static quality score: Suppose each document has a static quality score irrelevant to the query and it is used in the final scoring, for example PageRank score that evaluates page importance or authority. Maybe something like final\_score = static\_score + cosine\_similarity. We then could find 'champion' documents by these two ways:
1. Sory by static\_score + max tf-idf value of the document. We have a global champion list of documents.
This also poses the problem of postings order, which are now in the order of this static sorting score instead of docIds. This is supposed to make our quick intersection or document-at-a-time algorithm impossible. But in fact, as long as all documents in postings lists share an universal ordering scheme, we can still do it in one pass!
2. Sort by static\_score + tf-idf. We have a champion list for each term.
This is a direct combination of static quality score and champion list. We would need to keep a separate inverted index ordered by docIds in order to use quick intersection or document-at-a-time algorithm.
* Tiered indexes: If r is chosen too small, we may find no documents at all in the end. We could keep multiple backup champion lists and fallback to them when we could not find enough k documents.
* Impact ordering: We sort postings lists by idf and sort each postings by static\_score + tf like in the champion list. Then we accumulate documents scores in order until new scores are below threshold or we have accumulated more than enough documents. Notice we can only use term-at-a-time algorithm in this manner.
* Cluster pruning: Pick a subset (maybe square root of the number of all documents) of documents randomly as leaders and do one round of k-means to cluster all documents around these leaders. When we are computing scores we only compute for documents in the cloest cluster to the query vector.
Of course we can try other variant methods like doing more rounds of k-means or assigning documents to more than one leader.
* Query term proximity: Users prefer docs in which query terms occur within close proximity of each other. This is a very different scoring methods from discussed above that requires a custom scoring module.
* Query parser and custom scoring: In fact, modern search engine often uses a combination of retrieval methods to get different results and aggregating scores from multiple custom scoring methods to rank the different results.
### Probabilistic Model
In traditional IR systems, matching between each document and query is attempted in a semantically imprecise space of index terms. Probabilities provide a principled foundation for uncertain reasoning. The principle is to return documents by decreasing order of relevance probabilities.
#### Binary Independence Model
Binary: documents and queries are represented as binary incidence vectors of terms (**x** and **q**) like in boolean retrieval. Independence: Using naive bayes assumption, assuming terms occur in documents independently. Using the principle of probability ranking, we need to rank documents according to **p(R=1|q,x)**.
* The math (skip this if you want to): Using odds and Bayes' Rule, we rank documents by odds:
Since we are only interested in ranking, factors unrelated to documents can be ignored:
Here **p** is the probability of a term appearing in a document relevant to the query. **r** is the probability of a term appearing in a nonrelevant document.
* BIM RSV: Finally we have the retrieval status value for ranking:
In this equation, we let $$c\_i$$ be the log odds ratios. Then:
$$c\_i = \log \frac{p\_i(1-r\_i)}{r\_i(1-p\_i)} = \log \frac{p\_i}{1-p\_i} + \log \frac{1-r\_i}{r\_i}$$
$$\frac{p\_i}{1-p\_i}$$ is the odds of the term appearing if the document is relevant. $$\frac{r\_i}{1-r\_i}$$ is odds of the term appearing if the document is nonrelevant. The log odds ratio is the ratio of these two odds. So more likely a term appears in a relevant document, larger the this ratio. This is why the retrieval status value could act as term weight. And the sum is document score.
* Estimating .
* Maximum likelihood estimate: In theory, we can count from the whole document collection to get  and :
This called Maximum likelihood estimate. We can also use smoothing to avoid dividing zero and gives some probability to events we haven't seen in the document. A simple way is to add a small pseudocounts to each observed count. These pseudocounts act as a Bayesian prior and denotes the strength of our (small) belief in uniformity. This is call maximum a posterior estimation.
* Estimating  in practice: Assuming relevant documents are a very small percentage of the collection:
* Estimating  in practice: There are three ways:
* Relevance feedback: Use the frequency of term in know relevant documents.
* Just give it a constant 0.5. Only IDF is left in retrieval status value.
* From collection level statistics, .
* Relevance feedback: TODO
* Summary of assumptions in BIM:
* Relevance of each document is independent of others
* Naive Bayes Assumption: Term are independent of each other given query and document relevance
* Terms not in the query are equally likely in relevant and irrelevant documents. They don't affect outcome.
* Boolean representation of term/document/query/relevance
* Estimating : query words appear half of the relevant documents
* Estimating : Most documents are not relevant given query. |non-relevant| ≈ |doc. collection|
#### BM25
Best Match 25, since 1994. Its goal is to be sensitive to term frequency and document length while not adding too many parameters. It relaxes the assumption of term independence and boolean representation of term/document/query/relevance above. It also takes into consideration of document length.
* Background (skip this if you want to): Assuming a generative model. Words are drawn from vocabulary using a multinomial distribution. So the term frequency obeys binomial distribution. Assuming documents are very long compared to a term, we use Poisson distribution to approximate binomial distribution (see why is it legit [here](https://math.stackexchange.com/a/1050233)). But with this model, we cannot predict topic-specific terms that appear a lot in some documents and not once in others. So we introduce another binary hidden variable Eliteness between document and term frequency to describe if a term matches the topic of the document.
Similar to BIM, we derive a retrieval status value by considering term frequency:
Combined with our Poisson term frequency model, we get the 2-Poisson model for term frequency:
But there are too many unknown parameters. Here we have a look at the graph for $$c^{elite}\_i({tf}\_i)$$:
* Elite RSV: We can approximate $$c^{elite}\_i({tf}\_i)$$ with the Saturation function: $$\frac{\mathit{tf}}{k\_1 + \mathit{tf}}$$
We usually add a $$k\_1+1$$ to the numerator to provide a lower bound 1 to this function.
Finally we consider the document length by normalizing the term frequency with a length normalization component:
* Using the $$c^{elite}\_i({tf}\_i)$$ with length normalization component and $$c^{\text{BIM}}\_i$$. We get BM25 model:
* BM25F: Considering different zones of the document, use a weighted variant of term frequency. This would also affect document length which is the sum of term frequency.
* Adding non-textual feature: derive a simmilar RSV for the feature and add to BM25 RSV.
* Some advice on choosing $$k\_1$$ and $$b$$ from Elastic: For Lucene and ElasticSearch, the default is $$k\_1=1.2, b=0.75$$. Usually good enough for most cases.
* $$k\_1$$(0-3): Do you want terms to be saturated, so that the system wouldn't focus only on a few high-freqency terms? If yes, make $$$k\_1$$ smaller so that large term frequency number would contribute relatively less than when $$k\_1$$ is large. However for long documents, you may want a large $$k\_1$$ since all term frequencies are large and you need to find the most relative ones.
* $$b$$(0-1): Do you want to penalize lengthy documents? If yes, make $$b$$ larger so that some lengthy documents that covers a lot of topics (maybe spam) would appear less. For some lengthy engineering specification or patents, there may be no reason to penalize their length.
## Evaluation Metrics
* Binary Assessments
* Precision: fraction of retrieved docs that are relevant = P(relevant|retrieved). Recall: fraction of relevant docs that are retrieved = P(retrieved|relevant). F1 score = 2P\*R/(P+R)
* Precision\@K: fraction of relevant docs in top K results. Mean Average Precision: first get averge of P\@K from 1st to Kth result of multiple queries then do another averge. Similarly we have Recall\@K. By looking at the recall and precision of 1st to Kth result we can draw a Precision-recall graph.
* Reciprocal Score: considering the first relevalant result, it scores 1/K if at position K. Mean reciprocal rank: averge over multiple queries.
* Non Binary Assessments:
* Discounted Cumulative Gain: given relevance socre \[0, r] r > 2 of each result. Cumulative Gain at rank n is $$r\_1 + r\_2 + ... + r\_n$$. Discounted Cumulative Gain is $$r\_1 + r\_2/\log 2 + r\_3/\log 3 ... r\_n/\log n$$
* Normalized Discounted Cumulative Gain: Normalize DCG at rank n by the DCG value at rank n of the ideal ranking, which would first return the documents with the highest relevance level, then the next highest relevance level, etc. Normalization useful for contrasting queries with varying numbers of relevant results.
## Skipped Contents (for now)
* Ranked Retrieval: Parametric search, learning weights, safe ranking (in lecture 10 of Stanford)
* Relevance feedback
# Classification and Clustering
This part we dicuss the some of the classification and clustering techniques, focusing on those related to the models we've dicussed in ad-hoc retrieval. It's useful in a way that the system is able to prepare relevant content even when the user isn't actively inputing queries.
# Operating Systems
Based on Prof. Ryan Huang's [Principles of Operating Systems course](https://www.cs.jhu.edu/~huang/cs318/fall20/index.html).
OS: The layer between applications and hardware. Manage hardware (protection), ensure high utilization of hardware (resource sharing) and provide abstractions to applications.
## Hardware Support
* Protection.
* Dual mode: user/kernel. Recorded in the register. Modern CPU may have more than 2 levels (x86:4, ARMv7:8).
* Protected instructions: directly access I/O devices, manipulate memory management state, manipulate protected control registers, halt.
* Memory protection: translate virtual address at Memory Mangement Unit (MMU).
* Events. Immediately stops current execution, changes mode to kernel, transfers control to handler code in the OS, and finally restores program state.
| | Unexpected | Deliberate |
| --------------------------------------------------- | --------------------------------- | ---------------------------------- |
| Interrupts: caused by external event (async) | interrupt (I/O, timer) | software interrupt |
| Exceptions: caused by executing instructions (sync) | fault (page fault, division by 0) | syscall trap (x86 int instruction) |
* Interrupt (I/O): Polling or:
1. I/O devices wired with Interrupt Request Lines (IRQs).
2. IRQs are mapped to interrupt vectors by Programmable Interrupt Controller (PIC).
3. PIC sends the interrupt vectors to CPU for handling.
4. At software level, an Interrupt Vector Table (IVT), which in x86 is called Interrupt Descriptor Table (IDT), associate interrupts with handlers.
* Trap: system call. How to pass result from syscall to user? Issue a special descriptor (e.g. file descriptor number).
* Fault:
* Faster than actively detecting faults. Modern OSes use VM faults for many functions (Debug, gc, copy-on-write)
* Handing: fix and re-execute, notifying the process, kill the process.
* Synchronization: disable interrupts, atomic instructions
## Processes
A program in execution. Multiprogramming ensure higher throughput and higher hardware utilization.
* Process components: address space (code, data, execution stack), program counter (PC) indicating next instruction, some general registers and set of resources (opened files, network conns). Each process has its own view of the machine.
* The data structure: Process Control Block (PCB). It contains process state, process id, program counter, registers, address space, open files, etc.
* Inter-Process Communication (IPC): Passing message through kernel, sharing physical memory region, asyncrhonous signals or alert.
* OS point of view
* OS usually maintains a queue of process for each state. Usually most processes will be in the waiting state, waiting for I/O. There may be many wait queues for each type of wait.
* Scheduling, preemption described later in Thread.
* Context switch: Usually starts with saving program counter, integer registers, etc. Then changes virtual address translations.
* Programmer point of view
* Unix fork() duplicate current process, return child pid to parent process and return 0 to newly created child process.
* Unix exec() stops current process and loads new program, so it won't return unless there is a problem. Pintos exec() is fork() + exec() and it will return child pid.
* Compared to Windows CreateProcess(), fork() has no argument so it's much easier to use.
* wait(). [Wait for all child processes to finish](https://stackoverflow.com/questions/19461744/how-to-make-parent-wait-for-all-child-processes-to-finish).
## Thread
* Separate execution state from process concept.
* Process is static holding address space and attributes like privileges and resources. Thread is dynamic holding program counter, stack pointer and other register values.
* Thread is the unit of scheduling.
* Threads share heap, code, data, files. But have its own registers, stack.
* The data structure: Thread Control Block (TCB).
* thread\_create() allocates TCB, stack, put function name and arguments onto the stack (calling convention) and finally put thread on the ready list.
* Kernel level thread and User level thread:
* Kernel level thread: Must go through kernel, so it is often slower to create. Same features (priority, etc.) for every one. Requires fixed-size in the kernel.
* User level thread: Invisible to OS, so it cannot take advantage of multiple CPUs and may not be scheduled well.
* Solution: associate or multiplex user threads to kernel threads. (n:m mapping)
* Scheduling
* yield(): One thread yield the CPU. Context switch to another thread. That thread return from its own yield() and continue.
* Non-preemptive scheduling: voluntarily yield
* Preemptive scheduling: Timer interrupt forces current thread to yield.
* Context switch: save and restore context. Done at assembly. x86 examples below:
* Calling conventions: a standard on how functions should be implemented and called by the machine. Compilers compile code to assembly and set up stack and registers according to this standard.
* Stack:
```
+-----------------+
| |
| arguments |
| |
+-----------------+
| |
| return addr |
| |
+-----------------+
| |
| old frame ptr |
| |
fp +----> +-----------------+
| |
| callee-saved |
| registers |
| |
+-----------------+
| |
| local vars |
| and temps |
| |
sp +----> +-----------------+
| |
| |
```
* Registers:
* Caller-saved registers: %eax(return value), %edx, %ecx. Caller has saved them to the stack so callee function can freely modify these registers.
* Callee-saved registers: %ebx, %edi, %ebp, %esp. Restore to original before return.
* switch\_threads(cur, next)
## Scheduling
* Criteria: Throughput, turnaround time (start to finish), response time (request to first response) of processes. Secondary criterias are CPU utilization and process waiting time.
* Batch system often optimize for throughput and turnaround time. Interactive systems oftem optimize for response time.
* Non-goal: process starvation
* Textbook scheduling
* First-in-first-out: non-preemptive in nature. Has convoy effect.
* Shortest job first: choose the job with smallest expected CPU burst. Provable optimal minimum average waiting time.
* Inspiration: most jobs have bursts of computation and long waiting time for I/O. We can overlap computation of one thread with I/O time of others to maximize throughput.
* Can be done non-preemptively or preemptively.
* Does not minimize average turnaround time.
* Can lead to unfairness or starvation.
* It is impossible to know the CPU burst time ahead. Solution: estimate based on the past.
* Round robin: each job is given a time slice called a quantum. Preempted and moved to FIFO queue after the quantum.
* Low average waiting time.
* Frequent context switch cost and high turnaround time.
* Quantum should be picked larger than most CPU bursts time.
* Priority scheduling
* Avoid starvation: age the processes. Increase priority as waiting time increases. Decrease as CPU consumption increases.
* Avoid priority inversion (kind of like deadlock, but different in nature): high priority thread donates to low priority thread holding the resource.
* Combining algorithms: multiple queues each with different algorithm. E.g. multiple-level feedback queues (MLFQ).
* MLFQ: Optimize turnaround time for batch jobs and minimize response time for interactive jobs.
* Each queue has different priority. Within each queue we use RR.
* Change priority based on the past. Interactive jobs has high priority. Batch jobs that used up a quantum was demoted.
* Aovoid starvation and cheating: Periodically boost priority for jobs that haven't been scheduled. Also the demotion strategy can account for job's total run time at a priority level.
* Advanced scheduling
## Synchronization
Threads may share resources and may need to coordinate their execution.
Stack data are not shared. Global variables, static objects (both in static data segments) and dynamic objects (in heap) are shared.
The compiler might change the sequence of execution of your code. Threads may interleave executions arbitrarily.
* Mutual exclusion
* Safety property: if one thread is in critical section, then no other is.
* Liveness property:
* Progress: any one outside critical section can enter. Those inside will eventually leave.
* Bounded waiting (no starvation): any one waiting for critical section will eventually enter.
* Performance: small overhead.
* Locks: spinlock or mutex. Need hardware support to implement:
* Atomic instructions: test-and-set. Set to true but return old flag value. Break out of while loop if old value is different from new value. Can also be implemented using atomic swap. This is used to implement spinlocks.
* Disabling interrupts: no context switch anymore. Disabled only within acquire() and release().
## Semaphores and Monitors
* Semaphore: a counter and a waiting queue. P() waits and then decreases the counter. V() Increases the counter and signals others.
* Mutex semaphore (binary semaphore) vs counting semaphore: Limit the counter (number of access).
* Condition variables (C/V): wait for some condition.
* Can be implemented with semaphore. What is special about C/V:
* It must acquire lock before modifying the variable.
* The signal (or broadcase) has no history, unlike semaphore::signal. So it must atomically release the lock and started waiting to avoid missing the signal.
To implement broadcast and the no history property, we must use a queue of semaphores to implement C/V. The queue is protected by the lock.
* Two flavors:
* Hoare: signal() immediately switches from caller to a waiting thread and guarantees the condition holds.
* Mesa: signal() merely places a waiter on the ready queue and continue its own execution. The ready thread must recheck the condition when run.
* Monitor: programming language construct that controls access to shared data. It encapsulates the procedures on that shared data.
* Only one thread can execute within a monitor at a time.
* C/V can be used within Monitor without lock.
* Classic problems: Readers/Writers problem, Bounded Buffers problem.
## Deadlock
* Classic problem: Dining philosophers problem.
* Definition: every process in a set of processes is waiting for another one in the set.
* Exists with all kinds of synchronization methods. One thing to remember is that it is always dangerous to hold locks while crossing the bourdary:
```
lock(a);
foo() // Internally using C/V. Will not release a when waiting.
unlock(a);
```
* Conditions for deadlock. All 4 are needed for dealock to occur.
* Mutual exclusion
* Hold and wait
* No preemption: critical sections are not aborted externally
* Circular wait: can be shown with resource allocation graph
* Dealing with deadlock:
* Ignore it.
* Prevention. Eliminating one condition.
* Dealing with Mutual exclusion: buy more resources, split or copy resources. One less philosopher would solve the dining philosophers problem.
* Dealing with Hold and wait: wait on all resource at once. Need to know all in advance.
* Dealing with No preemption: give up resource to another, like virtual memory manangement
* Dealing with Circular wait: single lock for entire system or partial ordering of resources.
* Avoidance: System only grants resource requests if it knows that the process can obtain all resources it needs in future requests. Need to know all resources needed in advance. Not pratical. There is a Banker's algorithm. But it causes low resource utilization.
* Detection and recovery: implemented in VMS, MySQL.
* Detection: traverse resource allocation graph. But it may be expensive.
* Recovery: abort all/one process, preempt resource (force release. Tricky to implement).
## Virtual Memory
* Goal
* Abstraction for programming
* Allocate scarce memory resources.
* Issues with naive approach of allocating memory:
* Protection
* Transparency: a process doesn't require specific physical memory address but does often require large amounts of contiguous space
* Resource exhaustion: sum of all processes memories is often larger than physical memory
* Solution:
* Protection between processes
* Give each process its own virtual address space. Process does not see the physical memory addresses. A Memory-Management Unit (MMU) translates and allocate them.
* This space is often larger than the available physical memory.
* Implementation:
* For each process, records a base and a bound register for translation. Good performance, cheap space overhead but hard to grow or share memory.
* Segmentation: many bases and bounds (segments) in a table. Each virtual address is a segment number and offset concatenated together. Need translation (MMU hardware), not completely transparent (?), external (if use variable-sized segment) and internal fragmentation (if use fixed-sized segment) waste space.
* Alternative to hardware MMU: language-level protection (Java), software fault isolation (Google Native Client).
* Paging: fixed-sized segment. Usually 4K, an empirical choice.
* Virtual address: 4B, 32 bits. Least significant 12 bits ($$= \log\_{2} 4K$$) are offset. Rest 20 sigificant bits are virtual page number.
* Page table: maps virtual page number to physical page number, along with flags.
* Page table entry: 12 bits (?) flags + 20 bits physical page number
* Good and bad:
* Easy to allocate, no external fragmentation, easy to swap out.
* Still has internal fragmentation, memory reference overhead (improve by hardware cache), memory space overhead (per process, 32 bits address space and 4K page need $$4B \* 2^{32} / 2^{12} = 4MB$$ size page table. Can improve by paging the page table.)
## Virtual Memory Optimization
* How to reduce memory space overhead? Hierarchical page table. Some sub page tables don't need to be allocated. Use two-level x86 Paging as example:
* Enabled by control register %cr0. %cr3 points to a 4KB size page directory.
* Page directory: 1024 page directory entries ($$4KB / 4B$$ page directory entry size). $$1024 \* 4B = 4KB$$ size page directory.
* Page directory entry: Most significant 20 bits are base physical address of a page table. Rest are flags.
* Page table: 1024 page table entries. Each page table covers 4MB ($$= 4K \* 1024$$) memory space. Each page table is $$1024 \* 4B = 4KB$$ in size.
* Page table entry: Most significant 20 bits are base physical address. Rest are flags.
* Virtual address: Most significant 10 bits are page directory number, middle 10 bits are virtual page number, least 12 bits are offset.
Though we might use $$4KB + 4KB \* 1024$$ for this two level page table (4KB larger than previous approach), most of the secondary page tables are not allocated.
Also we are paging the page table, we won't page the outer page table to stop recursion (called wiring). Also we need special code when paging the OS address space.
* How to reduce memory reference overhead? Translation lookaside buffer (TLB, a hardware cache). Managed by MMU. Caches virtual page number to page table entry value (to include flags).
* Loaded either by hardware (x86 MMU) or software (MIPS, Alpha, Sparc, PowerPC OS)
* OS ensures consistency (invalidates if protection bit changes, context switches). (Usually hardware) Implements eviction policy like Last-Not-Used.
* Swap: paging in and out from disk. Designs: Page eviction if memory is full v.s. demand paging (all pages are default in disk until accessed).
* Page faults: when a process accesses a page that was evicted.
1. When the OS evicts a page, it sets the PTE as invalid and stores the location
of the page in the swap file in the PTE
2. When a process accesses the page, the invalid PTE causes a trap (page fault)
3. The trap will run the OS page fault handler
4. Handler uses the invalid PTE to locate page in swap file
5. Reads page into a physical frame, updates PTE to point to it
6. Restarts process
* Summary cases:
1. Read from TLB
2. TLB misses. Load from page table by MMU or OS. Might be recursive if the page table is paged.
3. TLB misses. If the page is invalid, page is not in physical memory, protection fault (read/write operation not permitted), causes a page fault.
* Page is invalid, protection fault. Sends segmentation fault to process.
* Page is not in physical memory. Sends page fault to OS for loading.
* Sharing: PTEs points to a same physical frame.
* Need to update all PTEs when evicting a frame.
* Pointer inside the shared region usually should not point to address outside the region.
* Even if the pointer only points to address inside the region, if we don't force virtual addresses to shared region exactly the same, we would have a problem. To conclude:
* Same virtual addresses: Might have conflict, but pointers inside the region are valid.
* Different virtual addresses: Flexible, but pointers inside the region are invalid.
* Copy on write: When `fork()`, child virtual address space points to read-only parent pages. Parent and child only copies the page when there is a write (which causes a protection fault).
* Memory mapped file: `mmap()` in Unix. Binds a file to a virtual memory region. Load into memory when a file segment is accessed. Writes back when a page is evicted.
* Good: uniform access for files and memory, less copying (page is never read or written if it is not accessed or dirty).
* Bad: Less control over data movement, does not generalize to streamed I/O.
## Page Replacement
Choose which page to evict.
* Some thoughs:
* Locality: temporal locality (recently referencied pages are more likely to be referenced again), spatial locality.
* 80/20 rule. 20% "hot" memory.
* FIFO
* Belady's Anomaly: more physical memory does not always mean fewer faults.
* Optimal algorithm: Belady's algorithm. Evict a page that is "never" touched again. Used as a yardstick.
* LRU
* Straw Man LRU: keep a timer value on PTEs. Large overhead. Using a doubly-linked list is also expensive.
* Clock algorithm
* Use a second clock hand for large memory
* How to decide the memory space to each process?
* Fixed space: replace its own pages. Might be too good/bad to some processes.
* Variable space: global replacement. One process might ruin all others.
## Dynamic Memory Allocation
* Stack allocation and Heap allocation (our focus).
* Problem with the naive approach: random allocation and free create fragmentation. Allocator cannot move regions already assigned to users.
* Some thoughts:
* Fragmentation comes from different lifetime and sizes of requested block.
* Important placement choice: Split large block (causes internal fragmentation), coalescing small blocks (causes external fragmentation).
* Best fit:
* Search freelist and find block closest in size to the request.
* Problem: sawdust. Small fragments every where. Not serious in practice.
* First fit:
* LIFO: free object on front of list. Simple, good locality but high fragmentation.
* Address Sort: easy coalescing. Good locality. Used in practice. Roughly like sorting list by size. Operationally similar to best fit. Serious sawdust at the beginning.
* FIFO: similar to address sort according to statistics.
* Worst fit: fight sawdust by find blocks to split that maximize leftover size. In real life seems to ensure that no large blocks around.
* Next fit: use first fit and remember last position. Tends to break down entire list in real life.
* Buddy systems: Round up allocations to power of 2 to make management faster. Used by Linux, FreeBSD.
* Memory usage patterns
* Ramps
* Peaks: use Arena allocation. Allocate just by moving pointer and free together. Save size tag space (?).
* Plateaus
* Slab allocation: useful when allocating many instances of same struct. A slab is multiple pages of contiguous physical memory. A cache is multiple slabs and only for one kind of object. Then we can use bitmap to manage and avoid internal fragmentation. Used in FreeBSD and Linux, implemented on top of buddy page allocator.
* Simple, Fast Segregated Free Lists. TCMalloc. Use lists and tree to record free block of different sizes. Fast small alloc without size tag. But might waste space when keeping the data structure.
* Inside `malloc()` move heap (program break) up by some size using `sbrk()`. But it is tricky to return memory to the system because we might not be freeing the last object. In reality we use `mmap()` and `munmap()`.
## I/O and Disks
* I/O device interfaces
* Port: The usual connection point.
* Bus: PCI/PCIe, expansion bus for slower devices.
* Controller: electronics that operate port, bus or directly on devices.
* Control:
* I/O instructions: `in` and `out` instructions on x86. Read and write device interface registers.
* Memory-mapped I/O: device registers appear as memory locations
* Status: Polling vs Interrupts: If the device is really fast (network card), polling is better.
* Data: programmed I/O v.s. direct memory access (DMA). DMA avoids data copying to memory. CPU only handles control requests. Let the device read and write memory.
* Use abstraction to handles different devices. E.g. File system > Block layer > Driver > Hard Drive
* Hard disk
* Provide 512B (\~ 4KB) atomically write.
* Seek (move head to the right track) cost most. Can be 4-10 ms. Rotate time can be 4ms if 7200 RPM. Transfer time is only 5us. So disk is good for sequential bad for random read.
* Disk scheduling
* First come first served
* Shortest seek time first: can cause starvation.
* Elevator (SCAN). SSTF but next seek must be in the same direction. Good locality and bounded waiting. But cylinders in the middle get better service and might miss locality SSTF could exploit. CSCAN: Only sweep in one direction. Very commonly used algorithm in Unix.
* Flash memory: faster but limited number of overwrites (wear out) and limited durability.
## File Systems
* Main tasks
* Don’t go away (ever)
* Associate bytes with name (files)
* Associate names with each other (directories)
* Can implement file systems on disk, over network, in memory, in non-volatile ram (NVRAM), on tape, w/ paper.
* Trends and observation
* Disk bandwidth, cost/bit and also CPU/memory improves exponentially
* Seek time and rotational delay is the bottleneck
* Major goal of FS design: operations have as few disk accesses as possible and minimal space overhead of content (file metadata)
* Content in a file, files in a directory tend to be used together
* File: named bytes on disk. Has properties (flags, timestamps) and type (encoded in the name or contents).
* Compare FS to VM: Both are doing mapping, CPU time not a big deal in FS but need to limit disk accesses.
* File access methods: sequential, random, indexed (file is like a structured kv), record (file is like an array)
* Index node or inode: The structure that tracks a file's sectors.
* Sector allocation scheme
* Contiguous allocation: inode records location and size. Like VM segmentation this causes external fragmentation.
* Linked files: inode records the location of first block. A free list records empty blocks. Each content block points to the next block in the file. This is in fact random accesses on disk. Bad for both reading the whole file and random access within the file.
* DOS FS: Put the links (including starting block position and end of file) in fixed-size file allocation table rather than content blocks. Easier for caching.
* Indexed files: Each file has an array holding pointers to all the content blocks. Good for random access now. But this array itself may need large chunk of contiguous space. Same problem as the single layer page table in VM.
* Multi-level indexed files (Unix inodes): First 12 pointers in the array are direct blocks pointing to the content block. Then single, double, triple indirect pointers. Plus some file metadata.
* Inode array: location and size fixed when disk initialized. The index of an inode in this array is called i-number.
* Directory: logical locations of the files. Directory itself is a file. Content is the file names and their i-numbers.
* `/`, `.`, `..` provided by the FS.
* `~`, `*` provided by the shell program.
* Hard link and soft link
* Hard link, synonym: `ln`. File not removed until all synonyms are removed. Inode of the file keeps a reference count.
* Soft link, symbolic link: `ln -s`. File may even not exist at all. Reference count unchanged.
* File Buffer Cache: system wide blocks r/w cache. Compete with VM for memory. Also needs replacement algorithms.
* Write cache: periodically flush to disk or forced to flush by `fsync`.
* Read cache: often read ahead to exploit locality
* File sharing: concurrency control and protection
* Access control list: for each file, maintain a list of users and their permitted actions. Easier to manage, but can be bad for performance if there are too many users.
* Capabilities: The permitted actions on each file of a user.
* In Unix, ACL is used on files, capabilities are used in file descriptors.
## Advanced File Systems
* Original Unix FS only gets 2% of disk maximum transfer rate when reading from disk. Because the blocks are too small (and large number of the indexes. Cause lots of disk access), free list is unorganized and often fragmented, inodes and content blocks are far away, the locality of files inside a directory is not utilized.
* Fast File System for BSD Unix:
* Larger block size: tradeoff between bandwidth and fragmentation. Improve by split block like malloc.
* Free list: use bitmap
* Locality: try to put file inode and content blocks, files inside the same directory in the same cylinder group. Each group now works as a mini FS.
* Log-structured File System: Writes are append-only. Optimize for smaller and random writes. Also not agnostic to disk geometry.
* How to read latest: use inode map. inode number -> latest inode location. inode map are segmented.
* Disk cleaning
## File System Crash Consistency
* Bitmap, inode, data blocks. Different writes before the crash leaves different inconsistent states. Some are not fixable. Some can be fixed by tools like file system checker (FSCK).
* Journaling
* Physical journaling: write full transaction to journal space.
* Logical journaling: write logical record of the operation
* Different types: Data journaling, Metadata journaling, ordered mode
# Parallel Programming
My notes after taking Randal Burns's JHU CS 601.320/420/620 Parallel Programming course.
## Amdahl's Law
1. Speedup
$$Speedup = \frac{T(1)}{T(n)}$$
T(1) = time to execute task on a single resource. T(n) = time to execute task on n resources.
2. Amdahl's Law: theoretical speedup of the whole task is limited to the fraction can be improved
$$Speedup = \frac{1}{1-p+\frac{p}{s}}$$
* $$p$$ is the Amdahl's number, the proportion of execution time that benefits from improved resources, i.e. the parallel part
* $$(1-p)$$ is the portion that does not benefit. i.e. the serial part
* $$s$$ is the speedup of the optimized part. It is equivalent to the number of resources $$n$$.
Speedup graph:
Speedup upper limit is $$\frac{1}{1-p+\frac{p}{\infty}} = \frac{1}{1-p}$$
Amdahl's Law usage:
* Estimating scalability based on the original implementation of the serial program
* Estimating Amdahl's number, the proportion of the parts that can be parallelized
3. Parallel Efficiency: Measures the efficiency of resources. It helps us decide how many resources we should put in.
$$E = \frac{S(n)}{n} = \frac{T(1)}{nT(n)}$$
## OpenMP
1. OpenMP is a parallel programming environment that can easily bring parallelism to a serial program. It supports both master/slave and fork/join execution model. Its fundamental principle is block parallelism (parallelize a block and run multiple instances of the block with parallel threads). It is often used for loop parallelism by simply adding a directive line ontop the loop code block.
* Merit: Incremental parallelism, simple to use, portable
* Limitations: hard to manage memory usage, no distributed capabilities, no parallel I/O
## MapReduce (Hadoop and GFS)
[MapReduce](https://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf) is **a programming model** that is easily parallelized. Google's original implementation runs ontop GFS. The open-source Hadoop! implementation runs on HDFS. Some details worth mentioning:
1. Input/output domain: Map is a transformation. So a Mapper reads text and can output any key and value type. Reduce is a collection. So a Reducer output different value type but doesn't change the key type.
2. Sorting guarantee: When shuffling, data are route to Reducer based the hash of key to achieve load balancing. So it is not sorted globally. Within one partition at Reducer the keys are sorted.
3. Parallelism cap: For Map, it is up to number of input (usually number of files). For Reduce, it is up to number of keys.
4. Implementation: Master/workers model.
5. System Issues:
* Master failure: Use checkpoint and restart
* Failed worker: Heartbeat liveness detection and restart
* Slow worker: Backup tasks
* Locality of processing to data: Big deal and they don’t really solve. But much subsequent research does
* Task granularity: Metadata size and protocol scaling (not inherent parallelism) limit the size of M and R
6. GFS:
* Google's world-changing distributed file system.
* Design for failures: Chunks are triple replicated.
* Out of band: Metadata and data are separated. Master/Chunkservers model.
* Append-only: Avoid contention to achieve good I/O.
## Resilient Distributed Datasets (Spark)
Notes for
RDD is **a distributed memory abstraction** that lets programmers perform **in-memory** computations on large clusters. It is implemented in Spark at Berkeley. They use Scala because it is concise and efficiency (static typing). It is functional and RDD does not require it.
1. Compared to MapReduce: RDD provides distributed memory abstraction that allow easy reuse of intermediate results (less I/O). This is helpful in iterative ML algorithms and graph algorithms, and iteractive data mining.
* MapReduce: one-time, functional programs and carries large I/O at every step
* RDD: Pipelined operations (lazy materialization of datasets), encourages memory reuse
2. RDD abstraction: a **read-only**, partitioned collection of records.
* Can only be created through **transformation** operation from data in stable storage or other RDDs. Examples of transformations: `map`, `filter`, `join`
* RDD are not actual data: RDD is not materialized. Each RDD stores its lineage, the set of transformations from source. This allows easy reconstruction if there is a failure.
* Tracking lineage: may think of it as a DAG graph. One important detail when implementing RDDs is the distinction between wide dependencies and narrow dependencies.
* Wide: one parent partition may be used by multiple child partitions. All parent partitions must be available and shuffled to the correct child node before next step.
* Narrow: one parent partition is used by at most one child partition. This is easily pipelined. Also it is easier to recover.
* The persistence and partitioning strategy can be configured in RDDs.
3. Spark Interface of RDD: transformations + **actions** (return values to application or export data to a storage, examples are `reduce`, `count`, `collect`, `save`)
* Lazy computation: pipelined transformations, only computed when there is an action.
* Persist: Encourages memory reuse. May still spill to disk if not enough memory.
4. Implementations:
* Job Scheduling: When an action is runned, scheduler generate a DAG of stages **separated by shuffle which is required in wide dependencies**. Tasks are assigned to machines based on data locality. In the original implementation, intermediate records are materialized just like MapReduce for wide dependencies.
* Checkpointing: Though not required, user may choose to checkpoint if the lineage is too long or there are wide dependencies.
## GPU