固定長配列データベースの改良

スタックデータベースができたので、固定長データベース（固定長配列データベースではありません。）を実装しましょう、と言いたいところですが、その前にもうちょっと準備が必要です。

固定長データベースを用いて固定長配列データベースを実装しようと思うので、固定長データベースのクラス変数を永続化する必要があります。そこで、固定長配列データベースのヘッダーに固定長データベースのクラスの変数を格納できるような一工夫をしました。

そして、もう一つ、他のプロセスが同一の固定長配列データベースを利用しても問題ないように、他のプロセスによりサイズ変更があったときに、それを検知して再マップする処理も加えました。なお、排他制御を実装していないので、複数のプロセスが書き込む場合には問題が生じますが、一つのプロセスが書き込みだけで、他のプロセスは読み込みだけなら、うまく動作するようです。

以下がそのソースです。"// <<<<"と"// >>>>"で囲まれた部分が変更した部分です。

#include <fcntl.h>
#include <errno.h>
#include <sys/mman.h>
#include <assert.h>

#include <iostream>
#include <exception>

class Exception : public std::exception {
public:
  Exception(const std::string &msg)
  {
    message = msg;
  }

  virtual ~Exception() throw() {}

  const char *what() {
    return message.c_str();
  }

  std::string message;
};


template <class T> class Array {
public:
  class Header {
  public:
    void initialize() {
      headerSize        = 256;
      pageSize          = sysconf(_SC_PAGE_SIZE);
      elementSize       = sizeof(T);
      arraySize         = 0;
      validArraySize    = 0;
      size              = headerSize;
    }

    size_t updateSize(size_t arraysize) {
      size = ((headerSize + arraysize * elementSize - 1) / pageSize + 1) *
             pageSize;
      arraySize = (size - headerSize) / elementSize;
      return size;
    }

    size_t headerSize;
    size_t pageSize;            // page size
    size_t elementSize;         // size of an element
    size_t arraySize;           // number of elements
    size_t validArraySize;      // number of valid elements
    size_t size;                // total size
  };

  Array():fd(-1) {}

  Array(const std::string &f):fd(-1) {
    initialize(f);
  }

  ~Array() {
    if (fd != -1) {
      // <<<<
      msync(header, initialSize, MS_SYNC);  
      munmap(header, initialSize);
      // >>>>
      close();
    }
  }

  void initialize(const std::string &f) {
    file = f;
    if ((fd = open(file.c_str(), O_RDWR, 0666)) == -1) {
      if (errno == ENOENT) {
        create(file);
      } else {
        throw Exception(strerror(errno));
      }
    }
    struct stat fs;
    fstat(fd, &fs);
    map(fs.st_size);
  }

  void map(size_t sz) {
    if (fd == -1) {
      throw Exception("Not ready");
    }
    // <<<<
    initialSize = sz;
    // >>>>
    header = (Header*)mmap(0, sz, PROT_READ|PROT_WRITE,MAP_SHARED,
                   fd, 0);
    if ((long long)header == -1){
      close();
      throw Exception(strerror(errno));
    }
    array = (T*)((unsigned char*)header + header->headerSize);
    if (sz != header->size) {
      close();
      throw Exception("Sizes are inconsistency");
    }
  }

  void resize(size_t arraysize) {
    resizeCapacity(arraysize);
    if (arraysize != header->validArraySize) {
      header->validArraySize = arraysize;
    }
  }

  T &at(size_t idx) {
    if (fd == -1) {
      throw Exception("Not ready");
    }
    if (idx >= header->validArraySize) {
      throw Exception("Invalid element");
    }
    return array[idx];
  }

  T &set(size_t idx, T& v) {
    if (idx >= header->arraySize) {
      resizeCapacity(idx + 1);
    }
    array[idx] = v;
    if (idx >= header->validArraySize) {
      header->validArraySize = idx + 1;
    }
    return array[idx];
  }

  // <<<<
  size_t reserved(size_t rs) {
    return reservedSize += rs;
  }

  size_t getReservedSize() {
    return reservedSize;
  }

  void *getReservedVariable(size_t offset) {
    return (void*)((unsigned char*)(Array<T>::array) - offset);
  }
  // >>>>

  size_t getSize() { return header->validArraySize; }

protected:
  void
  create(const std::string &file) {
    if ((fd = open(file.c_str(), O_RDWR|O_CREAT, 0666)) == -1) {
      throw Exception(strerror(errno));
    }
    Header h;
    h.initialize();

    if (write(fd, &h, sizeof(Header)) == -1) {
      close();
      throw Exception(strerror(errno));
    }
    unsigned char c = 0;
    for (size_t i = 0; i < h.headerSize - sizeof(Header); i++) {
      if (write(fd, &c, sizeof(c)) == -1) {
        close();
        throw Exception(strerror(errno));
      }
    }
  }
  // <<<<
  void remap(size_t sz) {
    msync(header, initialSize, MS_SYNC);
    munmap(header, initialSize);
    map(sz);
  }
  // >>>>
  void close() {
    if (fd != -1) {
      ::close(fd);
    }
    fd = -1;
  }

  void resizeCapacity(size_t arraysize) {
    if (fd == -1) {
      throw Exception("Not ready");
    }
    // <<<<
    if (initialSize != header->size) {
      remap(header->size);
    }
    // >>>>
    Header h;
    h = *header;
    size_t s = h.size;
    h.updateSize(arraysize);
    if (h.size == s) {
      return;
    }

    if (fd != -1) {
      msync(header, header->size, MS_SYNC);
      munmap(header, header->size);
      close();
    }
    if ((fd = open(file.c_str(), O_RDWR, 0666)) == -1) {
      throw Exception(strerror(errno));
    }
    if (ftruncate(fd, h.size) == -1) {
      close();
      throw Exception(strerror(errno));
    }
    if (write(fd, &h, sizeof(Header)) == -1) {
      close();
      throw Exception(strerror(errno));
    }
    map(h.size);
    if (arraysize < header->validArraySize) {
      header->validArraySize = arraysize;
    }
  }

 protected:
  Header        *header;
  int           fd;
  T             *array;
  std::string   file;
  // <<<<
  size_t        initialSize;
  size_t        reservedSize;
  // >>>>

};

前：スタックデータベース

次：固定長データベース

スタックデータベース

固定長配列データベースができたなら、やはり、可変長配列データベースへと行きたいところですが、これはさすがに大変そうですね。その前に幾つか手順を踏む必要があります。

可変長配列データベースは固定長配列データベース上に実装することにします。一つの可変長データは複数の固定長データに分割して固定長配列に保存します。したがって、配列の添え字を気にせずに、固定長のデータを自由に出し入れできるデータベースが必要になります。

つまり、固定長データを挿入するとIDが返ってくるデータリポジトリといえるようなものを作ると可変長配列データベースが実装しやすくなります。そこで必要になるのが固定長データのブロックを管理する機能です。ブロックを管理するといっても削除されたブロックがどれかを管理すれば十分なので、削除されたブロックのIDをスタックに入れて管理することにします。

ということでスタックデータベース（こんな言葉は聞いたことないですが…）を作成しました。STLと同様の使い方になっていますので、使い方の説明は省略します。

template <class T> class Stack : public Array<T>  {
public:
  Stack(const std::string &f):Array<T>(f) {}
  Stack() {}

  void initialize(const std::string &f) {
    Array<T>::initialize(f);
  }

  void push(T &t) {
    set(Array<T>::getSize(), t);
  }
  T front() {
    if (Array<T>::getSize() <= 0) {
      throw Exception("No data");
    }
    return Array<T>::at(Array<T>::getSize() - 1);
  }
  void pop() {
    Array<T>::resize(Array<T>::getSize() - 1);
  }
};

前：固定長配列データベース

次：固定長配列データベースの改良

固定長配列データベース

ちょっとしたデータを管理したいけどが、DBMSなどを使うほどでもない、かといってデータをいちいちファイルに書き出したり読み込んだりするのは面倒だということが、たまにあります。

では、そんな時に簡単に使えるものを試しに作ってみようということでSTLのvectorのようにデータを扱えて、自動でファイルへの読み書きを行ってくれるテンプレートを作成しました。固定長配列データベースとでも言えるかと思います。

固定長といっても要素の数はもちろん可変長です。この固定長は各要素が固定のサイズであることを意味しています。なんだ当たり前じゃないかと思われるかと思いますが、各要素が可変長サイズの配列データーベースも実装するつもりなので、可変長配列データベースと区別するために固定長配列データーベースとします。

いろいろ調べるとmmapを使えば後々他のプロセスとの共有も簡単そうなので、mmapを使って実装しています。

動作環境はCentOS4です。環境によってはうまく動作しないかもしれませんが、ご勘弁下さい。

シンプルですが、そこそこきちんと動くようです。

#include <fcntl.h>
#include <errno.h>
#include <sys/mman.h>
#include <assert.h>

#include <iostream>
#include <exception>

class Exception : public std::exception {
public:
  Exception(const std::string &msg)
  {
    message = msg;
  }

  virtual ~Exception() throw() {}

  const char *what() {
    return message.c_str();
  }

  std::string message;
};

template <class T> class Array {
public:
  class Header {
  public:
    void initialize() {
      headerSize        = 256;
      pageSize          = sysconf(_SC_PAGE_SIZE);
      elementSize       = sizeof(T);
      arraySize         = 0;
      validArraySize    = 0;
      size     = headerSize;
    }

    size_t updateSize(size_t arraysize) {
      size = ((headerSize + arraysize * elementSize - 1) / pageSize + 1) * pageSize;
      arraySize = (size - headerSize) / elementSize;
      return size;
    }

    size_t headerSize;
    size_t pageSize;            // page size
    size_t elementSize;         // size of an element
    size_t arraySize;           // # of elements
    size_t validArraySize;      // # of valid elements
    size_t size;                // total size
  };

  Array():fd(-1) {}

  Array(const std::string &f):fd(-1) {
    initialize(f);
  }

  ~Array() {
    if (fd != -1) {
      msync(header, header->size, MS_SYNC);
      munmap(header, header->size);
      close();
    }
  }

  void initialize(const std::string &f) {
    file = f;
    if ((fd = open(file.c_str(), O_RDWR, 0666)) == -1) {
      if (errno == ENOENT) {
        create(file);
      } else {
        throw Exception(strerror(errno));
      }
    }
    struct stat fs;
    fstat(fd, &fs);
    map(fs.st_size);
  }

  void map(size_t sz) {
    if (fd == -1) {
      throw Exception("Not ready");
    }
    header = (Header*)mmap(0, sz, PROT_READ|PROT_WRITE,MAP_SHARED, fd, 0);
    if ((long long)header == -1){
      close();
      throw Exception(strerror(errno));
    }
    array = (T*)((unsigned char*)header + header->headerSize);
    if (sz != header->size) {
      close();
      throw Exception("Sizes are inconsistency");
    }
  }

  void resize(size_t arraysize) {
    resizeCapacity(arraysize);
    if (arraysize != header->validArraySize) {
      header->validArraySize = arraysize;
    }
  }

  T &at(size_t idx) {
    if (fd == -1) {
      throw Exception("Not ready");
    }
    if (idx >= header->validArraySize) {
      throw Exception("Invalid element");
    }
    return array[idx];
  }

  T &set(size_t idx, T& v) {
    if (idx >= header->arraySize) {
      resizeCapacity(idx + 1);
    }
    array[idx] = v;
    if (idx >= header->validArraySize) {
      header->validArraySize = idx + 1;
    }
    return array[idx];
  }

  size_t getSize() { return header->validArraySize; }

protected:
  void
  create(const std::string &file) {
    if ((fd = open(file.c_str(), O_RDWR|O_CREAT, 0666)) == -1) {
      throw Exception(strerror(errno));
    }
    Header h;
    h.initialize();

    if (write(fd, &h, sizeof(Header)) == -1) {
      close();
      throw Exception(strerror(errno));
    }

    unsigned char c = 0;
    for (size_t i = 0; i < h.headerSize - sizeof(Header); i++) {
      if (write(fd, &c, sizeof(c)) == -1) {
         close();
         throw Exception(strerror(errno));
      }
    }
  }

  void close() {
    if (fd != -1) {
      ::close(fd);
    }
    fd = -1;
  }

  void resizeCapacity(size_t arraysize) {
    if (fd == -1) {
      throw Exception("Not ready");
    }

    Header h;
    h = *header;
    size_t s = h.size;
    h.updateSize(arraysize);
    if (h.size == s) {
      return;
    }

    if (fd != -1) {
      msync(header, header->size, MS_SYNC);
      munmap(header, header->size);
      close();
    }
    if ((fd = open(file.c_str(), O_RDWR, 0666)) == -1) {
      throw Exception(strerror(errno));
    }
    if (ftruncate(fd, h.size) == -1) {
      close();
      throw Exception(strerror(errno));
    }
    if (write(fd, &h, sizeof(Header)) == -1) {
      close();
      throw Exception(strerror(errno));
    }
    map(h.size);
    if (arraysize < header->validArraySize) {
      header->validArraySize = arraysize;
    }
  }

 protected:
  Header    *header;
  int       fd;
  T         *array;
  std::string  file;

};

使い方は簡単です。コンストラクタでファイル名を指定すれば配列用のファイルが生成されます。既に作成したファイルがあれば、それをmapします。配列のサイズは勝手に拡張されますが、明示的にresizeも可能です。

簡単なサンプルプログラムは以下の通りです。単純に配列に値を入れて、入れた値を表示させているだけです。

void
array_write()
{

  Array<int> array("sample_db");

  try {
    for (int i = 0; i < 10; i++) {
      int d = i + 1;
      array.set(i, d);
    }
  } catch (Exception &e) {
    std::cerr << e.what() << std::endl;
  }

}

void
array_read()
{

  Array<int> array("sample_db");

  try {
    for (int i = 0; i < 10; i++) {
      int d = i + 1;
      std::cerr << "array[" << i << "]=" << array.at(i) << std::endl;
    }
  } catch (Exception &e) {
    std::cerr << e.what() << std::endl;
  }

}

int
main()
{
  array_write();
  array_read();
}

この例ではintですが、もちろんクラスも配列にできます。ただし、クラスのメモリ領域内のものしか保存されませんので、ご注意下さい。

細かなところは荒削りなので、興味のある方は適当に修正して使ってください。

次：スタックデータベース

はじめに

興味のあることをちょっとだけ掘り下げて、人に役立ちそうな情報を書いていく予定です。

主にプログラム関係ですが、それ以外もいろいろ書きたいとは思っています。

でも、いつまで続くことやら…