CS 전공/리뷰2010. 10. 11. 10:54
지난 주 금요일에 있은 seminar에 Stefan Tai  박사가 오셔서 Cloud Service Engineering이라는 제목으로 약 90분간 발표. Host인 송준화 박사님의 말에 따르면, 가장 성공한 한인 2세대 중 한 명일 것이라고. 태씨라고..독일에서 태어나 미국의 대학을 거쳐 IBM Watson 에서 연구원으로 있다가 지금은 독일의 Karlsruhe Institute of Technology(KIT)에 교수로 초빙받아 가 계신다고.

Seminar는 technical depth가 깊지는 않은, 좀 개념적이고 비즈니스 쪽 얘기도 좀 있었지만 갈무리할만 내용들(특히 정의 관련하여) 이 있어서 정리를 해보자면,
  • Cloud services are infinite IT(compute, storage) resources.
    • available when needed
    • Ubiquitously accessible
    • offered in an open market of competitive service providers
    • cost-efficient ( if not free)

Cloud computing

  • Cloud computing is a business model, and a distributed computing model
    • building compute or storage virtualization, cloud computing provides scalable, network-centric, abstracted IT infrastructure, platform, and applications as on-demand services that are billed by consumption.
  • Three main objectives
    • Enterprise-grade system management
      • Under-utilized: waste computing power & energy
      • Over-utilized: cause interruption or degradation of service levels
    • Internet-scale service computing
      • Services, Internet-scale
      • Sophisticated infrastructure, platform& applications available as modular services
      • The Web as a combined computing, business and collaboration platform
    • Understanding business opportunities
      • Faster time-to-market & cost-effective innovation processes
      • Dynamic, open business, networks
  • Cloud Service Engineering-> business engineering + software engineering
  • "A service is a means of delivering value to customers by facilitating outcomes customers want to achieve without the ownership of specific costs and risks" - ITIL Handbook Service Definition

그리고, 현재 KIT에서 IBM과 같이 수행하고 있는 두 과제를 소개하였는데..

1) Recovery Cloud
 기본 개념은 재해에 대비한 데이터 복제를 cloud 기반으로 하자는 것인데, Tai 박사는 이를 Recovery-as-a-service, Business continuity services 등으로 설명. 결국엔 replica를 cloud platform위에 올리자는 얘기인데 이때의 ownership이나 보안 문제는 어떻게 해결할 것인가 의구심이 좀 든다. recovery가 필요한 기업의 운영 데이터를 클라우드 제공자에게 맡긴다라.

2) Cloud meta-storage
이것은 여러 다양한 클라우드 기반 저장소들(BigTable, HDFS, Dynamo 등)을 대상으로 공통된 abstraction을 제공하는 시스템의 개발을 목적으로 하는데, 쓰여져 있는 바로는

"For purposes of provider independence & scalability (data volume & concurrent users), 
store data with diverse cloud storage service providers on multiple replicas" 
-> High-available, single storage provider architectures to a service value network of multiple storage service providers"

이를 위한 설계 원리는
  • Implement a simple key-value storage model, following the REST architectural style
  • Trade-off "C" for "A" (cf. CAP theorem)
  • Consider failures/outages to be the norm, not the exception)
    • Quorum-based system with hinted handoff
  • Use asynchronous message within the system
  • Use custom levels of security (authentication, additional encryption, file transfer via https)
  • Elevate concept from storage solution like Amazon Dynamo, GFS, Yahoo! PNUTS to a cloud storage SVN(Service Value Network)
와 같이 기술. 사실 기술적 특성은 Amazon의 Dynamo와 유사한듯 싶고, Mediator-Wrapper 형태의 상위 시스템을 만든다라고 봐야할까.. 






Posted by Bart

댓글을 달아 주세요

CS 전공/리뷰2010. 10. 4. 22:37


David A. Patterson이 "데이터센터가 컴퓨터이다"
[각주:1]라고 말하였듯이 최근의 클라우드 컴퓨팅에서는 shared-nothing[각주:2] 구조로 저가의 PC들을 고속의 네트워크로 묶어 데이터를 병렬 처리를 수행함으로써 scalability와 speedup(이에 관해서는 블로그의 다른 글 참조)을 보장한다.

이렇게 많은 PC들을 엮어 병렬 처리함으로써 speedup을 이루는 것을 기존의 방식, 즉 좀더 빠른 연산을 위해 컴퓨팅 파워가 적은 서버에서 대형의, 컴퓨팅 파워가 높은 서버로 대체하는 scaleup과 대비하여 scaleout이라고 설명하기도 한다. 데이터 센터는 무수히 많은 노드들로 이뤄지고 이 노드들은 상대적으로 저가의 PC 서버들이다. 이렇다 보니 데이터 센터에서의 고장은 매우 빈번할 수 있다. 데이터 센터에서의 노드 장애들이 얼마나 빈번한가 하면, Google의 한 데이터센터에서 일할 구인 광고( Job posting)에는 이런 항목이 있다.  

Position requirements:
  • Able to lift/move 20-30 lbs equipment on a daily basis
    (매일 9~13.7Kg의 장비들을 들고, 옮길 수 있어야 함)

 그러면 데이터 센터에서는 어떤 유형의 장애들이 얼마나 많이 발생하는가? 데이터베이스 분야에서 장애는 크게 사용자의 오류나 응용 프로그램의 오류, DBMS 오류, OS 오류와 같은 SW 적인 오류와 하드웨어의 오류, 네트워크 분할(network partition)이나 네트워크 오류, 재해 등과 같은 여러 문제로 기인할 수 있다[각주:3]. 그 중 여기에서는 순수한 HW의 오류에 대해서만 살펴본다. 그중에서도 특히 메모리와 HDD의 오류에 대해서 살펴본다. (CPU 오류는 거의 없다고 본다. 물론 Pentium에서의 FDIV(Floating Division) 오류와 같은 오류가 있었기는하지만.. )흔히들 HW 오류는 SW 오류보다 매우 드물다는 것이 많은 사람들의 의견이지만 많은 노드들을 갖는 데이터 센터에서는 이 오류의 빈도가 만만치가 않다. 마침 HW 오류들에 대한 통계 정보가 있어 이들을 소개한다.  Bianca Schroeder가 Google의  데이터센터에 있는 노드들을 대상으로 2년 반 동안 조사한 바에 따르면 다음과 같은 메모리 오류를 겪는다는 결과[각주:4]가 나왔다.

Picture 27

이 조사에 따르면, 매년 32.2%의 노드들이 CE(Correctable Error)-ECC 등을 통해 잡히고 고쳐질 수 있는 메모리 오류, 하지만 오류 정정에 따른 비용은 물론 있다-를 겪었으며, 매년 22,696번의 오류를 겪는다고 보고되었다. 또한, 고쳐질 수 없어 결국엔 DIMM 모듈 자체의 교체로 대처할 수 밖에 없는 오류 UE(Uncorrectable Error)는 1.29%의 노드가 겪는다고 보고되었다.   DIMM 모듈 단위로 이 통계를 다시 써보면, 1년마다 8.2%의 DIMM 모듈이 CE를 겪고, 0.22%의 DIMM모듈이 UE를 겪는다.  예를 들어, 노드 1만대를 가지고 구성되는 데이터센터에서는 3,220여대의 노드가 CE를 겪고,  129여대가 UE를 겪는다는 얘기이고 129여대는 메모리 모듈을 교체해야 한다는 의미이다. 오류 발생이 균등 분포라 가정해보면 약 3일마다 한 노드에서 UE 메모리 오류가 발생하여 결국엔 DIMM 모듈을 갈아줘야 한다.  물론 그 장애가 메모리 오류에서 발생했다는 사실을 인지할 수 있는 경우에만. 디스크의 경우는 또 어떠한가? 

우리들은  FC(Fibre Channel)나 SCSI 드라이브가 SATA 드라이브보다 더 신뢰성이 높다고 생각한다. 또한 RAID level 5(block-interleaved distributed parity) 등으로 시스템을 구축하면 보다 안전하다고 생각각한다. 그리고  제조업체가 보증하는 MTTF(또는 MTBF)는 충분히 길다고 생각한다.  정말일까? 이와 관련한 재미있는 논문들이 있다.


  • MTTF(Mean Time To Failure)는 MTBF(Mean Time Between Failure)와 많이 혼동된다. 하지만 그 의미는 조금 다르다. MTBF(Mean Time Between Failure)는 한번 고장난 후 다시 고장 날 때까지의 평균 시간으로 고장이 수리될 수 있는 시스템에서 측정된다.  한 시스템에 대한 MTBF를 측정하는 경우 동일 시스템을 여러 개를 두고 이들의 두 고장간에 정상동작된 시간들의 합을 전체 고장횟수로 나눈 시간을 MTBF로 측정한다.  제조업체가 자신의 시스템에 백만시간의 MTBF를 보증한다 하자. 그러면, 두 고장간 드라이브가 정상 동작될 평균 시간은 백만 시간이다.  이것을 어떻게 제조업체들이 측정할까?  디스크들을 백만 시간(약 114년)을 돌리고 평균을 내는가? 물론 아니다. 많은 수의 드라이브들을 돌려서 정상동작 시간들의 합을 드라이브들의 총 고장 횟수+1로 나눈다. 즉 1,000개의 드라이브를 1,000시간 돌려서 드라이브 한개라도 고장이 안나면 (1000*1000)/0+1로 MTBF가 백만 시간이 된다. 때문에 우리는 MTBF가 백만이 넘는 디스크가 나가는 경우를 볼 수가 있다.
  • MTTF는 MTBF와 달리 고장이 수리될 수 없는 시스템에서 첫 고장이 발생하는 평균 시간을 의미한다.
  • AFR(Annualized Failure Rate)은 임의의 많은 수의 디스크들을 돌려 이들  중 1년 안에 얼마나 많은 디스크들이 고장이 나는지를 확률로 표현한다.
  • MTTF는 위의 MTBF와 같은 방식으로 계산될 수있지만,  1년에 고장없이 동작된 시간을 AFR로 나눔으로써 계산될 수도 있다. 가령1년에 5,800시간을 고장없이 동작했고,  AFR은 0.58%이라면 5800/0.0058= 1,000,000시간이 된다.

Google의 엔지니어들에 의해 쓰여진 첫 번째 논문[각주:5]은 100,000개의 디스크를 분석하여 디스크를 디스크의 나이와 사용 빈도,  온도에 따른 오류 발생률을 측정하였다(AFR: Annualized Failure Rates). 또한 SMART 와 같은 디스크의 자기 모니터링 기능의 유용성도 조사하였다.



그림 2에서 보이는 바와 같이 초기 디스크 설치 시에는 고장이 좀 나다가 발생하지 않는 경우에는 1년여간은 안정적으로 동작함을 볼 수 있다. 하지만 2년째부터 AFR는 급격히 올라가고 3년째부터는 AFR이 8%를 넘는다. 이는 간과할만한 수치가 아니다. 10,000개의 노드 PC들로 구성된 데이터 센터에서 노드가  디스크 1개씩만 가진다고 하면, 매년 800개 이상의 노드 PC들의 디스크가 교체되어져야 하기 때문이다. 균등 분포의 오류 발생을 가정할 경우 매일 2-3개의 PC들의 디스크가 교체되어져야 한다.


더불어 디스크는 쓰면 쓸수록 많이 고장이 난다. 그림 3은 활용도를 저, 중, 고로 나누고 이들 간의 AFR 차이가 어떤지를 보인다. 특이한 점은 3개월 짜리 어린 디스크를 많이 이용하는 경우 AFR이 가장 높게 나왔다는 점이다. 또 다른 특징은 어린 디스크들은 고온과 AFR간의 상관관계가 없다는 것이다. 오히려 저온에서 더 높은 AFR을 보인다. 하지만 이것은 디스크가 늙어갈 수록 온도 증가에 따라 AFR이 증가하는 형태로 역전된다.


또한 SMART(Self-Monitoring, Analysis, and Reporting Technology)와 같은 디스크 모니터링 도구는 대규모의 디스크 어래이에서는 거의 사용 의미가 없다고 한다.

Schroeder의 또다른 논문[각주:6]에서는 Los Alamos와 Pittsburgh의 Supercomputer Center의 HPC 클러스터들과 여러 인터넷 서비스 제공자들의 디스크들을 분석하여 다음과 같은 결과를 얻었다.



여기에서 발견한 내용은 다음과 같다.

1. SCSI, FC 디스크같은 고가의 디스크와 저가의 SATA 디스크 간의 연간 디스크 교체 비율(ARR)은 큰 차이가 없다. 즉 고가 디스크라고 ARR이 낮은 것은 아니다.

2. infant mortality(가동 초기의 높은 오류율)을 발견하지 못하였다. 디스크는 그냥 나이에 따라 서서히 닳아(wear-out) 간다. 즉,  나이가 듬에 따라 교체되는 비율이 점차 증가한다.

3. Vendor가 제시하는 MTTF와 실제 ARR과는 많은 차이가 나며, 벤더의 MTTF보다 훨씬 많은 디스크가 고장났다.

4. 디스크 교체 간 평균 시간은 생각보다 짧다. 이것은 RAID 시스템(특히 level 5)에서 고장난 디스크를 교체하는 동안에 다른 디스크가 고장나 데이터를 잃어버릴 확률이 그만큼 높음을 의미한다.  


결론
1. 메모리나 디스크는 무결점의 장치가 아니다.

2. 디스크는 수명이 있고, 생각보다 빨리 단다.  

3. 이런 장치들이 집적된 데이터 센터에서는 많은 수의 장치들이 빠르게 고장날 수 있다.

4. 이러한 환경에서는 빈번한 장애에 대한  내고장성을 지원하는 것이 보다 중요하다.
 

  1. David A. Patterson, The Datacenter is the computer, CACM Vol.51, No. pp.151--151. 2008 [본문으로]
  2. M. Stonebraker, The case for shared-nothing, Database Engineering Bulletin, Vol. 9 No. 1 , pages 4--9, 1986 [본문으로]
  3. M Stonebraker, In Search of Database Consistency, http://cacm.acm.org/magazines/2010/10/99500-in-search-of-database-consistency/fulltext [본문으로]
  4. Schroeder, B. and Pinheiro, E. and Weber, W.D., DRAM Errors in the Wild: A Large-Scale Field Study, In Proc. of ACM SIGMETRICS, 2009 [본문으로]
  5. Pinheiro, E. and Weber, W.D. and Barroso, L.A., Failure trends in a large disk drive population, Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST’07), 2007 [본문으로]
  6. Bianca Schroeder and Garth A. Gibson, Disk Failures in the Real World: What Does an MTTF of 1,000,000 Hours Mean to You?, 5th USENIX Conference on File and Storage Technologies(FAST'07), 2007 [본문으로]
Posted by Bart

댓글을 달아 주세요

  1. webtk

    와우. 정말 공들여 쓰셨네요. 노드가 기껏 수십개에 불과한 시스템에서도 디스크가 맛가는 경우를 많이 봐서, 결론이 더더욱 공감이 갑니다.

    2010.10.04 22:59 [ ADDR : EDIT/ DEL : REPLY ]

CS 전공/리뷰2010. 4. 7. 15:35
점차 가격 경쟁력을 키워가면서 HDD를 대체할 수단으로 인식되고 있는, NAND Flash Memory는 단순한 임베디드 기기에서의 이용을 넘어 이제는 데이터베이스 서버 등에서 데이터의 보관, 중간 데이터의 임시 저장 등 여러 용도로 활용되고 있다. 특히 플래시 메모리의 낮은 소비 전력은 internet-scale server cluster를 구축하는데 있어, 단위 질의 처리에 필요한 전력량을 낮추는데도 크게 기여를 한다. 하지만 NAND flash memory는 IO 연산의 비대칭성, in-place update의 불가능 등의 몇가지 한계에 대한 많은 논의가 있어 온 것도 사실이다.

이 2개의 논문은 NAND flash memory의 서버로의 도입의 효과와 그로 인한 여러 문제들(버퍼 교체 정책 등)을 논한다.

Integrating NAND flash devices onto servers

tamu.edu [PDF] 
Full-Text @ UofA Library

D Roberts, T Kgil, T Mudge - Communications of the ACM, 2009 - portal.acm.org

상기 논문에 추가하여 다음의 논문의 내용을 같이 참조하는 것이 좋을 것으로 판단합니다.
(위 전체분량은 아래논문의 분량을 같이 포함한 분량임): 
The Five-Minute Rule 20 Years Later (and how flash memory changes the rules), CACM July 2009, pp.48-59

Jim Gray가 실종된 후 Goetz Grafe가 Flash memory의 출현에 따른 변화를 Five-Minute Rule에 반영했네요.

Five-Minute Rule은 원래 87년에

란 제목으로 Jim Gray에 의해 처음 쓰여지고, 10년 뒤

 
다시 쓰여지고, 10년 뒤 J Gray가 실종된 후에는 Graefe 혼자 썼네요. 

The five-minute rule twenty years later, and how flash memory changes the rules

psu.edu [PDF]
G Graefe - Proceedings of the 3rd international workshop on Data …, 2007 - portal.acm.org

순서대로 읽어가보면 memory hierarchy의 변화가 어떻게 이 rule-of-thumb에 영향을 미쳤는지 볼 수 있을 듯.

ps. Jim Gray만큼 이 분야에서 사랑받고, 인정받는 대가는 없는 듯.

Tribute to honor Jim Gray in May 2008 http://goo.gl/2B0I 에 보면, Jim Gray의 업적들이 어떤지 알 수가 있음.
더불어 DB Guru들도 추모를 위해 한 자리에 모이는 것도 그렇고
.
..
great engineer를 어떻게 생각하고 어떻게 대우하는지를 보면 그 나라가 선진국인지 아닌지 알 수 있는 듯.

어디는 IT직종은 야근비 책정도 안하는 회사가 있다면서요? 야근이 잦다고? 나참. 

Posted by Bart

댓글을 달아 주세요

CS 전공/리뷰2010. 1. 8. 12:03

  블로그 주인장은 모 단체에서 DB 및 데이터 처리 기술 관련한 자료의 분석 추천및 검토를 담당하고 있습니다. 
이 분석 자료는 클라우드 컴퓨팅에서의 데이터 관리 이슈와 데이터 처리에 있어 MapReduce와 병렬 DBMS의 비교 분석을 중심으로 클라우드 컴퓨팅에서의 데이터 관리를 설명합니다.
이 자료의 분석은 고려대학교 대학원의 최현식씨께서 수고해 주셨습니다.

아래는 서문과 차례입니다. * 해당 자료의 열람 또는 다운로드는 www.kosen21.org에 가입 후 분석자료 메뉴에서 다운로드 하실 수 있습니다.


1. 분석자 서문 

최근 클라우드 컴퓨팅(cloud computing) 패러다임이 산업계뿐만 아니라 학계에서도 많은 관심을 받고 있다. 이와 더불어 데이터베이스 학계에서는 클라우드 컴퓨팅 환경에서 데이터관리에 대한 집중적인 연구들이 진행되고 있다. 본 분석은 현재 많은 관심을 받고 있는 비공유 구조(shared-nothing architecture) 기반 클라우드 컴퓨팅 환경(아마존 EC2와 같은)에서 유발되는 데이터 관리 이슈들과 이 환경에서 수행되는 데이터 관리의 한계점 및 가능성에 대해 살펴본다. 본 분석은 트랜잭션 데이터 처리보다는 대용량 데이터에 대한 분석 처리가 클라우드 환경에 적합하다는 것을 보인다. 그리고 대용량 데이터 분석을 위해 DBMS에 요구되는 기능들을 제시하고 이 기능들을 바탕으로 기존 오픈 소스 프로그램들과 상용 병렬 DBMS들을 평가한다. 추가적으로, 실험을 통해 두 계열 시스템의 성능을 비교 평가한 논문의 결과를 분석하여 성능 비교에 대한 추가적인 근거를 제시한다. 

2. 목차 

1. 개요 

2. 클라우드 환경에서의 데이터 관리 
2.1 클라우드 환경의 특성 
2.2 클라우드 환경에 적합한 데이터 관리 어플리케이션의 유형 

3. 클라우드 환경에서 데이터 분석용 어플리케이션 
3.1 클라우드 DBMS를 위한 필요기능 
3.2 MapReduce 계열 소프트웨어 
3.3 비공유 구조 기반의 병렬 DBMS 

4. MapReduce와 병렬 DBMS 시스템의 비교 
4.1 질의 시작 비용 
4.2 압축 기능 
4.3 데이터 적재 및 레이아웃 
4.4 실행 전략 
4.5 내고장성 모델 

5. 토론 
5.1 효율성의 비교 
5.2 입력 데이터 형식 
5.3 하이브리드 시스템 

Reference 


Posted by Bart

댓글을 달아 주세요

  1. 음 분석자료 제목이 뭔지 알수 있을까요? 검색이 안되는 것 같던데요~

    2010.04.12 17:48 [ ADDR : EDIT/ DEL : REPLY ]
    • 글 제목과 같은 제목입니다.
      아니면 지금 메인 페이지 하단에 제 1 인기글로 있으니 그것으로 찾으셔도 될 듯.

      2010.04.12 18:34 신고 [ ADDR : EDIT/ DEL ]

CS 전공/리뷰2010. 1. 6. 15:13
Univ. of Wisconsin-Madison(이 대학은 CS 특히 컴퓨터 구조 분야에서 아주 독보적인 위치에 있다.)의 Mark D. Hill 교수가 IEEE Computer 2008년 7월호에 기고한 글이다. HPCA'08 에서 키노트로, 또 2009년 2월에는 Google techtalk에서도 발표를 하였다.[Paper][Slides]




 이 논문은 멀티코어 환경에서의 병렬화를 통한 속도향상을 설명하기 위해 멀티코어의 종류와 특징을 설명하고, 이를 위해 자신들의 수정된 암달의 법칙에 대해 설명한다. 사실 암달의 법칙이 바뀐 것은 아니다. 다만, 멀티코어에 맞추어서 암달의 법칙을 보완한 정도이다. 컴퓨터 아키텍트를 주대상으로 발표한 듯 싶지만, 나같은 SW업자에게도 좋은 내용이라 생각된다.

 멀티코어는 크게 대칭형(symmetric)과 비대칭형(asymmetric)으로 구분할 수 있는데, Core2Duo 같은 것이 대칭형이고, Cell Broadband Engine  또는 셀 프로세서라 불리는 것이 비대칭형이다. 이들 각각에 환경에 있어 프로그램 내 병렬 실행 부분(F)에 따른 속도향상의 한계를 보인다. 
식을 간단하게 하기 위해 BCE(Base Core Equivalent)라고 하는 논리적 구성 요소를 가지고, 각 코어는 1개 이상의 BCE를 가진다고 가정하고, r개의 BCE로 구성된 한 코어의 성능을 perf(r)이라고, 정의하고 암달의 법칙을 설명한다.  자세한 내용은 식을 직접 참고하는 편이 낫다. 여기에서는 간단하게 정리만 하자면 결과는:

대칭형 멀티 코어의 경우:
  • 암달의 법칙은 멀티코어 환경에서도 그대로 적용된다. 즉 멀티코어의 성능은 코어 수에 따라 선형으로 증가되지 못하고 제한된다.
  • f 값의 증가, 즉 병렬화 부분을 증가시키는 것이 멀티코어 환경에서도 중요하다. f 값이 충분히 크지 않으면 그냥 CPU 하나의 성능을 증가시키는 것이 더 나은 속도 향상을 보인다.
  • 많은 경우 각 코어에 BCE는 여러개 있는 것이 효과적이다.(즉 코어 수를 많이 늘리는 것보다, 코어 성능을 개선하는 것이 나을 수 있다.) (F=90~99%)
  • 프로그램의 99% 이상이 병렬화 되었다면, 한 칩에 코어가 많은 것이 더 낫다.

비대칭형 멀티 코어의 경우: 
  • 언제나 대칭형 멀티코어보다 더 나은 성능을 보인다. (그래서 셀 프로세서가 인기있는가 보군)
  • r-BCE 코어 하나의 성능을 논할 때, r 값을 클수록 좋은 성능이 나왔다.
  • 상대적으로 작은 F값에 대해서도 주목할만한 속도향상이 있다.

이외에 동적(dynamic) 멀티코어를 논했는데, 이는 필요에 따라 제한된 BCE를 가지고 코어 수를 맘대로 변경할 수 있는 멀티코어를 의미한다. 시뮬레이션 결과는 이것이 가장 좋은 성능을 보인다. 하지만, 아직 존재하지 않으므로 컴퓨터 아키텍트들에겐 최종적인 골이 되어야 한다고. 물론 이 논문은 off-chip bandwidth에 따른 성능 저하나 cache hit에 따른 성능 향상을 고려하지는 않는다.

발표 또한 아주 훌륭하다. 사실 발표 후반부 가면 논문에는 없는 구글의 데이터 센터의 병렬성의 평가를 위한 Karp-Flatt metric도 잠깐 소개한다. 클라우드를 구성하는 노드들 중 성능이 좋은 노드를 r-BCE 코어로 생각함으로써. 이들 간의 연관성을 찾아볼 수 있다. 사실 멀티코어나 mapReduce 같은 비공유 구조의 병렬 컴퓨팅은 크게 다른게 아니다. 요새는 참 좋은 강의들을 인터넷으로 구할 수 있는 좋은 시대인 거 같다. 

PS. 암달의 법칙 자체에 대한 설명은 이 블로그의 http://bart7449.tistory.com/244 를 참고하세요.

written by bart7449 
Posted by Bart

댓글을 달아 주세요

  1. 좋은 자료 잘 보고 갑니다. :)

    2011.02.09 02:19 신고 [ ADDR : EDIT/ DEL : REPLY ]

CS 전공/리뷰2010. 1. 3. 17:23
2009년 11월 16일자 기사로 나온 이 기사는 엔터프라이즈 컴퓨팅에 중요한 역할을 할 10가지 기술을 소개한다.  (http://www.infoworld.com/d/infoworld/infoworlds-top-10-emerging-enterprise-technologies-378?page=0,0)

1. MapReduce
2. Desktop Virtualization
3. Data Deduplication
4. I/O Virtualization
5. NoSQL Databases
6. Solid State Disks
7. Many Core Chips(CMP; Chip-based Multi Processor) 또는 Multi-core
8. Hardware Power Conservation
9. Cross-Platform Mobile Application Development
10. Whitelisting

확실히 MapReduce와 CMP에 따른 Shared-Nothing, Shared-Memory 환경에서의 병렬화가 대세인 듯 싶다.  MapReduce와 Key-Value Store의 부각에 따른 NoSQL Database 의 부각 또한 유심히 거리이다. 특히 OLAP 쪽에서 기존 Parallel DBMS와의 경쟁 및 협력 관계가 볼만해 질 것이다. (OLTP 업무에서의 SQL DBMS 입지는 절대 줄어들지 않을거다.)
SSD는 이제 Enterprise 급에서도 HDD를 대체해 나갈 가능성이 크다. 단순히 HDD를 SSD로 교체하는 것만으로 Latency와 Power 문제를 크게 해결해 볼 수 있다.
그리고, 갈수록 보다 많은 Mobile app.이 개발될 것이다.


Posted by Bart

댓글을 달아 주세요

CS 전공/리뷰2009. 12. 30. 14:23
Google Fellow이자 우리에겐 MapReduce-OSDI'04와 BigTable-OSDI'06의 저자로 알려진 Jeff Dean이 WSDM'09 에서 keynote로 발표한 발표자료. (Jeff Dean은  두 시스템 덕분에 상당히 젊은 나이임에도 불구하고 올해 ACM Fellow로 임명되었다.)
Google이  어떻게 자기네 정보 검색 시스템을 운영하는데 필요한 대량의 데이터 처리를 지원하는지 그리고 시간이 지남에 따라 감당해야 할 작업량이 증가함에 따라 이를 어떻게 개선해 왔는지에 대해 잘 설명하고 있다. 올해에 행해졌던 technical speech 중 꼭 한 번 봐야 할 것 중 하나라고 생각된다.
 

Posted by Bart

댓글을 달아 주세요

  1. 좋은 자료 감사합니다 :)

    2009.12.30 17:57 [ ADDR : EDIT/ DEL : REPLY ]

CS 전공/리뷰2009. 12. 27. 09:41
NoSQL Movement에 대한 기사를  읽어 내려가던 중에 다음과 같은 내용을 보았다.
(언제 기회가 되면 요새 MapReduce, Key-Value Store, NoSQL Movement 에 대한 내용을 싹 정리해서 글로 쓰고 싶다. survey paper를 내던, 블로깅을 하던.)

아무튼 기사를 보던 중에 이런 글귀가 눈에 띄었다.
 
예를 들어, 페이스북은 기존 데이터베이스인 MySQL이 아니라 카산드라(Cassandra) 데이터 스토어를 개발해 새로운 검색 기능을 추가했다. 페이스북 엔지니어인 아비나시 락시먼의 프리젠테이션에 따르면, 카산드라는 0.12ms 만에 50GB에 이르는 데이터 스토어를 디스크에 기록할 수 있는데, 이는 MySQL보다 2,500배 빠른 것이다."

우아~! 대단하다. 50GB를 0.12ms만에... 가만 그런데 이것이 가능한 일인가? 
도대체 어떤 기술을 썼길래... 갑자기 궁금해져서 NoSQL discussion에서 있었던 TP를 찾아 보았다. (http://static.last.fm/johan/nosql-20090611/cassandra_nosql.pdf)
  • MySQL > 50 GB Data
    Writes Average : ~300 ms
    Reads Average : ~350 ms

    •Cassandra > 50 GB Data
    Writes Average : 0.12 ms
    Reads Average : 15 ms

실제 위와 같이 써 놓았다. 0.12ms만에 50GBytes에 이르는 데이터를 디스크에 기록한다면,
1ms에 약 416GBytes (=50/0.12ms)를 디스크에 기록할 수 있다는 얘기이다. 
이게 말이 되는가? 이게 말이 된다면, 페이스북은 물리 법칙을 초월한 디스크를 가지고 운영되고 있다는 말이 된다 왜?

모든 디스크의 스펙을 보면 1)seek time, 2) rotational delay time, 3)transfer time이 나와 있다. 
1) seek time은 디스크 암을 움직여서 원하는 트랙으로 움직이는데 걸리는 시간이고,
2) rotational delay time(또는 latency)은 이 암이 트랙상에 위치한 임의 블럭 섹터를 만나는데 까지 걸리는 시간이고,
3) transfer time은 암이 실제 디스크로부터 데이터를 읽거나 쓰는데 걸리는 시간이다.
즉 데이터를 디스크에 기록하는데 있어 걸리는 시간은 1)+2)+3)이다.
그리고 이 중 2),3)은 모두 disk의 RPM에 의해 제한되는 물리적인 한계값을 가진다. 또한 1의 값은 디스크의 크기에 제한된다.(디스크 직경이 클수록 디스크 암이 움직이는 거리도 길어지며, seek time은 그만큼 늘어난다.)

RPM이 빠르면 빠를수록 delay time은 줄어들고 또한 그만큼 빨리 디스크로부터 블럭들을 쓰거나 읽을 수 있다. 하지만 현재 데이터 센터에서 이용되고 있는 디스크들이 갖는 가장 빠른 RPM은 15K이다.
RPM이 15K란 얘기는 디스크가 분당 15,000회 돈다는 얘기이다. 바꿔 말하면, 1회 회전하는데 60000/15000 =  4 ms가 걸린다는 의미이고, rotation delay는  평균 값으로 반바퀴 도는 시간을 재니 이의 절반인 2.0ms가 평균적으로 걸린다고 할 수 있다.  
실제 디스크의 스펙을 보면 더 명백해진다. Seagate의 Data center용 HDD인 Savvio '2.5Inch 15K의 스펙을  보자.
latency가 2ms이다. 

즉 ,어떠한 경우던지, 디스크에 데이터를 기록할 때에는 평균적으로 이 latency값이 먼저 먹고 들어가야 한다. 근데 Cassandra를 보면 seek time은 고사하고, 이 latency 값보다도 작은 값이 걸린다고 하고 있다.
물론 transfer time은 디스크를 병렬로 구성해서 병렬 I/O를 수행하는 식으로 개선할 수 있다. 
예를 들어 sequential write가 100MB/ms인 디스크 하나를 가지고 50GB를 저장하려면, 50*1,024/100= 512ms가 걸린다. 하지만, 50GB를 1000개로 쪼개어 1000개의 디스크에 병렬로 저장한다면 이상적으로 0.512ms가 걸리겠다. 하지만 이 때의 경우에도 각 디스크의 latency는 절대 피할 수가 없다. 결과적으로 평균적으로 걸리는 시간은 seek time + 2ms + 0.512ms이상이 나와야 물리 법칙을 깨지 않게 된다.

그러면, latency가 HDD에 비해 훨씬 낮은 최근의 SSD를 쓰는 경우는 어떠한가?  
요사이 SSD 중 성능이 우수하다는 Intel X25-E Gen2 160GB의 스펙을 보면, 
  • read/write latency가 각각 75/85um, 
  • Random 4K Read/Write는 35K/3.3K IOPS, 
  • Sequential Read/Write가 250/170MB/S
이다. SSD의 latency 85um은 0.12ms = 120us보다는 작다.  즉 SSD로는 0.12ms라는 writing time이 불가능한 것은 아니다. 
그런데, 이 값에서 latency를 제외한 transfer time만을 계산해보면, 45us동안만 데이터를 디스크에 썼다는 얘기가 된다. Sequential write transfer time도 170MB/S이니까 45us동안에는 약 7.84KBytes만을 쓸 수 있다. 그렇다면, 50GB 기록을 위해 50GB/7.84KBytes= 약 660여만개의 SSD가 필요하다는 얘기가 된다.
이게 말이 되는가? SSD 하나 가격이 50만원이라고 해도, 660여만개를 구비하려면  3조 3천억원이상이 필요하다.

결국엔 Cassandra를 만들었다는 저 엔지니어들은 잘못되거나 왜곡된 실험 결과를 내놓은 거라고 밖에 생각할 수가 없다. 우리나라에서도 학부 2-3학년에 배우는 디스크가 어떤 구조인지, 디스크의 cost model도 모른다는 얘기가 된다.
 필시 메모리에 50GB 데이터를 유지하는 상태에서 저렇게 얘기하는 것으로 밖에 보이지 않는다.
근데 여기서 다시 또 생각해보면, 디스크의 데이터를 메모리에 올리는데 걸리는 시간은 디스크 읽기 속도에 의존적일 수밖에 없다.  이때도 쓰기 때와 비슷한 속도가 나올텐데, 도대체 어떻게 저런 실험 결과가 나왔다고 주장할 수 있는지 참 궁금할 따름이다. 
Posted by Bart

댓글을 달아 주세요

  1. 비밀댓글입니다

    2009.12.28 20:35 [ ADDR : EDIT/ DEL : REPLY ]
    • 네. 데이터를 디스크에 기록하는 시간은 절대 될 수 없습니다.
      말씀하신 바는 query 를 각 노드에 배분하여 writing 작업수행 준비에 걸리는 시간이 아닌가 하는거죠?

      그럴 가능성은 있겠네요. SQL은 질의 parsing하고, query plan 작성하고 이에 따라 subquery들을 각 노드에 배분해야 하니까, 시간이 좀더 걸릴 수 있겠네요.
      그런데 사실 이것도 일장일단이 있지요. 간다하고 몇개 안되는 질의들은 직접 프로그래밍 해서 뜨는게 나을 수 있고, 좀더 복잡하고, 재사용될 수 있는 질의들은 SQL로 뜨는게 더 낫겠고요.

      근데 질의 배분 시간을 의미한다면, 저렇게 write average란 단어를 TP에 쓰면 안되겠죠. 그리고 데이터 사이즈는 또 뭐란 말인지.

      2009.12.29 03:07 신고 [ ADDR : EDIT/ DEL ]
  2. 뫈퐁

    카산드라 관련 포스팅을 찾아 다니다 좋은 의견의 글을 보고 댓글 남깁니다.
    아무리 생각해도 물리적으로 디스크에 쓰는 경우 저 성능은 나올 수가 없겠지요.
    http://www.mikeperham.com/2010/03/13/cassandra-internals-writing/
    위 글을 보면 바로 디스크에 동기화 하지 않아도 되니 저 성능을 보이는군요.
    올리신 글이 작년 글이긴 하지만 몇 줄 남깁니다.

    2010.10.01 10:58 [ ADDR : EDIT/ DEL : REPLY ]
    • 글 감사합니다.

      네. 올리신 주소의 글에서 보이는 바와 같이 Cassandra도 BigTable에서와 마찬가지로 데이터를 메모리에 유지하고 있다가 disk에 임계값이 넘을 때 이것을 그대로 immutable image로 디스크에 쓰는 것으로 압니다. 더 구체적오르는 Patrick O'Neil의 LSM-tree에서 언급되었던 update-intensive한 작업 처리를 위해 인덱스 갱신을 sequential workload로 만드는 방법을 차용한 것으로 보여집니다. 이래놓고는 디스크에 기록한다고 해서 사람들 헷갈리게 만들었으니...

      2010.10.03 14:20 신고 [ ADDR : EDIT/ DEL ]

CS 전공/리뷰2009. 11. 22. 15:06
XML이 출현하여 관심을 받아오던 99년, 그 때부터 시작된 이 연구는(까맣게 모르고 있었지만, 이 바닥의 빅 가이들은 이미 눈치채고 연구해왔던), 기존의 DBMS 코드들이 고안되었던 70,80 년대의 컴퓨터 시스템과 지금의 컴퓨터 시스템의 차이 때문에 기존 DBMS에서 널리 사용되던 알고리즘들을 다시 고려해야 한다는 생각에서 출발하였다.

이전의 컴퓨터 시스템과 현재의 컴퓨터 시스템의 차이를 들자면, 여러가지가 있겠지만 현재까지 누적되어온 중요한 차이점들은 다음과 같다.

1) 더 커진 메모리 용량(capacity) 하지만 그만큼 개선되진 못한 접근속도(latency), 그리고 메모리 접근속도의 개선속도보다 더 빠르게 상승한 clock speed의 CPU. 그리고 이러한 접근속도의 차이에 의해 발생한 이에 따른 메모리 벽(memory wall) 문제
 (메모리 벽 문제에 대해서는 일전에 올려둔 을 참고하세요) 
2) 더 커지고 계층화된 HW cache와 이에 따른 메모리 계층(memory hierarchy)
3) Supersclalar CPU(Out-of-Order Instruction Execution), branch prediction, SIMD, 그리고 SMT(Symmetric Multithreading)와 같은 CPU에서의 개선기능들.
4) Multicore(CMP; Chil-level MultiProcessor), Cell Processor, GPU등과 같이 달라진 구조의 CPU
5) Flash Memory
6) FPGA(Field Programmable Gate Array)

즉, 현재의 시스템은 위와 같은 여러 추가적인 기능들을 제공하게 되는데, 기존의 코드들은 이러한 기능들을 제대로 이용하고 있지 않는다는 사실이다.
그래서, 사람들은 Colume-oriented DBMS와 같은 data placement의 변경을 고안하기도 했으며,
또한 메모리 벽 문제를 해결하기 위한 Cache-conscious와 Cache-oblivious algorithm들을 고안하였다.
뿐만 아니라, CSB+-tree 처럼, B-tree와 같은 주요 자료구조들을 다시 바꾸기도 하였다. (Main-memory DBMS에서 이용하는 T-tree는 cache에 대한 고려가 전혀없는 구닥다리라나...) 또 칩 레벨의 멀티 프로세서를 지원하기 위한 여러 방법들이 고안되었고, GPU를 CPU 이외에 질의처리를 위한 보조 프로세서로 활용하기 위한 연구들도 2004년부터 소개되어왔다. 
최근에는 I/O 비대칭성과 in-place update가 안되는, 하지만, latency와 요구전력이 HDD에 비해 월등히 낮은 Flash memory를 위한 여러 연구들도 진행되어 왔다.
요새는 또 FPGA를 이용해 알고리즘을 HW로 구현하는 방식을 통해, 현재의 폰 노이만 방식의 컴퓨터 성능보다 몇십배 향상된 처리 성능을 보장하기도 한다. 

이러한 약 10년간에 걸친 HW 변화에 따른 DBMS 기능의 개선을 위한 연구들의 흐름을 따라가기가 참 버거웠는데, 이들을 한눈에 파악할 수 있도록 해주는 좋은 참고문헌들이 있어서 이를 소개한다.

1) Database Optimizations for Modern Hardware'' J. Cieslewicz and K.A. Ross Proceedings of the IEEE, 96(5), ..... Ken Ross kar@cs.columbia.edu. April, 2009 Paper

2) Database Architectures for New Hardware (invited tutorial), in the 30th International Conference on Very Large Data Bases, Toronto, Canada, August 2004. Also presented as a refereed seminar at the 21st International Conference on Data Engineering, Tokyo, Japan, April 2005.  Slides

3) Query Co-processing on Commodity Processors, in the 22nd International Conference on Data Engineering, Atlanta, Georgia, April 2006 Slides Part I [2.3MB], Part II [2.8MB]

이 쪽 관련해서는 콜럼비아대의 Kenneth Ross, CMU의 Anastasia Ailamaki, 그리고 네덜란드 CWI의 Peter Boncz와 S. Manegold 등이 대가이고, Column-oriented DB 관련해서는 Yale의 Daniel Abadi 등이 많은 연구를 수행하였다.
Flash Memory 관련해서는 여기 문 교수님과 성대 이상원 교수님이 또 좋은 연구를 하셨다.

FPGA를 이용한 알고리즘의 HW로의 구현은 최근에 연구들이 나오기 시작했는데, 제시하는 실험 결과들을 보면 정말 대단하다. dynamic programming 기법의 알고리즘들을 대상으로는 상대적으로 불리할 듯 싶지만, static하게 작성된 알고리즘들을 FPGA로 구현하는 경우에는 그 속도 향상이 엄청난 듯 싶다. 이미 Kickfire 등에서는 FPGA를 이용해 DB 알고리즘들을 구현하기 시작했다고. (http://dbmsmusings.blogspot.com/2009/09/kickfires-approach-to-parallelism.html)


Posted by Bart

댓글을 달아 주세요

  1. 홍석진

    잘 지내시죠? 지난 번 문교수님 한국오셨을때 소식 전해 들었습니다.
    CIKM에서 발표하셨다면서요. 축하드립니다.^^
    요새 올라오는 post들이 너무 주옥같아서 계속 눈팅만 하다가 간만에 댓글 한번 올려봅니다.
    계속 멋진 연구 기대하고요~ 따뜻한 연말 보내세요~
    종종 들르겠습니다.^^

    2009.11.23 10:28 [ ADDR : EDIT/ DEL : REPLY ]
    • 석진씨도 잘 지내시죠? 블로그를 보면, 참 재밌게 사시는 듯 해서 부럽습니다.(여기는 정말 삭막+황량 ㅠㅠ)언제 한번 다시 뵈어야 할 텐데요.

      2009.11.24 01:34 신고 [ ADDR : EDIT/ DEL ]
  2. 정말 유익한 참고문헌들이네요 :) 항상 많이 배워 갑니다.

    2009.11.23 17:37 [ ADDR : EDIT/ DEL : REPLY ]
    • 별말씀을.. 이 바닥의 논문들을 잘 정리한 켄 로쓰와 아나스타샤 교수에게 감사를~~ 종종 의견 남겨주세용~

      2009.11.24 02:11 신고 [ ADDR : EDIT/ DEL ]
  3. webtk

    바쁘실텐데, 잘 이해가 안가는 부분이 있어서 질문 드립니다.
    "dynamic programming 기법의 알고리즘들을 대상으로는 상대적으로 불리할 듯 싶지만, static하게 작성된 알고리즘들을 FPGA로 구현하는 경우에는 그 속도 향상이 엄청난 듯 싶다."
    다이나믹 프로그래밍이란 게 문제를 큰 문제, 작은 문제로 분리하고 두 문제의 관계식(점화식)을 만들고는 작은 문제들의 해들을 배열에 저장한 후 재귀적인 성질을 결합해서 큰 문제들을 해결하는 것 맞나요? static이라고 하신 부분은 다이나믹 프로그래밍으로 풀지 못하는 문제를 가리키는 것 같고..

    근데, 다이나믹 프로그래밍을 FPGA로 구현한 것과 일반 폰노이만 컴퓨터에서 동작시키는 것에서 왜 차이가 나는지.. FPGA를 몰라서 그런가 잘 이해가 안되네요. ㅠㅠ

    2009.11.24 13:52 [ ADDR : EDIT/ DEL : REPLY ]
    • static이라는 얘기는 단순히 dynamic programming의 반대 개념으로 어떤 naive한 방법을 일컫기 위해 언급한 것인데...

      CS 쪽에서 Dynamic programming에 대한 정의는 큰 문제를 여러 문제로 나누어 푼다고 볼 수 있지만, 더 엄밀히 얘기하자면 어떤 복잡한 문제애 대한 최적의 해는 이 문제의 부분 문제에 대한 최적해의 조합이라는 점을 이용하는 것이고, 그러다 보면 , recursion을 이용해야 되고, 문제가 복잡함에 따라 코드도 복잡해지고...
      DBMS 쪾에서 dynamic programming을 이용하는 대표적인 경우는 query plan을 예를 들일 수 있는데, 어떤 SQL 질의를 처리하기 위해 각 기본 DB 연산들의 비용을 계산하고 이들의 조합으로 이루어지는 질의의 최적의 해(최저비용을 갖는 질의 플랜)을 세운느 등에 이용된다. 여기서 문제는 코드가 복잡해진다는 것인데, FPGA에서 한 기판에 담을 수 있는 CLB(Configurable Logic block)의 수는 한정되어 있으므로 매우 규모가 크고 복잡한 코드들을 FPGA로 뜨기가 어렵고, 또 한 기판에 logic 수가 많아지고 복잡해질수록 느려지는 현상이 일어난다는 것을 얘기하고 싶었지. 그리고 FPGA는 C/C++의 recursion을 제대로 지원하지 못해서 branch들로 전부다 풀어헤쳐서 구현해야 하는데 그러면, 더더욱 코드가 복잡해지고 그만큼 느려진다는 거지 머.

      2009.11.24 14:38 신고 [ ADDR : EDIT/ DEL ]
  4. webtk

    아. FPGA에서는 그런 제약이 있군요. 그럼 덜 복잡한 알고리즘에서 도전들을 하고 있겠군요. DB Operator Set에서 FPGA가능과 불가능으로 분류한 사람도 있을지도 모르겠네요. 설명 감사합니당~

    2009.11.24 16:50 [ ADDR : EDIT/ DEL : REPLY ]
  5. 홍석진

    블로그에 재밌었던 순간들만 올려서 그렇게 보이는 거에요;;;
    차근차근 연구의 정도를 밟아가시는 경하씨가 훨씬 부럽습니다 ^^;
    담에 한국 오시면 연락주세요~!

    2009.11.26 21:30 [ ADDR : EDIT/ DEL : REPLY ]
    • 차근차근 이라기 보다는, 거의 *우당탕탕* 수준입니다 ㅋ

      2009.11.28 08:16 신고 [ ADDR : EDIT/ DEL ]

CS 전공/리뷰2009. 9. 28. 21:49

프로그램을 코딩할 때에 우리는 종종 컴퓨터 구조를 무시하거나, 망각하고 코딩하는 경우가 종종 있다. 이렇게 프로그래머들이 컴퓨터 구조를 무시하는 이유는 내가 판단하기에 크게 두가지이다. 첫째는 몰라 서이고, 둘째는 프로그래밍 생산성(productivity)을 증가시키기 위해 잘 추상화된, 즉 high-level abstraction을 제공하는 프로그래밍 언어의 사용 으로 인해서이다. 즉 프로그램 성능에 관한 문제를 완전히 또는 상당 부분 컴파일러나 인터프리터에게 맡겨버림으로써 더이상 컴퓨터 구조에 대한 고민을 하지 않아서이다. Java만 해도 포인터를 없앰으로써 메모리 관리에 대한 고민을 더이상 하지 않게 하지 않았는가? 이러한 프로그래밍 언어의 abstraction은 프로그램의 생산성은 크게 향상시켜 주었다. 하지만 프로그램의 성능(performance)에 대한 고민을 한다면, 저수준의 추상화를 제공하는 다른 프로그래밍 언어를 이용해 컴퓨터 구조에 잘맞는 프로그램의 작성이 요구될 것이다. 그리고 그것이 내가 생각하는 C/C++, Assembly가 아직도 성능이 우선시 되는  여러 프로그래밍 분야, 특히 시스템 프로그래밍에 널리 이용되는 이유이다. 
 
프로그램을 코딩할 때에 왜 컴퓨터 구조를 고려해야 하는지 여기에 그 이유가 있다.

그림 1. Multi-level Caches in Computer Systems



그림 1은 컴퓨터 시스템의 캐시 구조를 개념적으로 도식화한 것이다. 프로세서는 instruction이나 data를 보관할 register와 L1 cache를 가지며, 또한 L2 cache를 갖는다. 어떤  CPU는 L1 cache로 Instruction cache와 data cache를 따로 가지는 경우도 있으며 또는 Unified L1 cache 하나만을 가지는 경우도 있다. L2 Cache는 현재 대부분의 CPU는 on-chip으로 되어 있으며, 간혹 어떤 CPU들은 Off-chip L3 cache를 갖는 경우도 있다. 메인 메모리는 I/O BUS를 통해 CPU 및 다른 디바이스들과 연결되며,  Disk 또한 I/O BUS를 통해 연결된 Disk controller를 통해 연결된다. BIOS(Basic IO System)을 제외한 컴퓨터 시스템의 운용들에 필요한 거의 모든 프로그램과 데이터는 초기 디스크에 저장되어 있으며, 필요에 따라 프로세서에 의해 요구된다. 
우리가 익히 알다시피 디스크는 용량(capacity)와 $/MBytes 는 우수한 반면에 속도(speed)는 늦은 저장매체이다. (사실 속도는 latencybandwidth 두 요소에 의해 결정된다.)
따라서, 필요한 데이터 접근을 위해 매번 CPU가 disk controller에 데이터를 요청한다면, CPU는 디스크가 해당 데이터를 제공하기 위해 필요한 시간(latency + read time+ delivery time)동안 아무일도 하지 못하는 stall 상태에 놓이게 된다. CPU는 가급적 놀리지 않아야 코드의 성능 향상이 있다.

따라서, 현대의 컴퓨터 시스템은 다단계의 캐시 구조를 가진다. 자주, 빈번하게 쓰이는 데이터들은 보다 상위의, 용량은 좀더 작고, $/MBytes는 보다 비싸며, 속도는 보다 빠른, 메인 메모리에 캐싱을 하는 것이다. 데이터베이스에서는 이렇게 디스크에서 메모리로 올려진 데이터들을 버퍼라고 얘기를 하기도 하며, 또 혹자는 메모리 캐시라고도 얘기하기도 한다.
메모리 또한, 접근 속도가 시스템 캐시(L2) 보다 느리므로, 메모리에서 또 다시 자주 사용되는 데이터나 루틴은 다시 L2로 캐시한다. 그리고 L2는 L1으로 L1는 프로세서의 레지스터로.... 결과적으로 컴퓨터 구조는 다음과 같은 메모리 계층(memory hierarchy)를 갖게 된다.
 

그림 2. Memory Hierarchy


최근까지 많은 컴퓨터 프로그램의 성능 향상은 주로 디스크와 메모리 간의 속도 차이를 극복하기 위한 방안으로 진행되어 왔다. 즉 느린 속도를 개선하기 위해 많이 쓰이는 데이터를 메모리에 가져다 놓기 위한 노력이 있어왔는데 대표적인 것이 Buffer Management(LRUK 등), B+-tree, R-tree와 같은 disk-resident indexing 기법들이 있을 수 있겠다. 실상 최근까지 데이터베이스 및 정보 관리 분야에서의 거의 모든 문제들은 이러한 디스크와 메모리 간의 gap을 어떻게 극복하느냐를 주된 관심으로 가졌으며, Jim Gray는 이러한 디스크와 메모리 간의 gap에 대해 저 유명한 Five Minute Rule[5] 로 매 5분 내에 다시 이용될 디스크 페이지는 메모리에 캐시하도록 제시했었다. 또, 디스크라는 storage는 latency 자체가 크게 성능 개선이 이루어지지 않아 왔던 관계로, 이러한 기법들이 지금까지도 아주 잘 먹혀 들어갔던 것도 사실이다. (Latency와 Bandwidth의 차이는 [1]을 참조)

그림 3. Memory Wall



하지만, 최근의 경향을 보면 이제는 메모리 또한 bottleneck이 되어 가고 있다는 것이다[2]. 메모리 월(Memory Wall)이라고도 불리는 이 현상의 설명을 위해 그림 3을 보자.
그림 3은 한 instruction 수행을 위해 요구되는 clock 수의 개선 경향과, 메인메모리로 사용되는 DRAM의 접근에 필요한 clock 타임을 비교한 것이다. 메모리 용량의 증가는 메모리 칩 내부에 더 많은 내부 공간을 가진다는 것이며, 접근할 내부 공간의 증가는 더 많은 system clock을 필요로 한다.  CPU의 system clock이 매년 크게 향상되어서, 실제 메모리 접근에 필요한 시간은 줄어든다 할지라도, 메모리 접근에 필요한 절대적인 clock 수는 증가한다라는 것이다. 예를 들어 한 프로그램이 100 Instruction으로 구성되고 프로그램이 필요한 데이터를 위해 각 LOOP마다 메모리에 1번씩 접근,메모리에 10번 access를 한다고 하자.  2010년 기준으로 100 Instruction 처리는 4.2 clock만에 끝나는 반면, 한번의 메모리 접근을 위해서는 1000 clock이 요구된다. 즉, 메모리에서 데이터를 읽어들여 CPU의 레지스터에 올리기 전까지 CPU는 995.8 clock 동안 아무런 일을 하지 않고 노는 stall 상태에 빠지게 된다. 이 후 두 번째 LOOP부터는 레지스터, L1, L2 cache에 접근하여 데이터를 읽어들이던가 아니면 또다시 메모리에 접근하겠다.
물론 매 LOOP마다 메모리에서 데이터를 가져온다면, 이 같은 현상이 반복될 것이다.

 따라서 이러한 메모리와 CPU 간의 속도 차이는 L1, L2 시스템 캐시의 효과적인 이용을 고민하게 한다. 마치 예전에 디스크와 메모리 사이의 갭을 극복하고자 했던 것과 마찬가지로 말이다.
그림 4와 5는 이러한 고민이 왜 필요한지 여실히 보여준다.
  

그림 4. Memory Mountain of Pentium III Xeon


 그림 4는 1999년 출시되었던 Intel의 Pentium III Xeon 을 탑재한 컴퓨터 구조에서 메모리와 L1, L2 시스템 cache 간의 데이터 처리량(throughput)의 차이를 보여준다. 

그림 5. Memory Mountain of Intel Core 2 Duo T9300


그림 5는 2008년 1분기에 출시된 Intel Core 2 Duo T9300(2.5GHz Clock speed, 2X 32KB On-chip L1 D-Cache, 2 X 32KB On-chip L1 I-Cache, 6MB Unified L2 Cache) 을 탑재한 컴퓨터 시스템에서 메모리와 L1, L2 시스템 캐시에서의 데이터 처리량을 보인다.    

 먼저 그림 4의 Xeon 에서의 L1, L2, Mem간의 단위 시간 당 처리량을 보면, Stride-1인 경우 메모리는 200 MB/S 이하, L2 Cache는 700MB/S 이상, L1 Cache는 1000MB/S 이상을 상회한다. 
최근에도 이 상황은 달라지지 않았다. 그림 5의 Core 2 Duo의 경우 Stride-1에서 메모리는 4,000MBps/S
L1 Cache는 8,000MBps/S, L2 Cache는 10,000 MBps/S로 이 경향은 그대로 유지되고 있다. (이 실험은 멀티코어에서의 병렬성은 이용하지 않고, sequential programming하여 코어 두 개 중 하나만 이용한 경우로 보인다. 그 이유는 나중에 설명한다.)

빈번하게 사용되는 데이터는 캐시에 올려놓음으로써, 가급적 메모리에 접근하지 않고, 프로그램을 수행하는 것이 보다 프로그램 성능을 향상시킬 수 있다. 하지만, 시스템 캐시에서의 데이터 또는 instruction의 배치(placement)와 교체(replacement)는 H/W에 의해 결정이 되므로, 우리가 임의로 어떠한 프로그램이 다루는 코드나 데이터를 임의로 캐시에 배치하기는 곤란하다. 하지만, 캐시되기에 좋게 프로그램을 작성할 수 있는 방법은 있다. 즉, Cache-aware한, 또는 Cache-friendly한 프로그램을 작성하는 것이다. 그러면, 어떻게 해야 cache-friendly한 프로그램을, cache-aware한 알고리즘을 작성할 수 있을까? 위 데이터 차트들에 그 힌트가 있다.

먼저 그림 4를 보면, L1 cache와 L2 cache, memory가 서로 다른 능선들을 그리는 것을 볼 수 있다.
어떤 한 프로그램의 data가 모두 L1 cache에 저장되어 있다면 최대 1000MB/S의 처리량으로 프로그램이 처리될 수 있을 것이다. 반대로 어떤 한 프로그램의 data가 모두 memory에 저장되어 있고 L1, L2에 의해 cache되지 못한다면, 200MB/S 정도의 처리량 밖에 얻지 못한다. 
이번에는 작업 데이터 크기(working set size)를 보자. working set size에 따라 달라지는 처리량은 시스템 캐시의 크기와 관련이 있다. L1 d-cache의 크기가 16KB이므로, 16kB를 넘는 작업 데이터는 당연히 L1 d- cache에 담을 수 없으므로 L2 cache에 담고, L2 cache에 접근하게 된다. 또한, 512KB L2 cache를 넘는 데이터는 종국엔 메모리에 접근해서 가져오게 된다. 결국, 16KB, 512KB의 작업 데이터 크기를 경계로 능선이 구분된다.

또다른 현상은 stride의 수에 기인한다. stride란 해당 작업 데이터가 메모리 공간에 서로 인접해 있어 한번의 scan으로 읽혀지는지, 아니면  나뉘어져 있는지를 구분한다. 즉, stride-1은 모든 데이터가 서로 메모리 공간에 인접해 있다는 것이며(data[0], data[1], ...data[n]), stride-2는 작업 데이터가 1개 공간씩 떨어져 있다.(data[0], data[2], data[4], ,,,, data[n]). 즉, stride-k은 data[0], data[k], data[2k], ....로
메모리에서 이전 데이터와 k만큼 떨어져 있는 데이터를 읽는다.
stride-1에서는 데이터가 서로 인접해 있으므로, data를 sequential scan 하기 용이하며 결과적으로 처리량도 제일 높다. stride-k에서 k가 증가하면 증가할 수록, 데이터가 서로 떨어져 있게 되어 메모리의 처리량은 떨어진다. 하지만 L2 cache는 어떨까? L2 cache에서는 처리량이 떨어지다가 stride-8 부터는 평지를 이룬다. 이것은 한 캐시 라인이 가지는 캐시 블록 크기와 관계가 있다. 여기에서 한 캐시 라인의 block size는 8word(32bytes)이다. stride-1일 때는 8개의 인접해 있는 word들이 한 캐시라인에 캐싱될 것이고, stride-2일 때는 4개의 인접해 있는 word들이 한 캐시라인에 캐싱될 것이다. stride-8일 때는 1개의 word만이 한 캐시라인에 캐싱된다. 따라서 stride-8인 경우는 8개의 cache line을 읽어야만 8 word를 복구시킬 수 있다. stride-8 이상의 경우에도 물론 8개의 cache line을 읽어야 한다. (word 단위 이하로 잘라서 캐싱하지는 않기 때문이다).  

프로그램은 로컬리티(locality)를 가진다. locality란, 프로그램은 최근에 이용했거나 참조한 인스트럭션이나 데이터를 다시 이용하는 경향을 보인다는 것이다. 이러한 로컬리티는 크게 temporal과 spatial로 나뉜다.
  • Temporal locality: 최근에 참조한 아이템은 가까운 미래에 다시 참조되는 경향이 있다.
  • Spatial locality : 인접해 있는 항목들은 한 번에 같이 참조되는 경향이 있다.

전체 캐시 크기(total cache size)는 temporal locality를 이용에 힌트를 준다. 즉 임의 프로그램이 작업 데이터를 반복적으로 읽어야 하는 경우, 한번에 참조하는 최대 데이터의 크기를 전체 캐시 크기 단위에 맞추어 블록 단위로 처리하면, 메모리 접근을 상대적으로 많이 피할 수 있으므로 성능 향상을 시킬 수 있다는 점이다.
두 번째로는 시스템 캐시의 캐시 크기는 spatial locality의 이용에 힌트를 준다.캐시 라인 크기에 맞추어서 데이터들을 서로 메모리 공간에 인접시키면, 프로그램이 데이터를 캐시에서 읽어 들일 때 여러 캐시 라인이 아닌, 한 캐시 라인 단위로 읽어들임으로써 성능 향상을 시킬 수 있다. 이는 포인터 이용에 관한 우리의 일반적 습관들을 다시 한번 고민하게도 한다.

다음 글에서는 행렬 곱셈과, Cache-aware한 B+트리, 해싱과 같은 예를 통해 로컬리티의 향상이 어떻게 프로그램의 성능을 개선하는지 보인다.

참고 문헌
[1] Latency Lags Bandwidth, David A. Patterson, Communications of ACM, 2004
[2] Hitting the Memory: Implications of the Obvious, ACM SIGARCH Computer Architecture News,  Bill Wulf and Sally Mckee, 1995
[3] Query co-Processing on Commodity Processors, Anastassia Ailamaki and et al., A tutorial in ICDE 2006.
[4] Computer Architecture: A Quantitative Approach The 4th Edition, John L. hennesy and David A. Patterson, 2007
[5] The 5 Minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time, Jim Gray, SIGMOD Record, 1987

Acknowledgement
이 글에서 참조한 그림 1,2,4 는 Computer Systems: A Programmer's Perspectivem Prentice Hall, 2002의 instructor's material에서 발췌함. 그림 5는 Wikipedia에서 발췌함. 그림 3는 참고 문헌 [3]의 저자들의 Lecture slides에서 발췌함.

Written by Bart, 2009

'CS 전공 > 리뷰' 카테고리의 다른 글

Casssandra의 매우 이상한 성능 값  (4) 2009.12.27
DBMS on New Hardware  (9) 2009.11.22
Memory Hierarchy, Memory Wall and Memory Mountain  (10) 2009.09.28
최근의 DB 연구 경향  (1) 2009.08.20
Claremont Report  (0) 2008.09.10
ASU의 Yi Chen 교수의 대학원 강의:Data on the Web  (0) 2008.03.25
Posted by Bart

댓글을 달아 주세요

  1. webtk

    '메모리 산'과 '메모리 벽'은 저도 이제야 알게 되네요.
    글 쓰느라 애 많이 고생하셨겠어요. 아~ 저도 이런 글 써야 되는데.. ㅠㅠ

    2009.10.01 12:55 [ ADDR : EDIT/ DEL : REPLY ]
  2. 응. cache-awareness와 multi-core 관련해서 한 번 써보려고. cache-awareness 관련해서, 한국 웹 사이트에서 아무런 내용을 찾지를 못하겠더라고.

    2009.10.05 15:57 신고 [ ADDR : EDIT/ DEL : REPLY ]
  3. 비밀댓글입니다

    2010.05.04 10:36 [ ADDR : EDIT/ DEL : REPLY ]
  4. 으허허허

    감사합니다 ㅜㅜ stride에 대해 몰라서 찾고 있었는데 바로 나오는군요

    2010.12.15 02:21 [ ADDR : EDIT/ DEL : REPLY ]
  5. 감사합니다! memory hierarchy 공부하다가 몰라서 구글링해서 들어왔는데 설명 너무 잘해놓으셨네용 ^^
    도움많이 받고가요~

    2011.05.22 20:30 [ ADDR : EDIT/ DEL : REPLY ]
    • 도움이 되었다니, 글쓴 보람이 있군요. 그냥 지나쳐도 되었을텐데 애써 글남겨주셔서 감사합니다.

      2011.05.23 20:16 신고 [ ADDR : EDIT/ DEL ]
  6. 신라

    안녕하세요?yelp 운영자이신가요?yelp사이트에 올라있는 신라식당을 인수한 사람입니다.메뉴가 많이 바뀌어서 어떻게 해야 할지 몰라서 찿다보니 여기가지 왔네요.메일 주시면 감사하겠습니다.
    choson12@nate.com기다리겠습니다.

    2011.06.10 23:05 [ ADDR : EDIT/ DEL : REPLY ]
    • 저는 yelp 운영진이 아닌, 여기 블로그 주인장입니당

      2011.06.11 12:57 신고 [ ADDR : EDIT/ DEL ]