Programming

抛砖引玉

Raft

Old time

• people are forced to use P2P for large scale network
• P2P’s need is replaced by scalable internet services within datacenters
• P2P’s extremes
  • scalability
  • failure (frequent join and leave)
  • security (anyone could access)
  • wide area (geo-distributed)
  • heterogeneity

Approximation is hard

1. sampling and sketches
   • low space and time complexity
   • make strong assumptions about the query workload - on-line aggregation
   • highly variable performance
   • make fewer assumptions about the query workload
     • OLA may need to read the entire table to compute a result with satisfactory error bounds

Why Deep Learning is hard?

• extremely hard to construct appropriate features

ML challenges

• needs enormous network bandwidth
• cost of synchronization and machine latency is high: since ML algorithms are sequential
• fault tolerance is critical: machines and jobs can be preempted

What “secure” means?

• Confidentiality
• Authentication
• Integrity. Intruder can change message
• Accountability. No party can deny sending message
• Availability (DoS)

Strong Consistency

• One copy, up to date
• Why we need it? it is easier to implement certain applications
• Why not? scale, latency, availability

Pregel-like

Why GraphX?

Storm

• Topology: is a DAG where vertices represent computation and the edges represent the data flow
  • is a logical plan from a DB system perspective
• more than one worker process on the same machine may be executing different part of the same topology
• one process is one JVM (While Heron Instance is a JVM process, runs only a single task of spout or bolt)
  • worker processes serve as containers
  • each worker runs a supervisor that communicates with Nimbus
• one JVM has multipe threads (executors)
  • executors provide intra-topology parallelism
• one thread has multipe tasks
  • task provide intra-bolt/intra-spout parallelism
• Nimbus is “JobTracker”: is the touchpoint between the user and the Storm system
  • Nimbus and Supervisor daemons are fail-fast and stateless, and all their state is kept in Zookeeper or on the local disk
  • Single point of failure in Storm, but not in Heron
• Supervisor: every 3 seconds, it reads worker heartbeats from local state and classifies those workers as either valid, time out, not started, or disallowed

Blocking

coordinator and server could block -> we don’t need all reply, majority reply is enough

Current distributed stream processing model

• requiring hot replication
• long recovery times
• do not handle stragglers
• Continuous operator model: Storm, TimeStream, MapReduce Online and streaming DBs
  • long-running, stateful operators receive each record, update internal state and send new records
  • since it is stateful, it is hard to provide fault tolerance efficiently
  • like Map and Reduce job, no start and no stop, always running
  • how to do recovery?
    • replication and also synchronization protocol
    • to ensure replicas receive messages in the same order
  • upstream backup: upstream nodes buffer sent messages and replay them to a new copy of a failed node
    • this will take longer time to recover: the whole system needs to wait for a new node to serially rebuild the failed node’s state by rerunning

Distributed Atomic Commit

Why hard?

Failures

• What kind of failures in hardware/software can it deal with?
  • Fail-stop failure and only one of primary or backup fails
    • it could handle both of them crash temporarily, since the data will remain crash-consistent
• What kind can’t it deal with?
  • Can not recover from nonfail-stop conditions
  • Both primary and backup fails permanently
  • Software bugs, which could propagate application errors to backup
• What happens when an unexpected failure arises?
  • if primary fails
    1. the backup node will try to wait the new checkpoint transmission until time-out
  • the alive node will upgrade itself as primary and resume execution from most recent checkpoint
  • if backup fails
    1. the primary will try to wait for a time-out of the backup responding to commit requests
  • the primary would have to replicate another backup

Problem

• I/O is the bottleneck of a system
• Read is easy to deal with, but write operations could not scale-out due to multiple replication

ReplicatedService

2 nodes at first

Impala

Why Spark SQL

Previous: Shark

• Could not apply on intermediate results of Spark program
• A single SQL string is hard to debug, hard for modularization
• Hive optimizer is only for MapReduce, we need new data types and new data sources

Hive

SQL on Hadoop or Spark
Hive - MR/Tez
SparkSQL - Spark
Impala

NFS

Why we need NFS?

Sparrow

• Yarn: centralized scheduling: limited throughput
• scheduling without coordination
  • sparrow distributed scheduling
  • omega uncoordinated, multi-schedules

Time, Clocks, and the Ordering of Events in a Distributed System

• Process: stream of events
• Communicate: send message, receive
  • Model: message send takes time, reliable
• Ordering:
  • a, c: a is before c

RDD

• read-only, partitioned collection of records
• a restricted form of shared memory
• coarse-grained transformations (e.g., map, filter and join) rather than fine-grained updates to shared state
• reuse intermediate results during iterative in memory not in external stable storage
• immutable data: could run bakcup copies of slow tasks to ease stragglers
• can schedule tasks based on data locality
• RDD degrade gracefully when memory is not enough, while DSM may get block
• RDD is best suited for batch applications that apply the same operation to all elements of a dataset
• general-purpose programming language

Why Tez?

1. allow users to model computation as a DAG
   • runtime query optimization, such as pruning data partitions, based on online information
   • YARN-compatible security, data-locality awareness, resource-reuse, fault-tolerance and speculation
   • pluggable API

An Analysis of Data Corruption in the Storage Stack

• Table 1: Corruption classes summary
  • This summary overturns my illusion that “once I have checksum and verified, I would trust the data”. In fact, a block of data may pass the checksum verification but is still inconsistent since the firmware returns false negative or there is logic error due to misdirected writes

Why YARN?

• Higher scalability: As the central arbiter of the compute cluster, the JobTracker was also responsible for (each of these limited its scalability):
  • admission control,
  • tracking the liveness of TaskTrackers (to re-execute running tasks or tasks whose output becomes unavailable),
  • launching tasks speculatively to route around slow nodes,
  • reporting job status to users through a web server,
  • recording audit logs and aggregate statistics,
  • authenticating users and many other functions;
• Decoupling from MapReduce programming model

MapReduce

• M/R programming model
• Execution isssues, run time problems
• Scheduling and fairness across jobs
  • greedy
  • fair scheduler (slot-based)
  • flow-based fair scheduler

Basics of Distributed Computing

• communication
• failure
• time

Timeline

Numbers

• Fire hydrant: 15ft
  • park: not within 10ft
• Red flashing school bus: stopped at 20ft
• railroad parking: 25ft
• crosswalk parking: 15ft
• 提前打信号灯: 100ft
• school zone when children are present: 15mph
• 商业居民区限速: 25mph

Why this paper

• How to improve performance and flexibility of netwroking layer performance?
  • move parts of the protocol processing into user space
  • remove kernel completely from the critical path and allow the communication layers used by each process to be tailored to its demands
  • the entire protocol stack should be placed at user level
  • OS and hardware should allow protected user-level access directly to the network

Network Construction Principles

The Datacenter as a Computer

• “DC” vs WSC
• key characteristics, goals
• details
• constraints impact on -> application desgin and data center design
• cloud computing
• EC2 EMR
  • spot pricing: auction, spot instances run when bid price > spot price
• illusion of infinite capacity (CPU, storage)
• scale out
• pay-as-you-go

VM operations

1. sudo virsh list --all
   • sudo virsh start ubuntu1404
   • virt-viewer ubuntu1404

原理

• 加盐早，肉就紧

fdisk

handle disk which is less than 2T

Query optimization

Naive thinks and problems

Concurrency Control

• much more deeper detail
• efficiency algorithm (performance rather than correctness)
• degree of consistency (between chaos and perfect)
• What concurrent access to data?
  • performance (e.g. transaction:
    • T1: transfer moeny from A to B
    • T2: giving 6% interest rate to all accounts)
    • Idea: structure access to DB as a bunch of Transactions
      • each transaction takes DB from consistant state to consistant state
      • then serial execution of a set of transactions guarantees consistency
        • want to run transactions concurrently but it should “look like” they ran serially
      • certain “conflicts” enforce another on the transactions
        • WR, RW, WW
        • Techniques: build serialization graph
        • Schedule is conflict serializable if and only if the serialization graph has no cycles

Lambda Calculus

• Full-beta reduction (random)
• Normal order (leftmost/outermost)
• call-by-value, most programming language, evaluate arguments before passing them, evaluate expression inside parenthesis first
• call-by-name, no reductions inside abstractions (lazy strategy, call-by-need)

虽然我没有看《变化社会中的政治秩序》一书，但是在看完几乎所有书评之后，我发现它对我的启发仍然是巨大的。

Relations

Before RPC

• sockets are the fundamental mechanism with a poor read/write only interface

Attacks

• tapping
• spurious messages injection
• replay

Consistency model

• defined: a mutation succeed without interference from concurrent writers
  • it may include mingled fragments from multiple mutations
• consistent: all clients will see the same data
• A global mutation order is defined first by the lease grant order chosen by the master
  • then within a lease by the serial numbers assigned by the primary

脑洞了一天关于金融矿工的工作，感想如下

Goals

• scale: how many clients can server serve?
• reasonable definition of consistency (top down)
• use local disk

Reviews

Design

Introduction

• A small kernel securely exports all hardware resources through a low-level interface to untrusted library operating systems
• The single overriding goal: to separate protection from management -> to provide an interface that is as low-level as possible, the approaches:
  • give each application its own virtual machine
  • exokernel way: export hardware resources rather than emulating
• three techniques to export resources securely:
  1. secure bindings
     • visible resource revocation
     • abort protocol

Design Goal

1. high performance
   • combine kernel code synthesis, which decreases kernel call overhead through specialization
   • reduce synchronization - self-tuning capability to dynamic load and configuration changes - a simple, uniform and intuitive model of computation with a high-level interface

I bought a HP laptop equipped with Windows 8.1, but it would jump over Ubuntu’s Grub after I install it.

This post is a digest of the first paper in my CS736 which will talk about the IPC benchmark briefly.

two minutes warning

• User-level thread packages can set the actual duration of the warning by writing a value in the virtual processor data structure to avoid acquiring a spin lock near the end of the virtual processor quantum
• if an about-to-be-preempted thread is working on an important computation that needs to be continued on another physical processor, two-minute warning handler can save the state of the thread and then send an explicit interrupt to another virtual processor in the same address space, prompting it to migrate and run the preempted thread

vm_allocate

1. User Processcall Kernel with vm_allocate()
   • Kernelcall Pager about page initialization
   • User Process meets page fault interrupt
   • Kernel request Pager
   • Pager provide page
   • Kernel resumes User Process

DEMOS

• links provide both message paths and optional data sharing between tasks
• Switchboard task is provided to allow mutually consenting arbitrary tasks to communicate
• security is a big issue to Los Alamos

2014-09-11

Introduction

Essential Proposals

Course Main Topics

Introduction

Mechanisms are applicable to any computer system which uses segmentation as a memory addressing scheme.

Install

• insert disks in your free disk slots
• sudo apt-get install lvm2

Rsyslog Configurations

We need a local rsyslog to detect local nginx log change and a remote rsyslog to receive logs.

logrotate.d

Create a configuration file in /etc/logrotate.d/ like:

查看可用的无线网络 sudo iwlist wlan0 scan

假设有机房A的机器10.1.0.10/16 1.2.3.4与机房B的机器192.168.1.10/24 5.6.7.8要搭建基于internet的内网隧道

处于DMZ之后的内网机器往往只配了一块网卡，所以往往只有一个内网ip(就算配了外网ip，外网的机器也ping不到，所以没有作用)(除非再去上游配置路由)

ubuntu 13.10自带的ibus拼音输入法有问题，总是打不对字。然后搜狗输入法又装不好，搞了2个小时终于装好了fcitx googlepin

背景介绍

keepalived构建于lvs之上，并实现了vrrp协议

安装

推荐使用apt-get install haproxy里面自带了重新启动脚本