• 검색 결과가 없습니다.

대용량 데이터

N/A
N/A
Protected

Academic year: 2021

Share "대용량 데이터"

Copied!
41
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

SMART SSD를 이용한 대용량 데이터 처리

2017. 3. 14 한용구

경희대학교 컴퓨터공학과

(2)

대용량 데이터

새로운 디지털 데이터의 크기가 점점 방대해 지고 있음

 eBay: 2.4PB 이상의 데이터

 Google: 400억 개 이상의 웹페이지

 Facebook: 8억 명 이상의 사용자 수

(3)

3

대용량 데이터 처리 트렌드

Data-intensive computing

 Map-reduce와 같은 무공유 대용량 병렬 처리가 일반화되고 있음

Bandwidth wall problem

 data-intensive programming framework는 분산 파일시스템 기반의 파일을 통한 데이터 통신이 증가하여 많은 IO를 발생시킴

이 결과, 메모리와 저장매체간의 bandwidth 차이가 발생하여 CPU와 같은 자원을 충분히 사용하지 못하는 문제점이 발생

데이터들이 storage로부터 호스트의 메모리까지 네트워크를 통해 전달되고, CPU만이 처리를 함

 이와 같은 데이터 접근 패스 과정에서의 Bandwidth가 일치하지 않아 성능이 저하되는 문제가 발생함

S. Kim, H. Oh, C. Park, S. Cho, and S-W. Lee, “Fast, Energy Efficient Scan inside Flash Memory SSDs,” ADMS’11

(4)

Near-Data Processing (NDP)

“Moving Computation is Cheaper than Moving Data” (HDFS Architecture Guide)

NDP는 계산을 데이터로 이동시켜 성능을 향상시킴

B. Gu, A. S. Yoon, D.-H. Bae, I. Jo, J. Lee, J. Yoon, J.-U. Kang, M. K., C. Y., S. Cho, J. Jeong, D. Chang, “Biscuit: A

(5)

5

In-Storage Compute (ISC)

Host processor의 계산의 일부를 스토리지로 offloading

 데이터 전송량과 지연시간을 줄여 성능을 향상시킴

S. Kim, H. Oh, C. Park, S. Cho, and S-W. Lee, “Fast, Energy Efficient Scan inside Flash Memory SSDs,” ADMS’11

(6)

SSD 시장 전망

향후 10년 내에 SSD가 HDD를 제치고 시장의 주류가 될 것이라는 전망 (International SoC Design Conference(ISOCC) 2014)

 물리적 작동이 없는 SSD는 속도가 빠르고 전력 소모가 적음

최근 슬림 노트북에 대부분 SSD가 탑재

엔터프라이즈 SSD는 42%성장 (IHS)

 데이터 센터 시장에서 대용량 스토리지 시스템도 SSD를 적용

소셜네트워크의 발전과 사물 인터넷 시대 개막으로 스토리지 수요 감당 필요

저전력, 친환경, 냉각 등 운영비용 절감 요구

(7)

7

삼성 Smart SSD

Smart SSD

 CPU processing과 DRAM storage를 내장한 SSD

 SSD내에서 사용자 프로그램 실행 가능 (In-Storage Compute: ISC)

데이터의 특성을 고려한 읽기/쓰기를 위한 프로그램을 내장하여 사용 환경에 따른 최적의 성능을 발휘하는 SSD를 개발할 수 있는 토대가 마련됨

Flash Memory Controller (FMC)

Flash Flash Flash Flash Flash memory bus 0

Flash Memory Controller (FMC)

Flash Flash Flash Flash Flash memory bus 1

Flash Memory Controller (FMC)

Flash Flash Flash Flash Flash memory bus 2

Flash Memory Controller (FMC)

Flash Flash Flash Flash Flash memory bus 3

SSD

CPU SRAM

DRAM Controller

SSD DRAM Host

Interface Controller

PCIe

(8)

In-Storage Compute (ISC)

ISC를 통한 데이터 처리속도 향상

 SSD의 internal IO 속도가 IO 인터페이스 속도보다 빠름

 처리 결과만 Host로 전송하여 IO 인터페이스를 통한 데이터 이동량을 줄임

고속의 Hardware Pattern Matcher 제공

(9)

9

관련 연구 1

J. Do, Y.-S. Kee, J. M. Patel, C. Park, K. Park, D. J. DeWitt, “Query Processing on Smart SSDs: Opportunities and Challenges”, SIGMOD’13

SmartSSD APIs

OPEN: User-Defined Program 시작 CLOSE: User-Defined Program 종료 GET: User-Defined Program의 상태 및

수행 결과를 가져옴

SmartSSD 내부에서 동작하는 프로그램들을 작성하기 위한 API들

Command APIs Thread APIs Data APIs Memory APIs

SmartSSD 내의 세션 열고 닫기

세션에 할당된 만큼 mater, worker

스레드 생성

SmartSSD의 DRAM, SRAM에 데이

터 읽어오기

SmartSSD의 DRAM, SRAM을

관리하는 API

(10)

 Smart SSD의 성능을 Microsoft SQL server를 통해 구현 및 평가

제공하는 API를 통해 질의를 Smart SSD에 구현하여 수행시킴

selection with aggregation query

NSM(레코드별), PAX(컬럼별)는 데이터 저장 방식으로 페이지의 selectivity에 영향을 줌

(11)

11

관련연구 2

B. Gu, A. S. Yoon, D.-H. Bae, I. Jo, J. Lee, J. Yoon, J.-U. Kang, M. K., C. Y., S.

Cho, J. Jeong, D. Chang, “Biscuit: A Framework for Near-Data Processing of Big DataWorkloads,” isca2016.

SmartSSD에서 사용자가 작성한 프로그램을 수행시킬 수 있는 프레임워크를 개발함

SSD 내에서 수행되는 프로그램

fiber를 통한 멀티스레딩 지원

Computation resource

파일에 존재하는 바이너리 시퀀스를 하드웨어 모듈을 통해 빠르게 탐색

(12)

Basic Performance

DB Scan and Filtering (11배의 성능 향상)

 MariaDB의 기능들을 Biscuit API를 통해 수정함

 HW pattern matcher를 활용하여 DB의 Scan 및 Filtering을 동시에 수행

(13)

13

관련연구 3

I. Jo, D.-H. Bae, A. S. Yoon, J.-U. Kang, S. Cho, D. DG Lee, J. Jeong, “YourSQL:

A HighPerformance Database System Leveraging InStorage Computing, ” VLDB 2016

Early Filtering

 데이터 집약형 컴퓨팅은 스토리지에서 host 시스템으로 전송하는 데이터의 사이즈를 줄이는 Early filtering이 중요함

인덱스와 같은 메타데이터를 활용하여 일부 데이터만을 읽는 소프트웨어 필터

데이터를 모두 읽되, 빠르게 필터하여 host로 전송하는 High-end 필터 서버

 Samsung SmartSSD를 활용하여 데이터를 읽기 전에, 필터링을 적용할 수 있음

: hardware pattern matcher

Filter Tasks

5 14 21 35

2. 키가 포함된 페이지들의 아이디를 반환 받음

3. 반환 받은 아이디의 페이지를 읽기 요청

1. 파일에서 찾고 싶은 키를 전달

(14)

 MySQL

MySQL의 Early Filtering인 Index Condition Pushdown

 MySQL ICP는 다음과 같은 한계점을 가지고 있음

스토리지 엔진에서 index를 참조하여 검색할 값이 포함된 데이터만을 읽음 스토리지 엔진

index

MySQL 엔진 key

result

Client

1. Index가 없는 경우 적용 불가

Join Order Table #of read requests

1 Part 245 2 Partsupp 98,520 3 supplier 45,679

4 Nation 5

5 region 4

2. Index nested-loop join에 최적화 되지 않음

(15)

15

 YourSQL의 동작

YourSQL 쿼리 엔진이 early filtering을 적용할 테이블 후보군을 결정함 (2)

SSD에서는 sampling을 통해 후보군 테이블들의 I/O benefit을 측정함 (3, 4)

HW pattern matcher를 사용하여 필터링 할 테이블들에서 읽어올 페이지 선택 (5)

읽어올 페이지들을 벌크로 읽음 (6)

(16)

 TPC-H 벤치마크를 통해 성능을 평가

YourSQL의 ISC Filtering을 통해 읽어온 페이지들 중 원하는 데이터가 없는 페이지가 너무 많은 경우를 제외하면 MySQL에 비해 높은 성능 향상을 보임

YourSQL이 필터링한 페이지들 내에 찾고 자 하는 데이터가 없는 페이지가

너무 많은 경우

(17)

17

관련 연구: iSSD

Y.-Y. Jo, S. Cho, S. Kim, D.-H. Bae, H. Oh, “On Running Data-Intensive

Algorithms with Intelligent SSD and Host CPU: A Collaborative Approach,” 30th Annual ACM Symposium on Applied Computing (SAC)

 iSSD와 host CPU간의 협력을 통한 data-Intensive Algorithm의 성능 향상 방법을 제안

 iSSD 내부의 FMC 코어 및 SSD 코어와 host 코어 간의 성능 차이, 사용하는 메모리의 차이를 스케쥴링하는 방법 제안

(18)

데이터 특성에 따른 SSD 성능 최적화

데이터의 종류, 크기, 액세스 패턴 등과 같은 특성에 따라 SSD 성능을 최적화 할 수 있는 고수준의 API의 개발이 필요함

 페이스북과 같은 소셜 네트워크 데이터는 그래프 구조 및 그래프 순회 패턴을 고려한 읽기/쓰기를 지원해야 함

 scientific 데이터는 다차원 배열 데이터로서, 배열의 특성을 고려한 읽기/쓰기를 지원해야 함

소셜네트워크: 대용량 그래프 SciDB: 대용량 다차원 배열

(19)

19

Smart SSD의 데이터 이동 경로

연산 사용함수 설명

Host IHC_read std::read ∙ Flash memory로부터 HOST DRAM으로 데이터를 읽는 연산 IHC_write std::write ∙ HOST DRAM으로부터 Flash memory로 데이터를 쓰는 연산

Smart SSD

ISC_read isc::read ∙ Flash memory로부터 SSD DRAM으로 데이터를 읽는 연산 ISC_write isc::write ∙ SSD DRAM으로부터 Flash memory로 데이터를 쓰는 연산 ISC_SSDtoHost isc::put ∙ SSD DRAM의 데이터를 Host DRAM으로 전송하는 시간 ISC_HOSTtoSSD isc::get ∙ Host DRAM의 데이터를 SSD DRAM으로 전송하는 시간

SSD CPU

SSD DRAM Host

Interface Controll

er Host

CPU

Host DRAM

[Smart SSD]

[Host Device]

Flash Memory

Array ISC_read

IHC_read

ISC_write

IHC_write

ISC_computing IHC_computing

ISC_HOSTtoSSD ISC_SSDtoHOST

(20)

Smart SSD 성능실험 환경

운영체제: Ubuntu 14.10 (linux kernel 3.19.0-28)

개발 언어: C++ 11

Compiler: g++

Host Device

Intel i5 6600 3.3GHZ

Samsung DDR3 8GB X 2ea

Smart SSD: Samsung PM1725 (from Website)

Cortex-R Series 750MHz

Interface: PCI Express Gen3 x8

Capacity: 6.4TB

Sequential Read (128KB): Up to 6,000MB/s

Sequential Write (128KB): Up to 2,000MB/s

Random Read IOPS (4KB): Up to 1M IOPS

Random Write IOPS (4KB): Up to 120K IOPS

(21)

21

Smart SSD 성능 실험 결과

Host

CPU SRAM

DRAM Controller

Host DRAM

Host Interface Controller

SSD

CPU SRAM

DRAM Controller

SSD DRAM

Flash Memory Controller (FMC)

Flash Flash Flash Flash

Flash Memory Controller (FMC)

Flash Flash Flash Flash

Flash Memory Controller (FMC)

Flash Flash Flash Flash

ihc read: 1.15GB/s

ihc write: 0.47GB/s HOSTtoSSD

200MB/s SSDtoHost

500MB/s

isc_CPU Cortex-R series

750MHz

isc_read 2.79GB/s ihc_CPU

intel i5 6600 3.3GHz

isc_write 0.15GB/s

(22)

Smart SSD의 성능 요약

Smart SSD 내부에서 컴퓨팅 가능

 Internal CPU, Internal RAM

Smart SSD 내부에서 캐싱 가능

 Internal RAM

고속의 Internal read

 ISC_read: 2.79GB/s (IHC_read: 1.15GB/s)

Hardware Pattern Matcher를 이용한 고속의 Match 제공

(23)

23

질의처리 경로 선택

그래프 질의의 비용이 최소가 되는 데이터 이동경로를 선택하여 처리

Path 1: Cost(IHC) = _ +

Path 2: Cost (ISC1) = _ + _ +

Path 3: Cost (ISC2) = _ + _ + _ + _

: input 데이터 크기, : computing한 결과 데이터 크기 ( )

예시) Path 1 선택 : Cost(IHC) < Cost(ISC1), Cost(ISC2)

(24)

ISC(In-Storage Computing)를 이용한

효율적인 그래프 처리 기법 연구

(25)

25

ISC 그래프 처리 구조

[Node File]

[Edge File]

(26)

노드 레이블 검색 연산

실세계 그래프들은 다중 애트리뷰트를 가지며, 특정 레이블 값을 갖는 노드를 검색하는 질의가 빈번히 발생함

노드 레이블 검색 연산의 비효율성

검색되는 애트리뷰트는 인덱싱하여 효율적으로 검색할 수 있지만, 인덱스 유지의 비용이 발생함

인덱스가 없는 애트리뷰트의 검색은 전체 파일을 읽어 레이블을 매칭해야 함

(27)

27

클러스터링 된 레이블 검색

빈번히 사용되는 레이블을 기준으로 노드들을 클러스터링하여 저장

인덱스 구성 없이, HW Pattern Matcher를 이용하여 클러스터 내에서 노드 레이블을 매칭

Match를 각 클러스터의 헤더(노드 레이블)에 대해서만 수행

찾은 클러스터 블록을 비동기 ISC_read 한 후 Host로 전송

[Node File]

DocGraph:

Medical providers 협업 그래프

Major Label을 기준으로 노드 클러스터링

(28)

클러스터링 되지 않은 레이블 검색

전체 파일에 대해 HW Pattern Matcher를 이용하여 노드 레이블을 매칭

 전체 파일을 비동기 Hardware Pattern Matcher로 매칭

 찾은 클러스터 블록을 비동기 ISC_read 한 후 Host로 전송

호스트에서 전체 파일을 읽어 순차 탐색하는 연산보다 빠르게 수행 가능

[Node File]

(29)

29

레이블 검색 성능평가 (1/3)

데이터 셋 (Stanford Large Network Dataset Collection)

 Patent citation network (PCN)

노드: Patents (3,774,768개)

- 노드 파일 크기: 0.12GB

- 두 종류의 애트리뷰트들을 가상으로 생성(att1: 14개 종류, att2: 29,476개 종류의 레이블)

에지: Patents간의 Citations 관계 (16,518,948개)

 LiveJournal social network (LSN)

노드: LiveJournal members (4,847,571개)

- 노드 파일 크기: 0.15GB

- 두 종류의 애트리뷰트들을 가상으로 생성(att1: 18개 종류, att2: 38,158개 종류의 레이블)

에지: LiveJournal members간의 친구관계 (68,993,773개)

 Friendster social network (FSN)

노드: Users (65,608,366개)

- 노드 파일 크기: 2.1GB

- 두 종류의 애트리뷰트들을 가상으로 생성(att1: 254개 종류, att2: 512,311개 종류의 레이블)

에지: Users의 친구관계 (1,806,067,135개)

(30)

레이블 검색 성능평가 (2/3)

클러스터링 된 레이블 검색 성능평가 (att1)

클러스터 블록 크기: 256KB (64페이지)

비교대상

IHC: 클러스터의 헤더(레이블 정보)를 호스트로 읽어 레이블을 매칭하고, 매칭된 클러스터 전체를 읽어옴

ISC: 클러스터의 헤더(레이블 정보)를 Hardware Pattern Matcher로 매칭하고, 매칭된 클러스터를 읽어 호스트로 전송

성능평가 결과

PCN과 LSN 데이터 셋에서는 ISC가 각각 1.18배, 1.4배의 빠른 성능을 보임

FSN 데이터 셋에서는 ISC가 2.9배의 빠른 성능을 보임

- 데이터 셋의 크기가 클수록 고성능의 Hardware Pattern Matcher가 더 많이 수행하기 때문에 전체 검색 성능이 더욱 향상됨

(31)

31

레이블 검색 성능평가 (3/3)

클러스터링 되지 않은 레이블 검색 성능평가 (att2)

비교대상

IHC: 전체 파일을 호스트로 읽어 레이블을 매칭

ISC: 전체 파일을 Hardware Pattern Matcher로 매칭하고, 매칭된 클러스터를 읽어 호스트로 전송

성능평가 결과

PCN, LSN, FSN 데이터 셋에서 ISC가 각각 2.8배, 2.9배, 3.1배 빠른 성능을 보임

(32)

이웃에지 탐색 연산

그래프 질의의 핵심 기초연산

그래프 질의에서 사용하는 shortest path discovery, graph matching, triangle listing 등과 같은 그래프 알고리즘의 수행시간의 대부분은 외향 에지 탐색이 차지함

이와 같은 그래프 알고리즘들은 이웃에지 탐색을 반복적으로 수행하는 BFS(Breadth First Search), DFS(Depth First Search), Common Neighbor Search 등의 그래프 기초 연산을 사용하기 때문임

따라서 이웃 에지 탐색 연산의 성능이 그래프 질의의 성능에 큰 영향을 미침

BFS의 이웃에지 탐색 연산

(33)

33

대용량 그래프의 이웃에지 탐색의 비효율성 (1/2)

에지들이 여러 페이지에 분산 저장되어 빈번한 페이지 IO 발생하여 성능 이 저하됨

Node 0으로 시작하는 BFS 탐색 예시:

 0번 노드 탐색을 위한 Page 0 읽기(①)

 0번 노드의 이웃 에지 탐색을 위한

Page1, Page3, Page4 읽기(②, ③, ④)

 노드 4912의 이웃에지 탐색을 위한 Page2 읽기(⑤)

 …

(34)

대용량 그래프의 이웃에지 탐색의 비효율성 (2/2)

다수의 노드에 대한 이웃 에지 탐색 연산이 그래프 응용에서 빈번히 발생함

소셜 네트워크에서 다수의 사용자가 친구 찾기를 동시에 요청

BFS, Shortest Path에서 다수의 노드들에 대한 이웃 에지들을 탐색

이웃에지 탐색을 각 노드마다 하나씩 수행하면 성능이 저하됨

ISC_SSDtoHOST와 ISC_HOSTtoSSD의 Latency 때문에, HOST에서 Smart SSD로의 빈번한 데이터 전송이 성능 저하를 발생시킴

ISC_SSDtoHOST Latency: 130.1

ISC_HOSTtoSSD Latency: 300.6

ISC read는 읽는 단위가 클수록 전송 속도가 높아져, 벌크로 읽어야 성능이 향상됨

[2GB의 파일을 다양한 페이지 단위로 읽는 속도]

(35)

35

이웃 노드 기반 그래프 파티셔닝

이웃 노드 기반 파티션

그래프는 인접 에지 순서로 탐색이 빈번히 발생함

인접한 에지들로 파티션을 구성하여, 그래프 탐색을 위한 IO를 줄임

이웃 노드 기반 파티셔닝 알고리즘

이웃 에지들을 동일한 파티션에 가능한 많이 담기 위하여,

차수가 가장 높은 노드를 기준으로 BFS로 탐색하며 에지들을

동일한 파티션에 저장

하나의 파티션이 가득 차면 SSD에 write하고, 새로운 파티션에

에지들을 저장

그래프의 모든 에지들을

탐색할 때까지 반복 수행하며 파티션을 생성

[Adj File]

(36)

벌크 이웃에지 연산

다수의 노드에 대한 이웃에지 탐색 연산을 동시에 수행

 다수의 노드에 대한 이웃 에지 탐색을 한 번에 Smart SSD로 요청

 요청한 모든 이웃 에지들이 포함된 Partition(대량)을 ISC_read를 수행하여 internal RAM에 적재

 Partition에서 이웃에지 레코드들을 포함하는 페이지들만을 ISC_SSDtoHost를 수행하여 호스트로 전송

(37)

37

에지 자료구조

To node ID Weight EdgeRecord

Number_of

_edges EdgeRecord EdgeRecord EdgeRecord AdjRecord

AdjBlock AdjRecord AdjRecord AdjRecord AdjRecord

EdgeRecord: 하나의 에지를 표현

AdjRecord: 각 노드의 이웃 에지들을 표현

AdjBlock: AdjRecord의 묶음으로 Host와 Smart SSD간의 통신 단위

Partition: AdjBlock의 묶음으로 ISC_read의 단위

Partition AdjBlock AdjBlock AdjBlock AdjBlock

(38)

이웃에지 파티션 캐싱

Smart SSD 내부 RAM을 이용하여 Internal cache를 이용한 성능 개선

Cache Manager

Smart SSD internal RAM의 캐시 풀에 8개의 에지 파티션(AdjBlock)을 유지함

LRU 정책으로 Cache replacement를 수행함

Host Application의 이웃에지 탐색 연산

① Host cache 검사

② Internal cache 검사

③ 플래시 메모리 읽기

(39)

39

성능평가

데이터셋

Stanford Network 데이터 중 SNS 데이터셋 인 Orkut 사용

Node: 사용자, 약 3,000,000개

Edge: 친구관계, 약 120,000,000개

실험환경

Partition 크기(ISC_read 단위): 8MB (2048페이지)

AdjBlock 크기(Host와 SSD 전송단위): 256KB (64페이지)

벌크 이웃에지 연산의 수행시간 성능 비교 (에지 차수가 500 이상 인 노드들을 벌크로 적재)

HOST: 호스트 캐시만 이용하여 이웃 에지 연산을 벌크로 수행

ISC: 호스트 캐시와 ISC 캐시를 모두 이용하여 이웃에지 연산을 벌크로 수행

(40)

결론

Smart SSD의 활용이 지속적으로 늘어날 것으로 예상

 데이터가 대용량화 됨에 따라 NDP가 주목 받고 있음

 SSD 기반의 All Flash 데이터 저장 시스템 도입이 늘어나고 있음

연구방향

 Smart SSD를 이용한 그래프 처리

 Smart SSD를 이용한 scientific 데이터 처리

 Smart SSD를 이용한 분산 처리

(41)

41

Q & A

참조

관련 문서

 기억장치에 쓰여질 데이터 혹은 기억장치로부터 읽혀진 데이터를 일시적으로 저장하는 버퍼 레지스터.. 실행

The ATmega48PA/88PA/168PA/328P provides the following features: 4/8/16/32K bytes of In- System Programmable Flash with Read-While-Write capabilities, 256/512/512/1K

phase 함수 : 직각좌표 형식의 복소수의 위상을 계산하는 함수 이 세함수에 사용되는 매개 변수와 반환값은 모두 radians. 한림대학교 박섭형 Python과

데이터 탐색가는 수많은 데이터를 걸러내 실제로 필요한 데이터를 발견하는 능력을 가진 사람이다.. - 분석한 자료를 가지고 찾아낸 우리가 적용할

데이터 수집 책임자는 일주일 동안 친구들이 데이터를 잘 수집할 수 있도록 돕는다.. 우리의 데이터

• DRAM buffer is a lot faster than flash memory in write operation. Buffer Management Techniques (Jihong Kim/SNU) 15.. Architecture of Target System..

• 시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에

gate vent Weld line