쿠...sal: deep

레이블이 deep인 게시물을 표시합니다. 모든 게시물 표시

[컴] Bittorent 의 peer message

아래 글은 ref. 1 > peer messages 에 대한 개인적인 이해에 바탕을 둔 번역입니다. 정확한 내용은 원문을 확인해 주세요.

peer messages

keepalive 메세지 이외(non-keepalive messages)에는 전부 첫 byte 에 type 정보를 가지고 있다.

type 의 종류는 아래와 같다.

0 - choke
1 - unchoke
2 - interested
3 - not interested
4 - have
5 - bitfield
6 - request
7 - piece
8 - cancel

위의 type 중에 0~4 번( 색)은 payload 가 없다.

have

have message 의 payload 는 한개의 index 이다. downloader 가 막 완료하고 hash 를 check 한 index 이다.

bitfield

bitfield(5) 는 항상 처음 메시지(first message) 로 보내진다.
bitfield 의 payload 는 bitfield 인데 downloader 가 보낸 index 는 1이 되고, 나머지들은 0 으로 set 된다.

현재 아무것도 갖고 있지 않은 downloader 들은 bitfield message 를 skip 할 수 있다.

bitfield 의 첫 byte 의 highest bit 이 index 0 이 되고, lowest bit 이 index 7 이 된다. 다음 byte 는 index 8-15 가 된다. 끝에 남는 bit 는 0 으로 set 된다.

실제 packet

request

request message 는 index, begin, 길이(length) 를 갖는다.
begin 과 length 는 byte offset 으로 표현된다.
파일의 끝부분에 걸려서 truncated 되지 않는다면 length 는 일반적으로 "2의 제곱" 이다.
모든 현재의 구현들은 2^14(16 KB) 를 사용한다.
그리고 이 이상의 크기를 요청하는 connection 들은 close 한다.

cancel

cancel 메시지들은 request message 와 같은 payload 를 갖는다. cancel 메시지들은 endgame mode(missing_piece/total_piece < 0.05) 동안에는 일반적으로 download 의 끝에 보내진다.

download 가 거의 끝났을 때, 마지막 몇개의 piece 들이 단일 modem line 에서 떨어진 채로 시간을 많이 소비하면서 다운로드 되어지는 경향이 있다.

downloader 가 자신이 가지고 있지 않은 piece 에 대해 request 를 보내는데, 이 때 이 request 가 pending 되고 있으면, downloader 는 자기가 연결해 download 하고 있는 peer 들에게 piece 에 대한 request 를 보낸다. piece 가 여러개라면, 한 peer 에 여러개의 request 를 보낸다.

이것이 비효율적이 되는 것을 막기위해, downloader 는 piece 가 도착할 때마다 다른 사람들에게 cancel message 를 보낸다.

piece

piece message 는 index, begin, piece 를 포함한다.
암묵적으로 이 piece 는 request message 와 관련이 있다는 것을 명심하자.
만약 빠른 승계(quick succession) 상태에서 choke 와 unchoke message 들을 받았을때나 전송이 너무 느릴때는 예상치못한 piece 가 download 되는 것이 가능하다.

Downloader 들은 일반적으로 piece 들을 random 한 순서로 다운로드 한다.
random 한 순서는 downloader 가 자신이 연결한 어느 peer 의 piece 에 대한 superset 이나 subset 만을 갖게 되는 것을 상당히 막아준다.

interested

interested 는 peer 가 내가 원하는 piece 를 가지고 있어서, 내가 관심있다의 표현이다. downloader 는 peer 에 대한 각 연결마다 am_interested / peer_interested 에 대한 변수를 갖고 있다. 그래서 downloader 가 peer 에게 관심이 있으면 am_interested 를 peer 가 downloader 에게 관심이 있으면 peer_interested 를 set한다.

choking

만약 downloader 가 peer 에게 choke 를 받으면 peer 가 downloader 를 choke 했기때문에 아무런 message 를 주고 받지 않는다. 마찬가지로 downloader 가 peer 에게 choke 를 날리면 그 peer 에게서는 아무것도 요청하지 않고, 받지 않는것이다. 그래서 보통 downloader 가 peer 마다 연결을 가지고 있는데 그 연결마다, downloader 가 peer 를 choke 했는지(am_choking) , 아니면, peer 가 downloader 를 choke 했는지(peer_choking) 에 대한 변수를 가지고 있다.

Choking 은 여러가지 이유로 수행된다. TCP congestion control 은 여러 connection 들을 통해 한번에 보낼 때는 매우 좋지 않게 동작한다. 또한 choking 은 각각의 peer 가 일관된 download rate 을 가지고 있다는 것을 확신할 수 있도록 tit-for-tat-ish algorithm 을 사용하게 해준다.

아래 설명된 choking 알고리즘은 현재 배포된 녀석이다.
모든 새로운 알고리즘들은 "완전하게 그 알고리즘으로 이뤄진 network" 와 "대부분 그 알고리즘으로 이뤄진 network 양쪽 모두에서 잘 동작하는 것"은 매우 중요하다.

좋은 choking 알고리즘이 준수해야 하는 여러 기준이 있다.

그것은 좋은 TCP performance 를 위해 동시 upload 수의 상한을 둬야만 한다.
fibrillation : choking 과 unchoking 을 빠르게 피해야만 한다.
download 를 하게 해준 peer 들에게 화답해야한다.(reciprocate)
optimistic unchoking : 때때로 현재 사용하고 있는 연결보다 더 나은 녀석들을 찾아내기 위해 사용되지 않는 연결들의 성능을 테스트 해 봐야 한다.

현재 배포된 choking 알고리즘

현재 배포된 choking 알고리즘은
단순히 매 10초마다 "한번이라도 choked 된 사람"을 변경하는 것으로 fibrillation 을 피한다.
가장 빠른 download rate 을 가지고 있고, interested 4 명의 peer 를 unchoking 하는 것으로 이 알고리즘은 화답과 upload 의 개수의 상한을 두는것을 한다.

참고로, 여기서 interested 는 peer 가 interested message 를 받은 상태이다. downloader 는 peer 에 자신에게 없는 새로운 piece 가 없다면 peer 에게 not interested message 를 보내게 된다.

4 개의 peer 들을 unchoking 하는 방법으로 화답(reciprocation) 과 upload 개수의 상한을 두는 것을 하는데, 이 4명의 peer 들은 가장 빠른 download rate 을 가지고 있고, interested 이다(are interested)
It does reciprocation and number of uploads capping by unchoking the four peers which it has the best download rates from and are interested.

좀더 나은 upload rate 을 가지고 있지만 not interested 한 peer 들은 unchoked 된다. 그리고 만약 그들이 interested 되면, 최악의 uploader 가 choked 된다.
만약에 downloader 가 complete file 을 가지고 있다면, unchoke 될 대상을 결정할 때 download rate 보다는 upload rate 을 이용한다.

낙관적인 unchoking 을 위해, 그것의 upload rate 와는 상관없이 한 순간에 하나의 unchoked 된 peer 는 존재한다.(만약 interested 라면, 그것은 4명의 허락된 downloader 중 하나로 count 된다.)

peer 가 낙관적으로 unchoked 되는 녀석은 매 30초마다 rotate 한다.
upload 하기위한 complete piece를 얻을 적절한 기회를 주기위해서, rotation 의 어느곳에서나 현재의 낙관적인 unchoke 보다 새로운 연결들을 3배 더 많이 시작하는 경향이 있다.
For optimistic unchoking, at any one time there is a single peer which is unchoked regardless of its upload rate (if interested, it counts as one of the four allowed downloaders.) Which peer is optimistically unchoked rotates every 30 seconds. To give them a decent chance of getting a complete piece to upload, new connections are three times as likely to start as the current optimistic unchoke as anywhere else in the rotation.

Reference

The BitTorrent Protocol Specification > peer messages

[컴][파이썬] yield 와 callback

yield 와 callback

yield 와 callback 은 많이 비슷하다. 실제로 작성하는 code 의 flow 는 많이 닮았다.

하지만, yield 는 직접 control(code 가 수행되는 순서로 보자) 을 제어할 수 있는 keyword 이기 때문에 이녀석이 좀 더 큰 범위에 있다고 보면 되겠다. 쉽게 이야기 하면, yield 로 callback 처럼 event 가 끝난 후에 다시 호출이 되는 구조의 code 를 구성할 수 있다.

callback 이 여러개인 경우

만약에 많은 callback 으로 표현해야 하는 경우, 예를 들면, network 에 대한 작업이 연속적으로 5번 일어나야 한다고 하면, callback 을 5번 이나 작성하게 되는데, 이러면 code 의 가독성이 떨어질 가능성이 많아진다.
하지만, yield 를 사용하면, 연속적으로 하나의 code 를 작성할 수 있어서 가독성도 좋고, 명확하게 하는 일을 보여줄 수 있다.

try/catch 를 한곳에

callback 에 비해 yield 를 이용할 때 또 하나의 장점은 같은 일을 하는 녀석을 하나의 code 처럼 한 function 안에 담을 수 있다. 이로 인해서 try/catch 를 이용할 때도 같은 종류의 exception 을 한 곳에서 try/catch 로 묶어놓을 수 있다.[ref. 1]

Reading a code

request 가 끝나면 doSomething() 을 해라

requests.get(callback=function(){
   doSomething()
})

http_request() 가 끝난 후 doSomething() 을 하겠다. http_request() 가 끝날동안 control 을 일단 양보(yield) 하마, 일단 다른일을 해라, 그 일이 끝나면 내가 doSomething() 을 하겠다.

yield http_request()
doSomething()

callback 을 yield 로 변경

ref. 3에 보면 callback 의 구조를 yield 를 사용하는 구조로 변경한 경우가 있다.(callback 을 yield 로 변경하는 법을 이야기하는 것은 아니다. 이 부분은 tornamdo.gen.coroutine 내부를 살펴보자.)

이 code 로 callback 과 yield 의 flow 의 차이를 느껴볼 수 있다.

class AsyncHandler(RequestHandler):
    @asynchronous
    def get(self):
        http_client = AsyncHTTPClient()
        http_client.fetch("http://example.com",
                          callback=self.on_fetch)

    def on_fetch(self, response):
        do_something_with_response(response)
        self.render("template.html")

class GenAsyncHandler(RequestHandler):
    @gen.coroutine
    def get(self):
        http_client = AsyncHTTPClient()
        response = yield http_client.fetch("http://example.com")
        do_something_with_response(response)
        self.render("template.html")

Reference

[컴][파이썬] python 3 의 string 정리

python 3 의 string

python 3 의 string 을 정리 해 보자. python 2 에 대한 정리는 복잡하고, 요즘은 딱히 할 필요가 없다고 생각하니 ref. 1 을 보고 알아서 판단하자.

python2 에서 python3 string 사용하기

여기서 python 3 의 string 만을 이야기하려는 것은 python 2 에서도 python 3 처럼 string 을 사용할 수 있기 때문이다. module 의 가장 상단에 아래처럼 적어주면 된다. 이것을 사용하는 것이 나중에 python 3 로 convert 하기에도 편하다.

from __future__ import unicode_literals    # at top of module

기본 string 의 표현, unicode

python 3 에서 기본적으로 모든 string 은 unicode 이다. 그리고 이 unicode 의 default encoding 은 utf-8 이다. 하지만 그렇다고 해서 python 3 의 string 은 utf-8 이다라고 생각하면 안된다. 그냥 unicode 이다 라고 인식해야 한다. 그래야 나중에 string.encode 등을 할 때 혼란이 없다.

byte object, b'가'

python 3에서 제공하는 다른 형태의 string 은 b'가' 형태의 string 이 있다. 앞에 b 를 붙여서 byte object 인 것을 보여준다. byte object 는 그냥 c/c++ 에서 char 의 array 이다.

>>>'가'.encode()
b'\xea\xb0\x80'
>>>inint = struct.unpack('<bbb', '가'.encode())
None

그래서 아래 같은 표현은 성립이 안된다.

>>> b'가'
SyntaxError: bytes can only contain ASCII literal characters.

b'가' 는 '가' 를 char 변수에 넣으려는 시도인데, utf-8 에서 '가' 는 3byte 를 사용하기 때문이다.
참고로 실제로 '가' 를 byte object 에 넣으려면 아래처럼 해야 한다.

>>> b'\xea\xb0\x80'

string.encode --> byte object

python 3 의 string 에서 encode 를 호출하면, 그 string 에 대한 byte object 를 return 해준다. 이 때 parameter 로 encoding 을 넘겨주는데, 그 encoding 에 따른 값을 전달해 준다.(이래서 string 은 unicode 라고 기억해야 한다.)

>>> '가'.encode() # default 값이 utf8 이다.
b'\xea\xb0\x80'
>>> '가'.encode('utf-16')


b'\xff\xfe\x00\xac'
>>> '\x80abc'.encode("mbcs", "strict")  
Traceback (most recent call last):
    ...
UnicodeDecodeError: 'cp949' codec can't decode byte 0x80 in position 0:
  invalid start byte
>>> '\x80abc'.encode("mbcs", "replace")
'\ufffdabc'
>>> '\x80abc'.encode("mbcs", "backslashreplace")
'\\x80abc'
>>> '\x80abc'.encode("mbcs", "ignore")
'abc'

replace() / backslashreplace() / ignore() 는 ref.3을 참고하자.

byte object.decode --> string

반대로 byte object 에서 string 으로 변경할 때는 decode 를 사용하면 된다.(참고로 string 은 decode 라는 함수가 없다.)

>>> b'\xea\xb0\x80'.decode()
'가'
>>> b'\xff\xfe\x00\xac'.decode('utf-16')
'가'

>>> b'\x80abc'.decode("utf-8", "strict")  
Traceback (most recent call last):
    ...
UnicodeDecodeError: 'utf-8' codec can't decode byte 0x80 in position 0:
  invalid start byte
>>> b'\x80abc'.decode("utf-8", "replace")
'\ufffdabc'
>>> b'\x80abc'.decode("utf-8", "backslashreplace")
'\\x80abc'
>>> b'\x80abc'.decode("utf-8", "ignore")
'abc'

file write

file 에 write 할 때도 python 3 에서는 기본적으로 unicode 이기 때문에 byte array 로 바꿔줘야 한다.
>> with open('nonlat.txt', 'wb') as f:
f.write(nonlat.encode())

json.dump

ensure_ascii 를 false 로 줘야 file 에서 제대로 된 '한글'을 확인할 수 있다.

with codecs.open(configPath, 'w', encoding='utf-8') as fp:
    json.dump(lastConfig, fp, ensure_ascii=False)

datetime

On Windows + Py3, time.strftime() and Unicode characters will raise UnicodeEncodeError · Issue #2102 · sphinx-doc/sphinx · GitHub

(sdate.strftime('%m월 %d일(%a) %I:%M %p'.encode('unicode-escape').decode())).encode().decode('unicode-escape')  # 11월 1일(수) 오후 3시

Reference

[컴][go] c/c++ 의 pointer 와 go 의 pointer 의 차이

golang / pointer variable of golang

c/c++ 의 pointer 와 go 의 pointer

go 에도 pointer 가 존재한다. 개인적으로 c/c++ 언어 이외에 처음본다 ^^;;

처음에 이것은 heap 에서 allocate 하는 메모리를 줄이려고 한줄 알았는데, 그것은 아닌듯 하다.

ref.2 의 글의 번역을 읽어보면 아니라는 것을 알수 있다.

pointer type으로 구현하나 value type 으로 구현하나 그것이 heap 이나 stack 에 가는 것을 결정하지는 않는다. 이 부분은 Go compiler 가 알아서 변수가 함수내에서만 쓰이면 함수의 stack frame 에 넣어준다고 한다. 그러나 compiler 가 함수가 return 한 이후에도 변수가 계속 referenced 되는지 판단하지 못하는 경우라면, compiler 는 이것을 heap 에다 넣는다.
또한 local 변수가 너무 크면, stack 보다는 heap 에 넣는다고 한다.
current compiler 에서는 변수가 자신의 주소를 가지고 있으면, 이녀석은 heap 에 넣을 후보(candidate) 가 되지만, escape analysis 가 이 변수가 function 이 return 한 이후에 살아 있지 않고, stack 에 머무를 수 있다는 것을 파악한다.(이런 녀석은 heap 에 넣지 않는다. 란 뜻인듯)[ref. 2]

다른 가능성 있는 이유들은 아래 글에서 찾아보자.

why golang has struct values? - Google 그룹스

여하튼 이녀석은 c/c++ 의 pointer 와 거의 유사하다. 그런데 한가지 다른 점은 사용할 때가 좀 다르다.

초기화

초기화는 c/c++ 과 크게 다를 것 없다. 아래처럼 pointer type에서의 intialization 과 value type에서의 intialization 은 다르다.

value 변수의 초기화

// Worker is job thread
type Worker struct {
 name      string
 readyChan chan int
 jobChan   chan interface{}
}


// Pool ...
type Pool struct {
 workers []Worker
}

func NewPool() *Pool {

    numWorkers := 3
    self := &Pool{workers: make([]Worker, numWorkers)}

    for i := 0; i < numWorkers; i++ {
        rc := make(chan int)
        jc := make(chan interface{})
        self.workers[i].readyChan = rc
        self.workers[i].jobChan = jc
    }

    return self
}

pointer 변수의 초기화

// Worker is job thread
type Worker struct {
 name      string
 readyChan chan int
 jobChan   chan interface{}
}


// Pool ...
type Pool struct {
 workers []*Worker
}

func NewPool() *Pool {

    numWorkers := 3
    self := &Pool{workers: make([]*Worker, numWorkers)}

    for i := 0; i < numWorkers; i++ {
        rc := make(chan int)
        jc := make(chan interface{})
        self.workers[i] = Worker{name: "n" + strconv.Itoa(i), readyChan: rc, jobChan: jc}
    }

    return self
}

사용

그런데 사용함에 있어서는 Go 는 좀 더 유연하다. 위의 두가지 initialization 모두 아래처럼 사용할 수 있다.
func main(){
pool := NewPool()
go func(){
pool.workers[0].readyChan <- 1
}()
<-pool.workers[0].readyChan
}

그리고 pointer 로 initialization 을 한 code 에서는 아래처럼 code 를 작성해도 된다.
(*pool.workers[0]).readyChan <- 1

이것은 method 를 사용할 때도 마찬가지이다. 만약 아래 처럼 pointer type의 method 를 하나 만들었다고 해도 value type 변수를 사용해서도 사용할 수 있다.
func (v *Worker) do() {}
func main(){
var w Worker
w.do()
}

이유

이런 것이 가능한 이유는 ref. 1 에 잘 설명되어 있다. 대략적으로 이야기 하면, go compiler 가 알아서 변경을 해주거나 wrapper function 을 만들어 주기 때문이다.

Reference

[컴][go] tunny goroutine 동작

thread pool / goroutine pool /routine pool 분석 / thread pool 분석 / 구현

Tunny goroutine pool

Channels of Channels

Source flow

unbuffered channel은 sender 나 receiver 가 준비가 돼서 communicate 가 될 때까지 block 된다. (wrapper.readyChan)[ref. 2]

pool, _ := tunny.CreatePool(numCPUs, func(object interface{}) interface{} {
    // this is job function
})

--> 
// tunny.CreatePool
for i := range pool.workers {
    newWorker := workerWrapper{
        worker: &(tunnyDefaultWorker{&job}),
    }
    pool.workers[i] = &newWorker
}

-->
pool.Open()
-->
// pool.Open()
for i, workerWrapper := range pool.workers {
    workerWrapper.Open()

    // create cases for select
    // case <- workerWrapper.readyChan : 
    pool.selects[i] = reflect.SelectCase{
        Dir:  reflect.SelectRecv,
        Chan: reflect.ValueOf(workerWrapper.readyChan),
    }
-->
// workerWrapper.Open()
go wrapper.Loop()
-->
// workerWrapper.Loop()
wrapper.readyChan <- 1

-->
// main()
result, _ := pool.SendWork(input)

-->
// WorkPool.SendWork()
/**
  select{ 
    case <--worker.readyChan : {
*/
if chosen, _, ok := reflect.Select(pool.selects); ok && chosen >= 0 {
    pool.workers[chosen].jobChan <- jobData
    result, open := <-pool.workers[chosen].outputChan

    if !open {
        return nil, ErrWorkerClosed
    }
    return result, nil
}

-->
// workerWrapper.Loop()
wrapper.readyChan <- 1 // block until the select finishes processing the readyChan

for data := range wrapper.jobChan {
    wrapper.outputChan <- wrapper.worker.TunnyJob(data)
    for !wrapper.worker.TunnyReady() {
        if atomic.LoadUint32(&wrapper.poolOpen) == 0 {
            break
        }
        time.Sleep(tout * time.Millisecond)
    }
    wrapper.readyChan <- 1
}

Full source

func main() {
    numCPUs := runtime.NumCPU()
    runtime.GOMAXPROCS(numCPUs + 1) // numCPUs hot threads + one for async tasks.

    pool, _ := tunny.CreatePool(numCPUs, func(object interface{}) interface{} {
        input, _ := object.([]byte)

        // Do something that takes a lot of work
        output := input

        return output
    }).Open()

    defer pool.Close()

    http.HandleFunc("/work", func(w http.ResponseWriter, r *http.Request) {
        input, err := ioutil.ReadAll(r.Body)
        if err != nil {
            http.Error(w, "Internal error", http.StatusInternalServerError)
        }

        // Send work to our pool
        result, _ := pool.SendWork(input)

        w.Write(result.([]byte))
    })

    http.ListenAndServe(":8080", nil)
}



func CreatePool(numWorkers int, job func(interface{}) interface{}) *WorkPool {
    pool := WorkPool{running: 0}

    pool.workers = make([]*workerWrapper, numWorkers)
    for i := range pool.workers {
        newWorker := workerWrapper{
            worker: &(tunnyDefaultWorker{&job}),
        }
        pool.workers[i] = &newWorker
    }

    return &pool
}

//--------------------------------------------- WorkPool

func (pool *WorkPool) Open() (*WorkPool, error) {
    pool.statusMutex.Lock()
    defer pool.statusMutex.Unlock()

    if !pool.isRunning() {

        pool.selects = make([]reflect.SelectCase, len(pool.workers))

        for i, workerWrapper := range pool.workers {
            workerWrapper.Open()

            // create cases for select
            // case <- workerWrapper.readyChan : 
            pool.selects[i] = reflect.SelectCase{
                Dir:  reflect.SelectRecv,
                Chan: reflect.ValueOf(workerWrapper.readyChan),
            }
        }

        pool.setRunning(true)
        return pool, nil

    }
    return nil, ErrPoolAlreadyRunning
}

func (pool *WorkPool) SendWork(jobData interface{}) (interface{}, error) {
    pool.statusMutex.RLock()
    defer pool.statusMutex.RUnlock()

    if pool.isRunning() {
        /**
          select{ 
            case <--worker.readyChan : {
              worker.jobChan <- jobData
              result, open := <- worker.outputChan
              if !open { return nil, ErrWorkerClosed }
              return result, nil
            } 
          }
          return nil, ErrWorkerClosed
        */
        if chosen, _, ok := reflect.Select(pool.selects); ok && chosen >= 0 {
            pool.workers[chosen].jobChan <- jobData
            result, open := <-pool.workers[chosen].outputChan

            if !open {
                return nil, ErrWorkerClosed
            }
            return result, nil
        }
        return nil, ErrWorkerClosed
    }
    return nil, ErrPoolNotRunning
}

//--------------------------------------------- workerWrapper

func (wrapper *workerWrapper) Open() {
    if extWorker, ok := wrapper.worker.(TunnyExtendedWorker); ok {
        extWorker.TunnyInitialize()
    }

    wrapper.readyChan = make(chan int)
    wrapper.jobChan = make(chan interface{})
    wrapper.outputChan = make(chan interface{})

    atomic.SwapUint32(&wrapper.poolOpen, uint32(1))

    go wrapper.Loop()
}

func (wrapper *workerWrapper) Loop() {

    // TODO: Configure?
    tout := time.Duration(5)

    for !wrapper.worker.TunnyReady() {
        // It's sad that we can't simply check if jobChan is closed here.
        if atomic.LoadUint32(&wrapper.poolOpen) == 0 {
            break
        }
        time.Sleep(tout * time.Millisecond)
    }

    wrapper.readyChan <- 1 // block until the select process the readyChan

    for data := range wrapper.jobChan {
        wrapper.outputChan <- wrapper.worker.TunnyJob(data)
        for !wrapper.worker.TunnyReady() {
            if atomic.LoadUint32(&wrapper.poolOpen) == 0 {
                break
            }
            time.Sleep(tout * time.Millisecond)
        }
        wrapper.readyChan <- 1
    }

    close(wrapper.readyChan)
    close(wrapper.outputChan)

}

References

[컴][go] 간단한 goroutine 을 사용한 pool - grpool

thread pool in golang / golang thread pool / simple thread pool of go /

grpool

Projects · golang/go Wiki 에 소개된 간단한 goroutine pool 을 한 번 봐보자.

Installation

c:\> go get github.com/ivpusic/grpool

Source flow

/**

*/

// source from : https://github.com/ivpusic/grpool
func main() {
    // number of workers, and size of job queue
    pool := grpool.NewPool(100, 50)
    defer pool.Release()
    
    for i := 0; i < 10; i++ {
        count := i
        // enqueue
        pool.JobQueue <- func() {
            fmt.Printf("I am worker! Number %d\n", count)
        }
    }
}

// Will release resources used by pool
func (p *Pool) Release() {
    p.dispatcher.stop <- true
    <-p.dispatcher.stop
}

func NewPool(numWorkers int, jobQueueLen int) *Pool {
    // create 'queue' and 'worker pool'
    jobQueue := make(chan Job, jobQueueLen) // channel with buffer
    workerPool := make(chan *worker, numWorkers)

    // create a 'Pool' with new dispatcher
    pool := &Pool{
        JobQueue:   jobQueue,
        dispatcher: newDispatcher(workerPool, jobQueue),
    }

    return pool
}
    

// Accepts jobs from clients, and waits for first free worker to deliver job
type dispatcher struct {
    workerPool chan *worker
    jobQueue   chan Job  // channel with Job objects
    stop       chan bool // channel with bool value
}

func newDispatcher(workerPool chan *worker, jobQueue chan Job) *dispatcher {
    d := &dispatcher{
        workerPool: workerPool,
        jobQueue:   jobQueue,
        stop:       make(chan bool),
    }

    // create workers
    for i := 0; i < cap(d.workerPool); i++ {
        worker := newWorker(d.workerPool)
        worker.start()  // at this point, worker is inserted into the workerPool
    }

    go d.dispatch()
    return d
}

func (d *dispatcher) dispatch() {
    for {
        select {
        case job := <-d.jobQueue:
            worker := <-d.workerPool
            worker.jobChannel <- job
        case stop := <-d.stop:
            if stop {
                for i := 0; i < cap(d.workerPool); i++ {
                    worker := <-d.workerPool

                    worker.stop <- true
                    <-worker.stop
                }

                d.stop <- true
                return
            }
        }
    }
}

// Gorouting instance which can accept client jobs
type worker struct {
    workerPool chan *worker
    jobChannel chan Job
    stop       chan bool
}

func newWorker(pool chan *worker) *worker {
    // create a Job channel and stop channel
    return &worker{
        workerPool: pool,
        jobChannel: make(chan Job),
        stop:       make(chan bool),
    }
}

func (w *worker) start() {
    // new thread start
    go func() {
        var job Job
        for {
            // worker free, add it to pool
            w.workerPool <- w

            select {
            case job = <-w.jobChannel:
                job()
            case stop := <-w.stop:
                if stop {
                    w.stop <- true
                    return
                }
            }
        }
    }()
}

References

ivpusic/grpool: Lightweight Goroutine pool

[컴][알고리즘] KNN

machine-learning / 머신러닝 / 알고리즘 / machine learning / ai /

k nearest neighbors classification(KNN)

어떻게 분류하는가?

이 KNN 을 우리말로 번역하면, "K개의 가장 가까운 이웃들" 정도가 되겠다. 일단 claaification 이라는 것은 "분류"를 이야기한다. 그러니까 KNN 은 분류를 하는 방법중 하나이다.

어떤 input(입력) 이 있을 때 KNN 이 어떻게 분류를 하냐면, "input 에 대해서 거리가 가장 가까운 이웃 k개의 모습을 확인하고, 그중에 가장많은 모습으로 input 의 모습을 결정(classify)"하는 것이다. "끼리끼리 노는 느낌"이라고 보면된다.

아래 그림에서 input (녹색) 을 보자. k=3 이면, input 은 "빨강" 이 되는 것이고, k=5 이면 input 은 "파랑" 이 되는 것이다.

k=3 일 때: "빨강 2개" , "파랑 1개" --> input 은 빨강
k=5 일 때: "빨강 2개" , "파랑 3개" --> input 은 파랑

from : ref. 2

거리, distance

이제 대략적으로 KNN 이 무엇인지는 알았다. 그럼 이제 좀 더 자세하게 보자.

위에서
"input 이 들어왔을 때 input 에서 거리가 가장 가까운 녀석 k개를 보고 분류(claasify) 를 한다"
고 했다. 그럼 여기서 문제는 "거리가 가장 가까운 녀석" 에서 "거리" 이다.

이 "거리" 를 측정하는 방법에 따라서 input 에 대해 3번째로 가까울 수도 있고, 1번째로 가까운 녀석이 될 수도 있다.

ref. 1 에 보면 이런 거리를 측정하는 방법 몇가지를 소개해 주고 있다.

from : ref. 1

위의 거리를 측정하는 방법 3개는 "연속적인 변수들"(continuous variables) 에서만 유효하다고 한다. categorical variables 에서는 Hamming distance 를 사용해야 한다고 한다.

이것은 또한 data set 에 숫자형 변수(numerical variables)들과 범주형 변수(categorical variables)들이 섞여있을 때 0과 1사이의 숫자형 변수들에 대한 표준화문제를 가져온다. (얘기가 어려운데 이 부분은 아래 "distance 의 표준화" 부분을 보자.)

from : ref. 1

적절한 K 값

이제 거리에 대한 정의도 되었다. 그러면 이제 k 값을 정해서 그냥 사용하면 된다. 여기서 누군가는 그럼 k 값은 얼마로 정해야 하지? 라고 물을지 모르겠다.

사실 이것은 상황에 따라 다르다. 그렇지 않으면 왜 굳이 K개를 선택하게 했겠는가? 그냥 값을 정해서 알고리즘을 만들었을 것이다.

하지만 어느정도 사람들이 사용을 해보니, 어느정도의 결론이 나왔다. 그 이야기가 ref. 1에 있다. 대략적으로 정리를 하면,

K값이 클수록 평균적인 잡음(noise) 를 제거해 준다면, 일반적으로 큰 K 값이 좀 더 정확한 결과를 가져다 준다.
cross-validation 이 좋은 K 값을 결정하는 다른 방법이다. (?)
역사적으로 대부분의 dataset 에서 가장 적절한 K(optimal K) 는 3~10 사이의 값이다. 이 것이 k=1 보다는 훨씬 좋은 결과를 보여준다.

distance 의 표준화, standardized distance

거리를 계산할 때를 한 번 봐보자. 아래처럼 input(녹색) 에 대해 거리를 계산하게 될 텐데, 이 때 위에서 나온 함수중에 Euclidean(유클리디안) 을 이용한다고 생각해보자.

from : ref. 1

그럼 아래처럼 계산할 수 있다.

그런데 이때 문제는 '나이' 와 '대출' 의 범위가 다르다는 것이다. 그래서 숫자의 크기가 다르다. 위의 예제에서는 대출은 2십만이 넘어가는 숫자이지만, 나이는 70살이하이다. 숫자의 크기가 다르니, 거리값이 숫자가 큰 '대출' 의 값에 의해 결정될 여지가 많아지는 것이다.

그래서 이 문제를 해결하기 위해 값을 표준화(standardization, normalization) 을 해야 한다. 표준화는 그리 어렵지 않다. 아래처럼 해주면 된다.

무슨 뜻이냐 하면, 값 x 를 전체 값 대비해서 어느 위치에 있는 값인지로 변경하는 것이다.

이러면, 값의 범위(scale) 이 0 ~ 1 로 같아지게 되고, 어느 한 변수가 더 큰 영향을 미치는 경우를 막을 수 있다.

scaling : x / (max-min) <--- 이것을 scaling 이라 한다.
mean normalization : x - min <---- 이것을 mean normalization 이라 한다.

References

[컴] flow graph 란?

example of flow graph / flow graph example

flow graph

플로우 그래프(flow graph) 가 뭔지 간략하게 알아보자.

ref. 1 에 나온 정의를 보면 아래와 같다.

계산(computation) 을 표현하는 그래프이다. 이 그래프에서 각 노드는 기본적인 계산과 값을 표현한다.

a flow graph is a graph representing a computation, in which each node represents an elementary computation and a value (the result of the computation, applied to the values at the children of that node). Consider the set of computations allowed in each node and possible graph structures and this defines a family of functions. Input nodes have no children. Output nodes have no parents.

ref. 1 에 나온

sin(a^2 + a/b)

를 아래처럼 그릴 수 있다.

보면 어느정도 파악이 될 것이다. child node 가 input 이 되고, parent 가 output 이 되는 것이다.

References

[컴][수학] 선형독립, 선형종속

선형 종속, 선형 독립

선형종속, 선형독립

선형종속, 선형독립에 대해 알아보자. 둘의 관계를 이야기 하자면 반대되는 관계이다.

선형 종속(linear dependent) <---> 선형 독립(linear independence)

일단 말뜻을 좀 풀어보자면, 선형독립은 linear 한 값들이 독립적이다. 라는 뜻으로 해석해 볼 수 있을 듯 하다.(수학적 정의를 이야기하는 것이 아니니 오해하지 말자.)

그러니까 여기서 linear 한 값이 vector 들인데, 이 vector 들을 합해서 0을 만들 수 없다면, 이 vector 들은 독립적이라고 본 것이다.

반대로 선형종속은 vector 들을 합해서 0을 만들 수 있으면 서로 의존성이 있다고 본 것이다.

그리고 밑의 예제에서도 보면 알겠지만, 이것은 즉 1차 방정식이 성립하는 가를 보여준다. 즉, 2x + 1 = 0 같은 1차 방정식이 성립한다면, 그것은 곧 linear graph 를 그릴 수 있다는 뜻이 된다. 그러므로 이것을 linear dependent 라고 이야기하는 듯 하다.

예제

선형종속이 어떤 모습인지 좀 더 구체적으로 알아보기 위해 아래 동영상에 있는 예제를 하나 가져왔다.

Linear Independence and Linear Dependence, Ex 1 - YouTube
가우시안-조단 소거법 : Using Gauss-Jordan to Solve a System of Three Linear Equations - Example 1 - YouTube
nontrivial : linear 방정식에서 '0' 이외의 해가 존재하는 것

아래처럼 vector 가 3개 있다. 이 vector 의 linear combination 이 0 이 되게 해주는 a1, a2, ... 가 0 이외에 있다면, 이녀석은 linear dependence (선형종속) 라고 이야기 한다.

여기서 0 을 만들어주는 a1, a2, a3 가 존재하는 지 알기 위해 아래처럼 방정식을 세운다.

그래서 이것을 "가우시안-조단 소거법" 으로 풀면 아래와 같이 풀 수 있다.

위의 수식을 만족시키는 (a1, a2, a3) 는 0 vector 를 만들어줄 것이다. 그러므로 위의 vector 3개는 linear dependent (선형종속) 하다.

그래프, 기하학 관점에서 생각해보기

이 '선형종속'을 그래프에서 생각해 보자. 3개의 vector 의 합으로 0 을 만들 수 있다는 이야기는 '2개 vector의 합' 을 이용해서 나머지 '1개 vector ' 를 만들 수 있다는 이야기가 된다.( 0 이 되기위해서는 방향이 정 반대인 같은 크기의 값을 가져야 하니까)

[컴][링크] Deep learning 자료

딥러닝 읽을 자료 / 딥러닝 파악하기

README SanghyukChun's Blog

Machine learning 스터디 (1) Machine Learning이란?

Deep-Learning-Papers-Reading-Roadmap

deep learning 을 위한 자료들이다. 처음에 어떤 자료를 읽어야 할지 막막한 사람들을 위해 songrotek 이라는 분이 정리해놨다. 참고로 영문자료다.

songrotek/Deep-Learning-Papers-Reading-Roadmap: Deep Learning papers reading roadmap for anyone who are eager to learn this amazing tech!

Deeplearning.net Reading list

http://deeplearning.net/reading-list/

Etc

[컴][알고리즘] Raft 알고리즘

Raft 알고리즘에 대한 설명은 ref. 2 를 먼저보자. 간결하게 그림을 이용해서 설명해 주기 때문에 이해하기가 더 쉽다. 아래 자료를 이해하는데에도 ref. 2 를 한 번 보고 보면 이해가 잘 될 것이다.

여기의 내용은 필자가 이해하려고 정리한 내용이라 내용이 부실할 수 있다. 그러니 되도록 Reference 에 적어놓은 원본을 확인하자.

State machine replication

분산에서 사용되는 Replication models(복제모델) 이 몇개 있는데(참고) , 이중에 State machine replication 이 있다. 이 모델이 distributed consensus 를 이용해서 만들어 졌다. 이 모델도 transactional replication model 처럼 많이 쓰인다.

이 모델은 replicated process 가 deterministic finite automation 이고 모든 event 에 대해 atomic broadcast 가 가능하다 는 것을 가정한다.

가정

replicated process 가 deterministic finite automation
모든 event 에 대해 atomic broadcast 가 가능하다

이 state machine replication 은 어떤 node(state machine) 가 동일한 순서로 input 을 처리한다면 동일한 순서의 output 이 나오게 된다. 그렇기 때문에 동일한 순서의 input 을 결정해서 그것을 모든 node 에 뿌려주는 작업을 해야 한다.

Distributed Consensus 는 뭔가?[ref. 1, 2]

이 동의(consensus)에 대한 이야기는 ref. 2 의 slide 를 보는 것이 효과적인 듯 하다.

consensus 동작을 설명하기 위해 "분산으로 구성된 database "를 보자. 이 db 는 각 node 가 같은 data 를 가지고 있어야 한다고 가정하자.

이 때 client 가 한 node 랑 통신을 할 것인데, 이 때 db 에 "x 라는 값을 5로 변경하라" 고 query 를 날렸다고 하자. 그러면 x 가 5으로 바뀌면 명령은 완료된다. 그런데 문제는 distributed system 이다. 여러개의 node 가 가지고 있는 x 라는 값이 다 똑같이 5로 바뀌어야 한다.

이렇게 여러개의 node 가 같은 명령(command) 을 수행해서 같은 동작을 하도록 하기 위해 필요한 것이 consensus(동의) 이다.

이 부분에 대해서는 여기서도 설명을 하겠지만 ref. 2 를 보는 것이 이해하기 좋다.

여하튼 모든 node 들이 같은 행동을 하기 위해서

일단 한 node (node A 라고 하자.)가 command 를 받으면
그것을 바로 수행하지 않고, 그 command 를 log 에 적는다.
그리고 다른 node 들에게 그 command 를 날려준다.
그럼 다른 node 들도 그 command 를 받고 log 에 적은 후에
log 를 적었다고 node A 에게 응답을 준다.
그럼 node A 가 응답들을 보고 과반수 이상이 command 를 log 에 적었다는 것을 확인하면,
node A 는 log 에 적어놓은 그 command 를 실제로 수행 한다.(commit)
그리고 client 에게 응답을 준다.

이 경우에 client 가 응답을 못받으면, command 는 실행되고, client 는 command 가 수행된지를 몰라서 같은 작업을 다시 반복하게 된다. 이렇게 계속 같은 작업을 하게 될 수 있기 때문에 command 에 unique serial number 를 포함시킨다.[ref. 4 > Client interaction]
그 다음 다른 node 들에게 자신(node A) 가 commit 했다고 알려준다.
그럼 다른 node 들도 log 에 적어놓은 comand 를 commit 하게 된다.

아래는 ref. 1 에서 이야기하는 Consensus 에 대한 설명이다.

----------------------------------------------------------------

동의(Consensus) 는 fault-tolerant distributed system(문제가 발생해도 계속 잘 동작하는 분산시스템이라고 보면된다.) 에 기본적인 문제이다.

consensus 는 여러개의 서버들이 값들(values)에 대해 동의하는 것을 포함한다. 그들이 어떤 값에 대한 결정에 도달하자마자, 그것은 최종결정이다. 일반적인 consensus algorithm 들은 다수의 서버들이 동작할 때 일을 진행한다. 예를 들면, 5개 서버로 된 cluster 는 심지어 2개의 서버에 문제가 생겨도 일을 계속해 나갈 수 있다. 만약 더 많은 서버에 문제가 생기면, 그들은 일을 진행하는 것을 멈춘다.(그러나 절대 틀린 결과를 return 하지는 않을 것이다.)

동의는 일반적으로 fault-tolerant system 들을 만드는 일반적인 방법인 replicated state machine들이 있는 상황안에서 발생한다.
각각의 서버들은

state machine과
log

를 갖는다. state machine 은 우리가 fault-tolerant 하고 싶은 구성요소(component)다. 예를 들면 hash table 같은 것이 있다.

client 는 하나의 믿을 수(reliable) 있는 state machine 과 상호작용하게된다.

각 state machine 은 input command 들을 그들의 log 로 부터 받는다.
우리의 hash table 예제에서, log 는 'x 를 3으로 set 하라' 같은 command 들을 가지고 있을 것이다. 서버들의 log 가 갖고 있는 command 에 대해 동의하기 위해서 consensus algorithm 을 사용한다.
consensus algorithm 은 다음과 같은 것을 보장해야만 한다.

만약 n번째 command 로 어떤 state machine 이 'x 를 3으로 set 하라' 는 명령을 적용한다면,
다른 state machine 은 항상 다른 n번째 command 를 적용해야 한다.

결과적으로 각각의 state machine 은 같은 series of commands 를 처리한다. 그리고 그래서 같은 series of result 들을 생산하고 같은 series of states 에 도달하게 된다.

----------------------------------------------------------------

Raft algorithm[ref. 3]

제일 일반적인 동의알고리즘(consensus algorithm) 은 Paxos 인데 이녀석은 이해하기 어렵고, 정확히 구현하기도 어렵다고 알려져 있다.

Raft 는 새로운 동의알고리즘(consensus algorithm)
이해가능함을 위해 디자인됐다.

Raft 는

먼저 server 를 leader 로 선출한다.
그리고 모든 결정들을 leader 에게 모아준다.

이 2가지 과정이 상대적으로 독립적이며 Paxos 보다 나은 구조를 만들어준다.

Raft 는 아래 방법을 이용해서 리더를 선출한다.

투표(voting) 와
랜덤화한 타임아웃(randomized timeouts)

선거(election)는 리더가 이미 필요한 모든 정보를 저장했다는 것을 보장 해 준다. 그래서 데이터는 오직 리더에서 다른 서버들로만 흘러간다.

다른 leader-based algorithm 들과 비교하면, 이것은 방법(mechanism) 을 줄이고 행동을 단순화한다. 리더가 선출되며, 리더는 복사된 log 를 관리한다.

Raft 는 로그들이 어떻게 커지는 지에 관한 간단한 불변(simple invariant)을 레버리지(leverage)해서 알고리즘의 state space 를 줄이고 적은 mechanism 으로 이 작업을 달성한다.

Raft 는 이전의 알고리즘들에 비해 실제 세계 구현에도 적합하다. 이것은 실질적인 배포(deployments) 에도 충분히 잘 동작한다.

이것은 "고객 상호작용을 어떻게 관리하는지", "cluster 의 membership 을 어떻게 바꾸는지", 그리고 "로그가 너무 커졌을 때 그것을 어떻게 컴팩트하게 하는지"를 포함한 모든 완전한 시스템을 만드는 모든 측면을 언급한다.

cluster membership 을 바꾸기 위해, Raft 는 한번에 하나의 서버를 더하거나 뺀다.

(복잡한 변경은 이 기본 과정들로 작성할 수 있다.)

그리고 cluster 는 변경을 하는 중에도 계속해서 request 들을 계속 처리할 수 있다.

리더 선출(leader election)

node 의 state

node 는 다음 3가지 state 를 갖는다.

follower
candidate
leader

처음 시작할 때 node 는 모두 follower 이다. 만약 follower 가 leader 를 가지고 있지 않으면 그들은 candidate 가 될 수 있다.

또는, node 는 leader 로 부터 heartbeat 을 주기적으로 받는데, 이 heart beat 이 오지 않아서 heartbeat timeout 이 끝나면 leader 를 가지고 있던 node 이지만, 이 node 는 candidate 가 되는 것이다.

2개의 timout 세팅

node 는 다음 두종류의 timeout 을 갖게 된다.

election timeout:
follower 가 candidate 가 되기까지 걸리는 시간이다. 150ms ~ 300ms 사이의 random 한 값으로 각 node 가 각자 setting 한다.

그리고 만약 2개의 node 가 candidate 가 되는 경우에는 같은 election term 을 가진 2개의 election 이 발생한다. 이 경우 각 candidate 가 vote 를 해달라고 node 에게 message 를 보낸다.

그러면 한 node 는 같은 election term 을 가진 vote request 를 2개 받을 것이다.
이 경우에 node 는 먼저 온 vote request 에 대해서만 응답을 해주고, 나중에 온 vote request 에는 응답을 하지 않는다.(node 는 한 election term 에 대해서 한개의 vote 만 한다.)

이 때 누군가 과반수를 얻는다면 그 candidate 가 leader 가 되지만, 과반수를 얻지 못하면 candidate 가 timeout 되고 새로운 election term 을 시작하게 된다.

아래 "leader 선출 과정" 참고
heartbeat timeout
주기적으로 leader 가 message 를 보내는데 이 heartbeat timeout 시간안에 보내야 leader 가 살아있다고 판단한다. 만약 이 시간안에 message 가 오지 않으면 node 는 바로 candidate 가 된다.

초기상태

이제 막 node 들의 설치가 끝나고 node 들을 실행(run) 했다고 가정해보자.

각 node 는 각자 150ms ~ 300ms 사이의 random 한 값으로 election timeout 을 setting 하고, 그 시간이 끝나면 follower 에서 candidate 로 상태가 바뀐다.

각 node 가 random 하게 timeout 을 설정했기 때문에 각자 candidate 로 상태가 바뀌는 시간이 다를 것이다.

leader 선출 과정

일단 candidate 가 된 node 는,

새로운 선거기간(election term) 을 시작한다. (termCount: 1)
그리고 자기한테 vote 하고, (voteCount: 1)
다른 node 에게 vote 를 해달라고 request 를 보낸다.(Request Vote message)

이 때 timeout 시작한다. 이 timeout 까지 과반의 vote 를 획득해야 한다.

참고로 다른 node 가 leader 라면서 message 를 보낼 수 있는데 이때는 termCount 가 자신보다 높은지를 확인하고, 높다면 자신은 follower 가 된다.

자세한 사항은 In Search of an Understandable Consensus Algorithm > 5.2 Leader election 을 참고하자.
그러면 request 를 받은 node 들 중에 이 선거기간(election term) 에 "vote 를 하지 않은 node" 들은 candidate 에게 vote 를 해준다.
그리고 이 node 들은 자신들의 election timeout 을 reset한다.
이렇게 해서 한 candidate 가 과반수의 vote(majority of votes) 를 얻으면 그 candidate 가 leader 가 된다. 이 과반수가 leader 가 단 하나만이 존재하도록 보장해 준다.

여러개의 candidate 가 vote 를 해달라고 node 에게 message 를 보내게 되면, node 는 같은 termCount(election term) 을 가진 request 을 여러개 받게 된다. 이 경우에 node 는 먼저 온 request 에 vote 를 하고, 뒤이어 오는 다른 request 에는 vote 를 하지 않는다.(한 election term 에는 한개의 vote 만을 하는 것이다.)

이래서 만약 어떤 candidate 도 '과반수' 를 얻지 못한다면, candidate 들은 timeout 되고, 새로운 election term 을 시작하게 된다.

leader 와 heart beat(Append Entries message)

node 가 leader 가 되면

leader 는 Append Entries message 를 follower 들에게 보내기 시작한다.
이 message 들은 각 node 들이 가지고 있는 heart beat timeout 에 의해 정해진 시간(interval)안에 node 들에게 도착하게 된다.
이 message 를 받으면 node 들은 heart beat timeout 을 reset 하고 다시 시작한다.
그리고 leader 에게 응답을 보낸다.
이 상태가 유지되면 election term 은 계속 같은 id 를 유지하게 된다.

follower 가 heart beat 을 받는 것을 멈추고 candidate 가 될 때까지, 선거기간(election term) 은 계속 된다. 즉 새로운 candidate 가 생겨서 새로운 election term 이 시작되기 까지는 기존의 election term 이 유지되는 것이다.

만약 현재 leader node 가 어떤 이유로 멈추면, hear beat timeout 시간안에 Append Entries message 가 오지 않아서 heartbeat timeout 이 끝나게 된다. 그럼 node 는 바로 candidate 가 되고, "leader 선출 과정" 을 시작하게 된다.

Log Replication, 로그 복제

로그는 client 가 request 한 command 를 적어놓은 것이기 때문에 로그 복제는 command 의 복제라고 보면 된다. 즉 로그 복제를 한다는 것은 실제 동작을 복사해서 follower node 에게 전달하는 것이다. (이것은 state machine 이기 때문에, 같은 순서의 command 를 제공하기만 한다면, 같은 결과를 가져오기 때문에 가능한 것이다.)

이 log replication 은 리더에 의해서 시작된다. 이는 Raft 에서 client 가 leader 에만 접근가능하기 때문이다.

여하튼 leader 는 위에서 heartbeat 로 사용했던 Append Entries message 를 이용해서 변경사항을 node 들에 전달한다.

이것을 대략 정리하면 아래와 같다.

일단 leader node (node A 라고 하자.)가 command 를 받으면
그것을 바로 수행하지 않고, 그 command 를 log 에 적는다.
그리고 다른 node 들에게 그 command 를 날려준다.
그럼 다른 node 들도 그 command 를 받고 log 에 적은 후에
log 를 적었다고 node A 에게 응답을 준다.
그럼 node A 가 응답들을 보고 과반수 이상이 command 를 log 에 적었다는 것을 확인하면,
node A 는 log 에 적어놓은 그 command 를 실제로 수행 한다.(commit)
그리고 client 에게 응답을 준다.

이 경우에 client 가 응답을 못받으면, command 는 실행되고, client 는 command 가 수행된지를 몰라서 같은 작업을 다시 반복하게 된다. 이렇게 계속 같은 작업을 하게 될 수 있기 때문에 command 에 unique serial number 를 포함시킨다.[ref. 4 > Client interaction]
그 다음 다른 node 들에게 자신(node A) 가 commit 했다고 알려준다.
그럼 다른 node 들도 log 에 적어놓은 comand 를 commit 하게 된다.

관련해서 자세한 사항은 ref. 2 를 참고하자. ref.2 에는 추가적으로 partition 이 나눠져서 log 가 2개가 생기는 경우에 대한 예제도 있다.

Client

client 가 처음에 cluster 에 접근하게 되거나 leader 가 crash 되었거나 하면, 여러 node 중에 아무 node 에나 접근하게 된다. 이 때 node 는 이 client 를 무조건 reject 하고 leader 정보를 준다. 그럼 client 가 이 정보를 가지고 다시 leader 로 접근하게 된다.

원래 node 가 leader node 로 부터 AppendEntries message 를 주기적으로 받는데, 이 녀석에 leader 의 network 주소도 같이 있어서 redirect 시켜주는 것은 어렵지 않다.

Read-only operation

Read-only 명령은 log 에 굳이 명령을 적지 않고 수행해도 문제가 없다. 다만 이 경우에 return 해주는 data 가 오래된 data(stale data) 가 아니어야만 한다.

그런데 client 가 통신하고 있는 도중에 leader 가 교체된 상태라면, data 는 최신 data 를 보장할 수 없다. client 에게 return 하는 data 가 아직 leader 의 최신 data 로 update되지 않은 data 일 수 있다.

(참고 : https://youtu.be/6Kwx8zfGW0Y?t=2032)

stale data 의 보장

log 를 이용하지 않고 stale data 가 아닌것을 보장하기 위해 Raft 에서 2가지 예방책이 필요하다.

리더가 최근 정보를 가져야만 한다. 이정보의 내용들은 당연히 commit 이 이미 된 내용(committed entries)이어야 한다.(Leader Completeness Property )

그러나 term 의 시작시점에서는 log 에 적혀있는 entry 중에 어떤 녀석이 commit 된 내용인지 알 수 없다.(ref. 4 > figure 8 참고)

이것을 알기 위해서 Raft 에서는 각 리더가 term 의 시작시점에 blank no-op entry 를 log 에 commit 한다. (그러니까 no-op entry 에 대한 commit 까지 완료하면, 이전의 entry 들은 commit 이 제대로 됐다고 볼 수 있다?)
두번째로 리더 노드는 read-only request 를 처리하기 전에 자신이 리더에서 물러난 상태인지 여부를 확인해야만 한다.

Raft 는 read-only reqeust 에 응답하기 전에 리더가 heartbeat message 를 cluster 의 과반수의 node 와 교환하게해서 이것을 처리한다.

User-group

궁금한 점은 아래 user-group 을 이용하면 될 듯 하다.

raft-dev - Google 그룹스

References

Raft Consensus Algorithm: raft 알고리즘과 관련된 자료들이 전부 모아져 있다. 동영상, library 들의 link 도 있다.
The Secret Lives of Data : Raft 설명, 자세하게 예제를 slide 를 이용해서 설명해준다.
Diego Ongaro's PhD dissertation, Consensus: Bridging Theory and Practice, published by Stanford University in 2014 > Abstract
In Search of an Understandable Consensus Algorithm,

[컴][알고리즘] 얼굴 인식, 안면인식

Face recognition

face recognition (안면인식)에 대한 글이 있어서 정리를 좀 해본다. 대부분의 내용은 번역이 될 듯 하고, 개인적으로 이해한 대로 좀 각색하게 될 듯 하다.

동작

컴퓨터가 얼굴을 인식할 때 아래 4가지 과정을 거치게 된다.

먼저, 사진을 보고, 그곳에 있는 모든 얼굴을 찾는다.
2번째로 각각의 얼굴에 집중하고, 얼굴이 이상한 방향으로 되어 있고, 조명이 좋지 않아도 그것은 여전히 같은 사람이라는 것을 이해할 수 있어야 한다.
3번째로 다른 사람과 다른 고유한 특징(unique features)들을 뽑아낼 수 있어야 한다. 예를 들면 눈이 얼마나 큰지, 얼굴이 얼마나 긴지 등의 요소들
마지막으로 이 고유한 특징을 당신이 이름을 알고 있는 모든 사람들과 비교한다.

Step 1. 얼굴 찾기

얼굴찾기 알고리즘

Paul Viola 와 Michael Jones 가 값싼 카메라에서도 충분히 빠르게 얼굴을 찾는 방법을 발명했다. 그 덕분에 2000년대초에 얼굴인식 이 주류가 될 수 있었다.

요새는 좀 더 신뢰성있는 알고리즘을 사용한다. 그 알고리즘이 Histogram of Oriented Gradients(HOG) 이다. 2005년 만들어졌다.

HOG

HOG 에서는 SIFT 방법을 사용해서 이미지의 윤곽을 인식한다.

SIFT

정확한 SIFT 방법은 여기 를 참고하자. 여기서는 대략적으로 어떤 식으로 동작하는지 알아보는 정도 수준이라는 것만 명심하자.

color 정보가 필요없으니, 이미지를 흑백으로 만든다.

이 이미지를 한 픽셀(pixel) 씩 보기 시작한다. 그러면서 이 pixel 의 위아래옆에 있는 8개의 pixel 도 같이 본다.

목표는 현재 보는 pixel 이 주위 8개의 pixel 보다 얼마나 어두운지를 알아내는 것이다.
그래서 어두워지는 방향으로 화살표를 그리는 것이다. 예를 들면, 현재 pixel 보다 위가 더 어두우면 up-arrow 를 사용하고, 위와 오른쪽이 더 어둡다면 up-right arrow 를 사용하는 것이다. 이렇게 되면 모든 pixel 은 화살표로 채워진다.

그리고 여기에 더해서 그 정도의 차이를 구한다. 그러니까 현재 pixel 에 비해 얼마나 진한가등의 정보를 구한다. 그래서 이 "방향 + 진한정도(magnitude)" 가 한개의 vector 가 되는 것이다. 이 화살표 vector 를 gradient 라고 부른다.
(실제로 구현은, 각 방향에 대한 gradient 값(histogram) 을 저장하는 형식으로 구현되는 듯 하다.)

이렇게 하면 어떤 방향으로 갈수록 더 어두워지는지를 알 수 있게 된다. 이 방법의 장점은 빛의 방향(?)을 알 수 있게 돼서 너무 밝은 사진에서도, 너무 어둡게 찍힌 사진에서도 사람의 형체를 알아보기가 수월해진다. 다시 말하면, 윤곽을 어두운 정도로 찾아내기 때문에 명확한 구분이 되는 선이 보이지 않아도 가능하다.

그런데 이 gradient 는 너무 세세한 level (그러니까 pixel level) 로 되어 있다. 그래서 오히려 형체를 알아보기가 어렵다. 장님이 코끼리 만지는 느낌이랄까. 그래서 좀 더 higher level 로 이 gradient 를 만들어야 한다. 그래서 이것을 16x16 pixcel 단위로 나눈다. 이 16x16 단위를 cell 이라고 부르자.( Histogram of Oriented Gradients(HOG) 에서는 16x16, 8x8 로 쪼개는 것이 효율적이라고 이야기한다. 자세한 내용은 원문을 참고하자.)

그래서 그 안에서 각 direction 에 해당하는 magnitude 의 합을 구하면, 어느 방향이 가장 큰 magnitude 를 가지는지 알 수 있다. 그 방향이 그 단위의 major direction (dominant direction)이 되는 것이다.

각 방향별로 vector 가 있다. 긴 화살표가 더 큰 magitude 를 나타낸다.

그 cell 을 major direction 을 표현하는 image 로 바꿔 놓는다. 그러면 이제 우리는 대략적인 윤곽을 보여주는 image 를 갖게 된다. 이것을 HOG image 라고 하자.

컴퓨터에게 A에 대한 여러 사진을 주면, 컴퓨터가 HOG image 들을 생성하고, 이 image 를 이용해서 A 에 대한 HOG pattern 을 만든다.

이것을 새롭게 올라온 사진의 HOG image 가 어떤 HOG image 와 비슷한지를 봐서 누구인지를 판단하는 것이다.(machine learning)

python 과 dlib 를 이용해서 구현할 수 있다.

작성중....

References

[컴][수학] 제곱, 제곱근의 의미

지수, 승수 / 빅오 /

내 멋대로 풀어보는 "제곱근"의 의미

이 이야기는 제곱의 느낌을 위해 log 의 개념을 이용했다고 보면 될 듯 하다.

제곱의 의미가 그렇게 어렵지 않다. 제곱은 곱하기를 몇번 하느냐를 나타낼 뿐이다.

예를 들어 2의 제곱은 2를 2번 곱하는 것이고, 2의 3제곱은 2를 3번 곱하는 것이다.

2² = 2 * 2
2³ = 2* 2 * 2
...

그럼 제곱근도 간단하다. 제곱근은 몇번을 곱해야 값이 나오는 가를 알려준다.

예를 들어 "2의 제곱근"은 "2의 제곱근" 을 2번 곱해야 2가 되는 것이고, "2의 세제곱근"은 "2의 세제곱근"을 3번 곱해야 2가 되는 것이다.(앞으로 제곱근은 편의상 root() 로 표현한다.)

그래서 이 제곱근은 아래 처럼 표현되기도 한다.

그런데 사실 이 제곱근이라는 숫자가 확 와닿지 않는다. 예를 들어 어떤 경우의 수가 10개가 있다라고 했을 때는 금방 이해되지만, 경우의 수가 root(10) 이라고 했을 때는 몇가지를 이야기하는지 잘 와닿지 않는다. 그나마 숫자라면 괜찮지만, 만약 N 이라고 한다면 어떨까?

사람마다 다르겠지만, 내 경우 어떤 값을 뜻하는지 느낌이 잘 안잡혔다. 그래서 이 글을 쓰고 있다.

제곱, 제곱근은 '단계' 이다.

여하튼 서론이 길었는데 결론은 이렇다.

제곱은 단계를 늘리는 것이고, root(N) 는 단계(level)를 줄이는 것으로 이해 하면 된다. 설명이 어렵지만, 일단 그림을 보자

먼저 "제곱"을 보면

2²라는 경우라면, 2개의 객체가 자기 자신만큼의 자식을 복제하는 것을 2단계 한 셈이다.
2³라는 경우라면, 2개의 객체가 자기 자신만큼의 자식을 복제하는 것을 3단계 한 셈이다.

즉 제곱이 한개 올라갈 때 마다, 각 객체가 자가 복제를 한 것이다. 3개도 마찬가지다. (아래 그림 참조.)

반대로 root() 는 단계가 줄어든다.

2의 제곱근은 2단계까지 간 녀석을 1단계로 돌려놓고,
2의 세제곱근은 3단계까지 간 녀석을 1단계로 돌려놓는다.

이제 상상을 하자. 그럼 root(N) 은 무엇일까?
그것은 N 이라는 수가 2²나 3²같은 숫자인 것이다. 그래서 N은 이미 자기 복제를 해서 2단계로 간 상황이다. 이런 상황에 있는 N을 다시 돌려놓는것이다. 이것이 root(N) 인 것이다.

[컴] 스칼라 곱 - dot product

스칼라 곱

2개의 vector 에 대한 dot product( 스칼라곱 , inner product, scalar product 라고 불린다. ) 는 a ∙ b 로 표현된다.

대수학 정의

그리고 실제 계산은 아래처럼 한다.

기하학적 정의

그런데 이것을 아래처럼 계산하기도 한다.

a ∙ b = |a||b| cos(θ) = |b||a|cos(θ)
(단 유클리드 공간이며, a, b 는 유클리드 벡터(Euclidean vector) 이다.)

이것은 서로 다른 방향의 벡터를 같은 방향으로 놓고, 그 값(magnitude) 만 계산하려고, A 를 B와 같은 방향으로 만들고, 이것을 곱한 것이라 볼 수 있겠다.

Reference

[컴] cosine similarity - 코사인 유사도

추천시스템 만드는 법 / 추천 시스템

코사인 유사도

cosine similarity (코사인 유사도) 에 대해 알아보자.

코사인 테이블 을 보면서 이야기를 하자. 코사인은 직각삼각형에서 3개의 각이 있는데 각각의 각(angle) 에 대한 비율을 표시하는 방법으로 sin, cos, tan 라는 이름을 썼다. 그중에 (밑변/빗변) 을 cos(코사인) 이라고 정의했다.

이것을 두개의 벡터(vector) 가 같은 방향(orientation) 을 갖는지 여부를 판별하는 데 사용할 수 있다.

무슨 말인가 하면, 두개의 vector 의 방향이 같다면, 각도는 0도가 되고, cos(0)=1 이 된다. 만약 두개의 vector 의 방향이 90도를 이룬다면, cos(90)=0 이 될 것이다. 만약 vector 의 각도가 180도가 되면 어떨까? 이 때는 -1 이 된다.

정리하면, 두 vector 의 방향이 같으면, 1 이 되고, 점점 각도가 벌어질 수록 값은 작아지고, 결국 90도가 되면 0 이 되는 것이다.

이런 이유로 cos 의 값을 보면 vector 의 방향이 서로 얼마나 다른지를 판단할 수 있게 된다. 이런 식으로 vector 의 방향의 유사성을 판단하는 것을 ‘코사인 유사도’(cosine similarity) 라고 한다.

이런 코사인 유사도는 특히 결과가 "0이상 1이하([0, 1])" 인 positive space(양수공간)에서 많이 쓰인다.

유사도 계산

두 벡터의 스칼라 곱에서 '기하학적 정의' 를 보면 아래와 같이 '스칼라 곱'을 표현할 수 있다.

a ∙ b = ||a|| ||b|| cos(θ)

이 식에서 cos(θ) 를 유도하게 된다. 아래는 ref. 2 에서 가져온 그림이다.

예를 들어 아래와 같은 vector 라면,

A = [1, 2]
B = [3, 4]

아래처럼 계산되어 진다.

즉, 벡터 A, B 의 유사성(similarity) 는

이 된다.(1 에 가까울 수록 더 유사도가 높다.)

References

[컴][파이썬] python 의 Future 가 동작하는 방법

python 3 에서 Future 의 동작 정리

python 3 의 Future 라는 녀석이 있다. 이녀석은 그냥 data 를 나르는 class 정도로 여기면 된다. c 에서 이야기하는 structure 같은 느낌으로 말이다.

그런데 python 의 code 에서 이녀석이 동작하는 방식이 library 안으로 들어가 있어서 언뜻 잘 이해가 안되다.

그래서 동작하는 순서대로 소스를 정리해봤다.

thread 와 future 의 flow

간단한 예제

간단한 아래 예제 소스를 한 번 보자.(출처 : Python: A quick introduction to the concurrent.futures module | Abu Ashraf Masnun)

아래 소스는 간단하다. pool.submit 을 하면 thread 가 만들어지고, thread 가 만들어지면서 future 를 return 해준다. 그러면 thread 가 동작을 하다가 동작을 완료하면 state 를 변경하고, future.set_result() 를 통해 결과를 future 에 넣어준다. 그러면 그 결과를 future.result() 를 통해 가져오게 되는 것이다.

future 를 share 해서 다른 thread 의 결과값을 가져온다고 생각하면 될 것 같다. 자세한 동작은 다음을 보자.

from concurrent.futures import ThreadPoolExecutor
from time import sleep
 
def return_after_5_secs(message):
    sleep(5)
    return message


 
pool = ThreadPoolExecutor(3)
 
future = pool.submit(return_after_5_secs, ("hello"))
print(future.done())
sleep(5)
print(future.done())
print(future.result())

동작

아래 소스를 쭉 따라가보면 최종적으로 _WorkItem.run() 에서 self.future.set_result(result) 를 해서 future 에 result 를 넣어주게 된다.

그래서 우리는 이 future 로 현재 동작하고 있는 thread 의 결과를 쉽게 얻어오게 된다. 이것은 특별한 방법은 아니지만, worker thread 와 main thread 와의 data 전달을 하는 방법을 future 라는 것으로 규격화했다. 그래서 개념만 잘 익힌다면, programming 을 쉽게(?) 할 수 있다.

이런 pattern 이전에 썼던 방법들---queue 를 이용하던지, 아니면 공유되는 variable 을 사용하던지 하는 방법등---을 생각해 보면 이해가 쉬울 듯 하다.

# thread.py

class ThreadPoolExecutor(_base.Executor):
    def __init__(self, max_workers):
        ...
        self._work_queue = queue.Queue()
        ...

    def submit(self, fn, *args, **kwargs):
        with self._shutdown_lock:
            if self._shutdown:
                raise RuntimeError('cannot schedule new futures after shutdown')

            f = _base.Future()
            w = _WorkItem(f, fn, args, kwargs)

            self._work_queue.put(w)
            self._adjust_thread_count()
            return f

    def _adjust_thread_count(self):
        # When the executor gets lost, the weakref callback will wake up
        # the worker threads.
        def weakref_cb(_, q=self._work_queue):
            q.put(None)
        # TODO(bquinlan): Should avoid creating new threads if there are more
        # idle threads than items in the work queue.
        if len(self._threads) < self._max_workers:
            t = threading.Thread(target=_worker,
                                 args=(weakref.ref(self, weakref_cb),
                                       self._work_queue))
            t.daemon = True
            t.start()
            self._threads.add(t)
            _threads_queues[t] = self._work_queue

class _WorkItem(object):
    def __init__(self, future, fn, args, kwargs):
        self.future = future
        self.fn = fn
        self.args = args
        self.kwargs = kwargs

    def run(self):
        if not self.future.set_running_or_notify_cancel():
            return

        try:
            result = self.fn(*self.args, **self.kwargs)
        except BaseException as e:
            self.future.set_exception(e)
        else:
            self.future.set_result(result)

            
def _worker(executor_reference, work_queue):
    try:
        while True:
            work_item = work_queue.get(block=True)
            if work_item is not None:
                work_item.run()
                # Delete references to object. See issue16284
                del work_item
                continue
            executor = executor_reference()
            # Exit if:
            #   - The interpreter is shutting down OR
            #   - The executor that owns the worker has been collected OR
            #   - The executor that owns the worker has been shutdown.
            if _shutdown or executor is None or executor._shutdown:
                # Notice other workers
                work_queue.put(None)
                return
            del executor
    except BaseException:
        _base.LOGGER.critical('Exception in worker', exc_info=True)






# threading.py
class Thread:
    ...
    def __init__(self, group=None, target=None, name=None,
                 args=(), kwargs=None, *, daemon=None):
        ...
        self._target = target
        ...
    def start(self):
        ...
           _start_new_thread(self._bootstrap, ())
        ...
        self._started.wait()

    def _bootstrap(self):
        try:
            self._bootstrap_inner()
        except:
            if self._daemonic and _sys is None:
                return
            raise

    def _bootstrap_inner(self):
        try:
            ...
            try:
                self.run()
            except SystemExit:
                ...

    def run(self):
        try:
            if self._target:
                self._target(*self._args, **self._kwargs)
        finally:
            del self._target, self._args, self._kwargs


# thread.py

[컴][머신러닝] Strategies to scale computationally: bigger data

아래는 6. Strategies to scale computationally: bigger data — scikit-learn 0.17.1 documentation 의 내용을 번역했다.

6.1. Scaling with instances using out-of-core learning

Out-of-core learning 은 RAM 용량보다 더 큰 data 를 통해 learn 할 때 사용하는 기술이다. 대략적으로 아래같은 기술을 사용한다.

instance를 stream 으로 만드는 것
이 instance 에서 feature 들을 추출(extract) 하는 것
incremental algorithm(점진적인 알고리즘)

6.1.1 Sreaming instances

기본적으로 file들, database, network stream 에서 instance 들을 만들어내는 reader 들일 것이다. 그러나 자세한 이야기는 이 문서의 범위를 넘어간다.

6.1.2. Extracting features

scikit-learn 에 feature 추출을 하는 부분은 구현되어 있다. 하지만 "data 에 대한 vectorization 작업하는 위치"와 "feature 나 값들의 집합이 미리 알려져 있지 않은 부분"에 대해서는 작업을 해줘야 한다.

만약 application 관점에서 data 에 대해 여러개의 pass 들을 만드는 것이 합리적이면 stateful vectorizer 를 사용하는 것은 가능하다.
그렇지 않으면 stateless feature extractor 를 사용해야 하는데 이것이 어렵다. 요즘 선호되는 방식은 hashing trick 이라 불리는 것이다.
scikit-learn 에 구현되어 있는데,

sklearn.feature_extraction.FeatureHasher 는 python dicts 들로 이뤄진 list 로 표현된 categorical 변수들의 data set 에 사용할 수 있고,
sklearn.feature_extraction.text.HashingVectorizer 는 text documents 에 사용할 수 있다.

6.1.3. Incremental learning

모든 알고리즘이 전체를 파악하지 않고서는 배울 수 없다.
partial_fit API 을 구현한 모든 estimator 들은 후보자들이다.(아래 리스트 참조)

instance 들의 mini-batch 로 부터 점차적으로 배우는 능력(때때로 이것을 online learning 이라 부른다.) 은 out-of-core learning 에서 중요한 부분이다. 알다시피 어떤 주어진 시간에도 메인메모리에 오직 instance 들의 작은 부분만 있는 것만을 보장하기 때문이다.

relevancy 와 메모리 footprint 의 균형을 맞추는 적절한 mini-batch 의 size 를 선택하는 것은 약간의 조율 작업을 필요로할 수 있다.

estimator 리스트

Classification

sklearn.naive_bayes.MultinomialNB
sklearn.naive_bayes.BernoulliNB
sklearn.linear_model.Perceptron
sklearn.linear_model.SGDClassifier
sklearn.linear_model.PassiveAggressiveClassifier

Regression

sklearn.linear_model.SGDRegressor
sklearn.linear_model.PassiveAggressiveRegressor

Clustering

sklearn.cluster.MiniBatchKMeans

Decomposition / feature Extraction

sklearn.decomposition.MiniBatchDictionaryLearning
sklearn.decomposition.IncrementalPCA
sklearn.cluster.MiniBatchKMeans

리스트중에 classification 에 대해서, 약간 언급해야 할 중요한 것은 비록 stateless feature extraction routine 이 새롭거나 보이지 않는 속성(attribute)들을 다룰 수 있을 수 있지만,
점진적인 learner , 그 자체는 새롭거나 보이지 않는 target 들의 class 들을 다룰 수 없을 것이다.
이 경우에 우리는 모든 가능한 class 들을 처음 partial_fit 을 호출할 때 classes parameter 를 통해서 넘겨줄 수 있다.
(역자: stateless feature extraction 으로 새로운 feature 들을 뽑아내는 것은 문제가 없지만, 이 feature 를 어떤 class 로 분류해야 하는데, 이 때 새로운 class 를 알아서 learner 가 만들 수는 없다. 그러므로 이를 위해서 partial_fit 을 처음 call 할 때 classes= 를 통해서 모든 가능한 class 들을 넣어줘야 한다.)

6.1.3. Incremental learning

적절한 알고리즘을 선택할 때 고려해야 할 다른 부분은 모든 알고리즘들이 시간이 지남에 따라 각각의 예제에 대한 중요도가 변한다.

다시말하면, Perception 은 여전히 나쁘게 labeled 된 예제들에 민감하다. 심지어 많은 예제를 처리한 이후에도 그렇다. 반면에 SGD* and PassiveAggressive* family 들이 이런 요소에 좀 덜 민감하다.

반대로, 이후에는 또한 "너무 다름" 에 대해 중요도를 덜 부여하는 경향이 있다. 그렇지만, 시간이 지남에 따라 learning rate 가 감소할 때 stream 의 뒷부분에 적절하게 labeled 된 예제들이 있을때는 그렇지 않다.(해석이 불분명)

[컴][머신러닝] Feature extraction

4.2. Feature extraction — scikit-learn 0.17.1 documentation 의 글 중 일부를 번역해 놓는다.

Feature extraction

Feature extraction 은 text 또는 image 같은 임의의 data(arbitrary data) 를 machine learning 에 쓸수있는 "숫자와 관련된 feature 들(numerical features)"로 변환하는 특징을 갖는다. [ref. 1]

Text feature extraction

The Bag of Words representation

text content 에서 numerical feature 를 추출하기 위해 scikit-learn 에서 다음 3개의 utility 를 제공한다.

tokenizing : 이건 문자열을 token 들로 쪼개는 것이다.
counting : 각 문서(document) 의 토큰이 몇번 나왔는지를 세는 것
normalizing and weighting with diminishing importance tokens that occur in the majority of samples / documents.

tokenizing, counting, nomalizing 을 하는 이 특정 전략을 bag of words 라 한다.

이 전략에서 feature 와 sample 의 정의는 아래와 같다.

feature : 여기서 feature 는 "각각의 token의 발생 빈도" 이다.
sample : 모든 token 의 빈도들을 갖고 있는 vector 는 다변수의 sample 로 여겨진다.

참고로, text documents 더미를 numerical feature vector 들로 변환하는 것을 vectorization 이라 한다.

"Bag of words" 표현(representation) 또는 "Bag of n-grams" 표현 이라 얘기한다.
여기서 document 는 word 의 occurrence로만 표현된다. 단어의 상대적인 위치 정보는 무시한다.

...

Limitations of the Bag of Words representation

자세한 이야기는 link 를 이용하자. 대략적으로 Bag of words representation 의 한계를 이야기하면, 같은 의미의 단어인데,

철자가 틀렸거나,
복수형등으로 조금 변형된 상태

에서도 다른 단어로 처리하게 되는 것이다. 이런 요소로 classification 의 정확도가 떨어진다. 이런 것을 극복하기 위해 "n-grams" 를 사용하게 된다.

이건 단어 하나를 그대로 하나의 token 으로 인식해서 판별하는 것(n-gam 0)이 아니라, 그것을 여러개의 combination 을 만든다. 예를 들어,
"A T T C A" 라는 문장이 있다면, 이것을 unigram(n-gram 0) 으로 분할 하면,
A, T, T, C, A
로 나눠서 검사를 하는데, bigram(n-gram 1) 로 분할하면,
AT, TT, TC, CA
로 나눠서 이것들을 검사하게 된다.

이렇게 n-gram 을 vectorizer 의 parameter 로 지정해 줄 수 있다. 자세한 것은 link 를 참고하자.

Vectorizing a large text corpus with the hashing trick

이제까지 언급한 vectorization 방법들(CounterVectorizer, TfidfVectorizer 등등) 은 메모리 안에서 token 들을 "정수 feature의 인덱스"에 mapping 했다. 근데 이게 큰 dataset 을 처리할 때 문제가 있다.

더 큰 크기의 문서를 다루면, 많은 더 많은 단어들이 사용되고 이게 또 메모리를 더 많이 사용하게 된다.
fitting 은 원본 dataset 에 비례하는 크기의 중간 데이터 구조에 대한 메모리 할당을 필요로 한다.
word-mapping 을 만드는 것은 dataset 를 전부 읽는 과정이 필요하다. 그래서 text classifier 를 특히 온라인 등의 환경에 맞우는 것은 불가능하다.
큰 vocabulary_ 를 가지고 vectorizers 를 pickling 과 un-pickling 하는 것은 매우 느릴 수 있다.(일반적으로 같은 크기의 NumPy array 같은 flat data structures 를 pickling / un-pickling 하는 것보다 훨씬 느리다.)
vocabulary_ 속성은 공유되는 state 로 하고 "잘 만들어진 동기화 장벽(synchronization barrier)"를 이용해서 vectorization 작업을 concurrent 한 sub task 로 분리하는 것은 쉽지 않다.
token 문자열 을 feature index 에 mapping 하는 것은 각 token 의 첫 occurrence 의 순서에 달려있다. 그래서 공유되어야만 한다. 그런데 이것은 잠재적으로 councurrent worker들의 sequential variant 보다 더 느리게 만들정도로 성능에 해를 끼친다.

sklearn.feature_extraction.FeatureHasher class 에 구현되어 있는 hashing trick (Feature hashing) 과 CountVectorizer 의 text preprocessing, tokenization feature 들과 결합해서 이 한계를 극복할 수 있다.

Feature hasing

machine-learning 에서 feature hashing 은 hashing trick 으로 알려져 있다.
빠르고, space 효율적인 feature 를 vetorize 하는 방법이다. 즉, 임의의 feature 들을 vector 안의 index 로 바꿔주는 작업이다.
hash function 를 feature 들에 적용한다. 그리고 그들의 hash 값들이 바로 index 로 이용된다. 중간에 hash 와 array 의 index 를 다시 mapping 하는 부분을 두지 않는다.

보통 document 가 있으면 이것을 word 로 쪼개서 matrix 를 만들게 된다. 그러면 하나의 row 가 하나의 document 를 뜻하게 되고, column 이 한개의 word 를 뜻하게 된다. 이 경우에 word 에 해당하는 index 가 무엇인지를 알려주기 위해 index table 이 필요하다. 일반적으로 learning time 또는 그 전에 training set 의 vocabulary 에 대한 dictionary 를 하나 만들게 된다.

1st doc : Nam is working
2nd doc : Nam is not working

         Nam     is  working   not
1st doc.  1       1     1       0
2nd doc.  1       1     1       1

dictionary = {
 'Nam': 0,
 'is': 1,
 'working': 2,
 'not': 3
}

value = matrix[1][dictionary['Nam']]

 |
 |
 |
 \/
 
value = matrix[1][hashFunc('Nam')]

이것의 문제는 document 크기가 크거나, document 가 많아져서, training set 이 커지고, 그 안의 vocabulary 가 많아지면, dictionary 를 만들기 위해 더 많은 memory 가 필요하다.

이렇게 dictionary 를 만드는 대신에 hashing trick 을 이용하는 feature vectorizer 는 hash function 을 feature(여기선 word 가 되겠다.) 에 적용해서 "미리 정해진 길이의 vector" 를 만들 수 있다.
hash value 를 feature index 로 사용해서 그 index 에 있는 vector 값을 업데이트 한다.(hash value 가 vector size N 을 넘지 않게 하기 위해 mod N 을 해준다.)

이 경우에, collision 이 생길 수 있다. 이를 위해 또 다른 hash function을 제공한다.(그러나 이것으로 collision 이 해결되지는 않을 듯 한데....)

Reference

[컴] go-ethereum 빌드 하기

이테리움 go 버전 빌드하기 / 에테리움 /

go-ethereum

이녀석이 ref. 1 에 따르면

"Ethereum 의 공식 구현체 중 가장 빠르게 버전업이 되는 구현체이며, DApp 클라이언트 플랫폼으로 Go Ethereum (Geth) 를 공식화" <from ref. 1, ref. 3>

하고 있다고 한다. 여하튼 그래서 이녀석을 택했다.

windows 에서 go-ethereum 설치하기

Installation instructions for Windows · ethereum/go-ethereum Wiki · GitHub

windows 64 bit 에서 설치하는 법이 나와있다. 여기서는 당연히(?) source compile 부분을 살펴보겠다.

여기서는 winbuild 를 사용해서 compile 하는 방법을 사용한다. (Installation instructions for Windows · ethereum/go-ethereum Wiki · GitHub)

필요한 프로그램

git : Git - Downloads
golang :
Downloads - The Go Programming Language
> go1.6.1.windows-amd64.msi 설치
winbuilds 설치 :
Download and Installation From Windows [Win-builds]
혹시나 mingw32 가 설치되어 있다면, 지우거나 path 에 드러나지 않게 하자. 여기선 64bit compiler 가 필요하다.(참고)
MinGW-w64 이용 : delve debugger 를 이용할 때 MinGW-w64 가 있어야 해서 MinGW-w64 를 이용하는 것이 winbuilds 를 이용하는 것보다 낫다.(windows 에서 go deubugger delve 설치 를 참고하자.)

위의 3가지가 필요하다.
여기서는 아래 directory 에서 작업을 한다.

GOPATH, go-ethereum 설치한 곳 : d:\mine\programming\go\ethereum
GOROOT, golang 설치한 곳 : d:\go
winbuilds 설치 : d:\winbuilds

빌드 과정

환경 변수 설정

set GOROOT=d:\go
set GOPATH=d:\mine\programming\go\ethereum
set path=%path%;c:\Program Files (x86)\Git\bin\;%GOPATH%\bin;%GOROOT%\bin;d:\winbuilds\bin\

godep 설치
```
d:\go\bin>go get github.com/tools/godep
```

go-ethereum source 다운로드:

git clone https://github.com/ethereum/go-ethereum src\github.com\ethereum\go-ethereum

빌드 :
%GOPATH%\go-ethereum\cmd\geth 로 가서
```
git checkout develop && godep go install
```
그러면 아래 경로에 geth.exe 가 만들어진다.

%GOPATH%\bin\geth.exe

go-ethereum 소스가 약 360 MB 정도 된다.(git 설정파일까지 합해서는 약 450 MB 정도 된다.)

Linux Ubuntu 14.04 에서 빌드

확실히 원래 리눅스 계열에서 작업한 것이라 그런지 리눅스에서 build 하는 것이 간단하다. windows 가 편해서 windows 에서 build 하려고 애썼긴 했는데, 삽질을 줄이려면 vm 깔고, linux 에서 build 하는 것이 훨씬 나은듯 하다.

Go v 1.5.x 설치

apt repository 추가 : Installation Instructions for Ubuntu · ethereum/go-ethereum Wiki · GitHub

sudo add-apt-repository -y ppa:ethereum/ethereum
sudo apt-get update
sudo apt-get install golang
mkdir -p ~/go; echo "export GOPATH=$HOME/go" >> ~/.bashrc
echo "export PATH=$PATH:$HOME/go/bin:/usr/local/go/bin" >> ~/.bashrc

필요한 library 들 설치

sudo apt-get install -y build-essential libgmp3-dev

빌드

git clone https://github.com/ethereum/go-ethereum ~/go/src/github.com/ethereum/go-ethereum
cd ~/go/src/github.com/ethereum/go-ethereum
make geth

최종적으로 geth 파일은 아래 경로에 만들어진다.

geth file path : ~/go/src/github.com/ethereum/go-ethereum/build/bin/geth

Reference

[컴] Porter / Duff Mode - 1

안드로이드 / 그래픽 포터 더프 모드 / 색 조합 방법 / 그래픽 모드

Porter/Duff Mode

shader 를 사용할 때 모드중에 PorterDuff Mode(Porter/Duff) 가 있다. 오늘은 이녀석에 대해 간략하게 알아보자.

Porter/Duff 는 이 두사람이 쓴 논문에 있는 내용이 2개의 image 를 pixel 정보를 가지고 composite(조합?) 하는 방법에 대해 이야기하는데, 거기에 나온 내용을 구현해 놓은 것이다. 필자도 대충 본 것이라 일단 넘어가자 ^^

ref. 4 를 보면 PorterDuff Mode 의 연산방법에 대한 enum 값이 나와 있다. 근데 공부좀 해야 알아먹을 정도이다. 그래서 여기서는 조금 쉽게 이야기 한다.(대신에 부정확할 수 있지만 그것은 알아서 판단하자.^^;;)

일단 어떤 연산(operator) 이 있는지 알아보자.

DST
DST_ATOP
DST_IN
DST_OUT
DST_OVER
CLEAR
SRC
SRC_ATOP
SRC_IN
SRC_OUT
SRC_OVER
XOR
LIGHTEN
ADD
DARKEN
MULTIPLY
OVERLAY
SCREEN

18개나 있다 ^^;; 오늘은 이중에 설명이 비교적 쉬운(?) 위의 12개에 대해서만 이야기하도록 하자.

설명을 위해서 ref. 2 에서 그림을 좀 가져왔다. 그림을 보면 대략 감이 잡힌다.

from : ref. 2

Porter/Duff formula

Porter / Duff 의 operator 들은 아래 공식을 사용한다. operator 는 모두 아래 공식을 이용하고, s, d , b 에 어떤 값이 들어가느냐에 차이가 있다.

A_src⋅[s]+A_dest⋅[d]+A_both⋅[b]

s, d , b 는 영역을 나타내는 변수라고 보면 된다.

source(s) : source 의 영역
destination(d) : destination 의 영역
both(b) : 겹쳐지는 영역

연산방법들, operators

겹쳐지는 부분

SRC_* : "겹쳐지는 부분에서 Source 의 색"을 사용한다.
DST_* : "겹쳐지는 부분에서 Dest 의 색"을 사용한다.
*_OUT/CLEAR/XOR : 이들은 "겹쳐지는 부분의 alpha 가 0" 이어서 아무런 색도 표현되지 않는다.

겹쳐지지 않는 부위

*_ATOP : *에 해당하는 녀석의 alpha 값이 0 + 그 반대에 해당하는 녀석은 자기 색을 갖는다.
*_IN : *에 해당하는 녀석의 alpha 값이 0 + 그 반대에 해당하는 녀석의 alpha 값도 0
*_OVER : 각자 자기색을 이용한다.
*_OUT : * 에 해당하는 녀석은 자기색 + 그 반대에 해당하는 녀석은 alpha 값이 0
SRC/DST: * 에 해당하는 녀석은 자기색 + 그 반대에 해당하는 녀석은 alpha 값이 0

예를 들어 DEST_ATOP 이라면, DEST 의 영역들의 alpha 값이 0 이 되는 것이다. 그런데 위에서 겹쳐지는 부분에 대한 정의는 따로 내렸기 때문에 겹쳐지지 않는 영역에 대해서만 적용된다.

이를 표로 나타내면 아래와 같다.

	[s]	[d]	[b]
SRC	s	0	s
SRC_ATOP	0	d	s
SRC_IN	0	0	s
SRC_OVER	s	d	s
SRC_OUT	s	d	0
DST	0	d	d
DST_ATOP	s	0	d
DST_IN	0	0	d
DST_OVER	s	d	d
DST_OUT	s	d	0
CLEAR	0	0	0
XOR	s	d	0

일단 대충 여기까지로 이해는 됐을 것 같다. 좀 더 자세한 이야기는 ref. 2 , ref. 5 를 참고하면 된다.

Reference

Fun with Android Shaders and Filters : 안드로이드의 shader/ filter 를 이용하는 법이 예제, 그림과 함께 나와 있다. 예제 소스는 demo sources 에 있다.
Porter/Duff Compositing and Blend Modes – Søren Sandmann Pedersen : Porter/Duff 에 대한 설명이 잘 나와 있다.
Xenomachina: Android's 2D Canvas Rendering Pipeline : 안드로이드의 2D rendering 순서(pipeline)을 다이어그램으로 보여준다.
PorterDuff.Mode | Android Developers
Alpha compositing - Wikipedia, the free encyclopedia

peer messages

have

bitfield

실제 packet

request

cancel

piece

interested

choking

현재 배포된 choking 알고리즘

Reference

yield 와 callback

callback 이 여러개인 경우

try/catch 를 한곳에

Reading a code

callback 을 yield 로 변경

Reference

python 3 의 string

python2 에서 python3 string 사용하기

기본 string 의 표현, unicode

byte object, b'가'

string.encode --> byte object

byte object.decode --> string

file write

json.dump

datetime

Reference

c/c++ 의 pointer 와 go 의 pointer

초기화

value 변수의 초기화

pointer 변수의 초기화

사용

이유

Reference

Tunny goroutine pool

Source flow

Full source

References

grpool

Installation

Source flow

References

k nearest neighbors classification(KNN)

어떻게 분류하는가?

거리, distance

적절한 K 값

distance 의 표준화, standardized distance

References

flow graph

References

선형종속, 선형독립

예제

그래프, 기하학 관점에서 생각해보기

README SanghyukChun's Blog

Deep-Learning-Papers-Reading-Roadmap

Deeplearning.net Reading list

Etc

Distributed Consensus 는 뭔가?[ref. 1, 2]

Raft algorithm[ref. 3]

리더 선출(leader election)

node 의 state

2개의 timout 세팅

초기상태

leader 선출 과정

leader 와 heart beat(Append Entries message)

Log Replication, 로그 복제

Client

Read-only operation

stale data 의 보장

User-group

See Also

References

Face recognition

동작

Step 1. 얼굴 찾기

얼굴찾기 알고리즘

HOG

SIFT

References

내 멋대로 풀어보는 "제곱근"의 의미