순차파일 또는 인덱스된 파일을 만들 때 최대한 디스크 접근을 줄이는 방법?

superkkt의 이미지

안녕하세요.

이번에 개발하는 프로그램이 대용량 벡터 데이터를 파일로 저장하고 검색을 해야 합니다.

데이터의 가장 작은 단위를 엔트리라고 하고, 하나의 엔트리는 128바이트의 크기를 가지며, 512개의 엔트리가 모여서 하나의 논리적인 레코드를 형성합니다. 프로그램에서는 레코드 단위로 데이터 파일에 접근하고, 데이터 파일은 단순히 레코드를 순차적으로 나열한 형태로 파일의 전체 크기는 (레코드의 개수 * 하나의 레코드 크기)와 같은 형태입니다. 이렇게 구현한 이유는 프로그램의 검색 성능이 굉장히 중요해서 레코드 번호만 가지고 한번의 디스크 접근으로 데이터를 읽어들이기 위해서 입니다.

데이터가 삽입되는 과정에서 새로운 레코드가 생성되면 무조건 512개의 엔트리가 들어가는게 아니라 점진적으로 엔트리가 삽입이 됩니다. 그리고 레코드에 엔트리가 꽉 차면 분할이 되어서 두 개의 레코드로 나누어 집니다. 그래서 데이터 파일을 생성할 때 비록 레코드에 엔트리가 꽉 차있지 않아도 일단 512개의 엔트리가 삽입될 공간을 미리 만들어두고, 나중에 해당 레코드에 엔트리가 삽입될 때 실제로 데이터를 기록하는 형태로 구현하였습니다. 그리고 데이터베이스 구축 과정에서는 일정 크기의 메모리 버퍼에 우선 삽입되는 데이터를 모아 두었다가 한번에 디스크에 기록하는 형태로 되어있습니다.

그런데 데이터 파일의 크기가 작을 때는 레코드가 몇 개 없고, 또 대부분의 데이터가 연속적이기 때문에 캐쉬 데이터를 비울 때 적은 수의 시스템콜로 상당히 빠르게 디스크에 기록을 합니다. 하지만 파일의 크기가 커질 수록 캐쉬된 데이터들은 비연속적으로 변하고, 그로 인해서 시스템콜의 횟수가 계속적으로 증가하게 되어서 속도가 상당히 느려지는 문제가 발생하고 있습니다. 그리고 파일의 크기가 수백GB로 커지면 seek time도 속도를 느리게 하는 요인인것 같습니다.

그래서 해결 방법으로 데이터는 삽입되는 순서대로 데이터 파일에 순차적으로 기록하고 인덱스 파일을 별도로 만드는 방법을 고려하고 있는데, 이 방법도 데이터 파일의 크기가 커지면 인덱스를 갱신하기 위해 결국엔 비슷한 횟수의 시스템콜이 발생할것 같습니다. 인덱스 용도로 SQLite도 사용을 해봤는데 속도가 많이 느리더군요. 그리고 인덱스를 메모리에 올리기에는 처리하는 데이터가 워낙 고용량이라서 불가능 합니다.

혹시 다른 좋은 방법이 있으면 조언 부탁 드립니다.

charsyam의 이미지

1. 파일 I/O 시에는 최대한 한번에 많이 읽고 많이 쓴다.

읽으실 때도 block을 약간 크게 해보시길 바랍니다.

시스템 상황에 따라서 틀릴수도 있는데 보통 1M 가 단위로 읽으니 최적의 속도가 나오더군요.

2. 메모리가 충분하면 최대한 메모리에 올린다.

3. 파일에 쓸 경우, 한번에 찾을 수 있는 방법으로 쓰고 읽는다.
예를 들어, 인덱스 파일을 하나만 찾는게 아니라, 특정 영역별로 인덱스를 나눠 놓아서 한번에 읽을 수도 있습니다.

뭐, 이런 식으로 적당히 읽어야 할 부분으로 가고, 메모리에 잘 올려놓고 하시면
(결국 적절한 캐싱이죠.)

파일에도 데이터의 Locality 를 고려해서 저장하시면, 적은 I/O로 많은 효과를 얻을 수 있습니다.

=========================
CharSyam ^^ --- 고운 하루
=========================

=========================
CharSyam ^^ --- 고운 하루
=========================

powersys의 이미지

일단 데이터파일들을 분리하는 방안을 검토해보세요..
그리고.. 각 데이터파일들을. 분산해시테이블처럼 관리하시고 개별파일(파티션)들에 개별 인덱스파일을 두시는게 어떠실지.

superkkt의 이미지

데이터 파일의 크기가 커지는게 속도를 느리게 하는 원인일까요?

저는 시스템콜의 횟수가 증가하는게 직접적인 원인이라고 생각해서 계속 시스템콜의 횟수를 낮출 수 있는 방법만 고민하고 있었거든요. 요약하면 처음에는 큰 블럭 크기로 적은 수의 시스템콜이 호출되는데, 레코드의 개수가 많아질수록 엔트리가 여러 레코드에 분산되기 때문에 이걸 디스크에 기록하려면 결국 작은 블럭 크기로 많은 시스템콜을 호출하게 됩니다.

그래서 파일을 분산하더라도 호출하는 시스템콜의 횟수는 변화가 없을텐데 그럼 큰 성능 변화도 없지 않을까요?

======================
BLOG : http://superkkt.com

======================
BLOG : http://superkkt.com

powersys의 이미지

작은 블럭단위io를 하지마시고 메모리에서 일괄작업을 하시고 한꺼번에 저장하세요.

또한 아무래도 파일이 크다보면 seek 이 힘들어지겠죠.

superkkt의 이미지

답변 감사합니다. 그런데 본문에서 제 설명이 조금 부족했던것 같습니다.

메모리에서 캐쉬했다가 디스크에 기록하지만 현재 데이터 파일의 구조상 데이터가 디스크의 여러 부분에 분산되어서 저장되기 때문에 여러번 write를 호출해야 합니다. 데이터 파일이 커질수록 분산되는 정도가 심해져서 더욱 많은 write를 호출하게 되고요. 이 부분이 설명하기가 좀 복잡해서 제대로 전달이 안된것 같습니다.

그래서 데이터는 삽입되는 순서대로 데이터 파일에 한번의 write로 저장을 하고, 각각의 데이터 위치를 인덱스 파일에서 갱신해주는 방향으로 수정해보려고 하는데요. 이때 인덱스 파일을 갱신할 때 여러 번의 write 호출이 발생하게 되어서 결국엔 현재 구조와 다를게 있겠나하는 의문에서 질문을 올린겁니다.

그리고 데이터가 워낙 크기 때문에 인덱스 자체도 메모리에 올리기는 힘들고요. 최대한 가용 메모리에 캐쉬를 하는 방법으로 해보겠지만 뭔가 더 좋은 방법이 없을까 싶어서 질문 드렸습니다.

======================
BLOG : http://superkkt.com

======================
BLOG : http://superkkt.com

powersys의 이미지

데이터자체가 여러곳에 분산저장된다면 데이터구조를 바꾸지 않는이상(저장될데이터가 한곳으로 몰아저장하는구조로바뀌지않는이상) 다른방법이 없어보이구요
그건 일단 다른문제로 제쳐두고
데이터를 분산시키면 해당데이터파일및 인덱스또한 줄어들기에 최소한인덱스만이라도 일괄저장할수 있을겁니다.
또한 인덱스나 데이터파일을 한꺼번에 올리지 못한다하더라도 대용량파일을 컨트롤하는데는 그만큼 부하가 걸리기마련입니다.
예를들어 혼자서 전국에 편지를 순서없이 배달하는것(서울에서 재주도 갔다가 다시 인천갔따가 하는방식)과
각 시도별로 나누어 배달하는것(같은동네 한꺼번에 배달하고 다음동네로 이동) 을생각해보면 차이가있지요.

charsyam의 이미지

가장 위에는 원론적인 거였는데, 위의 정책과도 영향을 맺는게

데이터가 어떤 특성을 갖는가 입니다.

한가지 데이터만 잔뜩 있는건지

insert 가 많은지
update 가 많은지
delete 가 많은지
select 가 많은지

각각의 데이터들이 연관성있게 가져와야 하는지
Row 형태로 접근이 많은지, Column 형태로 접근이 많은지

클러스터링이 되는지(즉, 데이터들 끼리 연관성이 있는지, 없는지)

등등의 특성에 따라서, 파일을 쓰고, 읽고의 정책 자체가 많이 바뀌게 될껍니다.

결국 스스로 DBMS 를 하나 만드신다고 보셔야 할듯 ㅎㅎ

그리고 위의 특성에 대해서 많이 설명해주실 수록, 답변 역시 더더욱 상황에 적합해질듯

합니다. 고운 하루되세요.

=========================
CharSyam ^^ --- 고운 하루
=========================

=========================
CharSyam ^^ --- 고운 하루
=========================

bushi의 이미지

좀 천진난만한 생각일 지 몰라도... 파일시스템을 쓰지 않으면 어떨까요 ?

데이타를 그냥 /dev/sdb 에 보관하는 식이죠. (O_DIRECT 나 /dev/raw/ 사용하고.)
단, 파일 시스템의 기능이 필요하다면 어플리케이션 자체적으로 해야합니다.
cache, buffer, lookup table 같은 것 말입니다.

주로 DB 서버 응용이나 media player 응용에서 각광받습니다만,
현재 고민하고 계시는 그 응용은 이것들보다 더 간단하니 더 쉽게 적용하실 수 있을 것 같습니다.

system call 횟수를 줄이려면 mmap() 으로.
open()/mmap()/munmap()/close() 네번에 추가적으로 필요한 만큼의 msync() 횟수가 고작입니다.
... 크기가 크다면 64bit OS 로 address space 를 극복해야겠죠.
LFS 를 써야 size_t, off_t 도 64bit 가 되겠고.
(사실, 이게 가능한지는 잘 모르겠습니다. 전엔 mmap64() 니 mmap2() 니.. 뭐 이런게 있었는데말이죠.)

I/O 의 양 자체를 줄이고 싶다면 compress/decompress 밖엔 없습니다.
CPU 의 성능과 storage 의 성능에 따라 적절히 선택해야하는데,
lzma 가 실시간성이 어쩌구하며 무척 광고를 때리는군요. 압축률이 떨어지는 대신 CPU 부담이 거의 없다고 자랑합니다.
오래 전, 150MHz MIPS CPU 에서 ROM 에 파일시스템을 구성할 때,
romfs 보다는 lzramfs 가 훨씬 더 압도적인 성능을 보이던 것을 기억하고 있습니다.
cramfs 는 ... gzip 이라 압축률은 종은데 CPU 가 받쳐주질 못해서 romfs 보다도 성능이 떨어지더군요.
레코드별로 압축을 하던가, 엔트리별로 압축을 하던가해서 I/O 를 하시면 될텐데,
헤더를 기록하기 위한 추가공간 부담이 있습니다.

OTL

superkkt의 이미지

raw device를 직접 쓰는 방법도 생각은 해봤었는데 그쪽으로는 잘 몰라서 시도는 안해봤습니다.
이렇게 파일시스템을 쓰지 않고 raw device를 직접 제어하면 얻을 수 있는 이점이 뭐가 있는지요?
어디선가 듣기로는 어설프게 시도하면 파일시스템의 여러 가지 눈에 보이지 않는 기능들을 이용하지
못해서 더 성능이 떨어진다고 하더군요.

그리고 mmap을 사용하는 방법은 파일이 계속 커지고 있기 때문에 사용을 안했는데요. 혹시 삽입이 발생할
때마다 open/mmap/munmap/close를 수행하는걸 의미하신건가요?

I/O 양을 줄이려고 lzma도 써보고, gzip도 써봤는데 바이너리 데이터라서 압축률이 85~90%로 나옵니다.
그래서 들어가는 CPU 비용에 비해서 얻는 이득이 작아서 포기했고요. Floating point 데이터라서 single-
precision을 사용하고 있는데 이걸 half-precision으로 바꾸는것도 시도해 봤는데, 아직 CPU에서 지원해주지
않아서 이것 역시 연산 비용이 비싼 관계로 포기했습니다.

raw device를 직접 사용하는게 관심이 가는데 좀 더 알아봐야겠네요.

감사합니다.

======================
BLOG : http://superkkt.com

======================
BLOG : http://superkkt.com

bushi의 이미지

모든 것은 /dev/sdb 를 직접 사용한다는 가정 하에 말씀드렸습니다.
런타임에 /dev/sdb 용량이 점점 증가하지는 ...

OTL

geoplab의 이미지

저는 데이타베이스에 대해서는 잘 모르지만요...
지금 추진중인 프로젝트에서 HDF 를 이용할려고 하거든요.
HDF는 데이타 엑세스에 상당히(?) 유용한 걸로 알고 있습니다.
인덱스만 가지고 직접 엑세스한다고 하더군요.
즉 순차적으로 화일을 읽어들이지 않고 원하는 데이타를 처리하는 것을 말하지요.
관심이 있으시면 한번 보세요.
여기에 사이트를 올립니다.

http://www.hdfgroup.org/

물론 저보다 고수들이 많이 계시므로
더 좋은 아이디어들이 있겠지만요.

참, HDF를 사용해 보신 분들은 어떻게 생각하시는지 궁금하군요.
어떤점들이 괜찮았고 어떤 기능들은 불편 또는 개선해야 되는지...

antaran의 이미지

system call회수를 줄이는게(bulk i/o) 일반적인 환경이라면 아마 맞는 접근 방법일 것 같은데요.

그리고 파일이 커졌을 때 얼마나 seek time에 영향을 미치는지는 댓글을 읽다보니 궁금해지네요.

그래도 HDD가 명색이 random access 장치인데 얼마나 차이가 날지...

seek를 호출 회수를 개선하는 방향이 어떨까 합니다만 이건 무척 들인 노력에 비해 소득도 적을 것 같다는

생각입니다.

분산된 파일 찾기 + 작은 파일의 short(?) seek vs. 큰 파일에서의 long(?) seek. 쯤 되려나요?

일단, 제 생각에는 지금 하시는 프로젝트의 대략의 i/o volume을 산출을 해보시고 그 양이

장비에서 어느 정도 충족하는가를 확인하시는게 선행되어야 하지 않을까 싶네요.

다른 분이 말씀하신대로 raw모드를 이용해서 하면 좋을 수도 있겠지만, 비유를 하자면

TCP/IP쓰는데 병목 일어난다고 raw socket으로 열고 프로토콜 만들어서 성능 끓어올려보겠다는

얘기나 마찮가지 같은데 이건 정말 가시밭길 일 것 같습니다(최대의 결과가 나올 수 있는 방법이긴 하지만

현실을 고려하면 결코 최선일 경우가 흔치 않을 듯).

전송량이 안나올 땐 회선 bandwidth부터 먼저 확인해 보듯이 개발 장비, 상용장비 그리고 i/o 요구량 등을 확인해 보시는게 옳은 순서 아닐까 싶습니다.

mach의 이미지

비슷한 얘기지만, 시스템호출(system call)이란 말보다는 DISK I/O 또는 I/O를 줄인다는 말이 더 적절해 보입니다. 물론, DISK I/O도 시스템 호출의 하나이지만 말입니다.
column oriented dbms, compression등의 테크닉도 DISK I/O를 줄이는 방안으로 부터 출발했다고 봅니다.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

comafast의 이미지

http://www.haifa.ibm.com/Workshops/ir2005/papers/DougCutting-Haifa05.pdf

가장 중요한 부분인 [seek vs transfer]를 보시면 도움이 될듯합니다.

보통 검색엔진에는 DBMS와같이 실시간 트랜잭션을 처리하지 않아도 되는경우가 많습니다.
그럴때 증분색인(Incremental Indexing)알고리즘을 사용합니다.
java와 c++로 구현된 오픈소스입니다.

색인데이터가 테라급이상으로 가신다면 [lucene + hadoop] 조합으로 성공사례가 많으니 참고하시길 바랍니다. ^^

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.