Well, first let me confess that inSync v3.1 took much more time than we planned.
We had initially planned to release inSync by July 09 and Phoenix public beta by Sep 09.
In Short -
We are working on a new storage engine codename Blackbird (based on the SR-71 legend). The new engine will use application specific deduplication technology to improve performance and bandwidth/storage savings.
Initially planned for inSync v3.1 and Phoenix v1.0 , this now will be available in next major releases.
The longer version -
For the past two years, we have been doing experiments on various different algorithms for global source based data deduplication. While releasing inSync v2.0 we finalized on chunk based or variable-block based data deduplication, because of the simple fact that it was tough to find similar data blocks at natural block boundaries across different users. We also worked on the performance which gradually improved over time.
While the approach was reasonably accurate, there was a scope of significant improvement. We realized that 90% of the backup data on customer PCs comes from the documents and PST files, hence something totally focussed on PST files can dramatically improve the deduplication performance.
Also, while working on Phoenix, we came across a bigger challenge of finding duplicates across different data sources within the enterprise. We soon realized that simple block based approach will not take us too far. We also realized that most of the vendors use fixed and variable block/chunk based hashing techniques. This works well for them, because they have been treating backups as “byte streams”, and the only way to remove duplicates is fixed or variable size data deduplication.
Looking at various data types and possible ways improve, we could clearly see two fundamental changes in our approach which could bring paradigm shift in data deduplication -
- For accuracy - Application aware data deduplication
- For performance - Hierarchical block based deduplication
Application aware deduplication, can actually pin point duplicates across PST file attachments and normal office documents.
On the PC side, majority of the data is office documents and Email files. This makes it simpler to introduce the new approach, but still a lot of work needs to be done to productise it. For Phoenix, the problem is much bigger and would take some more time to solve.
The new engine should be ready soon. It would be shipped first in inSync v4.0 early next year and then in Phoenix v2.0 . In the next few posts, I will try and get some benchmark data.
November 9th, 2009
This topic has been on my plate for some time now. It’s interesting to see how databases have come a long way and have clearly out-shadowed file-systems for storing structured or unstructured information.
Technically, both of them support the basic features necessary for data access. For example both of them ensure -
- Data is managed to ensure its integrity and quality
- Allow shared access by a community of users
- Use of well defined schema for data-access
- Support a query language
But, file-systems seriously lack some of the critical features necessary for managing data. Lets take a look at some of these feature.
Transaction support
Atomic transactions guarantee complete failure or success of an operation. This is especially needed when there is concurrent access to same data-set. This is one of the basic features provided by all databases.
But, most file-systems don’t have this features. Only the lesser known file-systems - Transactional NTFS(TxF), Sun ZFS, Veritas VxFS support this feature. Most of the popular opensource file-systems (including ext3, xfs, reiserfs) are not even POSIX compliant.
Fast Indexing
Databases allow indexing based on any attribute or data-property (i.e. SQL columns). This helps fast retrieval of data, based on the indexed attribute. This functionality is not offered by most file-systems i.e. you can’t quickly access “all files created after 2PM today”.
The desktop search tools like Google desktop or MAC spotlight offer this functionality. But for this, they have to scan and index the complete file-system and store the information in a internal relational-database.
Snapshots
Snapshot is a point-in-time copy/view of the data. Snapshots are needed for backup applications, which need consistent point-in-time copies of data.
The transactional and journaling capabilities enable most of the databases to offer snapshots without shopping access to the data. Most file-systems however, don’t provide this feature (ZFS and VxFS being only exceptions). The backup softwares have to either depend on running application or underlying storage for snapshots.
Clustering
Advanced databases like Oracle (and now MySQL) also offer clustering capabilities. The “g” in “Oracle 11g” actually stands for “grid” or clustering capability. MySQL offers shared-nothing clusters using synchronous replication. This helps the databases scale up and support larger & more-fault tolerant production environments.
File systems still don’t support this option :( The only exceptions are Veritas CFS and GFS (Open Source).
Replication
Replication is commodity with databases and form the basis for disaster-recovery plans. File-systems still have to evolve to handle it.
Relational View of Data
File systems store files and other objects only as a stream of bytes, and have little or no information about the data stored in the files. Such file systems also provide only a single way of organizing the files, namely via directories and file names. The associated attributes are also limited in number e.g. - type, size, author, creation time etc. This does not help in managing related data, as disparate items do not have any relationships defined.
Databases on the other hand offer easy means to relate stored data. It also offers a flexible query language (SQL) to retrieve the data. For example, it is possible to query a database for “contacts of all persons who live in Acapulco and sent emails yesterday”, but impossible in case of a file system.
File-systems need to evolve and provide capabilities to relate different data-sets. This will help the application writers to make use of native file-system capabilities to relate data. A good effort in this direction was Microsoft WinFS.
Conclusion
The only disadvantage with using the databases as primary storage option, seems to be the additional cost associated. But, I see no reason why file-systems in future will borrow features from databases.
Disclosure
Druvaa inSync uses a proprietary file-system to store and index the backed up data. The meta-data for the file-system is stored in an embedded PostgreSQL database. The database driven model was chosen to store additional identifiers withe each block - size, hash and time. This helps the filesystem to -
- Divide files into variable sized blocks
- Data deduplication - Store single copy of duplicate blocks
- Temporal File-system - Store time information with each block. This enables faster time-based restores.
January 25th, 2009
“Data deduplication is inarguably one of the most new important technologies in storage for the past decade” says Gartner. So let’s take a detailed look at what it actually means.
Definition
Data deduplication or Single Instancing essentially refers to the elimination of redundant data. In the deduplication process, duplicate data is deleted, leaving only one copy (single instance) of the data to be stored. However, indexing of all data is still retained should that data ever be required.
Example
A typical email system might contain 100 instances of the same 1 MB file attachment. If the email platform is backed up or archived, all 100 instances are saved, requiring 100 MB storage space. With data deduplication, only one instance of the attachment is actually stored; each subsequent instance is just referenced back to the one saved copy reducing storage and bandwidth demand to only 1 MB.
Technological Classification
The practical benefits of this technology depend upon various factors like –
- Point of Application - Source Vs Target
- Time of Application - Inline vs Post-Process
- Granularity - File vs Sub-File level
- Algorithm - Fixed size blocks Vs Variable length data segments
A simple relation between these factors can be explained using the diagram below -
Target Vs Source based Deduplication
Target based deduplication acts on the target data storage media. In this case the client is unmodified and not aware of any deduplication. The deduplication engine can embedded in the hardware array, which can be used as NAS/SAN device with deduplication capabilities. Alternatively it can also be offered as an independent software or hardware appliance which acts as intermediary between backup server and storage arrays. In both cases it improves only the storage utilization.
On the contrary Source based deduplication acts on the data at the source before it’s moved. A deduplication aware backup agent is installed on the client which backs up only unique data. The result is improved bandwidth and storage utilization. But, this imposes additional computational load on the backup client.
Inline Vs Post-process Deduplication
In target based deduplication, the deduplication engine can either process data for duplicates in real time (i.e. as and when its send to target) or after its been stored in the target storage.
The former is called inline deduplication. The obvious advantages are -
- Increase in overall efficiency as data is only passed and processed once
- The processed data is instantaneously available for post storage processes like recovery and replication reducing the RPO and RTO window.
the disadvantages are -
- Decrease in write throughput
- Extent of deduplication is less - Only fixed-length block deduplication approach can be use
The inline deduplication only processed incoming raw blocks and does not have any knowledge of the files or file-structure. This forces it to use the fixed-length block approach (discussed in details later).
The post-process deduplication asynchronously acts on the stored data. And has an exact opposite effect on advantages and disadvantages of the inline deduplication listed above.
File vs Sub-file Level Deduplication
The duplicate removal algorithm can be applied on full file or sub-file levels. Full file level duplicates can be easily eliminated by calculating single checksum of the complete file data and comparing it against existing checksums of already backed up files. It’s simple and fast, but the extent of deduplication is very less, as it does not address the problem of duplicate content found inside different files or data-sets (e.g. emails).
The sub-file level deduplication technique breaks the file into smaller fixed or variable size blocks, and then uses standard hash based algorithm to find similar blocks.
Fixed-Length Blocks v/s Variable-Length Data Segments
Fixed-length block approach, as the name suggests, divides the files into fixed size length blocks and uses simple checksum (MD5/SHA etc.) based approach to find duplicates. Although it’s possible to look for repeated blocks, the approach provides very limited effectiveness. The reason is that the primary opportunity for data reduction is in finding duplicate blocks in two transmitted datasets that are made up mostly - but not completely - of the same data segments.
For example, similar data blocks may be present at different offsets in two different datasets. In other words the block boundary of similar data may be different. This is very common when some bytes are inserted in a file, and when the changed file processes again and divides into fixed-length blocks, all blocks appear to have changed.
Therefore, two datasets with a small amount of difference are likely to have very few identical fixed length blocks.
Variable-Length Data Segment technology divides the data stream into variable length data segments using a methodology that can find the same block boundaries in different locations and contexts. This allows the boundaries to “float” within the data stream so that changes in one part of the dataset have little or no impact on the boundaries in other locations of the dataset.
ROI Benefits
Each organization has a capacity to generate data. The extent of savings depends upon – but not directly proportional to – the number of applications or end users generating data. Overall the deduplication savings depend upon following parameters –
- No. of applications or end users generating data
- Total data
- Daily change in data
- Type of data (emails/ documents/ media etc.)
- Backup policy (weekly-full – daily-incremental or daily-full)
- Retention period (90 days, 1 year etc.)
- Deduplication technology in place
The actual benefits of deduplication are realized once the same dataset is processed multiple times over a span of time for weekly/daily backups. This is especially true for variable length data segment technology which has a much better capability for dealing with arbitrary byte insertions.
Numbers
The dedupication ratio increases everytime to pass the same complete data-set through the deduplication engine.
If compared against daily full backups, which I think is not widely used today, the ratios are close to 1:300. Most if the venders use this as a marketing jargon to attract customers, even though none of their customers could be doing daily full-backup 
If compared against modern day incremental backups, our customer statistics show that, the results are between 1:4 to 1:50 for source based deduplication.
January 9th, 2009
