Data Scientist

Hacking skills, Math & statistics knowledge, Substantive Expertise
Machine Learning, Data Science, Traditional Research

Raw data – processing – data set – statistical models / analysis – machine learning predictions – data driven products, reports visualization blogs

‘substantive expertise’
– knows which question to ask
– can interpret the data well
– understands structure of the data
– data scientist often work in team

Data science can solve problems you’d expect…
– netflix, social media, web apps, (okcupid, uber, etc)

bioin formatics, urban planning, a straphysics, public health, public health, sports

Tools to use
– Numpy
– multidimensional arrays + matrices
– mathematical functions
– Pandas
– handle data in a way suited to analysis
– similar to R
Both common among data scientists

Heavy Lifting Done by the run time

spow workers assign mappers
assign reducers

Issues to be handled by the run time
Master data structures
– location of files created by completed mapper
– score board of mapper/reducer assignment
– fault tolerance
* start new instances if no timely resonse
* completion message from redundant stragglers
– locality management
– task granlarity
– backup tasks

Content Delivery Networks
Napster started for music sharing

content hash, node-id where content stored
content-hash = 149 => <149, 80>

Name space {key-space, node-space}
content -> sha-1 -> unique 160-bit key, unique 160-bit node id
Objective:
-> node id such that –
APIs
– put key, getkey

CDN – an overlay network
routing table at A, name, node id, next

multimedia API
middleware
commodity OS

Parallel program
-pthreads: API for parallel programs
Distributed programs
-sockets: API for distributed programs
Conventional Distributed program
client – unix(socket) – server e.g. NFS

Novel multimedia Apps
sensor-based: sensors, distributed
sense -> prioritize -> process -> actuate
computationally intensive, real time

large-scale situation awareness

PTS Programming Model
Channel ch1 =
lookup(“video channel”)
while(1){
// get data
response γ =
ch1.get()
// process data
…
// produce output
ch2.put(item,)
}

RioVista

RioVista
– performance-conscious design of persistent memory
Quicksilver
– making recovery a first class citizen in os design

LRVM Revisited
begin-xact, nomal program writes, end-xact
cpu, undo <- memory, cpu memory, memory data reda CPU, application memory, File cache mmap => normal application memory secomes rersistent

Crash Recovery
Treat like abort
– recover old image from undo log -> servives crashes since it is in RIO file cache
Crash during crash recovery?
– idempotency of recovery -> no problem

Server design

Server design
-persistent metadata m1, m2, ..mm
-normal data structures + code
=>
create external data segments to back persistent data structures
-apps manage their persistence needs

Designer’s choice to use single or multiple data segment

RVM Primitives
Initialization
– initialize(options)
– map(region, options)
– unmap(region)

Body of server code
– begin_xact (tid, restore_mode)
– set_range(tid, addr, size)
– end_xact(tid, connect, t_mode)
– abort_xact(tid)

GC to reduce log space
– flush()
– truncate()

bigin_xact(tid,mode);
	set range(tid, base_addr, #bytes);
	write meta data m1
	write meta data m2
end_xact(tid, mode);

No action by LRVM
LRVM create redo log in memory

Redo log
-AV changes of different region between begin and end xact

Commit
Redo log, window of vulnerability

Log truncation
apply to data seg, read redo log

Log based striping

Client: memory, log seq, log fragments parity, LAN, storage services

Stripe Group, stripe group for x, y, z, L, M, N
-subset server into stripe group
-parallel client activities
-increased availability
-efficient log cleaning

Cache coherence
-single writer, multiple reader
-fileblock unit of coherence
write- request
-receive token
-manager revokes

Log cleaning
log segment evolution, writes to file blocks
– may belong to different files

Unix File System
{filename, offset} -> i-node -> data blocks on disk

Client node action
filename -> mmap -> metadata manager
Manager node actions
filename -> File Dir -> i-number -> i-map -> i-node a dir -> stripe group map -> storage server -> index node of logseg id -> stripe group map -> storage servers -> data blocks form -> storage severs

LRVM
– persistent memory layer in support of system service
Riovista
– performance conscious design of persistent – memory
Quicksilver
– making recovery a first clacks citizen in os design

Persistence
– need of os subsystems
– make virtual memory persistent
– subsystem designers 4 is performant
– use persistent logs to record changes to VM
VM -> replace VM

Implementation

Write(x)
DSM + OS coop x -> twin, original writable
Write project after release Twin, X’ diff run length

Non-page-based DSM
shared r/w -> dsm software -> <-data library-based -annotate shared variables -coherence achons inserted at point of access API calls lang runtime structured DSM -APU for struct -coherence action on app calls DSM and speedup LAN - DSM library - p -> mem

First NFS
-SUN, 1985

Client, LAN, Servers(student), file cache

DFS
no central server
-each file distributed across several nodes
DFS implemented across all disks in the network

Preliminaries: Striping a file to multiple disks
-increase I/O bandwidth by striping to parallel disks
-Failure protection by ECC

Log Structured File System
– Buffer changes to multiple files in one contiguous log segment data structure
– log segment to disk once a file up or periodically solves small write program
mods to x, mods to y, log segment written the disk

Eebra File System(uc-berkeley)
-combines LFS + RAID
use commodity hardware
-stripe by segment on multiple nodes’ disks in software

xFS – a DFS
-log based striping, cooperative caching, dynamic manageent of data, subsetting storage servers, distributed log cleaning

Traditional NFS with centralized server(s)
– memory content
* metadata, file cache, client caching divectory

Software DSM

Address space partitioned address equivalence
distributed ownership
contact owner of page to get current copy

application, global virtual memory abstraction, dsm software implementation, local physical memeories

LRC with multi-writer coherence protocol
PI lock(L);
x, y, z pages modified in cs => Xd, Yd, Zd } diffs
unlock(L);　fetch at point of access
P3 lock(L); x <- => X’d unlock(L);

Implementation
write(x), twin, original writable
release run-length encoded

Systems from Components

specify -> code -> optimise -> deploy
ioa, ocaml, nuprl

digging deeper from spec to implementation

Spring Operating System
-> spring system
Java RMI, EJB

How to innovate OS?
brand new os? or better implementation of known os?
Market place needs
-large complex server software
=>Take the Intel inside approach… in the case unix inside for box makers like sun microsystems

Spring Approach
Strong interfaces, open, flexible, and extensible
conncet to other machines, Mkernel(threads/ipc)
All outside the kernel

Nucleus – “microkernel” of Spring
Domain, Door table, Door IDs, nucleus, door, target domain
Object invocation across the network
client domain, server domain, proxy A・B、Nucleus

client domain -> doory nucleusB -> front object -> underlying object -> ACL

Sources of overhead in RPC

marshaling
data copying
control transfer
protocol transfer

Three copies
-client stub
-kernel buffer
-dma to controller

Reducing copies?
-marshal into kernel buffer directly
-shared descriptors between client stub and kernel

Routing on the internet
Application
transport
network
link
physical

network, link, physical
App payload|qos
protocol stack++
IP-hdr code payload
dst dst dst

Potential Apps
protocol independent multicast
reliable multicast
congestion notification
private ip(PIP)
any casting

Distributed system definition

N1, N2, … Nn
LAN/WAN
fiber, cable, satellite
no physical shared memory between nodes
N1, N2

Even a cluster is a distributed system

Belief!
-processes sequential
-> events totally ordered
h->i, f->g, d->e..
-send before receive
->a-b, e->f,…

Lamport’s logical clock
each node
* its own events
* its communication events
Lamport’s logical clock
* monotonic increase of own event time
condition 1: Ci(a) by lamport’s
logical clocks plus PID to break ties

Latency
Elasped time
Throughput
Event per unit time
Bandwidth: throuput measure
RPC performance
Hardware overhead
Software overhead
Foucs of this lesson
How to reduce software overhead

Components of RPC Latency
1.client call
2.Controller latency
3.Time on wire
4.Interrupt handling
5.Server setup to execute call