'DBMS'에 해당되는 글 2건

  1. 2010.04.07 Integrating NAND Flash Devices onto Servers
  2. 2009.11.22 DBMS on New Hardware (9)
CS 전공/리뷰2010.04.07 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 전공/리뷰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 ]