jeff

notebooks

Jan 1
Code a brute-force recursive backtracking solution to 279. Perfect Squares. The solution timed out, even with memoization. The AC solution uses bottom-up DP.

The difference between optimistic and pessimistic locking. Optimistic locking is when you read a record and take note of a version number, timestamp or hash, and check that the version hasn’t changed before you write to the record. Pessimistic locking is when you take an exclusive lock (Mutex) on the record until you have finished writing the record.

Optimistic locking is used when you don’t expect many collisions and don’t think anyone’s going to change your record while you’re reading it. For non-collision operations, optimistic locking is cheaper than pessimistic but if a collision does occur it’s more expensive because the version number needs to be re-read from the db.

Pessimistic locking is more expensive for normal non-collision operations but is efficient when many collisions occur in the system due to automatic retry capability.

So, for most web apps, use optimistic locking. Occasional dirty reads are ok. For applications where consistency is critical — such as financial applications — use pessimistic locking.

The difference between two prominent ORM patterns: Active Record and Data Mapper. When you load objects from the db with Active Record, those objects are directly connected to a single row in a table. Creation, updates, and deletes of objects will fire a db transaction immediately. Data Mapper, on the other hand uses “repositories” which are the pipes that translate objects into a database representation. Thus, when you create and load objects, any modification to those objects won’t be committed to the db until you persist and flush them. A data mapper is like git but for your entities. You need to persist (commit) your entities so the Data Mapper’s Entity Manager can track them, and flush (push) them when you want those changes to be pushed and actually changed in the db.

Active Record is great when there is little no logic in your app. Data Mapper is great when your business logic is complex and needs to be modelled via DDD, separating the domain from the app and infra layers of your server. Pure SQL is great when you need to optimize your queries, and can’t afford any misdirection with the abstraction that ORMs provide.

Jan 2
Actually grok what it means to create exports asynchronously. At run time, consumers consuming those exports might have an undefined import.

Regrok docker basics — containers, images, volumes, networks — while dockerizing a project.

Fix my typescript implementation of the Result type by overloading the definition of resultsAllOk with one version for different array lengths.

A Javascript function returning an object which accesses variables via closure is an implementation of the Factory pattern.

Builder patterns, generally, are applied to classes with constructors that have large parameter lists. Using an object with named keys and values fixes the readability, somewhat. However, if you need to enforce certain protocol like if X is set, then Y and Z must be too, then using a Builder is the way to go.

Builder pattern can also apply to function invocation. If the function’s parameters are complex, sometimes it makes sense to encapsulate that complex argument-creation logic in a Builder.

The revealing constructor pattern (only a thing in Javascript-land), and realize that native Promises use the revealing constructor pattern. Instantiating a new Promise takes an executor callback which the Promise will give a resolve and reject function as arguments to the callback. These two arguments are internals of the Promise that is being revealed only to the executor during instantiation. If you pass the Promise around, no one else has access to the resolve and reject functions.

Dependency injection is used to remove coupling to concretions, allowing more flexibility with plug-and-play architecture, and being able to test easier by injecting mock objects.

Monkey patching objects can be done using the Proxy pattern. Simply create methods which override the behaviour of the target object and not forward any calls to other objects.

Javascript has support for built-in Proxy objects with new Proxy(target, handler). Proxy objects are useful because they give us an easy way to proxy only the bits (methods) that we need to enhance, without having to explicitly delegate all other properties and methods.

Decorators are the same things as Proxies except Decorators add behaviour. That is, the class of Proxies of X is are subset to Decorators of X. Decorators and Proxies only differ in usage. The Proxy, Decorator and Adapter patterns are very similar, the difference between them can be appreciated from the perspective of the interface consumer: proxies provide the same interface as the wrapped object, decorators provide an enhanced interface, and adapters provide a different interface.

Jan 3
Solve Leetcode question Maximum Subarray in one go. It is an algorithm problem that was solved by a computer science prof, John Bentley in 1984.

The Template pattern is the “static” version of the Strategy pattern that uses inheritance instead of composition. Also realize that the State pattern is just a variation of the Strategy pattern, that swaps out an instance’s strategy based off it’s state.

Jan 4
First day of the Winter 2 2021 batch at Recurse Center! Lots of onboarding and meets and greets :)

Jan 5
The big picture of event sourcing. The idea is that your data is stored in a big log of events. You can think of event sourcing as the “functional” version of a relational db. All events are immutable and any modifications to events must be appended as a new event modification. This is super useful when you need to do any time series history-like functions on the data. For example, give me the data that occurred between Jan - Apr 2020.

Apache Hadoop implements mapreduce with distributed file systems.

Apache Spark implements mapreduce with distributed memory.

The default map function in Python is lazy.

Jan 6
Netstrings. A declarative encoding of a string that is used as basic building block for reliable network protocols. It’s used to simplify the exchange of byte strings.

It declares the string size up front, allowing applications to check in advance whether its as enough space to store the string. That’s why netstrings are often seen in network programming.

A netstring encoding of a string is [len]”:”[string]”,”. For example, the string “hello world!” Is encoded as <31 32 3a 68 65 6c 6c 6f 20 77 6f 72 6c 64 21 2c>, i.e., "12:hello world!,". [len]":"[string]"," is called a netstring. [string] is called the interpretation of the netstring.

QMQP (Quick Mail Queueing Protocol): a faster protocol than SMTP over high-latency connections. Don’t really know how it works though and I don’t want to dive deep into it now.

The BitTorrent protocol extended netstrings to also include numbers and collections list lists or maps.

BSON: a binary-encoded serialization of JSON-like documents. It’s designed to be more efficient in space. BSON also adds additional data types unavailable in JSON - BinData and Date data types. The Date type specifically is unavailable in JSON because Douglas Crockford didn’t want JSON to be coupled to Javascript. This allowed widespread adoption of JSON in other languages.

For every value, there is a single valid bencoding; there’s a bijection between values and encodings. This has the advantage that applications may compare bencoded values by comparing their encoded forms, eliminating the need to decode values.

Internet access is assymmetrical — there are more people downloading than uploading content. P2P addresses the problem by decentralizing the distribution. The burden on the network is spread among the downloader, rather than a central party.

URI identifies a resource either by location, name, or both. URI has two subsets: URL and URN. A URN is like the ISBN for a book. It uniquely identifies it. However, it does not locate it nor tell us where the book is.

Distributed hash tables — a distributed key value lookup service often used in P2P systems.

Constants in Rust are available at compile time which allow compiler optimizations like constant folding.

CGI (Common Gateway Interface. It’s a standard way of running programs from a web server instead of a file.

@decorator()foo() (python decorator syntax) is just sugar for decorator(foo)).

Packet switches have two types of delay: store-and-forward delays and queuing delays. Store-and-forward delays refer to the fact that a router cannot transmit a packet until it’s fully received it. Queueing delays refers to when a packet needs toe be transmitted onto a link but finds the link busy with the transmission of another packet.

The differences between circuit switching and packet switching. In circuit-switched networks, parties must reserve resources for communication. Telephone networks are examples of circuit-switched networks. As a consequence, some may have to wait for access to a communication link. A simple analogy is two restaurants: one that requires reservations and another that either requires nor accepts them. A packet-switched network does not reserve any link resources — it just sends a packet over the link.

Networking protocols work in layers and service models and that application and transport-layer protocols are usually implemented in software. Physical layer and data link layers are usually implemented in a network interface card (ethernet or wifi).

Each layer in networking has a header field and payload field.

Application protocols are simply about getting two processes to communicate. The interface they use to communicate is called a socket. Sockets are simply doors (numbers) for processes to listen to.

Transport-layer protocols provide logical communication between processes running on different hosts. Network-layer protocols provide logically communication between hosts.

Jan 9
Adjacency matrix representation of a graph are good for dense graphs. All the entries in the matrix are being used due to many edges.

Adjacency list representation of a graph is good for sparse graphs with few edges. Only edges that exist are recorded in the data structure.

The edge list representation of a graph.

Core graph theory algorithms: shortest paths, connectivity, negative cycles, strongly connected components, travelling salesman problem, bridges, articulation points, minimum spanning tree, network flow: max flow.

Jan 10
Rust has a high-level feel paired with low-level performance.

Rust’s distinguishing feature is its ability to prevent invalid data access at compile time.

Global interpreter lock (GIL). It’s a mechanism used in interpreted languages to limit execution of threads so the only one hardwre thread can execute at a time. The GIL is used to avoid sharing code that is not thread-safe with other threads. However, it prevents parallelism.

One of the main use cases of macros (“functions” that expand to code at compile time) is support for variadic parameters.

Numbers in Rust have methods. 24.5_f32.round() is valid Rust.

Casting is safest when promoting instead of demoting.

Rust includes some tolerances when comparing floating point values, namely, f32::EPSILON and f64::EPSILON.

Rust has a f32::NAN type. NaN values are never equal to other NaN values.

Indexing values in a for loop is slower than iterating over a collection. This is because indexing into a collection incurs a runtime cost for bounds checking.

Loop labels. They are identifiers prefixed with an apostrophe. `outer: for x in 0. This way, you can break out of a nested loop and return control to a non-direct parent loop.

Expression-based languages enables two patterns: 1) very concise helper functions and 2) condition variable statement.

All of Rust’s operators are syntactic sugar for a trait’s methods. During compilation, a+b will be converted to a.add(b).

In Rust (presumably other languages like Typescript too), type aliases are only used by your source code. Compilers won’t distinguish between the type alias and the primitive type. For ex, type ID = string when compiled will just replace string for IDs.

If you need the compiler to treat type aliases as a real type rather than alias in Rust, you can use “newtype” instead of “type”.

Reversing memory in a Vector minimizes allocation when data is inserted byte-by-byte (doubling strategy).

Methods aren’t simply the label for functions on objects. They are functions that don’t need to specify one of their parameters, and that parameter is of course the object. Methods allow objects to be implicit in function call.

Errors need to be handled in software because underneath, hardware is unreliable.

Enums are just type safe strings that the compiler knows about.

In Rust, for some type T, has three kind of types. T is owned, &mut T is exclusive, and &T is shared. This, in essence, is Rust ownership in one sentence.

A useful example explaining lifetime in Rust. If you try to give a buffer allocated on a stack frame to a thread, the compiler will won’t let you because the thread can live longer than the stack.

A Mutex provides safe mutations on shared data.

The upgraded version of a Mutex, the R/W lock. A R/W lock allows multiple readers, or one writer, but not both.

Locks provide safe wrappers around **shared** pointers.

In Rust, print, write, and format macros rely on Display and Debug traits. The trait implementations are what convert the {} to what is printed to the console.

The difference between *mut T and a *const T in Rust is minimal.

A pointer knows it’s referent’s width in bytes. This makes sense because it must know how many bytes to fetch from RAM.

In Rust, creating a raw pointer of any type is legal. However, dereferencing that pointer is what is unsafe, and hence must go in the unsafe block.

Fat pointers refer to dynamically sized types which contain a “length” information.

Another use case for when you would prefer allocating something on the stack versus the heap. It’s obvious that if your data grows at run time, you need to allocate it on the heap.

The CPU is responsible for translating virtual addresses to physical ones with the memory managed unit (MMU).

The translation lookaside buffer is the CPU’s address-translation cache.

The block starting symbol (.bss) section of an ELF. It’s the section that contains statically-allocated variables that have been declared but have not assigned a value yet.

handler.join() suspends execution of the current thread and waits for the child thread to finish.

Spawning more threads doesn’t mean performance will grow linearly. More threads ==> more overhead in memory ==> more threads to manage for the scheduler. Switches between threads also invalidates caches.

CPU intensive multi-threading doesn’t scale well past the number of physical cores.

Signals and interrupts are kind of opposites. Signals are a software-level abstraction associated with the OS. Interrupts are a CPU-related abstraction and associated with the system’s hardware.

Signals are a form of limited inter-process communication (IPC). They don’t contain context, but their presence indicates something.

Interrupts are raised by hardware and exceptions are raised by CPU. Both of them “interrupt” the current process and hand control to the kernel.

Exceptions come in three forms: aborts, faults, and traps.

SIGINT signals interrupt, usually generated by person. SIGTERM signals terminate, usually generated by another program. SIGKILL immediately terminates a program, without the ability to recover.

f(i32) -> () is used to create a signal handler in Rust.

To wriggle out of the constrained environment of a signal handler (no access to information from app), it’s sole responsibility is to set a flag. Then, the main function will regularly check the flag to detect if it’s been modified.

Jan 11
You can map over a Result in Rust. This makes sense because you’re just mapping a single value to another value. In Javascript, built-in map support must only be done to Iterators. (Oh, I’m back from a few more minutes of google). These things you can map over to turn A -> B are called functors in Haskell. In Rust, Options, Results, Iterators, and even Futures are functors. Neat.

Finish the bencode parser for matey.

Jan 12
One use of DFS in general graphs is finding connected components. We loop through all unvisited nodes in an adjacency list and for each node perform a DFS on it.

One use of BFS in general graphs is finding shortest path on unweighted graphs.

Grids are implicit graphs because we can determine a node’s neighbors based on our location within the grid.

Instead of storing multi-dimension coordinates in an object to place on queues, a potentially more efficient solution would be to use multiple queues, each queue representing one dimension of the coordinate.

A technique called rooting a tree. Rooting a tree turns an undirected acyclic graph into a directed acyclic graph (tree). This is easily done depth first.

How to find the centre of a tree when in UAG-form. The centre is always the middle vertex or middle two vertices in every longer path along the tree.

A technique to find isomorphic trees. Serialize them into a bracket-pair encoding, and check for equality on the two strings.

On top of depth-first and breadth-first search, there is also a family of algorithms called best-first search. Best-first search algorithms on graphs can find solutions to problems like the minimum spanning tree problem. One algorithm to solve this problem is called Prim’s algorithm.

Jan 13
The Cow type in Rust.

The difference between 1:1 and M:N (green) threads. PL’s that support 1:1 threading have one language thread per OS thread. M:N threading on the other hand supports M green threads per N OS threads.

In Rust, “runtime” refers to the code included by the language in every binary. Every non-assembly language will have some amount of runtime code.

Rust only supports 1:1 threading because M:N model requires large language runtime to manage threads. Having a large runtime is one of Rust’s non-goals.

JoinHandle.join() in Rust, which blocks the thread currently running until the thread represented by the handle terminates.

Go’s motto on concurrency and communication: Do not communicate by sharing memory; instead, share memory by communicating. It’s the idea of avoiding complicated locking and concurrent primitives with fixed memory addresses. And instead, opting for a simpler approach where threads send state over the channel and promptly, forget about it.

Rust channels. A rx can wait on the tx with rx.recv(). If it has other work to do, it can loop and execute a rx.try_recv() which returns a Result

The Arc type in Rust comes with a performance penalty. This makes sense because you need finer control with atomic operations.

root name server hard coded into DNS server (u have 13 of them). You ask them, where’s google.com? “Look idk, why don’t you ask the .com server”

Jan 14
String and Vec are smart pointers in Rust.

Smart pointers implement the Deref and Drop traits.

Rust cannot compute the size of a recursive type at compile time. To remedy this, wrap the recursive reference with a Box. Then rustc will know the size of the reference — it’s a box.

Box’s in Rust only provide indirection and heap allocation. If indirection is the only feature you need, use a Box, rather than other smart pointers available.

Rust substitutes references that implement Deref with *(y.deref()) if the value for y is needed (like for comparison).

Deref coercion in Rust. When the Deref trait is defined for types passed in as arguments, Rust will analyze and use Deref::Deref as many times as necessary to get a reference to match the parameter’s type.

In Rust, variables are dropped in the reverse order that they are created in.

The interior mutability pattern in Rust. We can use types that use the interior mutability pattern when we can ensure that the borrowing rules will be followed at runtime.

Alan Kay’s version of OOP is an architecture in which objects pass messages to each other.

Inheritance in traditional OOP languages is used for two purposes. 1. Code-reuse, and 2. Polymorphism (type
Jan 15
Hex encoding is for humans, not computers. It’s an abstraction for the raw number.

Percent encoding. When a character has a special meaning in a certain context, and a URI scheme says that it is necessary to use that character for some other purpose, then the character must be percent-encoded. Percent encoding a reserved character involves converting the character to its corresponding byte value in ASCII and then representing that value as a pair of hexadecimal digits.

#[tokio::main] function is a macro that transforms the async fn main() into a synchronous fn main() that initiales a runtime instance and executes the async main function.

Box is a trait object; it’s a stand-in type for any type inside a Box that implements the Foo trait.

When to use generic type parameters with trait bounds and when to use trait objects. Structs with generic type parameters with trait bounds can only be all of type T. They’re ok for homogeneous collections.

rustc monomorphizes functions and methods with generics, and creates nongeneric implementations for each concrete type that we use in place of a generic type parameter. The code that results from monormorphization is doing static dispatch.

This is the opposite of dynamic dispatch, which is when rustc can’t tell at compile time which method you’re calling. Rust uses dynamic dispatch with trait objects. There is a runtime cost when this look happens that doesn’t occur with static dispatch. Trait objects provide more flexibility (clients can implement the trait your structs and functions need), so it’s a trade-off between speed and flexibility.

The RefCell type in Rust. To compare, Box enforces the borrowing rules at compile time. RefCell enforces them at runtime. If you break the rules with Box, you’ll get a compiler error. With RefCell, you'll get a runtime error — your program will panic and exit.

rustc does not check for exhaustiveness in if let expressions.

Pattern matching can be refutable or irrefutable in Rust. let x = 5 is irrefutable. If let Some(x) = a_value is refutable.

Topological sort is used when figuring out build dependencies.

A topological ordering is just a fancy way for aligning all the nodes such that all edges point to the right.

Heap sort is similar to selection sort insofar to dividing the array into a sorted and an unsorted region. However, it differs in that it doesn’t perform a linear scan. It maintains the heap invariant for the unsorted part.

Learn and implemented Dijkstra’s shortest path algorithm.

Jan 16
The relaxation modelling strategy.

If a graph has a negative weighted cycle, there is no shortest path. This makes intuitive sense, because you can just keep taking that cycle to get a shorter path.

Jan 17
Applications are either data-intensive or compute-intensive.

Data tools no longer neatly fit into traditional categories. There are datastores that are also used as message queues (Redis) and there are message queues with database-like guarantees (Apache Kafka). The boundaries are becoming blurred.

Many backends nowadays demand wide-range requirements that no single tool can no longer meet. The work is broken down into tasks that can be performed efficiently on a single tool.

For example, you can have an application-managed caching layer, a full-text search server separate from your main database. It’s the application code’s responsibility to keep those caches and indexes in sync with the main database.

We are now not only an application developer, but also a data system designer. The three things you should keep in mind when designing data systems is reliability, scalability, and maintainability,

A good mental model for the separation of concerns within the computing stack. App devs decide on how to model the real world with objects and data structures. Infra devs decide on how to model data in terms of bytes in memory, disk or network. Hardware ppl figure out how to represent bytes in terms of electrical currents, and pulses of light.

Single-server systems requires planned downtime when rebooting the machine. A system that can tolerate machine failure can be patched one node at a time, without downtime of the entire system. This is called a rolling upgrade.

Different database models.

The hierarchical database model structures data as a tree of records. This was restrictive as it only modelled one to many relationships. This was actually quite similar to the JSON model some NoSQL databases use today.

To solve the limitations of the hierarchical model, two solutions were proposed. The network model, and the relational model. The “great debate” between these two camps lasted for much of the 1970s.

The network model is a generalized graph structure which allows each record to have multiple parent and child records. The links between records though were not foreign keys, but more like pointers in a programming language. The only way of accessing a record was to follow a path from a root record along these chains of links. This was called an access path. Similar to a traversal of a linked list.

The network model was displaced by the relational model. It was more high-level and more declarative. Data was layed out in the open. A relation (table) is simply a collection of tuples (rows). You can read any row you want. In a relational database, the query optimizer automatically decides which parts of the query to execute and in which order. These choices are effectively the “access path”. If you want to query your data in new ways, you can just declare a new index, and queries will automatically use whichever indexes are most appropriate.

A cool term, the object-relational mismatch. I can now explain to others briefly, in one sentence, ORMs are made to solve the object-relational mismatch. It’s a translation layer.

You achieve better locality if your data is encoded in denormalized JSON, rather than in a normalized, relational way

If your database does not support joins (some NoSQL dbs), you have to emulate a join in application code by making multiple queries to the database. In this sense, document databases have reverted back to the hierarchical model in one aspect: storing nested records.

Arguments for document databases: schema flexibility, better performance due to locality, and for some applications it’s closer to the data structures used by the application. Also, sometimes your application has a document-like structure (a tree of one-to-many relationships). The relational model counters by providing better support for joins, and many-to-one and many-to-many relationships.

All data models (document, relational, and graph) have structure. It’s just a question of whether the schema is explicit (enforced on write) or implicit (handled on read).

Schema-on-read is similar to dynamic type checking whereas schema-on-write is similar to static type checking. This is why document databases were popular with Javascript developers. Inherently, since they were already using Javascript, they probably didn’t mind the non-strictness of a document db. On the other hand, it’s not surprising that devs who enjoy compile-time type checking prefer relational databases.

Schema-on-read is advantageous if the items in the collection don’t all have the same structure for some reason. Either, 1. A collection inherently has different types or 2. The structure of the data is determined by external systems over which you have no control and which may change at any time. In situations like these, a schema may hurt more than it helps.

The locality advantage for document databases only applies if you need large parts of the document at the same time. Document databases typically need to load entire documents. So if you want a small portion of it, you are wasting memory on large documents. This is why it’s generally recommended to keep documents fairly small and avoid writes that increase the size of the document. This performance limitation significantly reduces the set of situations in which document databases are useful.

Document and relational databases are converging. Relational databases are adding support for JSON documents, and document databases are adding support for relational-like joints. A hybrid of the relational and document model is a good route for databases to take in the future.

Choosing a data model is not just on how the software is written but also on how we think about the problem that we’re solving.

In one sentence, declarative languages make you write what you want, not how to achieve that goal.

Declarative languages also benefit developers who are making a system. It gives them more flexibility to change the internal implementation. Declarative languages is like an API, where the application in question is more low-level like a database or programming language, rather than a backend REST server. It also allows the implementation to execute in parallel. Imperative code is hard to parallelize across multiple cores because it specifies instructions that must be performed in a particular order. Declarative languages specify only the pattern of the results, not the algorithm that is used to determine the results.

Keys and indexes are important with OLTP’s because our application needs to respond to requests quickly. On the other hand, OLAP, what’s important is encoding data very compactly to minimize the amount of data that the query needs to read from the disk, hence making queries faster. Column-oriented storage helps achieve this goal.

OLTP system’s bottleneck is disk seek time, whereas OLAP systems bottleneck is disk bandwidth.

OLTP systems are either log-structured or update-in-place. Update-in-place systems are often implemented with B-trees.

Databases can encode their data in three ways.

1. PL-specific encodings which are restricted to a single PL and fail to provide forward and backward compatibility

2. Textual formats like JSON, XML, and CSV. These formats are vague about datatypes, and optional schema languages. They are sometimes helpful and sometimes a hindrance.

3. Binary schema-driven formats like Thrift, Protocol Buffers, and Avro. They allow compact, efficient encoding with a clearly defined forward and backward compatibility semantics. The downside is that data must be decoded before it’s human-readable.

Jan 18
System blocks are made up of database, cache, search indices, and batch processing.

Reliable, it continues to work correctly even when there are faults (hardware faults and software faults) Fault tolerance prevents failures in the system.

Many companies test if their system works. Not many test if it can survive faults/failures.

The Rust prelude is a list of things that Rust automatically imports in every program. It’s focused particularly on traits which are used in almost every single Rust program.

std::marker is a module with mainly traits that simply “mark” a type, without having any kind of additional functionality. They simply communicate to the compiler that some types are used in a certain way. That’s why the trait definitions are empty.

Network protocols reserve bits/bytes to gain additional features in the future.

Cloning in Rust should be used by calling code, not “library” functions. Cloning is at the highest level abstraction. The decision making for heap allocations is higher up in your application.

Rust implicitly infers some reference types. Like &Vec to &[T] and &String to &str

Bytes can represent very different things. For instance, raw numbers (truth), or ascii characters. 1 in bytes !== '1'

Jan 19
It’s easier to remove code and abstract it out later rather than add stuff in.

The await in Tokio’s tcp_socket.write().await? is implicitly the reliableness of TCP. If it throws, then the message didn’t get sent.

A program is well defined if no possible execution can exhibit undefined behaviour. If a language’s safety checks ensure that every program is well defined.

You can’t assign an array at an index greater than the length in Python. It’s not undefined behaviour, and so Python is type safe. Being type safe is independent of the language checking types at compile time or run time. Python, Java, Javascript, Ruby, and Haskell are type safe. C is not.

Rust aims to resolve type safety in systems programming. C is a systems programming language because it’s fast, but not type safe. The other languages are type safe but have GC. Rust bridges that gap.

Jan 20
Rust doesn’t do any lifetime inference in functions. It doesn’t want to change the meaning of their contract. Closures are more flexible.

String slices live for the lifetime of your program because they are in your binary. These are called static string slices.

&[T] accepts Vec, and VecDeque as arguments because of reference coercion.

Index operator’s are fallible due to design decision. foo[0] is the same as foo.get(0).unwrap(). Anything in Rust can panic.

Jan 21
You often see Arc and Mutexes togheter in the wild. It combines shared ownership and mutation.

Shared memory is used to share memory. Channels are used to send messages, and units of work.

The terms concurrency and asynchronous code usually refer to two separate things. Concurrent code means multiple threads running (either in parallel or interleaved). Asynchronous code implies the existence of an event loop and green thread.

Green threads are called green threads because the the original thread library for Java was made by The Green Team at Sun Microsystems.

Rust MPSC channels don’t support “putting back” units of work onto the channel. If you need to support fallible operations you must create a new return channel.

Jan 22
Channels in Rust must have both sides of the channel (sender and receiver) be connected. If not, the channel returns SendError and RecvError.

Channels have underlying FIFO ordering, but the problem is Async await is basically just a scheduler implemented in user-land instead of the OS in kernel-land.

Async channels in Rust are unbounded because they need to support asynchronous sending. Sync channels are bounded because they are blocking.

Futures are lazy. The most common way to run a Future is to .await it. When .await is called on a Future, it will attempt to run it to completion.

The constituents of a system depend on the eye of the beholder. For instance, the aircraft’s components, according to engineer includes the body, wings, control surfaces, and engines. The components in the captain’s point of view is a flying object, the seats, flight attendants, and gallery.

Complexity in systems is hard to measure. Instead of quantifying complexity, we instead look look for signs. Those are 1. Large number of components, 2. Large number of interconnections, 3. Many irregularities, 4. A long description, 5. A team of designers, implementors, or maintainers

Complexity arises from the accumulation of requirements. This results not only in accumulation of individual complexities of new requirements but also complexities from their interactions. It’s a factorial explosion. This is why the computer is so complex. It’s a personal system with a well-organized file system, storage, I/O devices, network, security, usable, reliable, and low-cost. This whole idea is the principle of escalating complexity. Adding a requirement increases complexity out of proportion.

A principle in systems is to avoid excessive generality. If it is good for everything, it is good for nothing.

Common techniques to cope with complexity are modularity, abstraction, layering, hierarchy.

Software has no noise, unlike analog. If you take a photocopy of a photocopy, it’s worse than the original. Unlike analog systems, digital systems can grow in complexity until they exceed the ability of their designers to understand them.

The three abstractions for computer system components is the memory, the interpreter, and the communication link.

Operating system layers usually exhibit a phenomenon called layer bypass. Rather than completely hiding the lower hardware layer, an OS usually hides only a few features of the hardware layer, such as dangerous instructions. The remaining features of the hardware layer pass through the operating system layer for use directly by the application layer.

Hardware devices are specialized computers (interpreters) that simply implement I/O programs. For example, the disk controller is an interpreter of disk I/O programs. It maps disk addresses to track and sector numbers and moves data from disk to memory.

The reason why we have open/close in addition read/write on file systems was originally for performance reasons. Passing in the file name to read/write every single time would be very expensive, due to file name/address resolution.

More recently, file systems use open/close to make the beginning and end of an atomic operation. One cost however to using the open/close model is that the file system must main per-client state in the form of the resolved file name and cursor(s). You can design a stateless file interface such as the Network File System.

The file is such a convenient memory abstraction that some systems (like Unix) use the file interface for *every* input/output device. In these systems, files are not only for non-volatile memories (like disks), but they are also a convenient interface to the keyboard, the display, communication links, etc. The file system acts as an intermediary that provides a uniform, abstract interface. One feature of this uniform interface is that application programs can replace an I/O device with a file, or vice-versa by simply rebinding the name.

The unix file system has layers. In order, the layers are, from top to bottom: symbolic links, absolute path name, path name, file name, Inode number, files, blocks.

The bottom layer of the Unix file system is the block layer. Storage on disk is divided into fixed-size units called blocks. It’s the smallest allocation unit of disk space. Modern Unix file systems use 8kb blocks. The names of these blocks are numbers. A storage device can be viewed as a context that binds block numbers to physical blocks.

Modern Unix file systems often use a bitmap for keeping track of free blocks.

The next layer in the file system is the file layer. Users need to store items that are larger than one block in size. To support such items, Unix file system introduces a layer for files. A file is a linear array of bytes of arbitrary length. The file system needs to record in some way which blocks belong to each file. To support this requirement, the unix file system creates an index node, or inode for short, as container for metadata about the file.

Jan 23
Exceptions lie at the intersection of the hardware and the operating system. Moving up one level of abstraction and you reach processes and signals which lie at the intersection of applications and the operating system.

System calls to the OS trigger trap handlers. Trap handlers run the system code, process is pit to sleep, system code is complete, sends an interrupt, and the OS wakes up the process.

OS give the illusion of logical flow to applications through processes.

A signal is a small message that notifies a process that an event of some type has occurred in the system. A common use case for signals is for the kernel to expose exceptions to processes. Signals can also be used by other processes to message processes too. A process can even send a signal to itself

When receiving a signal, the process can either ignore, terminate, or catch the signal with a user-level function called the signal-handler.

A signal that has been sent but not yet received is called a pending signal.

Every process belongs to exactly one process group. By default, a child process belongs to the same process group at its parent. But a process can change the process group of itself or another process by using the setpgid system call.

Using a negative process id like /bin/kill -9 -PID sends a SIGKILL signal to every process in the process group.

When we pass the address of a handler to the signal system call function, it’s known as installing the handler. The invocation of the handler is called catching the signal. The execution of the handler is referred to as handling the signal.

Linux provides implicit and explicit mechanisms for blocking signals. Implicit blocking mechanism, whereby the kernel blocks any pending signals of the type currently being processed by a handler. And Explicit blocking mechanism where applications explicitly block selected signals using sigprocmask.

Each process has its own distinct descriptor table while all processes share the same open file and v-node tables.

Input/output is the process of copying data between main memory and external devices such as disk, network, terminals, etc.

Std I/O libraries in C are built on Unix I/O

All I/O devices such as networks, disks, and terminals are modelled as files and all input and output is performed by reading and writing the appropriate files. This uniform mapping allows to create a common app-level interface, known as Unix I/O.

To open a file, a process asks the kernel to open a file at the given path, and the kernel returns a small nonnegative integer called a descriptor. Each process created by a Linux shell begins life with three open files: standard input (descriptor 0), standard output (descriptor 1), and standard error (descriptor 2).

When a process closes the file, it asks the kernel to close the file, and the kernel responds by freeing data structures it created to keep track of file info. It also restores the descriptor to a pool of available descriptors.

A directory is a file consisting of an array of links, where each link maps a filename to a file, which may be another directory. Each directory contains at least two entries. . (dot) is a link to the directory itself and .. (dot-dot) is a link to the parent directory.

A socket is simply a file that is used to communicate with another process across the network.

As part of its context, each process has a current working directory that identifies its current location in the directory hierarchy. You can change this with cd.

The kernel represents open files using three related data structures.

1. Descriptor table Each open descriptor entry points to an entry in the file table.

2. File table The files in the file table are all open files shared by all processes. Each file table entry consists of a file position, a reference count, and a pointer to an entry in the v-node table. Closing a descriptor decrements the reference count in the associated file tabla entry. The kernel will not delete the file table entry until its reference count is zero.

3. v-node table Each entry in the v-node table is shared by all processes. Each entry contains most of the information in the stat structure.

In the context of the C Standard library, a stream is an open file.

UDP extends IP insofar as providing support for process to process communication with datagrams instead of simply host to host.

The two families of storage engines is log-structured and page-oriented.

Any kind of index on a storage engine slows down writes since indexes need to be updated every time data is written. This is a trade-off in storage systems. Well chosen indexes speed up reads but every index slows down writes.

Jan 24
RWLocks are more expensive than Mutex’s because they have two locks.

Arc/Rc solves ownership, Mutex/RwLock solves mutability

CPUs can either have a strong memory model or weak memory model. Strong ordering gives a few guarantees: 1.reads are not reordered with other reads 2. writes are not reordered with older reads 3. writes to memory are not reordered with other writes

Critically, it also includes one non-guarantee: reads may be reordered with older writes to different locations but not with older writes to the same location.

CPU has three levels of cache. L1, L2 L3. L2 and L3 are shared between cores, L1 is a per-core cache

We can think of the MESI caching protocol for ourselves by thinking that every cache line in the CPU has an enum with four states attached to them. Modified, Exclusive, Shared, and Invalid.

Jan 25
Os doesn’t trust your code, and so has preemptive scheduling. Application-based event loops do, and so has cooperative scheduling.

Lock contention control depends on PL-implementation, it’s not OS dependent

Threading is about workers, asynchrony is about tasks

In async code, *there is no thread*

Most tasks are not processor-bound. For processor-bound tasks it makes sense to hire as many workers (threads) as there are processors (cores), and assign one task to each worker, assign one core to each worker, and have each core do the job of nothing else but computing the result as quickly as possible.

But for tasks that are not waiting on a processor, you don’t need to assign a worker at all. You just wait for the message to arrive that the result is available and *do something else while you’re waiting* When that message finally arrives then you can schedule the continuation of the completed task as the next thing on your to-do list.

System calls poll and select are inefficient because the CPU asks the OS on file descriptors “are there updates now? How about now? How about now? How about now?” The solution to this is either signal driven I/O or epoll. Apparently epoll is just better.

mio in Rust is a fast, low-level I/O library for Rust which focuses on non-blocking APIs and event-based notifications. It’s a thing wrapper over epoll, kqueue, IOCP, et al. The structure of mio goes like: source input -> [poll(registry)] -> event output

You register a source with poll.registry().register(Source, Token, Interest) and you poll to a specific event output (queue) with poll.poll(events: Events, timeout: Option(Duration)).

You can see that both the input and output sources are not coupled to Poll

libuv is an abstraction over kqueue, epoll, and IOCP. libuv/mio ask the OS to watch a source (lets say a socket) and put an event notification in the queue. Before, nodejs async was implemented with libev (bingo wheel select ) and libeio (thread pool for fs). We need a thread pool for fs because events don’t make sense with file systems. If a file has been updated in the middle an event makes no sense? So nodejs replaced libev and libeio with libuv which uses an event queue.

Jan 26
In networking applications, separate parsing from business logic.

Every call to TcpStream::read results in a system call. A BufReader performs large infrequent reads on the underlying Read and maintains an in-memory buffer of the results. Thus, BufReader’s can improve the speed of programs that make small and repeated read calls to the same file or network socket. It does not help when reading very large amounts at once, or reading just a few times.

Jan 27
Tasks are a handle for futures to give to underlying threads. If a thread thinks the future can be advanced, the thread will call task.notify(), which means the executor will poll the future during the next iteration of the executor. If task.notify() is never called, than the executor will never poll the future again. If you’re implementing a future in Rust, you must arrange for yourself to be awoken again.

Futures in std describe the interfaces of Futures. tokio provides an implementation.

tokio reactor is the bridge between operating systems and the future model

All parallel code is concurrent. The opposite is not true.

Jan 28
In Heroku, a slug is is a bundle of your source, dependencies, language runtime, and compiled code, ready for execution.

In Heroku, dynos are isolated, virtualized Unix containers, that provide the environment required to run an application.

In Heroku, releases are an append-only ledger of slugs and config vars. They are the aggregate entity that binds slugs and config variables.

Implementing sticky sessions with HTTP cookies is the most reliable and least invasive means compared to IP addresses or URL-based mechanisms.

The hierarchy of GitHub Actions is Events > (trigger) > Workflows > Jobs > Steps > Actions

The xv6 bootloader loads itself into memory at physical address 0x100000. It places the kernel at 0x100000 rather than 0x0 because the address range 0xa0000:0x100000 contains I/O devices.

Common sector size was 512 bytes until 2010. Now, many manufacturers start migrating to 4KB sectors.

Even hard drives can have DRAM buffers in the drive controller. Caches are everywhere.

States transfer rates for hard disks are always higher than effective transfer rates. The advertised transfer rate may be the rate at which bits can be read from the magnetic media by the disk head. That is different from the rate at which blocks are delivered to the operating system.

Nonvolatile Memory (NVM) Devices can bee ore reliable than HDDs because they have no moving parts can can be faster because they have no seek time or rotational latency.

Magnetic tape was used as an early secondary-storage medium before HDDs. Random access is a thousand times slower than random access to HDDs and a hundred thousand times slower than random access to SSDs.

Storage devices are addresses as large one-dimensional arrays of logical blocks, where the logical block is the smallest unit of transfer. Each logical block maps to a physical sector (HDD) or semiconductor page (SSD).

Disks now have hundreds of sectors per outer track and tens of thousands of cylinders within the entire drive.

In the past, HDD interfaces required that the host specify which track and which head to use, and much effort was spent on disk scheduling algorithms.

Absolute knowledge of head location and physical block/cylinder locations is not possible on modern drives due to the drive abstracting it away. But, as a rough approximation, algorithms and processes can assume that increasing logical block addresses mean increasing physical addresses, and logical block addresses close together equate to physical block proximity.

Some algorithms for disk scheduling are FCFS, and the SCAN (aka elevator algorithm). Sometimes the extra overhead of scheduling computation isn’t worth it.

Some drive schedulers maintain separate read and write queues, and gives reads priority because processes are more likely to block on read than write.

NVMs don’t need scheduling algorithms because they don’t have moving disk heads. No need to minimize the amount of disk head movement. FCFS is usually used.

Sequential access is optimal for mechanical devices like HDD and tape because the data is contiguous. Random access I/O however causes lots of disk head movements and so is much faster on NVM. An HDD can provide hundreds of input/output operations per second, while an SSD can produce hundreds of *thousands* of IOPS.

Some operating systems can handle only one specific sector size.

Before an operating system can use a drive to hold files, the os still needs to record its own data structures on the device. It does so in three steps. 1. Partition the device. (Partition for os, partition for fs, etc) 2. Create volumes. 3. Logical formatting. The os stores the initial file-system data structures onto the system.

To increase efficiency, most file systems group blocks together into larger chunks, frequently called clusters.

The full bootstrap program is more sophisticated than the bootstrap loader: it’s able to load the entire os from a non-fixed location.

Low-level formatting also sets aside spare sectors not visible to the os. The controller can be told to replace each bad sector logically with one of the spare sectors. This scheme is known as sector sparing or forwarding.

A process control block (PCB) serves as the repository for all the data needs to start, or restart, a process. It contains process state, program counter, CPU registers, CPU-scheduling info, and memory-managed info.

Swap space is used in various ways by different operating systems, depending on the memory-management algorithms in use. Some systems implement swapping for holding entire process images including code and data segments. Others may simply store pages that have been pushed out of main memory. The amount of swap space needed on a system varies from a few megabytes to gigabytes.

In the past, Linux has suggested setting swap space to double the amount of physical memory. Today paging algorithms have changed for the better, and most Linux systems use considerably less swap space.

Swap space can either be 1. Carved out of the normal file system or 2. Be in a separate partition

Jan 29
To encapsulate the details of different devices, the kernel uses device-drivers to present a uniform device-access interface to the I/O subsystem.

A PCIe bus connects the processor-memory subsystem to fast devices, and an expansion bus connects relatively slow devices such as keyboard and USB ports.

PCIe is a flexible bus that sends data over one or more lanes. A lane is composed of two singling pairs, transmitter and receiver.

PCIe links may contain 1, 2, 4, 8, 12, 16, or 32 lanes.A PCI gen3 x8 has maximum throughput of 8 gigabytes per second.

Hard drives have disk controllers which is a chip with microcode and a processor to do many tasks: bad-sector mapping, prefetching, buffering and caching.

Writing millions of bytes to the graphics memory is faster than issuing millions of I/O instructions.

Naive way of accessing memory is for the system to poll the hardware devices. If the controller and device are fast, this method is reasonable. But if the way is long, than the operating system should switch to another task to not waste CPU time. This presents the idea of the hardware controller notifying the CPU when the device is ready for service. Moving from polling to pushing. This is called an interrupt.

The CPU hardware has a wire called the interrupt-request line that the CPU senses after executing every instruction. Most CPUs have two interrupt-request lines. 1. nonmaskable interrupt (unrecoverable errors that need to be handled), 2. maskable interrupt: it can be turned off aka “masked” by the CPU before the execution of critical instruction sequences that must not be interrupted.

The interrupt handler table has non-maskable events in entries 0-31, and 32-255 are reserved for maskable interrupts.

Traps setup by system calls are given a relatively low interrupt priority compared with those assigned to device interrupts. Executing a system call on behalf of a process is less urgent than servicing a device controller before its FIFO queue overflows and loses data.

A kernel must be multithreaded to support different priority interrupts. It can have a thread running a high priority interrupt handler, and another for low-priority interrupts.

When servicing a system call, the corresponding interrupt handler completes the user-level I/O by copying data from kernel buffers to the application space and the calling the scheduler to place the process in the ready queue.

For a device that does large transfers such as a disk drive, it’s wasteful to use an expensive general-purpose processor to watch status bits and to feed data into a controller register one bytes at a time. This is called programmed I/O (PIO). Computers avoid burdening the main CPU with PIO by offloading the work to a special-purpose processor called a direct-memory-access (DMA) controller. When the entire transfer is finished, the DMA controller interrupts the CPU.

The major types of I/O devices are block/character devices, networking devices, and clocks/timers.

Functional languages do not maintain state and therefore are generally immune from race conditions and critical sections.

Shared memory for IPC can be faster than message passing, since message passing systems are typically implemented using system calls and thus require more time-consuming tasks of kernel intervention. In shared-memory systems, system calls are required only to establish shared memory regions. Once shared memory is established, all accesses are treated as routine memory accesses, and no assistance from the kernel is required.

Typically, a shared memory region resides in the address space of the process creating the sacred-memory segment. Other processes that wish to communicate using this shared-memory segment must attach it to their address space. Normally the os tries to prevent one process from accessing another processor’s memory. So shared memory requires that two or more processes are to remove this restriction.

There are two types of parallelism: data parallelism and task parallelism. Data parallelism distributes subsets of the same data across multiple computing cores and performs the same operating on each core. Task parallelism distributes not data but tasks (threads) across multiple computing cores.

The many-to-one multithreading model allows the developer to create as many user threads as they wish, but it does not result in parallelism, because the kernel can schedule only one kernel thread at a time. The one-to-one model allows greater concurrency, but the developer has to be careful not to create too many threads within an application. The many-to-many model suffers from neither of these shortcomings: developers can create as many user threads as necessary, and the corresponding kernel threads can run in parallel on a multiprocessor.

A race condition occurs when a final result depends n the particular order in which concurrent accesses to shared data occur.

Atomic types in Rust such as AtomicUsize allow mutation across threads, but only for small values. Instead of using Arc(Mutex(usize)) you could just use an Arc(AtomicUsize). Atomic types do not require locking because they are manipulated through atomic hardware instructions. Use atomics when you can, they are much cheaper than using locks because they have no overhead.

Two hardware strategies for atomics are test and set and compare and swap.

It’s important to note that although atomic variables provide atomic updates, they do not entirely solve race conditions in all circumstances. If you need to perform extra logic after reading from an atomic, you should use a lock because your code should be part of the “transaction” to shared memory.

Two strategies when a thread cannot achieve lock on a resource wrapped in a Mutex is 1. Spin locks or 2. Sleeping. Spin locks are preferable when the wait time is short. You don’t want all the overhead of thread context switching. However, if the wait time is long, you want the thread to sleep so you can schedule another thread on the core and not waste CPU cycles.

To prevent race conditions, each process must request permission to entire its critical section. A critical section is segment of the code where the process/thread accesses data that is shared with another process/ thread.

The kernel is very prone to race conditions. It has many threads of execution for maintaining memory allocation, maintaining process lists, and for interrupt handing.

A Semaphore is similar to a mutex lock but can also provide more sophisticated ways for processes to synchronize their activities. A semaphore is an integer variable that is accused only through two standard atomic operations: wait() and signal(). Each semaphore has an integer value and a list of processes list. When a process must wait on a semaphore, it’s added to the list of processes. Later, when a signal() operation updates the counter, the semaphore will remove one process from the list of waiting processes and awake it.

Mutexes, semaphores and other concurrency primitives are implemented with hardware-level atomics.

Jan 30
A browser is a wrapper around ftp

Jan 31
#[tokio::main] is a macro that initializes a runtime instance and executes the async main function.

A Tokio task is an asynchronous green thread. They are created by passing an async block to tokio::spawn.

tasks in Tokio are very lightweight, they only require 64 bytes of memory. Applications should feel free to spawn thousands, if not millions of tasks.

In Tokio, the term handle is used to reference a value that provides access to some shared state.

Tasks spawned by tokio::spawn must implement Send. This allows the Tokio runtime to move tasks between threads while they are suspended at an .await

A common error is to unconditionally use tokio::sync::mutex from within async code. An async mutex is a mutex that is locked across calls to .await

As a rule of thumb, using a synchronous mutex from within asynchronous code is fine as long as contention remains low and the lock is not held across calls to .await

If contention on a synchronous mutex becomes a problem, the best fix is rarely to switch to the

Tokio mutex. Instead, consider switching to a dedicated task to manage state and use message passing, star the mutex, or restructure the code to avoid the mutex. As a last resort, you can use Tokio’s asynchronous mutex which is held across an .await without any issues, It should be used as a last resort because an async mutex is more expensive than a regular mutex.