TmStorage contains methods to create, open and delete streams. When stream is created or opened, TmStorage returns a stream derived from standard .NET Stream class so it's really easy to use it.
Introduction
For some time, I wanted to write some kind of a file system that will enable storing many different types of information inside one file. I also wanted it to be a generic file system with flat structure. Later, instead of the name "file system", I decided to use the name "storage".
I've added TmStorage into NoSQL category because, although it's a file system (and can be used as such), it is also meant to serve as a base on top of which custom storages or databases can be built. By building a custom storage or database, its structure can be adapted to the structure of the data that will be stored in it. It also gets all the features already implemented in TmStorage (transactions, caching, snapshots and more in the future).
With this in mind, TmStorage was designed to:
- Store large number of data streams inside one file (millions).
TmStorage would automatically allocate space when stream length is increased and deallocate it when decreased. - Support full transactions so changing/creating/deleting one or more streams is an atomic operation.
- Reference streams with GUIDs, not by names - reason for these is mentioned later.
- Use 64bit integers internally so limitations are very high.
All points above have been fully implemented.
TmStorage contains methods to create, open and delete streams. When stream is created or opened, TmStorage returns a stream derived from standard .NET Stream class so it's really easy to use it.
Here is an example of how to save an image inside a storage stream. In storage constructor, master file and transaction-log file are specified.
Image image = Image.FromFile("c:\\image.png");
Storage storage = new Storage("c:\\images.storage", "c:\\images.storagelog");
Guid streamId = Guid.NewGuid();
storage.StartTransaction();
try
{
Stream stream = storage.CreateStream(streamId);
image.Save(stream, ImageFormat.Png);
stream.Close();
storage.CommitTransaction();
}
catch
{
storage.RollbackTransaction();
}
Open-Source Project
I made TmStorage as an open-source project with MIT license. Everyone can use it freely for all purposes (commercial or not). I would also be glad if some would join the development.
SourceForge: https://sourceforge.net/projects/tmstorage/
I've recently put it also to GitHub: https://github.com/tomazk8/TmStorage
How It Works
TmStorage uses one master file where all of the streams are stored. Master file is divided into variable-length segments where one segment can be owned by only one stream. Each stream can be composed of zero or more segments that are chained together. Segments that mark the free space are also chained in a stream called free-space stream.
Each segment has a segment metadata written at the beginning and holds the following information:
- Size of the segment (
Int64) - Location of the next segment (
null when this is the last one) (Int64) - Metadata checksum (
Int)
To prevent high fragmentation, segment size is always a multiple of block size which is fixed to 512 bytes.
Space Allocation and Deallocation
When new empty storage is created, free-space stream is created which is made up of one segment occupying all of the virtual space available in master file (264 bytes). Master file will never be as large as the free-space stream because free-space stream doesn't contain any data and it's size is just virtual.
When allocating or deallocating space for streams, only two operations can be performed on segments: split or merge. When stream is enlarged, segments from free-space stream are taken in whole or split and added to stream's segment chain.
Before: There are four segments representing free space.
After: In this space allocation, two segments where moved to the new stream while the third was split in two.
When stream is shrunk, the process is the same but only stream and free-space stream are switched.
When segments are added to segment chain, all adjacent segments are merged into bigger segment to prevent excessive segmentation.
Stream Table
Metadata of all the streams is stored inside stream table. Stream table itself is stored inside one of the streams with hard-coded stream Id and hard-coded first-segment position so it can be found when opening the storage when stream table is not yet loaded.
Stream metadata holds the following information:
- Stream Id (
GUID) - Stream length (
Int64) - Initialized stream length (
Int64) - Position of first segment in chain (
null when empty) (Int64) - Tag (
Int)
Stream Id is of type GUID for one very good reason. Whoever creates a new stream Id (i.e., with Guid.CreateNew()) can create it anywhere and anytime independent of TmStorage. Therefore, you can be sure that stream Id is unique even if is was created long before it is used. If Stream Id would be integer, some kind of a Stream Id generator with stored MaxId value would be required.
Initialized length is length up to which stream contains valid data. This is used for optimization. When stream size is enlarged, newly allocated space contains random (or leftover) data because bytes are not initialized to 0. If it would be initialized, writing to stream would be performed twice, decreasing performance. Initialized length is always less or equal to stream length and is not changed when enlarging the stream but will grow when writing to it. All bytes read above initialized length (up to stream length) are automatically set to 0 without actually reading from the stream.
Tag is a place to store some custom information, i.e., type of data in the stream.
Transactions
TmStorage supports full transactions. They are implemented on a master-file level. During a transaction, on every write to the master file, TmStorage copies the about-to-be-overwritten data into transaction log file. TmStorage also notes which parts have already been backed-up so that it doesn't do this twice. Transaction log file is a separate file located next to the master file and is cleared when transaction is committed.
Transaction can be rolled back when an exception is thrown. If computer crashes during transaction, the next time the storage is opened, storage recognizes that transaction didn't complete and does a rollback.
Performance and Future Development
TmStorage is currently not meant to be used for high-performance multi-user databases but more as a data storage for various applications where performance is not crucial.
I filled TmStorage with one million streams and the performance was still superb. It still worked great when filled with three million. Stream table is fully loaded in memory so access is very fast.
One feature missing is caching layer. The idea is to cache blocks of master file in memory for faster reads. If storage is not too big, all data can be cached.
I also want to implement snapshots. The idea is to be able to make a snapshot of current storage so all changes to it are written only to the snapshot. At the end, you would choose whether to merge changes with master file or to discard them. This is very useful when i.e., testing a software that writes to storage so you don't have to make a full backup of the storage master file every time when starting the test.
Possible Usage Examples
With TmStorage, anyone can create their custom or specialized storage with custom data structure or simply use it as it is.
Here are a few of examples of storages/databases built on top of TmStorage:
Hierarchical File System
Table of items inside one folder would be stored in a stream where each folder item would point to a stream holding subfolder table and each file item would point to a stream storing file data. Only the Id of the stream holding root items would be hard-coded while others would be generated. Each item in table would also store file/folder name, creation date and more.
Document Management Database
Application which handles scanned documents would, for each scanned document, first store a document metadata and then stores different information about the document in various streams referenced from the metadata. Metadata would store the date when image is scanned and i.e., references to these streams:
- Stream holding the scanned image (or many streams if document has many pages)
- Stream holding OCR-ed image (i.e., for full-text search)
- Stream(s) holding translation of a document for one or more languages
- Stream holding a document, i.e., Word document, PDF or spreadsheet (instead of scanned image)
- Stream holding metadata about the history of changes or older versions
Database would also contain one or more streams holding indexed data for fast retrieval.
Database could use two TmStorages, one for current data and one for archived data located on another drive or computer.
Message Queue
Each message would be stored in one stream along with a metadata specifying Id of the stream where the next message is stored (or null if it's last one). Messages would therefore construct a linked list.
File Package
If you need to create a package with files for i.e. application deployment, TmStorage can be used like a zip file.
If your application uses lots of files (images, sounds, textures for games...) and you don't want to have huge number of files in the installation folder, all files can be accessed directly from TmStorage without the need of extracting a file to a temporary folder first.
History
- 21st November, 2014: Initial version
