Coding, Algorithm, Data Structure

https://www.bmpi.dev/dev/deep-in-program-language/how-to-implement-concurrency/concurrency-model/ 编程语言是如何实现并发的之并发模型篇

相比CSP模型，Actor模型可以跨节点在分布式集群中运行: 存在信箱满后消息丢失的问题

Python

1. Python Project Structure
2. Google Python Style Guide
3. PEP 8 -- Style Guide for Python Code
4. https://buckbuild.com/function/glob.html

Go

• Goroutines
• GOMAXPROCS: # of operating system threads = # of logical processors
• Thousands of goroutines are bound to maybe 1 single processor
• Contention is low: Goroutines are currently partially preemptive (before Go1.9)
• Switch cost is low: modern scheduler is O(1) ~ O(logN), only 3 registers
• Concurrency: run at the same time
• Parallelism: threads run on different processors
• has little to do with CPU-bound test
• help a lot with non-CPU-bound test
• go test
• go test -cpu 4: set GOMAXPROCS to 4 (affects preemptive contentions)
• b.SetParallelism(p): sets the number of goroutines used by RunParallel to p*GOMAXPROCS
• go test -parallel n: maximum n tests to run simultaneously
• Context
• Context should go away for Go 2
• How to correctly use context.Context in Go 1.7
• idiomatic go

Coding

https://oi-wiki.org/ds/

https://github.com/allaboutjst/airbnb
https://zhuanlan.zhihu.com/p/25697275

Why recursion is heavy? Stack frames may be too many which contains call's return address, local data, and parameters

算法

• https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_sorts
• QuickSort: O(logn) < O(Space) < O(n). Worst case: 基本有序, Partition value can only order one element at a time O(Time) = O(n*n)
• partition(): move pivotIndex to the a[right]
• MergeSort: O(Space) = O(n): new queue for merging
• HeapSort: heapify(); siftdown(a, start, end)
• remove node: a[0], move a[-1] to the top, then siftdown()
• add node: a[-1], then siftup()
• heapify: siftup() 从前到后; siftdown() 从后到前
• 计算机科学中最重要的32个算法
• 《编程之法：面试和算法心得》
• 刘未鹏: 知其所以然（三）：为什么算法这么难？
• leetcode题解
• Design Pattern
• 图说设计模式

Site Reliability Engineering - How Google Runs Production Systems

Site Reliability Engineering - How Google Runs Production Systems

Ch10: Practical Alerting from Time-Series Data

Borgmon clusters could stream with each other, upper-tier filter the data from lower-tier and aggregate on it. Thus, the aggregation hierarchy provides metrics with different granularity. (DC -> campus -> Global)

Ch19: Load Balancing at the Frontend

Traffic are different. Search requests want latency, Video requests want throughput.

• DNS layer LB
• Clients don't know the closest IP -> anycast -> a map of all networks' physical locations (but how to keep it updated)
• DNS middleman's cache (don't know how many users will be impacted)(need a low TTL for propagation)
• DNS needs to know DC's capacity
• Virtual IP layer LB: LVS packet encapsulation GRE(IP inside)

ch20: Load Balancing in the Datacenter

1. Active-request limit: client marks backend as bad if its backlog is high. But many long queries will fail client quickly
2. Backend has states: healthy, unresponsive, lame duck (stop sending requests to me)
3. Subsetting: one client could only talk with limited backends to prevent "backend killer" client
4. Weighted Round Robin on backend-provided load information

ch21: Handling Overload

• Client-side adaptive throttling: Preject = max(0, req - K*accept/req)
• Request is tagged with priority
• When to retry
• per-request retry budget is 3
• per-client retry budget is 110% (avoid 3X load)
• backend will give "overloaded; don't retry" if the backends' retry histogram is heavy
• Put a batch proxy if clients have too many connections on backends

ch23: Managing Critical State: Distributed Consensus for Reliability

Whenever you see leader election, critical shared state, or distributed locking, use distributed consensus system.
Different algorithms: crash-fail or crash-recover? Byzantine or non-Byzantine failures?
Fundamental is replicated state machine (RSM): is a system that executes the same set of operations, in the same order, on several processes.
The consensus algorithm deals with agreement on the sequence of operations, and the RSM executes the operations in that order.

What RSM could build?

• Replicated Datastores and Configuration Stores: RSM provides consistency semantics. Other (nondistributed-consensus-based) systems rely on timestamps (refer Spanner)
• Highly Available Processing: Leader election of GFS to ensure only one leader for coordinating workers
• A barrier: blocking a group of processes from proceeding until some condition is met -> MapReduce's phases and distributed locking
• Atomic broadcast: for queueing, ensure messages are received reliably and in the same order

Performance

• Network RTT: use regional proxies to hold persistent TCP/IP connections, and it could also serve for encapsulating sharding and load balancing strategies, as well as discovery of cluster members and leaders
• Fasst Paxos: each client sends Propose directly to each member
• Stable Leaders: but leader will be a bottleneck
• Batching jobs
• Disk: consider batching/combine transaction log into a single log

ch24: Distributed Periodic Scheduling with Cron

1. Decouple processes from machines: sending RPC requests instead of launching jobs
2. Tracking the state of cron jobs:
1. where
1. Store data externally like GFS or HDFS
2. Store internally as part of the cron service (3 replicas), store snapchat locally, do not store logs on GFS (too slow)
2. what
1. when it is launched
2. when it has finished
3. Use Paxos:
1. Single leader launches cron job (or through another DC scheduler), only launch jobs after Paxos quorum is met (synchronously) is it slow?
2. Followers need to update each jobs' finish time in case leader dies
4. Resolving partial failures:
1. all external operations must be idempotent; or the state is stored externally unambiguously
2. must record launched schedule time to prevent double scheduling. Trade-off between risk double launch vs skipping a launch

ch25: Data Processing Pipelines

How to implement a periodic pipeline? (latency, throughput, fast startup, even distributed, thundering herd issue)

Google Workflow uses model-view-controller pattern

• Task Master(model): hold all jobs states (pointers) in RAM, and actual input/output data is stored in a common HDFS
• Workers(view): stateless
• Controller: auxiliary system activities: runtime scaling, snapshotting, workcycle state control, rolling back pipeline state

How to guarantee correctness?

• Worker output through configuration tasks creates barriers on which to predicate work
• All work committed requires a currently valid lease held by the worker
• Output files are uniquely names by the workers
• The client and server validate the Task Master itself by checking a server token on every operation

Failure model:

• Task Master store journals on Spanner: achieve global availability, global consistency, low-throughput filesystem.
• Use Chubby to elect writer and persist result in Spanner
• Globally distributed Workflows employ 2+ local Workflows running in distinct clusters
• Each task has a "heartbeat" peer, upon peer timeout it will resume the task instead

Network

 

  Network

http://tasteturnpike.blogspot.com/2017/03/sre-knowledge.html

• 网络基本功系列：细说网络那些事儿
• https://github.com/alex/what-happens-when#dns-lookup 浏览器如何访问google
• Proxy Digest Authentication?
• Why TChannel?
• Why not HTTP? HTTP connections are uni-directional, can only be used for one concurrent request, and are built for delivering web pages with cache hints. HTTP tightly couples encoding and transport concerns (the path implies both the procedure name and sometimes even parts of the request body), having a single, header namespace with variable widths. It is not ideal for RPC, but it's fantastic for web pages.
• HTTP2:
• Solve head of line blocking by HTTP pipelining
• HTTP is poll mode, not bidirectional: http协议和websocket协议的区别
• Multiplexing over single TCP connection
• HTTP2 vs WebSocket
• WebSocket is bidirectional; HTTP2 is client/server + server push
• TChannel: RPC, multiplexing, bi-directional message passing, fast forwarding, work shedding with deadlines, cancellation, speculative execution, and communicates more clearly about when and when not to retry.
• Improve Web Speed: client -> DNS resolver -> DNS -> DNS resolver -> client --req--> Web server
• Speed = DNS latency + Request latency. Which DNS has lowest latency? Can't measure directly because of DNS resolver delegates the name resolution. Solution: create a special hostname to resolve (avoid cache), latency = server access time - special hostname resolve time

DNS resolvers

DNS客户端设置使用的DNS服务器(8.8.4.4)一般都是递归服务器，它负责全权处理客户端的DNS查询请求，直到返回最终结果。而DNS服务器之间一般采用迭代查询方式

1. clear DNS cache sudo killall -HUP mDNSResponder
2. check DNS client: sudo lsof -i -P | grep LISTEN
3. http://whoismydns.com/Index.html
4. dig @127.0.0.1 -p 53 google.com +tcp +trace

TLS handshake

TCP

• Connection Reset: the peer rejects it with an RST to let you know it isn't listening.
• send() returns only means transmitted through interface

Load Balancer

• 网络地址转换NAT原理及应用
• Consistent Hash for routing
• LVS
• LVS包转发模型和调度算法(图)
• LVS full-NAT (详解SNAT+DNAT): DR只能在同一个网段, DR和NAT必须在同一个VLAN
• https://www.quora.com/What-is-the-difference-between-layer-3-and-layer-4-load-balancing-Why-is-layer-7-LB-used-inspite-of-its-drawbacks-of-being-a-bottleneck
• https://www.nginx.com/resources/glossary/layer-4-load-balancing/
• L7 load-balancing is better for data locality on same type data

课外加强阅读

• computer networking top down approach

GFW

• vpn工作原理和搭建方法
• 翻墙路由器的原理与实现 
• 墙与梯的较量——那些年我们一起用过的翻墙手段
• 聊聊分布式散列表（DHT）的原理——以 Kademlia（Kad） 和 Chord 为例

哥德尔、艾舍尔、巴赫

哥德尔不完备定理

• 2条定理
• 任何相容的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的真命题，因此通过推演不能得到所有真命题（即体系是不完备的）。
• 任何相容的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明它本身的相容性。
• 希尔伯特计划: 这个计划的主要目标，是为全部的数学提供一个安全的理论基础。具体地，这个基础应该包括：
• 所有数学的形式化。意思是，所有数学应该用一种统一的严格形式化的语言，并且按照一套严格的规则来使用。
• 完备性。我们必须证明以下命题：在形式化之后，数学里所有的真命题都可以被证明（根据上述规则）。
• 相容性。我们必须证明：运用这一套形式化和它的规则，不可能推导出矛盾。
• 保守性。我们需要证明：如果某个关于“实际物”的结论用到了“假想物”（如不可数集合）来证明，那么不用“假想物”的话我们依然可以证明同样的结论。
• 确定性。应该有一个算法，来确定每一个形式化的命题是真命题还是假命题。
• 希尔伯特第二问题，是希尔伯特的23个问题之一，即关于一个公理系统相容性的问题，也就是判定一个公理系统内的所命题是彼此相容无矛盾的，希尔伯特希望能以严谨的方式来证明任意公理系统内命题的相容性。

Linux & OS & Linux内核设计与实现 & 深入理解计算机系统

Unix / Linux systems and internals

Preparations

Operating Systems: Know about processes, threads and concurrency issues. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.

Linux internals

• Process Execution and/or Threads
• Memory Usage
• RAID Levels
• The kernel and how it interacts with other system components
• System Calls
• Signals and Signal Handlers
• Modern Web Architectures and Webservers

Preparations:

• Review userspace / Kernel space boundaries and interactions.
  Examples might include: ioctls, sysctls, context switches.
• Review troubleshooting tools for system-level performance issues.
• Review troubleshooting tools for debugging application-level performance issues or bugs.

file system processing, file properties, user permissions, text parsing

Linux

• Process
• Process group
• Linux process states: Running, interruptible/uninterruptible sleep, defunct/zombie, stopped (job control signal or traced)
• CPU time: User time, System time, Idle time, Steal time (hypervisor forbidden)
• Core dump
• Why process can't kill: waiting on hardware device or network resource
• Why Zombie stay around: keeping exit status
• Forget Waitpid()
• Can't get killed, kill its parent, then released by init
• Can signal be ignored (lost)?
• Context switch
• Process context switch: need to switch virtual memory mapping, so that need to flush TLB (which is expensive)
• User mode to Kernel mode: a mode transition usually 
• Kernel
• How the Kernel Manages Your Memory
• Kernel can preempt a task running in the kernel so long as it does not hold a lock. Because the kernel is SMP-safe, if a lock is not held, the current code is reentrant and capable of being preempted
• Permissions
• chmod
• sticky bit, 1, t: has the final decision无法删除
• guid, 2, s: 目录下新文件保留原目录ownership
• suid, 4, s
• chmod -R a+rX . 所有子目录可搜索(regular file retain excutable permission)
• chattr
• i, immutable
• filetype
• umask: file permissions are set for newly created files
• TCP/UDP packet size: 64KB, MTU: 1500 B
• Zero Copy: From kernel to NIC, no user space
• https://fabiokung.com/2014/03/13/memory-inside-linux-containers/
• executing machine code in memory: Doable, think JIT runtime and python interpreter
• HDD vs SSD:
• SSD连续读的能力相比普通磁盘优势并不明显; SSD适合多读，多随机读写
• erase-before-write: SSD必须erase before write
• 因为SSD存在“写磨损”的问题，当某个单元长时间被反复擦写时（比如Oracle redo），不仅会造成写入的性能问题，而且会大大缩短SSD的使用寿命，所以必须设计一个均衡负载的算法来保证SSD的每个单元能够被均衡的使用，这就是wear leveling，称为损耗均衡算法 -- offline erase
• 传统数据库日志是sequential logging因为是连续位置的随机写入; SSD会大大折寿, SSD采用in-place logging: data and log in the same block; 日志文件还是适合HDD
• SSD作为flashcache掉电后数据是有效还是无效？被当作无效的
• 4K对齐是一种高级硬盘使用技术，用特殊方法将文件系统格式与硬盘物理层上进行契合，为提高硬盘寿命与高效率使用硬盘空间提供解决方案。因该技术将物理扇区与文件系统的每簇4096字节对齐而得名。当前电脑传统机械硬盘的每个扇区一般大小为512字节

Filesystem

• Filesystems
• hard link can not cross multiple partition
• i-node has reference counter
• directory inode holds pairs of (inode_num, filename)
• https://www.tecmint.com/clear-ram-memory-cache-buffer-and-swap-space-on-linux/
• What is a Superblock, Inode, Dentry and a File?
• Dentry is not an on disk data structure; constructed on the fly from pathname string and cached
• From one file to its inode to disk data block: http://www.cs.ucsb.edu/~rich/class/cs170/notes/FileSystem/index.html

《Linux内核设计与实现》

• Overview
• In Linux, each processor is doing exactly one of three things at any given moment
• In user-space, executing user code in a progress
• In kernel-space, in process context, executing on behalf of a specific process
• In kernel-space, in interrupt context, not associated with a process, handling an interrupt
• top halve has interrupt disabled
• Kernel memory is not pageable
• Process Management
• Process includes
• open files
• pending signals
• internal kernel data
• processor state
• memory address space (multiple memory mappings) page tables
• data section containing global variables
• Thread includes
• unique program counter
• process stack
• set of processor registers
• The kernel stores the list of processes in a circular doubly linked list called the task list.
• Fork() only overhead: duplication of the parent's page tables & creation of a unique process descriptor for the child
• ZOMBIE only has kernel stack, thread_info structure, and task_struct structure
• When a task is ptraced, it is temporarily reparented to the debugging process
• kernel threads do not have an address space (not normal process)
• Process Scheduling: low latency (process response time) and high throughput (system utilization)
• Context switch, the switching from one runnable task to another:
• calls switch_mm() to switch virtual memory mapping
• calls switch_to() to switch the processor state: saving/restoring stack information and processor registers and others
• User preemption can occur:
• when returning to user-space from a system call
• when returning to user-space from an interrupt handler
• Kernel preemption can occur: Linux 2.6 is a fully preemptive kernel, it is possible to preempt a task at any point, so long as the kernel is safe to reschedule.
• NO LOCK. locks are used as markers of regions of nonpreemptibility
• scheduler_tick() will check flag need_resched (which is per-process)
• Kernel preemption can occur:
• When an interrupt handler exits, before returning to kernel-space
• When kernel code becomes preemptible again (NO LOCK, preempt_count is 0)
• If a task in the kernel explicitly calls schedule()
• If a task in the kernel blocks (which results in calling schedule())
• System Calls
• syscall (interrupt vector 128): an exception or trap to enter the kernel
• syscall must be reentrant
• Interrupts and Interrupt Handlers
• Why interrupt? Processor polling incurs overhead, interrupt is what hardware to signal the kernel to get attention
• Interrupt vs Exception:
• interrupt handlers (top halves) are executed by the kernel asynchronously in immediate response to hardware interrupt
• exceptions occur synchronously with respect to the processor clock, that they are called synchronous interrupts. (e.g., divide by zero, a page fault)
• Special interrupt context: it is called atomic context as code executing in this context is unable to block (Top Halves)
• Interrupt handlers can form only the first half of any interrupt processing solution due to these limitations:
• Interrupt handlers run asynchronously and thus interrupt other, potentially important, code, including other interrupt handlers. (need to run fast)
• Interrupt handlers run with at best the current interrupt level disabled, and at at worst all interrupts on the current processor disabled. But disabling interrupts prevents hardware from communicating with the operating systems
• Interrupt handlers do not run in process context; therefore, they cannot block
• They are often timing-critical
• Kernel Synchronization
• When only a single processor, the only way data could be concurrently accessed was: interrupt occurred or if kernel code explicitly rescheduled and enabled another task to run
• Causes of concurrency:
• Interrupts: An interrupt can occur asynchronously at almost any time, interrupting the currently executing code
• Softirqs and tasklets: The kernel can raise or schedule a softirq or tasklet at almost any time, interrupting the currently executing code
• Kernel preemption: Because the kernel is preemptive, one task in the kernel can preempt another
• Sleeping and synchronization with user-space: A task in the kernel can sleep and thus invoke the scheduler, resulting in the running of a new process
• Symmetrical multiprocessing: Two or more processors can execute kernel code at exactly the same time (per CPU memory)
• Lock data not code
• Deadlock
• Implement lock ordering
• Prevent starvation. Ask yourself, does this code always finish? If foo does not occur, will bar wait forever?
• Do not double acquire the same lock
• Only one process move at one time (prevent livelock)
• Memory Management
• A page may be used by page cache, private data, or as a mapping in a process's page table
• kernel page structure is associate with physical pages not virtual pages
• high memory: memories one architecture can not directly map

《深入理解计算机系统》

链接

• Static Linking: ld copies functions from AR file
• Dynamic Linking:
• At loading:
• compile to get partial executable object file from shared object (mark symbols relocatable)
• execve(ld-linux.so)，relocate目标文件和可重定向文件libc.so,  relocate text and data
• At runtime: dlopen() loads functions from 共享库 to its memory directly (top中SHR的一部分就是dll文件)
• 3 kinds of object files:
• Executable object file
• Relocatable object file
• Shared object (shared library)

异常处理

• interrupt(键盘), trap, fault (除0), abort(机器检查)
• syscall is trap 128
• User vs Kernel mode is controlled by one mode bit in 控制寄存器
• context: 寄存器、浮点寄存器、PC、User stack、状态寄存器、Kernel stack、页表、进程表、文件表
• 信号的缺陷：
• 同类型待处理信号被阻塞
• 待处理信号不会排队等待：queue = 1
• 系统调用可以被中断：read会返回EINTR
• fork() vs execve()
• fork将父子进程每个页面标记为read only，每个section都标记为private copy-on-write
• execve: 删除已存在的用户区域->映射私有区域(text data bss stack heap)->映射共享区域(libc.so)->设置PC
• execve会继承打开了的fd
• 打开文件的数据结构
• 描述符表(descriptor table): 指向file table
• 文件表(file table): shared by all processes. 当前文件位置, 引用计数(多少个进程指向它),  指向v-node table
• v-node table: shared by all processes. 文件访问、大小、类型

Linux startup process

Boot

1. Power On Self Test 
2. Boot from CD, USB, HD 
3. Load kernel into initramfs
1. BIOS -> Master Boot Record (first sector) -> GRUB -> Active Partition load kernel
2. UEFI (低阶OS) -> GPT -> /boot/efi/boot.efi -> GRUB/kernel
1. EFI system partition is based on FAT, contains boot loader or kernel image
3. Why GRUB has so many stages?
1. stage 1, boot.img, 446 B, within first sector: to locate stage 2
2. stage 1.5, core.img, 25 KB, between MBR and first partition: contains a few common filesystem drivers (Not all filesystems)
3. stage 2, /boot/grub2, The kernels are located in the /boot directory, along with an initial RAM disk image, and device maps of the hard drives
4. Why BIOS could not load kernel directly? Does not have system driver for addressing

Startup

1. Kernel loads systemd/init, then mounts filesystems in /etc/fstab
2. Kernel calls start_kernel() to set up system functions: hardware and memory paging, interrupt handlers, the rest of memory management, device and driver initialization
1. idle process: power saving mode
2. scheduler: Complete Fair Scheduler O(logN)
3. init/systemd who mounts /etc/fstab
3. init start services from specific levels
4. display manager and login manager -> session manager

Shutdown

1. Close down user space functionality
2. init terminates
3. kernel shutdown

Cassandra

Cassandra

• LSM Tree + SSTable
• PRIMARY KEY(PARTITION KEY, CLUSTERING KEY) Rows are spread across cluster on Partition Key, then ordered by Clustering Key
• Why Cassandra doesn’t need vector clocks
• Delete:
• tombstone
• https://docs.datastax.com/en/cassandra/2.1/cassandra/dml/dml_about_deletes_c.html
• a batch containing conditional updates can only operate within a single partition, because the underlying Paxos implementation only works at partition-level granularity

SSTable

• Cassandra SSTable Storage Format
• The Missing Manual for Leveled Compaction Strategy (Wei Deng & Ryan Svihla, DataStax) | Cassandra Summit 2016
• when to use leveled compaction
• Each level ensures non-overlapping
• SizeTiered is better for write-intensive workloads, and Leveled better for read-intensive

Node repair 2.1

• Frequent data deletions and downed nodes are common causes of data inconsistency. Manual repair: Anti-entropy repair
• Parallel repair will only repair each token range ONCE. if you are using “nodetool repair -pr” you must run it on EVERY node in EVERY data center, no skipping allowed.

한국어

처음 뵙(拜)겠습니다 初次见面
잘 부탁(付托)드리겠습니다 请多多关照
천만(千万) 에요 哪里哪里 不客气
? 两个人的位置
저 미안(未安)합니다만 劳驾
메뉴를 보여 주세요 请给我看下菜单
물 좀 더 주세요 请加点水
? 没关系
조심(操心)하세요 保重

옆을 짧게 깎아 주세요 两侧请剪短一些

通过日语学韩语: https://www.zhihu.com/question/19830338/answer/93071137
Taeyeon的唱功: https://www.zhihu.com/question/21424874/answer/115636610