CS 544 — MASTER: Decks 2–5

All 103 official Anki cards: Networking (39), Memory (17), Compute (26), Storage (21). Includes labeled corrections to two Compute Python API examples. Source: https://tyler.caraza-harter.com/cs544/f26/anki.html

How many bits are in a MAC address?

48

What does the prefix of a MAC address indicate?

The vendor/manufacter that produced the NIC

This is so that we can achieve globally unique MAC addresses (each vendor gets a prefix, and is expected not to reuse the same suffix for different devices).

How can you see the MAC addresses and IP addresses for your NICs?

ip address

What is a virtual NIC that is only reachable from the local machine, and what IP address does it use?

The "loopback" device, which has address 127.0.0.1

What is a network?

A collection of computers that can send each other messages by MAC address

Within a network, what device can forward data that is sent to a specific MAC address?

A switch

What is the device that connects multiple networks to form an internet, or the Internet?

a router

How many bits does an IPv4 address contain, and how many possible addresses are there?

32 bits, and about 4 billion possible addresses

What does the prefix of an IP address tell you?

It identifies the network

Why do routers forward based on IP address rather than MAC address?

Because there are too many MAC addresses in the world, and forwarding tables would need to be too big if every router needed to remember where every MAC address lives. With IP addresses, IPs with the same prefix are on the same network. A router just needs to know where to forward data to get it closer to the correct network.

The following are private IP ranges, meaning multiple networks can use the same IPs from these ranges internally: 192.168.0.0 to 192.168.255.255 172.16.0.0 to 172.31.255.255 10.0.0.0 to 10.255.255.255 What device/software can let us connect to machines using these IPs, given they are not unique?

A NAT (network address translation). It can map a unique public address to one or more private IPs within a network.

What is something that both UDP and TCP add in addition to what IP provides?

The both provide port numbers, which let us direct communication to a specific process on a machine

What is something that TCP provides that UDP does not?

TCP provides more reliable communication: retry when a packet is dropped buffer packets on receiving side and re-arrange so they arrive in the same order they were sent

What does UDP stand for?

User Datagram Protocol

What does TCP stand for?

Transmission Control Protocol

Why would you ever prefer UDP over TCP?

TCP does extra work, which is sometimes not necessary. For example, in a Zoom call, if some packets are dropped the session may freeze. After that, it's more natural for humans to repeat what they were saying (it would be weird if it replayed video/audio from the few seconds when the connection was lost).

What is the relationship between domain names in a URL and IP addresses? Example: https://tyler.caraza-harter.com:443/cs544/s23/schedule.html

When you enter a domain name into a browser, it gets translated to an IP address automatically for you.

If you are using HTTP over TCP/IP, what functionality does TCP/IP provide, and what does HTTP provide?

TCP/IP gives you IP addresses and port numbers, letting you communicate with a specific process (a server on a specific machine. HTTP additionally lets you specify what resource you want to access via that server. For example, consider this URL: https://tyler.caraza-harter.com:443/cs544/s23/schedule.html The resource is "/cs544/s23/schedule.html"

What does RPC stand for?

Remote Procedure Call Procedure: another name for a function/method Remote: we want it to run on a different process/container/computer

What are the RPC implementations created by Meta and Google called, respectively?

Thrift and gRPC

What is gRPC layered on top of?

HTTP Every method call is an HTTP POST request. The arguments go in the request body, the return value goes in the response body.

What is it called when we convert various data types into bytes to send over the wire? What about the reverse conversion?

serialization/deserialization

What does gRPC use for serialization?

Protocol Buffers (protobufs for short)

What is variable-length encoding, and what are the pros/cons of using it?

Use more space for bigger numbers. E.g., if an int32 value is small enough, we could use 1, 2, or 3 bytes (instead of the usual 4). Pros: save space. Very important for sending data over the network, so protobufs do this. Cons: CPUs cannot directly operate on int32's unless they are 4 bytes, so conversion is necessary before sending and after receiving this data.

Port forwarding: if we want to forward port 300 of the loopback device on a VM to port 80 inside a container, how do we run the container?

docker run -p 127.0.0.1:300:80 myimg

What does this do? ssh USER@VM -L localhost:1234:localhost:5678

This is executed on a machine (say your laptop) to create an SSH tunnel to the VM. While the tunnel is in use, any requests to localhost:1234 on the laptop will be forwarded to localhost:5678 on the VM ("localhost" is not redundant here because it is referring to two different loopback devices, the one on the laptop and the one on the VM).

Consider this: docker run -d -p 300:80 myimg We specify the port on the VM (300) and container (80), but we don't specify which NIC. What will be used?

By default, the command is equivalent to this: docker run -d -p 0.0.0.0:300:80 myimg This means traffic on all of the VM's NICs will forward to the container (possibly a security risk, depending on your firewall settings). Inside the container, it will forward to whatever the main NIC is (e.g., eth0), NOT the loopback device (so anything inside the container should listen on 0.0.0.0, not localhost).

What is container orchestration, and what is currently a very popular orchestrator?

Orchestration lets you deploy cooperating containers across many different machines. Kubernetes is probably the most well known.

What does "docker compose" do?

Lets you start a bunch of cooperating containers on the same machine.

protobuf files (.proto) can support two different syntaxes, v2 and v3. If you want v3, what should the first line of your .proto be?

syntax = "proto3";

What are the two main things a .proto file contains?

messages services Example: message MyMessage { … } service MyService { … }

In a .proto file, what does a message contain?

Fields, each with a type and a number, like this: message MyMessage { int32 x = 1; int32 y = 2; }

In a .proto file, what does a service contain?

RPCs, like this: service MyService { rpc MyRPC(Message1) returns (Message2); } Each RPC has one message containing arguments and another containing return values.

When you generate code for a .proto file, you get two files:

????_pb2

????_pb2_grpc

What are they each for?

????_pb2: code for serializing/deserializing the messages

????_pb2_grpc: servicer (class to be inherited from) and stubs for making remote procedure calls

Consider this: python3 -u server.py &> log.txt What does "-u" do?

"force the stdout and stderr streams to be unbuffered" Otherwise, if its buffered, any prints from server.py might not immediately appear in log.txt (that can be confusing if you're using log.txt to debug).

If you have a docker-compose.yml in the current directory, and you want to start running the services defined, what can you do?

docker compose up

If you want to see the compose containers currently running, what do you do?

docker compose ps

If you want to stop running containers for a compose cluster, what can you do?

docker compose down

If you want to delete all containers for a docker compose cluster, what can you do?

docker compose rm (add -f to force it; for example, might be necessary if they're currently running)

Before a CPU can add two values in RAM, what must it do?

Load those values to CPU registers

Which CPU cache level is fastest, of L1, L2, L3?

L1

Which CPU cache level is biggest, of L1, L2, L3?

L3

When data in a cache is too old and no longer valid, we say it is _______

stale

What does FIFO stand for?

First In First Out

What does LRU stand for?

Least Recently Used

How are FIFO and LRU similar? How are they different?

They are the same for a miss: the data is added to the cache, in the "newest" position. They are different for a hit: FIFO does not change how it prioritizes the item, but LRU resets it to the "newest" position.

What do you call it when you find an item in a cache?

"hit"

What do you call it when you CANNOT find an item in a cache?

"miss"

What is a pattern where a random eviction policy would beat LRU and FIFO?

A common pattern is that the data is too big to fit completely in cache, and the program loops, repeatedly reading over the dataset in the same order. LRU and FIFO will have a 0% hit rate, but random will at least get some hits.

What is the name for a piece of data loaded to CPU cache?

cache line

What is the most common cache line size for modern CPUs?

64 bytes is common (other sizes like 128 used to be more common; new Macs haved started using 128 again)

If you want to sum over column in a numpy matrix in a cache friendly way, how should you create the array?

First create an array where each column is actually stored as a row in the matrix. Then transpose it. This will get you columns that are contiguous in memory, resulting in fewer cache lines being loaded as the data is scanned.

How does PyArrow indicate which strings/ints/etc are null/None in an array?

validity bitmap: 1 means valid, 0 means null/None

How can you add a region to your virtual address space that is not backed by a file?

anonymous mmap

How can you map a file into your virtual address space?

Open the file, get the f.fileno(), and pass it to mmap.

If you want to be able to evict pages in anonymously mmap'd regions, what do you need to do?

enable a swap file in Linux

There is one virtual address space per _______

process

A process is a running ______

program

Virtual memory maps to ______

physical memory

Which address space can contain "holes" (invalid addresses)

Virtual address spaces can have holes (physical address spaces do not -- they are contiguous)

What are three things that go in a virtual address space?

code stack heap

Which pointer indicates what code to execute next?

The "instruction pointer"

There is one stack per _____ and one heap per ______

thread, process

What is it called when the scheduler stops running one thread and starts running a different one?

A "context switch"

What are three states a thread can be in?

running, blocked, ready

What are some reasons a thread might be blocked?

waiting on user input, disk operations, network operations, timer sleep, etc.

How do you create and launch a thread object for running function f(x)?

t = threading.Thread(target=f, args=(x,)); t.start() [Corrected Python API: target and args belong in Thread(), not start().]

How do you wait for a thread t to finish running?

t.join()

How can you print a thread's ID?

For the calling thread: threading.get_native_id(). For a started Thread object t: t.native_id. [Corrected Python API.]

What is a "race condition"

A bug that only sometimes surfaces, depending on when context switches happened between threads

When might a context switch occur?

Between instructions -- a single line of code might correspond to multiple bytecodes or machine instructions, so it's important to note that context switches often occur in the middle of a line of code being executed.

What is a "race condition"?

A bug, where whether or not you get correct behavior depends on how threads get scheduled. Race conditions are tricky to test+debug because they're non-deterministic (not same behavior each time), and you might only see the incorrect behavior rarely (say one in a million times).

What is "deadlock"?

This is when threads can never make progress, because they each want to acquire a lock that will never be released. One example: t1 has A and t2 and B; t1 is waiting to additionally acquire B, and t2 is waiting to additionally acquire A. This will never happen because neither thread will release its first lock until it has acquired the second lock and done some work.

How can a thread (a) get a lock and (b) let go of it?

lock.acquire() lock.release()

How can you rewrite the following code so that the release will happen, even if an exception occurs? lock.acquire() # code with possible exception lock.release()

with lock: # code with possible exception

What do you call a section of code where certain interleavings with other code would be a problem?

critical section

What is "atomicity" in the context of multi-threaded programs?

If a thread is changing multiple things together, we never want to see (say from another thread) partial results, with only some changes made.

What is an "invariant"?

A rule that applies to the data, often something a human might know from context. For example, an invariant might be a list of ages cannot contain negative numbers. Some invariants are known by the system (for example, that the length of the list itself cannot be negative).

What is "consistency" in the context of threading?

All invariants are enforced.

If thread t1 holds a lock, what could happen? 1. we could context switch to another thread t2 2. another thread t2 could acquire the lock

(1) is possible, (2) is not

What happens in Python when you try to release a lock that has already been released?

There is an exception

What is the GIL?

Global Interpreter Lock

Memory is byte-addressible. But what is the unit of access for an HDD, SSD, etc?

These are block devices, so the unit is a block . A typical block size might be about 512 bytes.

What are two ways we can use memory to make access to block devices more efficient?

caching: keep some disk data in memory, so we don't need to go back to disk if the data is reused buffering: when doing many smaller reads/writes, accumulate more data in memory before doing the transfer between disk and memory (because block devices are more efficient for bigger accesses).

What are the names for these two data access patterns? 1. reading lots of data in order 2. jumping around and reading from many different places

1. sequential 2. random

"block" and "page" have different meanings for SSD internals than we've seen for operating systems and interactions with block devices. What are the differences?

block (for SSDs): unit of erasure (perhaps 100s of KBs)

block (for using a block device): unit of transfer to/from device, perhaps 512 bytes

page (for SSDs): unit of read/write within the define (few KBs)

page (for system memory): unit of mapping between virtual memory and physical memory (usually 4 KB)

How can we break a block device into smaller sections?

with partitions

How can we treat multiple individual block devices like one bigger, more reliabel one?

With RAID (redundant array of inexpensive disks)

What is the data structure in a file system that points to blocks containing file data?

inode

On UNIX, how do we make many smaller file systems appear as one big one?

By mounting them on top of each other

What does it mean for a format to be "column oriented"?

The data in the column is layout out consecutively in memory or within a file.

What is the orientation of CSVs and parquet files?

CSVs: row oriented Parquet: column oriented

What is the tradeoff between text encoded and binary encoded formats?

text: easier to debug (because you can just look at it) binary: usually more efficient (often less space, and numbers usually already in a format on which CPUs can directly operate without further conversion)

Compression works by looking for repetition over some window, say 32 KB. What would be the advantage and disadvage of increasing the window size?

Advantage: find more repetition, and use that to get a smaller file size Disadvantage: spend more computation time finding the repetition

What does snappy prioritize, high speed, or high compression ratios?

high speed from the docs: "[Snappy] does not aim for maximum compression, or compatibility with any other compression library; instead, it aims for very high speeds and reasonable compression."

Considering CSVs and parquets: when do we need to infer the schema?

With CSVs we need to infer it, because everything in a CSV is a string (need to detect that all the strings in a given column look like integers, for example). Parquets have schema information built in, so there is no need to infer the schema.

What is transactions processing?

Operating on individual rows or a small number of rows at a time (e.g., adding, modifying, deleting rows).

What is analytics processing?

Trying to answer questions about the data, which involves computation over whole columns of data.

What does OLTP stand for?

Online Transactions Processing

What does OLAP stand for?

Online Analytics Processing