PFS+ISAM

[iztok-savnik]

Here is the starting point of the design of Page File Server and ISAM index.

---

Page file server

• Page file is a sequence of pages
  • Page is a basic unit of processing
  • All pages have the same length
  • A page identifier points to the beginning of the given page (offset of a page in page file)
  • The page FS does not know anything about the contents of pages
• Architecture of Page file server
  • Page server is an Erlang process
  • Page file server accepts requests from many (TP-AM) processes
  • Requests are placed in a queue and served one by one
  • Buffer manager is serving as a cache
    • Page are read into buffer pool
    • Some page replacement strategy should be used
• Page server interface
  • N-th page is accessed by reading|writting from|to the position n*page-size in db file
  • read command reads a sequence of pages in the internal buffer
  • write command writes a sequence of pages to the disk.

ISAM index

• ISAM index is a key/value store
  • Keys/Values are stored in pages
    • Keys are composed of instances of K\subseteq{S,P,O}
    • Values can be either complete triples or references to triples
  • Index pages are storing keys/pointers to subtrees
  • Data pages store entered keys/values
• Architecture of ISAM index
  • ISAM index is an Erlang module and process
  • ISAM index is stored in a file of pages
    • ISAM index module includes Page FS module
  • At this level it would make sense to implement cursors (I suggest we discuss this)
  • We can have dense/sparse indexes... this should be illuminated
• ISAM index interface
  • Open access for a given key with the comparison operation equal|eq-more-then|eq-less-then
  • read results of the operation (possible with a cursor operations)
  • Close access to ISAM index
  • Batch creation of ISAM index from complete data

[iztok-savnik]

Some questions that come to mind.

• How to represent pairs <key,value> in the leaves of ISAM?
  • We have fixed size "key".
  • We have a fixed size "value".
  • The sizes of keys and values should be defined per page file.
  • These parameters should be stored in a page file header or something.
• Operation compare should be provided for an ISAM index.
  • I suggest we use, at least for now, standard compare that returns <0, 0, >0 meaning smaller-then, equals, and larger-then, respectively.
  • We should study the binary representation, how to convert binary data into a particular data type and back.
  • Functions can be passed as arguments in erlang.

[iztok-savnik]

Regarding the architecture of PFS and ISAM.

The idea about merging PFS and ISAM into one process (that I suggested and we discussed on Friday) is not OK... The original idea, i.e., the one discussed before, seems to be stable.

• PFS is a separate process as defined above.

• One ISAM process works with an open PFS process.

  • Index pages are read to ISAM process and they are processed in ISAM process.
  • The results of an ISAM index access are the leaf pages, more precisely, key/value records in leaf pages.
  • In initial version ISAM can read also the results, but it seems that the results can be sent directly to the initiator of ISAM process, i.e., the TP-AM process (triple-pattern access method).

Is that OK? Do you have a comment?

I suggest that we create also, as we have discussed, a record-based file server with sequential and direct access. Here is a sketch of Record-based file server (RFS).

• Record file is a sequence of records
  • Records are the basic units of operation
  • All records have the same length
  • Record identifier (RID) identifies a record
  • RFS does not know anything about the content of records
• Architecture of RFS
  • PFS is an Erlang process
  • Records are stored in pages
  • RID = sequential number of a record in a file. PID = RID / (num.of records per page).
• RFS interface
  • Initialization of the RFS process
  • Read N-th record
  • Write a new record to the end of file

Above specification is far from complete. In the case that we use 6 SPO indexes (implemented with key/value store ISAM index) storing complete triples in the leaves then we do not need RFS :|

[iztok-savnik]

It would make sense now if all these ideas would be gathered in a separate text that can be later used for the thesis. It can also be used as the documentation of the modules.

Are there any other problems that you see? The current design seems stable. Perhaps it can be improved later (e.g., optimization of inter-process communication) but for now, it can be a basis for the implementation.

[iztok-savnik]

I started to put together the material we gathered so far in file.