B-tree vs Log-Structured Merge-Tree

 

데이터베이스에서 일반적으로 많이 사용되는 데이터 구조는 B-Tree LSM(Log-Structured Merged-Tree)이다.

B-Tree

B-Tree 데이터베이스에 널리사용되며, B-Tree 인덱싱 구조를 사용하면 데이터가 고정 크기 페이지 세그먼트로 디스크에 기록된다. 이러한 페이지 세그먼트의 크기느 4KB (DMBS마다 다를 있음) 이며 키별로 정렬된 Key-Value 가지고 있다. 단일 B-Tree노드는 페이지 범위에 대한 참조가 있는 배열과 같다. 배열의 최대 참조 수를 “branching factor” 한다. 페이지 범위는 다른 페이지 범위를 참조하는 다른 B-Tree 노드이다. 결국 리프수준에서 단일 페이지를 찾을 있다.

B-Tree 페이지 참조가 메모리가 아닌 디스크에 저장된다는 점을 제외하면 저수준 프로그래밍 언어의 포인터와 유사하다. B-Tree에서 삽입 삭제가 발생하면 branching factor 충족하기 위해(밸런스를 맞추기 위해) 노드를 개의 하위 트리로 분할 있다. 데이터베이스가 충돌하는 위험이 발생할 있다. 데이터베이스가 충돌하는 시나리오를 완화하기 위해 B-Tree 구현은 모든 단일 원자 데이터베이스 트랜잭션을 기록하는 WAL (Write-Ahead Log) 작성하여 기록을 추적한다.  WAL B-Tree 손상된 경우 B-Tree 상태를 복원 하는데 사용된다.

 

Algorithm

Average

Worst case

Space

O(n)

O(n)

Search

O(log n)

O(log n)

Insert

O(log n)

O(log n)

Delete

O(log n)

O(log n)

 

 

 

 

LSM Tree

LSM Tree Bitcask, MongoDB, Bigtable, Cassandra, InfluxDB SQLite4 같은 최신 관계형 비관계형 데이터베이스에서 사용하고 있는 인기있는 데이터 구조이다. LSM Tree 각각의 기본 저장 매체에 최적화된 개이상의 개별 구조로 데이터를 유지한다. 메모리에는 실제 디스크의 데이터 값을 포함하는 바이트 오프셋에 대한 참조 정보를 Key-Value  형태로 해시 테이블 (또는 해시 인덱스) 관리한다.

실제로 사용되는 대부분의  LSM Tree 여러 수준을 사용한다. 레벨 0 주로 메모리에 보관되며 트리를 사용하여 표시 있다. 디스크 데이터는 정렬된 상태로 실행될 있도록 구성되며 실행에는 인덱스 키별로 정렬된 데이터가 포함된다. 실행은 디스크에서 단일 파일로 표시되거나 범위가 겹치지 않는 파일 모음으로 표시 있다. 관련 값을 얻기 위해 특정 키에 대한 쿼리를 수행하려면 레벨0 트리에서 검색하고 실행을 수행해야한다.

 

Algorithm

Average

Worst case

Insert

O(1)

O(1)

Find-min

O(N)

O(N)

Delete-min

O(N)

O(N)

 

 

 

[참고자료]

·       B-Tree : https://en.wikipedia.org/wiki/B-tree

·       Log-structured merge-tree : https://en.wikipedia.org/wiki/Log-structured_merge-tree

 

 

 

2021-03-17 / Sungwook Kang / http://sungwookkang.com

 

B-Tree, LSM Tree, Data Structure, Log-Structured-Merged-Tree, Database Index, 자료구조, 데이터스트럭처, 데이터인덱스

Python Multiprocessing(Process) 사용한 데이터 처리 속도 개선

 

·       Version : MAC OS, Python 3.X, PIP3

 

대용량 데이터를 효율적으로 처리하기 위해서는 병렬 처리를 활용하는것이 좋다.  파이썬에서 병렬처리를 제공하는 대표적인 라이브러리는 Threading Multiprocessing 모듈이다. Threading 모들은 파이썬의 GIL(Global Interpreter Lock)라는불리우는 잠금 모델을 사용하기 때문에I/O 작업이 아닌 CPU 작업이 많을 경우 오히려 성능이 저하된다. 방식은 Lock 풀고 스레드를 교환하고 다시 Lock 거는 형태의 멀티스레드이기 떄문이다.

파이썬에서는 Multiprocessing 권장하고 있으며,   모듈에는 대표적으로 Pool Process 있지만 이번 글에서는 Process 대해서 다루기로 한다.

 

·       Pool 사용한 처리 속도 개선 : https://sungwookkang.com/1478

 

Process 하나의 프로세스에 하나의 함수를 할당하여 실행한다. Target= 파라메터에 작업을 할당하고, args=(agr1, ) 인수를 할당하여 프로세스 객체를 생성한다. start() 프로세스를 시작하여 join()으로 프로세스의 종료를 기다린다.

import os

import multiprocessing as mp

from multiprocessing import Pool, Process

import threading

import time

import datetime

 

def multiprocess():

    start = int(time.time())

 

    ojbect_list = []

    for i in range(1,12):

        task = Process(target=work_func, args=(i,))

        ojbect_list.append(task)

        task.start()

 

    for task in ojbect_list:

        task.join()

   

    end = int(time.time())

    print("***run time(sec) : ", end-start)   

   

    print("Number of Core : " + str(mp.cpu_count()))

   

 

def work_func(x):

    print("time : " + str(datetime.datetime.today()) +  " value :" + str(x)  + " PID : "  + str(os.getpid()))

 

if __name__ == '__main__':

# execute only if run as a script

   

    multiprocess()

 

 

코드를 실행한 결과를 살펴보면 실행마다 다른 프로세스(PID 각각 다름)에서 실행된것을 있다.

 

Pool Process 차이점은, Pool 경우 실행되어야 작업이 코어수 만큼 분할되고 코어수 만큼 프로세스가 생성되어 힐당받은 작업을 처리하는데, Process 경우 작업마다 새로운 프로세스가 할당되어 작업을 처리한다.

 

 

2021-03-02/ Sungwook Kang / http://sungwookkang.com

 

파이선파이썬, python, 병렬처리, Multiprocessing, Python Multiprocessing, 파이썬 병렬처리, 데이터 처리, Data Processing

 

Python Multiprocessing(Pool) 사용한 데이터 처리 속도 개선

 

·       Version : MAC OS, Python 3.X, PIP3

 

대용량 데이터를 효율적으로 처리하기 위해서는 병렬 처리를 활용하는것이 좋다. 대부분의 머신러닝/딥러닝에 사용되는 프레임워크들은 함수 내부에서 병렬처리가 가능하도록 설계되어 있기 때문에 시스템의 자원을 효율적으로 사용하지만, 일반적으로 많이 사용되는 데이터 가공 모듈인 pandas 같은 모듈은 병렬처리를 기본적으로 제공하지 않기 떄분에 별도의 병렬처리가 가능하도록 코딩을 해야한다.

 파이썬에서 병렬처리를 제공하는 대표적인 라이브러리는 Threading Multiprocessing 모듈이다. Threading 모들은 파이썬의 GIL(Global Interpreter Lock)라는불리우는 잠금 모델을 사용하기 때문에I/O 작업이 아닌 CPU 작업이 많을 경우 오히려 성능이 저하된다. 방식은 Lock 풀고 스레드를 교환하고 다시 Lock 거는 형태의 멀티스레드이기 떄문이다.

파이썬에서는 Multiprocessing 권장하고 있으며,   모듈에는 대표적으로 Pool Process 있지만 이번 글에서는 Pool 대해서 다루기로 한다.

 

아래 실습코드는 1에서 12까지 숫자를 1 간격으로 출력하는데, for 문을 사용한 싱글처리와 Pool 사용하여 병렬 처리를 하였을때의 처리 시간 할당된 프로세스를 확인한다.

import os

import multiprocessing as mp

from multiprocessing import Pool

import threading

import time

import datetime

 

def non_multiprocess():

    print("non multiprocess")

    start = int(time.time())

   

    for i in range(1,12):

        work_func(i)

 

    end = int(time.time())

 

    print("Number of Core : " + str(mp.cpu_count()))

    print("***run time(sec) : ", end-start)   

 

def multiprocess():

    print("non multiprocess")

 

     #멀티 프로세싱을 위한 CPU 숫자 확인 만들기

    num_cores = mp.cpu_count()

    pool = Pool(num_cores)

 

    start = int(time.time())

 

    ojbect_list = []

    for i in range(1,100):

        ojbect_list.append(i)

    #멀티 프로세싱 워커 호출

    pool.map(work_func, ojbect_list)

 

    end = int(time.time())

 

    #메모리 방지 위해 사용

    pool.close()

    pool.join()

 

    print("Number of Core : " + str(mp.cpu_count()))

    print("***run time(sec) : ", end-start)   

 

def work_func(x):

    print("time : " + str(datetime.datetime.today()) +  "value :" + str(x)  + " PID : "  + str(os.getpid()))

   

    time.sleep(1)

 

if __name__ == '__main__':

# execute only if run as a script

    #non_multiprocess()

    multiprocess()

   

 

 

코드를 실행하면 아래와 같은 결과를 확인할 있다. non multiprocess 라고 되어 있는 결과는 for문을 사용한 싱글 프로세스이며, 개의 프로세스(PID : 49650) 사용되었으며, 순차적으로 실행되어 12초의 시간이 소요된 것을 확인할 있다. Multiprocess 경우 동시에 6개의 프로세스(필자의 테스트 컴퓨터는 6core이다.) 할당되었으며 PID 다른것을 확인할 있다. 전체 실행시간은 2초가 소요된 것을 확인할 있다.

 

간단한 테스트에서는 Multiprocessing 대한 효과를 크게 느끼지 못할수도 있으나 데이터가 기하급수적으로 커질때에는 데이터 처리 속도에 따른 시간이 엄청나게 차이난다.

 

 

2021-03-01/ Sungwook Kang / http://sungwookkang.com

 

파이선파이썬, python, 병렬처리, Multiprocessing, Python Multiprocessing, 파이썬 병렬처리, 데이터 처리, Data Processing

 

Python에서 Yahoo 주식 데이터 가져오기

 

·       Version : MAC OS, Python 3.X, PIP3

 

Yahoo Finance(https://finance.yahoo.com/) 에서 제공하는 API 사용하여 Python에서 주식 데이터를 가져오는 방법에 대해서 알아본다.

 

Yahoo Finance API 종류가 다양하며 API에서 제공하는 데이터도 조금씩 다르다. 단순한 시계열 데이터 부터, 기업 재무제표를 제공하는 API 다양하게 제공한다. 다양한 파이썬 패키지로 제공되고 있으며 아래 링크에서 확인할 있다.

·       yahoo-finance-api : https://github.com/topics/yahoo-finance-api?l=python

이번 포스트에서는 일일 주가 데이터를 제공하는 yfinance라는 파이썬 패키지를 사용하였다.

pip3 install yfinance --user

 

패키지 설치가 완료 되었으면, yfinance import하고 원하는 종목명 날짜를 입력하면 데이터를 가져올 있다.아래 예시는 AAPL(APPLE inc) 주가 데이터를 2020 12 1일부터 데이터를 가져온다.

import yfinance as yf

yf.download('AAPL', start = '2020-12-01')

 

 

2 이상의 종목에 대한 데이터를 가져올 경우, list 형식으로 사용할 있다.

yf.download(['AAPL', 'F'],start = '2020-12-01')

 

 

배당이나, 분할, 애널리스트 평가 정보도 yfinance 패키지에서 확인할 있다.

aapl = yf.Ticker('AAPL')

 

배당 내역

aapl.dividends

분할 내역

aapl.splits

애널리스트 평가

aapl.recommendations

 

지금까지 파이썬으로 패키지를 사용하여 데이터를 가져오는것을 실습하였는데, 이렇게 수집된 데이터를 나만의 데이터베이스로 만들고, 각종 지표를 만들어서 비교해봄으로써, 의미있는 2, 3 데이터를 만들어내는것이 중요하다. 단순히 주가의 가격 변동이나 흐름이 아닌, 시장의 방향과 주가의 방향이 매칭되는 종목을 찾고, 다양한 변수를 대입하여 종목을 추천할 있는 알고리즘을 만든다면, 직감이나 일부 정보만을 가지고, 이른바 바라는 주식투자가 아닌 공학 관점에서 가까이 투자할 있지 않을까 생각해 본다.

 

 

 

2020-12-28/ Sungwook Kang / http://sungwookkang.com

 

파이선, 파이썬, python, 주식 데이터 가져오기, 파이썬 주식, 금융공학, 주식 분석, 미국 주식 

 

+ Recent posts