Feb 152014
 

In the previous post we dived into Compression and Deduplication in ZFS. Here we’ll look at Deduplication in practice based on my experience.

To Dedup or Not to Dedup

Compression almost always offers a win-win situation. The overhead of compression is contained (not storage-wide) and except where there is heavy read/modify/write, it will not have unjustified overhead. It’s only when we have heavy writes on compressed datasets that we need to benchmark and decide which compression algorithm we should use, if any.

Deduplication is more demanding and a weightier decision to make. When there is no benefit from deduplication, the overhead will bring the system performance to a grinding halt. It is best to have a good idea of the data to be stored and do some research before enabling dedup by default (i.e. on the root). When the benefit from deduplication is minimal, the overhead will not only be in terms of higher memory usage, lower performance, but the DDT will be using disk space in the dozens, if not hundreds, of GBs. This means that there is a minimum dedup gain below which the overhead will simply negate the benefit, even if our hardware is powerful enough.

Regardless on the data, there are four scenarios that I can think of where deduplication makes sense. These are when:

    1. Duplicates are between multiple users.
    2. Duplicates are between multiple datasets.
    3. Duplicates are spread over millions of small files.
    4. Need copy-on-write functionality.

To see why the above make sense, let’s take a hypothetical case where we have one user and one dataset with thousands of GB-sized files. If we have duplicate files in this case, we can simply find them and hardlink duplicates. It should be clear that this will work perfectly, and it’s practical to frequently rediscover duplicates and hardlink them, except for the above four cases. That is, hardlinks don’t work across users (I’ll leave aside the issue of privacy and consider what happens when one user decides to modify a hardlinked file and inadvertently ends up modifying the other user’s version as well, since they are hardlinked,) they don’t work across datasets (i.e. filesystems) by definition (because inodes are only meaningful in a single filesystem) and hardlinking will be more complicated and a maintenance issue if our duplicate data is mostly a large number of small files. Finally, hardlinks simply means the filesystem is pointing multiple files to the same data. Modifying one will modify the other, which might not be desirable even in a single-user scenario, rather than create a new copy. ZFS dedup feature works using copy-on-write, so modifying a deduplicated block will force ZFS to copy it first before writing the modified data, thereby preserving the other previously-duplicate files to the one being modified.

If after ingesting data in a dedup=on dataset we decide to remove deduplication, we will need to create another dataset with dedup=off, and copy our data over (one can also use send/receive, which are beyond the scope of this write up see below). If you are in a situation where you have dedup enabled (at least on some of the datasets) but aren’t sure whether or not performance is suffering, there are a few tools I can suggest.

Monitoring Tools

zpool iostat [interval [count]] works very much like iostat except it is on the ZFS-pool level. I use zpool iostat 10 to see the IOPS and bandwidth on the pool averaged at 10 second periods.

Unfortunately, zpool iostat doesn’t include cache hits and misses, which are very important if we are interested in DDT thrashing. Fortunately, there is a python script (direct link) in the ZFS on Linux sources that does that.

arcstat.py [interval] dumps hit and miss statistics as well as ARC size and more (the columns are customizable, but the default should be sufficient). For those interested, arcstat uses raw numbers with some fields computed on the fly directly from /proc/spl/kstat/zfs/arcstats, which can be read and parsed as one wishes. Try cat /proc/spl/kstat/zfs/arcstats for example.

Here is a sample from my zpool showing the output of both tools at the same time while reading 95,000 files with an average of 240KB each. The dataset is dedup=verify and has a large percentage of duplicates in it:

               capacity     operations    bandwidth
pool        alloc   free   read  write   read  write
----------  -----  -----  -----  -----  -----  -----    ¦        time  read  miss  miss%  dmis  dm%  pmis  pm%  mmis  mm%  arcsz     c
tank        8.58T  7.67T    239     40  28.9M   101K    ¦    15:05:27  1.1K   238     21    14    1   224   97     7    2   3.0G  3.0G
tank        8.58T  7.67T    240     41  28.6M   103K    ¦    15:05:37  1.1K   236     21    16    1   220   98     8    3   3.0G  3.0G
tank        8.58T  7.67T    230     36  27.4M  91.7K    ¦    15:05:47  1.1K   229     21    17    2   212   97     8    3   3.0G  3.0G
tank        8.58T  7.67T    239     41  28.7M   102K    ¦    15:05:57  1.1K   234     20    15    1   218  100     7    3   3.0G  3.0G
tank        8.58T  7.67T    205     39  24.5M   101K    ¦    15:06:07  1.0K   215     21    17    2   198   99     5    2   3.0G  3.0G
tank        8.58T  7.67T    266     37  32.3M  97.3K    ¦    15:06:17  1.2K   255     21    15    1   240  100     5    1   3.0G  3.0G
tank        8.58T  7.67T    261     40  31.6M   104K    ¦    15:06:27  1.6K   272     16    13    0   259   99     7    1   3.0G  3.0G
tank        8.58T  7.67T    224     52  26.7M   239K    ¦    15:06:37  1.6K   229     14    16    1   213   96     8    1   3.0G  3.0G
tank        8.58T  7.67T    191     37  22.7M  93.0K    ¦    15:06:47  1.4K   200     14    17    1   183  100     8    2   3.0G  3.0G
tank        8.58T  7.67T    182     40  21.6M   103K    ¦    15:06:57  1.2K   180     15    15    1   165  100     7    2   3.0G  3.0G
tank        8.58T  7.67T    237     41  28.4M  98.9K    ¦    15:07:07  1.5K   241     15    13    1   227  100     7    1   3.0G  3.0G
tank        8.58T  7.67T    187     38  22.1M  96.1K    ¦    15:07:17  1.2K   183     14    16    1   166   99     7    2   3.0G  3.0G
tank        8.58T  7.67T    207     39  24.5M  99.6K    ¦    15:07:27  1.3K   201     15    18    1   182  100     9    2   3.0G  3.0G
tank        8.58T  7.67T    183     47  21.5M   227K    ¦    15:07:37  1.3K   199     15    18    1   181  100     9    2   3.0G  3.0G
tank        8.58T  7.67T    197     37  23.4M  95.4K    ¦    15:07:47  1.2K   183     15    16    1   167   97     7    2   3.0G  3.0G
tank        8.58T  7.67T    212     60  25.3M   370K    ¦    15:07:57  1.4K   210     14    16    1   193  100     8    1   3.0G  3.0G
tank        8.58T  7.67T    231     39  27.5M   104K    ¦    15:08:07  1.5K   223     15    17    1   206  100     8    1   3.0G  3.0G

The columns are as follows:

       pool : The zpool name
      alloc : Allocated raw bytes
       free : Free raw bytes
 (ops) read : Average read I/O per second
(ops) write : Average write I/O per second
  (bw) read : Average read bytes per second
 (bw) write : Average write bytes per second

       time : Time
       read : Total ARC accesses per second
       miss : ARC misses per second
      miss% : ARC miss percentage
       dmis : Demand Data misses per second
        dm% : Demand Data miss percentage
       pmis : Prefetch misses per second
        pm% : Prefetch miss percentage
       mmis : Metadata misses per second
        mm% : Metadata miss percentage
      arcsz : ARC Size
          c : ARC Target Size

Of important note is the IOPS relative to the bandwidth. Specifically, if the bandwidth divided by IOPS is <128KB, it means we are reading small files, which will affect performance compared to reading large files with sequential 128KB blocks. In other words, an average 25MB/s looks poor until we take into account that it is during reading 100s of small files (<128KB each) per second. For large files the average bandwidth is typically 10x higher.

ARC reads is rather high, betraying the fact that we are accessing deduplicated data. With ~15% ARC misses, we can assume that about 15% of our reads are wasted to ARC reads. Prefetching is virtually useless here (and if this were a typical usage, we should disable prefetching altogether, but for larger file reads prefetching pays dividends handsomely).

Another very important thing we learn from the above numbers is the low data and metadata misses. This is extremely important, arguably more important than ARC misses and DDT thrashing, as having high metadata miss-rate will translate in far higher latency in statting files and virtually any file operation, however trivial, will also suffer significantly. For that, it’s best to make sure the metadata cache is large enough for our storage.

During the above run my /etc/modprobe.d/zfs.conf had the following options:
options zfs zfs_arc_max=3221225472
options zfs zfs_arc_meta_limit=1610612736

We can see that the ARC size above is exactly at the max I set and I know from experience that the default ARC Meta limit of ~900MB gives poor performance on my data. For an 8GB RAM system, 3GB ARC size and 1.5GB ARC Meta size gives the most balanced performance across my dataset.

DDT Histogram

If you already have dedup enabled at all, a very handy command that shows deduplication statistics is zdb -DD . The result is extremely useful to understand the distribution of data and DDT overhead. Here are two examples from my pool taken months apart and with very different data loads.

#zdb -DD
DDT-sha256-zap-duplicate: 3965882 entries, size 895 on disk, 144 in core
DDT-sha256-zap-unique: 35231539 entries, size 910 on disk, 120 in core

DDT histogram (aggregated over all DDTs):

bucket              allocated                       referenced
______   ______________________________   ______________________________
refcnt   blocks   LSIZE   PSIZE   DSIZE   blocks   LSIZE   PSIZE   DSIZE
------   ------   -----   -----   -----   ------   -----   -----   -----
     1    33.6M   4.18T   4.09T   4.10T    33.6M   4.18T   4.09T   4.10T
     2    3.52M    431G    409G    412G    7.98M    976G    924G    931G
     4     250K   26.0G   23.0G   23.6G    1.20M    128G    113G    116G
     8    15.5K   1.07G    943M   1001M     143K   9.69G   8.29G   8.83G
    16    1.16K   46.0M   15.9M   23.2M    23.5K    855M    321M    470M
    32      337   7.45M   2.64M   4.86M    13.7K    285M    102M    195M
    64      127   1.20M    477K   1.33M    10.1K    104M   45.9M    116M
   128       65   1.38M   85.5K    567K    11.5K    258M   14.6M    100M
   256       22    154K   26.5K    184K    7.22K   45.5M   10.2M   61.1M
   512       11    133K   5.50K   87.9K    7.71K    101M   3.85M   61.6M
    1K        3   1.50K   1.50K   24.0K    4.42K   2.21M   2.21M   35.3M
    2K        2      1K      1K   16.0K    4.27K   2.14M   2.14M   34.1M
    4K        3   1.50K   1.50K   24.0K    12.8K   6.38M   6.38M    102M
    8K        2      1K      1K   16.0K    21.6K   10.8M   10.8M    173M
   16K        1    128K     512   7.99K    20.3K   2.54G   10.2M    162M
 Total    37.4M   4.62T   4.51T   4.52T    43.1M   5.27T   5.11T   5.13T

dedup = 1.13, compress = 1.03, copies = 1.00, dedup * compress / copies = 1.16

The first two lines give us footprint information. First we get the number of entries with at least 2 references (refcnt >= 2) and the size per entry on disk and in RAM. In my case 3.96m deduplicated entries are taking 3385MB on disk and 545MB in RAM. The second line represents the same information for unique entries (entries that are not benefiting from deduplication). I had 35.2m unique entries consuming 30575MB (29.9GB) on disk and 4032MB (3.9GB) in RAM. That’s a total of 33960MB (33.2GB) on disk and 4486MB (4.4GB) in RAM in 39.2m entries, for the benefit of saving 12-13% of 5.13TB of data, or a little over 600GB.

This is not that bad, but it’s not great either, considering the footprint of the DDT, the benefit of saving 12-13% comes at a high cost. Notice that compression is independent of dedup gains and so I’m not accounting for it. Although it’s nice to see the overall gains from dedup and compression combined. We’ll get to copies in a bit.

The histogram shows the number of references per block size. For example, the second to last line shows that there are 16-32 thousand references to a single block that has a logical size (LSIZE) of 128KB taking 512 bytes physically (PSIZE,) implying that this is a highly compressed block in addition to being highly redundant on disk. I’m assuming DSIZE is the disk size, meaning the actual bytes used in the array, including parity and overhead, for this block. For this particular entry there are in fact 20.3 thousand references with a total logical size of 2.54GB but compressed they collectively weigh at only 10.2MB, however, they seem to be taking 162MB of actual disk real estate (which is great, considering without dedup and compression they’d consume 2.54GB + parity and overhead).

Powered by this valuable information, I set out to reorganize my data. The following is the result after a partial restructuring. There is certainly more room for optimization, but let’s use this snapshot for comparison.

#zdb -DD
DDT-sha256-zap-duplicate: 1382250 entries, size 2585 on disk, 417 in core
DDT-sha256-zap-unique: 11349202 entries, size 2826 on disk, 375 in core

DDT histogram (aggregated over all DDTs):

bucket              allocated                       referenced
______   ______________________________   ______________________________
refcnt   blocks   LSIZE   PSIZE   DSIZE   blocks   LSIZE   PSIZE   DSIZE
------   ------   -----   -----   -----   ------   -----   -----   -----
     1    10.8M   1.33T   1.27T   1.27T    10.8M   1.33T   1.27T   1.27T
     2    1.07M    124G    108G    110G    2.50M    292G    253G    258G
     4     206K   22.5G   11.4G   12.4G    1021K    112G   50.9G   56.1G
     8    18.7K    883M    529M    634M     177K   9.37G   5.47G   6.43G
    16    31.0K   3.80G   1.67G   1.81G     587K   71.8G   31.9G   34.5G
    32      976   93.7M   41.6M   46.6M    42.2K   4.09G   1.80G   2.02G
    64      208   13.0M   5.30M   6.45M    17.0K   1.04G    433M    531M
   128       64   2.94M   1.30M   1.73M    11.1K    487M    209M    286M
   256       20    280K     25K    168K    7.17K   81.0M   10.0M   60.7M
   512        8    132K      4K   63.9K    5.55K   80.5M   2.77M   44.4M
    1K        1     512     512   7.99K    1.05K    536K    536K   8.36M
    2K        4      2K      2K   32.0K    11.9K   5.93M   5.93M   94.8M
    4K        3   1.50K   1.50K   24.0K    19.8K   9.89M   9.89M    158M
 Total    12.1M   1.47T   1.39T   1.40T    15.2M   1.81T   1.60T   1.62T

dedup = 1.16, compress = 1.13, copies = 1.01, dedup * compress / copies = 1.29

A quick glance at the numbers and we see major differences. First and foremost the DDT contains only 12.7m entries (down from 39.2m above,) while the dedup ratio is up at 15-16% (a net gain of ~3%). Compression is way up at 13% from 3% with a slight overhead of extra copies at 1%. The extra copies showed up when I manually “dedpulicated” identical files by hard-linking them. Normally copies “are in addition to any redundancy provided by the pool, for example, mirroring or RAID-Z. The copies are stored on different disks, if possible. The space used by multiple copies is charged to the associated file and dataset, changing the used property and counting against quotas and reservations.” according to the ZFS man page, but I’m not entirely clear as why they showed when I hard linked large files and not, say, when I already had highly-redundant files which could benefit from extra redundancy in case of an unrecoverable corruption.

What really counts in the above numbers is the relative effectiveness of deduplication. That is, the higher the dedup percentage, the lower the overhead of unique blocks becomes. It’s true that I reduced the number of duplicate blocks, but that’s mostly because I either deleted duplicate entries or I hardlinked them. So they weren’t really beneficial to me. Meanwhile, I reduced the number of unique entries substantially, increasing the utility of deduplication. This means the overhead, which is now far lower than it used to be, is being utilized better than before. This gives me an overall net gain that could be quantified by the dedup * compress / copies formula, which went from 16% to 29%, which is almost double.

I still have more work to do in optimizing my data and deduplicated datasets. Ideally, we should only have dedup enabled on datasets that either gain at least 20% from deduplication (although some would put that number far higher) or the unique blocks are potential duplicate entries pending future ingestion. Unique data that is deemed to remain unique has no place in deduplicated datasets and should be moved into a separate dataset with dedup=off. Similarly, duplicate that that is best manually deduplicated by hardlinks, or duplicates deleted, should be done so to reduce undue overhead and waste.

Undeduplication

Once we decide that a dataset is not benefiting from deduplication (typically by finding duplicates across the full zpool or by doing other statistical analyses,) we can set dedup=off on the dataset. However this will not remove blocks from the DDT until and unless they are re-written. A fast and easy method is to use send and receive commands.

First, we need to either rename the dataset or create a new one with a different name (and rename after we destroy the first).

#Rename old dataset out of the way
zfs rename tank/data tank/data_old

#Take a recursive snapshot which is necessary for zfs send
zfs snapshot -r tank/data@head

#Now let's create the new dataset without dedup
zfs create -o dedup=off -o compression=gzip-9 tank/data

#And let's copy our data in its new home, which will not be included in the DDT
zfs send -R tank/data_old@head | zfs recv tank/data

#After validating everything is as we want, destroy the source
#zfs destroy -r tank/data_old

The end result of the above is to remove a dataset form the DDT.

Note that a -F on recv will force it, which will not fail if data has some data! This is useful if we need to start all over after moving some data into the new dataset. There is a -d and -e options, which are useful for recreating the tree structure of the source. These are typically needed when datasets move between pools. To see the target tree with a dry run, add -nv to recv. Note that the target dataset will be locked during the receive and will show empty using ls. The output of send can be redirected to a file or piped into gzip for backup.

Hope you found this helpful. Feel free to share your thoughts and experience in the comments.

Share
Jan 262014
 

In the previous post we looked at performance and benchmark statistics on a home NAS/HTPC with ZFS on Linux. Here we’ll take a deeper dive into some of the more interesting features of ZFS–Compression and Deduplication.


When I set out to build a NAS I aimed for the lowest cost with the best utility. My primary goal was to move all my precious (and the less-than-rare) files in a redundant storage that is accessible, manageable and low-cost, but reliable. The idea of extending it to HTPC came to me after comparing prices of commercial home/small-biz NAS solutions with the cost of the bare components. One can do so much more with a generic Linux box than a specialized black-box. However I wasn’t willing to pay a premium to turn what started out as NAS into a general purpose rig; It had to be low-profile.

ZFS offers enterprise-level features and performance at the cost of maintaining it. Never underestimate the overhead of maintenance though. The biggest issue I’ve had to face with ZFS on Linux was that of memory starvation. I had read that ZFS has less than humble memory requirements and it could always put more of it to good use. Recommendations of 1-2GB / TB of storage floats on the web. However I ended up supplying it with only 8GB for 18TB of storage to be shared with the OS and other applications. The experience is worth sharing, especially the lessons learnt, which should prove worthwhile for others with similar plans to mine. But first, we need to take a look at some of the internals of ZFS.

Compression vs Deduplication

Both compression and deduplication are designed to reduce disk space usage as much as possible. One should keep in mind that these features don’t come for free and there are caveat to be aware about. First and most important point to keep in mind before deciding which features to enable is that deduplication happens on the zpool level. The pool is at the volume management layer and dedup works on the block-level, away from any file structures. The filesystem dataset sits atop the zpool and that’s where compression works, before deduplication is done. When enabled, zfs compresses each block using the chosen compression algorithm and writes to the pool. While writing, the zpool compares the checksum of the incoming block with existing block checksums, and, if a match is found, the matching block’s reference count is incremented, the block reference ID passed back to the filesystem and no data is written to disk (expect the reference count increment in the deduplication table).

Neither dedup nor compression work retroactively. So a change in either setting will not propagate to existing data. When new data is written, or old data read/modified/written, the new settings will take effect. Due to the fact that compressed block data depends on the compression algorithm (and level,) identical blocks compressed with different compression algorithms virtually certainly will not match as identical (although their uncompressed bytes match). This is only an issue when the pool has identical duplicate data in different datasets with different compression algorithms or level. Datasets that have similar data that can benefit from deduplication will lose that opportunity if they utilize different compression settings. Changing the compression setting of a dataset should be done when one is fairly confident that the gains will outdo any loss of dedup opportunities with other datasets with a different compression setting.

Compression

The overhead of compression is very much contained and bounded in that the hit is taken for each block at the time of reading and writing to that block and that block alone. Compression will require no extra disk space beyond the compressed file bytes and the memory overhead is typically negligible and of fixed size (because the block size is also fixed). Do note that a block will be written uncompressed if after compression there is no saving of at least 12.5% (1/8th) of the block size. That is, for a 128KB block, if compression doesn’t save at least 16KB, the block will be written uncompressed. Future reads will not have any decompression overhead of course, but re-writing said block will go through the same compression cycle to decide whether or not to write the compressed version. Notice that the compression algorithm and level is stored with each block, so changing these values on the dataset does not affect existing data, but only apply to future modify and writes. Naturally when a block is written uncompressed the metadata of the block will mark it as uncompressed. This means that having uncompressible media files on a compressed dataset will only incur the overhead of compressing at ingestion time and, in virtually all cases, the uncompressed data will be written to disk, and no overhead when reading (I read the code to be sure). Where compression could make a net gain of 12.5% or more, those blocks will be written compressed and it’d only be fair to pay the penalty of decompression for them and them alone when reading.

By default, lz4 compression could be used, unless we know we will store incompressible data, such as already compressed video or audio files, that will not be write-once read-many (WORM). If files will be modified heavily, we have to make a very educated decisions (read: experiment/research before you commit). While for highly compressible data (such as source code, databases, XML dumps etc.) gzip will do much better than lz4, it will also have a much higher CPU cost, and for those who care about it, latency. On the other hand, if you use gzip, it wouldn’t matter much whether you use gzip-1 or gzip-9 (relatively speaking to lz4, that is). My preference is to default to gzip-7 for the root of the pool and either choose no compression (very rarely) or choose gzip-9 for all WORM data.

Deduplication

Unlike compression, Deduplication has to keep track of all blocks in the pool (that belong to datasets with dedup=on). The number of blocks will be at least as large as the number of files, in the rare case that each file is less than or equal to a single block size. In practice, the number of blocks will be orders of magnitude larger that the number of files. Each block will therefore have both a disk, memory and cpu overheads. All three resources will increase the more the blocks we have. On disk the dedup tables (DDT) are stored to survive reboots, which are loaded to memory to maximize the performance of finding matches when writing files, which will require more processing the more the block checksums there are to compare against. Of the three the most worrisome is the memory overhead. On disk a few extra gigabytes will not be noticeable and searching even trillions of checksums should take microseconds at worse. It’s the memory needed to hold said trillions of checksums to perform fast comparisons is the problem. It is recommended to have 1-2 GB of RAM per TB of disk for good performance. Interestingly, the more duplicate blocks in the pool, the smaller the memory requirement per entry will be. This is because the DDT stores the unique block checksums that are written to disk, which is less than or equal to the total number of blocks. So a pool that doesn’t benefit from deduplication will be wasting more resources than one that is benefiting handsomely. As such, if we do not expect a significant gain from deduplication, the overhead will not be justified and should be avoided by disabling it.

Deduplication works on the block level. It computes a checksum per block and looks up the checksums in a deduplication table (DDT) to find duplicates. The default checksum is sha256. Although sha256 is a cryptographic hash (meaning it’s designed to have great avalanche characteristics and be exceedingly difficult to synthesis,) there is still a negligible chance that two different data blocks might hash to the same value. For the paranoid, ZFS dedup supports verification by byte comparison when checksums match and before assuming the blocks to be identical (and discarding one for the other). However, and as dedup author Jeff Bonwick has pointed out, the chance that sha256 will have a collision is less than that of an undetected ECC memory error, although the actual error rate by chance is far higher than he calculates due to the birthday paradox. Because this miscalculation is parroted elsewhere, it might be worthwhile to point out why it’s wrong.

Checksums, Collision and the Birthday Paradox

Sha256 has 256 bits, and while it’s true that a single random bit flip will have a chance of 1 in 2^256 to match the same hash as another block, in reality we do not have just two hash values but millions. We are worried that a corrupted block will change the hash of that block such that it matches any other block’s hash, and of course all blocks are subject to the same possibility of corruption. To go back to the birthday paradox (which asks about the minimum number of people in a room so there’d be at least 50% chance that any two share the same birthday,) the question here isn’t about the chance that another person shares your birthday, rather that anyone shares any other’s birthday (or in this case hash-value). The chances are obviously higher than just 1 in 2^256, since we have many other blocks and any one of them is a candidate for a collision. In addition, because cryptographic hash functions (indeed, any hash function) is designed to flip on average 50% of its bits for every bit change in the input (i.e. minimum change in the input results in maximum change in the output,) whenever there is corruption, there will be more than a single bit change in the hash value. This will not affect the probability of collision, but it is an important distinction from the naive assumption. (This feature of good hash functions is called Avalanche effect.)

Considering that cryptographic hash functions are designed to fingerprint documents, a considerable research is done in this area. A particular attack on hashes which exploits the birthday paradox is called birthday attack. So for a random collision with 50% or better probability between any two 256 bit hashes, one will need to have 4 x 10^38 hash values, or 4 followed by 38 zeros. (For the interested, with 23 people there is more than 50% chance that any two will share the same birthday. A year has 365 days, which is 9-bits, and this is why it takes such a small candidates to hit 50%, compared to 256bit hashes.) This is still huge, to be sure, but orders of magnitude more likely than the miscalculated 1 in 10^77 by Bonwick. (For comparison, at about 10^31 hashes, the chances of a random collision between any two is comparable to the chances of an undetected corruption in magnetic hard drives, which have an error recovery rate of 10^-14 to 10^-15 or about a bit of error every 12-120TB of data transferred.)

The verify option is useful when used with a less secure checksum function that is much faster but will produce more collisions on average. As I’ve written in the first part of this series, Fletcher4, which has a much smaller size, is no longer enabled for deduplication purposes. And in any case using a shorter hash (such as Fletcher4) is not recommended. Unless you know what you’re doing, using weak hash functions without verify will sooner rather than later have collisions and so will corrupt your data (hence the need for verify with weak hashing). The problem with verify on weak hash functions is that you’ll have a higher number of bit-for-bit comparisons when the hashes collide. The gains of a faster hashing function vs the higher verify comparisons will probably be counter productive, or at least will diminish the performance advantage that fletcher4 and the like offers.

Personally, I’d stick with sha256+verify for deduplication and use gzip-7 or higher for compression by default. For uncompressible data with high write or modify operations I would disable compression and deduplication (unless one knows that the compressed data could be deduplicated, it most probably won’t). For highly compressible data with high write or modify operations (i.e databases or virtual machine images,) lz4 should prove a winner.

In the next part we will look at practical usage of compression and deduplication with analysis.

Share
Dec 152013
 

In the previous post I wrote about the software layer in a home NAS/HTPC with ZFS on Linux. Here we’ll take a look at the performance of the system.

6x 3TB WD REDs in case and connected (cables on opposite side).

6x 3TB WD REDs in case and connected (cables on opposite side).

I had planned to run performance tests at different stages of data ingestion. Features such as compression and deduplication are bound to have some impact on performance. Even without these features, I wasn’t sure what to expect from my hardware and RaidZ either, especially that I didn’t exactly aim for the top level hardware. I don’t even have a decent boot drive; just two cheap flash drives. The only components that I didn’t get cheapest possible were the drives (WD green or Toshiba would have been significantly cheaper).

While the performance of the hardware is mostly independent of data, ZFS is a filesystem and its performance depended on the number of files, blocks, and total data size for a given hardware.

Flash Drive Benchmarks

Performance tests on 16GB ADATA Value-Driven S102 Pro USB 3.0 Flash Drive Model AS102P-16G-RGY

Two ADATA flash drives were used to create a Raid-0 (12GB) and Raid-1 (10GB) drives.
These are raw read and write performance directly to the drives without filesystem overhead.

Read performance benchmark:

Write performance benchmark:

ZFS Benchmarks

At 24% capacity with 2.88TiB of data in 23 million block, 7% dups. RAM is 8GB.

The data size is important in evaluating deduplication performance in light of the available RAM. As previously noted, ZFS requires copious amount of RAM even without deduplication. When deduplication is enabled, performance deteriorates rapidly when RAM is not sufficient. My performance tests confirm this as you’ll see below.

All tests were run without any cpu-intensive tasks running or any I/O (beyond that of the network activity by SSH). The files I chose were compressed video files that gzip couldn’t compress any further. This exercised the worst-case scenario of gzip in terms of performance when writing.

Read Tests

Reading was done with a larger than RAM (13GB vs 8GB) file to see sustained performance and with smaller than RAM (1.5GB vs 8GB) files with variations on hot, cold and, dirty cache (i.e. the same file was read previously or not or there were written data to flush to disk at the time or reading the target file.)

Cold read, file >> RAM:

# dd if=/tank/media/movies/Amor.mkv  of=/dev/null bs=1M
13344974829 bytes (13 GB) copied, 36.5817 s, 365 MB/s

365MB/s of sustained read over 13GB is solid performance from the 5400 rpm Reds.

Cold read, file << RAM, with dirty cache:

# dd if=/tank/media/movies/Dead.Man.Walking.mkv of=/dev/null bs=1M
1467836416 bytes (1.5 GB) copied, 5.84585 s, 251 MB/s

Not bad, with all the overhead and cache misses, managed to do 251MB/s over 1.5GB.

Hot read, file << RAM, file fully cached:

# dd if=/tank/media/movies/Dead.Man.Walking.mkv of=/dev/null bs=1M
1467836416 bytes (1.5 GB) copied, 0.357955 s, 4.1 GB/s

4.1GB/s is the peak for my RAM/CPU/Bus and ZFS overhead. I couldn’t exceed it, but I can do much worse with smaller bs values (anything lower than 128KB, which is the ZFS block size, will trash the performance, even when fully reading from RAM).

Cold read, file << RAM:

# dd if=/tank/media/movies/Dead.Man.Walking.mkv of=/dev/null bs=1M
1467836416 bytes (1.5 GB) copied, 4.10563 s, 358 MB/s

~360MB/s seems to be the real disk+ZFS peak read bandwidth.

Write Tests

Disk-to-Disk copy on gzip-9 and dedup folder, file >> RAM:

# dd if=/tank/media/movies/Amor.mkv  of=/tank/data/Amor.mkv bs=1M
13344974829 bytes (13 GB) copied, 1232.93 s, 10.8 MB/s

Poor performance with disk-to-disk copying. I was expecting better performance, even though the heads have to go back and forth between reading and writing which trashes the performance. More tests to find out what’s going on. Notice the file is not compressible, but I’m compressing with gzip-9 and dedup is on, and this is decidedly a dup file!

Now, to find out a breakdown of overheads. Before every test I primed the cache by reading the file to make sure I get >4GB/s read and remove read overhead.

No Compression, Deduplication on verify (hits are byte-for-byte compared before duplication assumed):

# zfs create –o compression=off –o dedup=verify tank/dedup
# dd if=/tank/media/movies/Dead.Man.Walking.mkv of=/tank/dedup/Dead.avi bs=1M
1467836416 bytes (1.5 GB) copied, 82.6186 s, 17.8 MB/s

Very poor performance from dedup! I thought compression+reading were the killers, looks like dedup is not very swift after all.

Gzip-9 Compression, No Deduplication:

# zfs create –o compression=gzip-9 –o dedup=off tank/comp
# dd if=/tank/media/movies/Dead.Man.Walking.mkv of=/tank/comp/Dead.avi bs=1M
1467836416 bytes (1.5 GB) copied, 5.4423 s, 270 MB/s

Now that’s something else… Bravo AMD and ZFS! 270MB/s gzip-9 performance on incompressible data including ZFS writing!

No Compression, No Deduplication:

# zfs create –o compression=off –o dedup=off tank/test
# dd if=/tank/media/movies/Dead.Man.Walking.mkv of=/tank/test/Dead.avi bs=1M
1467836416 bytes (1.5 GB) copied, 3.81445 s, 385 MB/s

Faster write speeds than reading!! At least once compression and dedup are off. Why couldn’t reading hit quite the same mark?

Disk-to-Disk copy again, No Compression, No Deduplication, file >> RAM:

# dd if=/tank/media/movies/Amor.mkv  of=/tank/data/Amor.mkv bs=1M
13344974829 bytes (13 GB) copied, 74.126 s, 180 MB/s

The impact that compression and deduplication have are undeniable. Compression doesn’t nearly have such a big impact and as others have pointed out, once you move from LZ4 to GZip, you might as well use GZip-9. That seems to be wise indeed. Unless one has heavy writing (or worse, read/modify/write,) in which case LZ4 is the wiser choice.

Deduplication has a very heavy hand and it’s not an easy bargain. One must be very careful with the type of data they deal with before enabling it nilly-willy.

ZFS ARC Size Tests

ZFS needs to refer to the deduplication table (DDT) whenever it writes/updates/deletes to a deduplicated dataset. The DDT can use 320 bytes per block for every block in a dedup enabled dataset. This can add up quite rapidly, especially with small files and unique files that will never benefit form deduplication. ARC is the adaptive cache that ZFS uses for its data. The size is preconfigured to be a certain percentage of the available RAM. In addition to the ARC there is a Metadata cache, which hold the file metadata necessary for stating and enumerating the filesystem.

Here I run performance tests with different ARC sizes to see its impact on the performance. First, let’s see how many blocks we have in the DDT.

# zdb -DD tank

DDT-sha256-zap-duplicate: 3756912 entries, size 933 on disk, 150 in core
DDT-sha256-zap-unique: 31487302 entries, size 975 on disk, 157 in core

DDT histogram (aggregated over all DDTs):

bucket allocated referenced
______ ______________________________ ______________________________
refcnt blocks LSIZE PSIZE DSIZE blocks LSIZE PSIZE DSIZE
------ ------ ----- ----- ----- ------ ----- ----- -----
1 30.0M 3.74T 3.66T 3.66T 30.0M 3.74T 3.66T 3.66T
2 3.34M 414G 393G 395G 7.58M 939G 889G 895G
4 231K 25.3G 22.5G 23.0G 1.11M 125G 111G 113G
8 14.6K 1.09G 974M 1.00G 135K 9.92G 8.57G 9.04G
16 1.06K 43.2M 14.2M 21.0M 21.4K 777M 270M 407M
32 308 6.94M 2.62M 4.64M 12.4K 265M 101M 184M
64 118 1.19M 470K 1.26M 9.40K 103M 45.4M 111M
128 63 1.38M 84.5K 551K 11.2K 258M 14.4M 97.8M
256 21 154K 26K 176K 6.78K 45.3M 9.93M 57.6M
512 8 132K 4K 63.9K 5.35K 99.8M 2.67M 42.7M
1K 2 1K 1K 16.0K 3.01K 1.50M 1.50M 24.0M
2K 3 1.50K 1.50K 24.0K 8.27K 4.13M 4.13M 66.1M
4K 1 512 512 7.99K 4.21K 2.10M 2.10M 33.6M
8K 2 1K 1K 16.0K 21.6K 10.8M 10.8M 173M
16K 1 128K 512 7.99K 20.3K 2.54G 10.2M 162M
Total 33.6M 4.17T 4.07T 4.07T 39.0M 4.79T 4.64T 4.66T

dedup = 1.14, compress = 1.03, copies = 1.00, dedup * compress / copies = 1.18
# zpool list
NAME SIZE ALLOC FREE CAP DEDUP HEALTH ALTROOT
tank 16.2T 7.05T 9.20T 43% 1.14x ONLINE -

We have 7.05TiB of raw data comprising 43% of the disk space. The DDT contains about 31.5M unique blocks and 3.75M duplicated blocks (blocks with at least 2 references each.) The zfs_arc_max controls the maximum size of the ARC. I’ve seen ZFS exceed this limit on a number of occasions. Conversely, when changing this value, ZFS might not react immediately, whether by shrinking or enlarging it. I suspect there is a more complicated formula to splitting the available RAM between the ARC, ARC Meta and the file cache. This brings me to the ARC Meta, controlled by zfs_arc_meta_limit, which at first I thought was not important. The default for ARC max on my 8GB system is 3.5GB and ARC Meta limit is about 900MB. ARC Meta is useful when we traverse folders and need quick stats. ARC, on the other hand, is when we need block dedup info or to update one. In the following benchmark I’m only modifying ARC max size and leaving ARC Meta on the default.

To change the max ARC size on the fly, we use (where ’5368709120′ is the desired size):

# sh -c "echo 5368709120 > /sys/module/zfs/parameters/zfs_arc_max"

And to change it permanently:

sh -c "echo 'options zfs zfs_arc_max=5368709120' >> /etc/modprobe.d/zfs.conf"

Before every run of Bonnie++ I set the max ARC size accordingly.
I used Bonnie to Google Chart to generate these charts.
Find the full raw output from Bonnie++ below for more data-points if interested.

Raw Bonnie++ output:

zfs_arc_max = 512MB
Dedup: Verify, Compression: Gzip-9
Bonnie++
Version 1.03e ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP
S 14G 66854 80 6213 2 4446 6 84410 94 747768 80 136.7 2
------Sequential Create------ --------Random Create--------
-Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP
16 8934 90 28044 88 16285 99 8392 90 +++++ +++ 16665 99
S,14G,66854,80,6213,2,4446,6,84410,94,747768,80,136.7,2,16,8934,90,28044,88,16285,99,8392,90,+++++,+++,16665,99

No dedup, gzip-9
Version 1.03e ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP
S 14G 66260 79 163407 29 146948 39 88687 99 933563 91 268.8 4
------Sequential Create------ --------Random Create--------
-Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP
16 16774 91 +++++ +++ 19428 99 16084 99 +++++ +++ 14223 86
S,14G,66260,79,163407,29,146948,39,88687,99,933563,91,268.8,4,16,16774,91,+++++,+++,19428,99,16084,99,+++++,+++,14223,86

No dedup, no compression
Version 1.03e ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP
S 14G 63889 77 191476 34 136614 41 82009 95 396090 56 117.2 2
------Sequential Create------ --------Random Create--------
-Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP
16 14866 88 +++++ +++ 19351 99 15650 97 +++++ +++ 14215 93
S,14G,63889,77,191476,34,136614,41,82009,95,396090,56,117.2,2,16,14866,88,+++++,+++,19351,99,15650,97,+++++,+++,14215,93

zfs_arc_max = 5120MB
Dedup: off, Compression: Gzip-9
Version 1.03e ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP
S 14G 76192 94 203633 42 180248 54 88151 98 847635 82 433.3 5
------Sequential Create------ --------Random Create--------
-Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP
16 19704 99 +++++ +++ 19350 99 9040 92 +++++ +++ 15842 97
S,14G,76192,94,203633,42,180248,54,88151,98,847635,82,433.3,5,16,19704,99,+++++,+++,19350,99,9040,92,+++++,+++,15842,97

zfs_arc_max = 5120MB
Dedup: verify, Compression: Gzip-9
Version 1.03e ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP
S 14G 81563 98 5574 2 2701 4 83077 97 714039 77 143.9 2
------Sequential Create------ --------Random Create--------
-Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP
16 14758 79 +++++ +++ 13951 94 7537 89 +++++ +++ 14676 98
S,14G,81563,98,5574,2,2701,4,83077,97,714039,77,143.9,2,16,14758,79,+++++,+++,13951,94,7537,89,+++++,+++,14676,98

zfs_arc_max = 5120MB
Dedup: off, Compression: off
Version 1.03e ------Sequential Output------ --Sequential Input- --Random-
-Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks--
Machine Size K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP
S 14G 76409 97 312385 73 149409 48 83228 95 368752 55 183.5 2
------Sequential Create------ --------Random Create--------
-Create-- --Read--- -Delete-- -Create-- --Read--- -Delete--
files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP
16 10814 58 +++++ +++ 16923 99 6595 89 11372 93 3737 99
S,14G,76409,97,312385,73,149409,48,83228,95,368752,55,183.5,2,16,10814,58,+++++,+++,16923,99,6595,89,11372,93,3737,99

Conclusion

The zpool sustained raw read and write speeds are in excess of 350 MB/s. Reading reached 365MB/s while writing 385MB/s.

Cached-reads exceeded 4GB/s, which is fantastic, considering the low-end hardware. I should note here that the CPU isn’t overclocked and RAM is at 1600Mhz, not its rated 1866Mhz or higher. It’s 9-10-9cl, not exactly the fastest, but very decent.

Compression is very fast, even on incompressible data and when gzip, unlike lz4, doesn’t short-circuit and bail on incompressible data.

Deduplication overhead, on the other hand, is unbelievable! The write dropped well below 20MB/s, which is dismal. I suspect this is what happens when you have barely enough RAM for DDT (dedup table) and file cache. I must have forced some DDT reads from disk, which must be painfully slow. I strongly suspect this was the case, as when I rm-ed the 13GB file from dedup-enabled folder it took over 10minutes. This must be to find and remove dedup entries, or, in this case, to decrement the ref-count, as the file was cloned from the array. Now I really wish I got 16GB RAM.

The bigger surprise than dedup sluggishness is how fast disk-to-disk copy is. Considering that reads are around 360MB/s, I wasn’t expecting an exact halving with read and write on at the same time. But we got a solid 180MB/s read/write speed. It’s as if ZFS is so good with caching and cache-writes that the head seek overhead is well amortized. Notice this was on 13GB file, which is significantly larger than total RAM, so caching isn’t trivial here.

There is more to be said about the ARC size. It seems to have less of an impact when the DDT is already thrashing. I found that changing the ARC Meta limit I got a more noticeable improvement on the performance, but that only affects metadata. Dedup table looking and updates are still dependent on the ARC size. With my already-starving RAM, changing the ARC limit didn’t have a clear impact one way or the other. For now I’ll give 1.5GB to ARC Meta and 2.5GB to ARC. In this situation where DDT is too large for the RAM there are three solutions:

    1. Buy more RAM (I’m limited to 16GB in 2 DIMMs).
      Install L2ARC SSD (I’m out of Sata ports.)
      Reduce DDT table by removing unique entries (timely, but worthwhile.)
  • Overall, I’m happy with the performance, considering my use case doesn’t include heavy writing or copying. Dedup and compression are known to have tradeoffs and you pay for them during writes. Compression doesn’t nearly impact writes as much as one cold suspect. Perhaps with generous RAM thrown at ZFS dedup performance could be on par with compression, if not better (technically, it’s a hashtable lookup, must be better, at least on paper). Still, solid performance overall, coming from a $300 hardware and 5400 rpm rust-spinner disks.

    …but, as experience shows, that’s not the last word. There is more to learn about ZFS and its dark alleys.

    Share
    Nov 292013
     

    In the previous post I wrote about building home NAS/HTPC with ZFS on Linux. Here I’d like to talk a bit about ZFS as a RAID manager and filesystem.

    ZFS Zpool

    ZFS was originally developed for Solaris, by then Sun Microsystems. It has since been ported to Linux in two flavors: FUSE and native kernel module. Unlike the latter, the former run in userland and, owing to being in user-space, has a rather flexible configuration (in terms of setting it up and running it) than kernel modules. I have had an interesting run with custom kernel modules when I upgraded Ubuntu, which broke my zpool, that I’ll get to in a bit. I haven’t tried running ZFS with FUSE, but I’d expect it to have lower complexity. For the best performance and highest integration, I went with native kernel support.

    Of the biggest issues with kernel modules is the question of stability. One certainly doesn’t want an unstable kernel module. Doubly so if it manages our valuable data. However the ZFS on Linux project is very stable and mature. In the earlier days there were no ZFS boot loaders, so the boot drive couldn’t run ZFS. Grub2 already supports ZFS (provided ZFS module is installed correctly and loaded before it,) but I had no need for it. FUSE would do away with all of these dependencies, but I suspected it also means ZFS on boot drive wouldn’t be trivial either, if at all possible.

    As explained in the previous post, I used a two flash drives in RAID-1 with ext4 for the boot drive. However, soon after having ran the system for a couple of weeks, and filled it with most of my data, I “moved” /usr, /home and /var to the zpool. This reduces the load on the flash drives and potentially increases the performance. I say “potentially” because a good flash drive could be faster than spinning disks (at least for I/O throughput and for small files) and the fact that it doesn’t share the same disk (especially spindle disks) makes for higher parallel I/O throughput. But I was more concerned about the lifetime of the flash drives and the integrity of the data than anything. Notice that /var is heavily written to, mostly in the form of logs, while /usr and /home are very static (unless one does exceptionally high I/O in their home folder,) and it’s mostly reads. I left /bin and /lib on the flash drive along with /boot.

    Installation

    Once the hardware is assembled and we can run it (albeit only to see the BIOS,) we can proceed to creating the boot drive and installing the OS and ZFS. Here is a breakdown of what I did:

    1. Download Ubuntu Minimal: https://help.ubuntu.com/community/Installation/MinimalCD
    2. Create bootable USB flash drive using UnetBootin: http://unetbootin.sourceforge.net/
    3. Insert the USB flash drives (both bootable and target boot) and start the PC, from the bios make sure it boots from the bootable flash drive.
    4. From the Ubuntu setup choose the Expert Command-Line option and follow the steps until partitioning the drive.
    5. Partition the flash drives:
      1. Create two primary Raid partitions on each drive, identical in size on both flash drives. One will be used for Swap and the other RootFS. The latter must be marked as bootable.
      2. Create software Raid-0 for one pair of the partitions and set it for Swap.
      3. Create software Raid-1 for the other pair of the partitions and format it with ext4 (or your prefered FS,) set the mount to be / and options ‘noatime’.
      4. Full instructions for these steps (not identical though) here: http://www.youtube.com/watch?v=z84oBqOxsD0
      5. Allow degraded boot and resliver with a script. Otherwise, booting fails with a black screen that is very unhelpful.
    6. Complete the installation by doing “Install base system,” “config packages,” “select and install software,” and finally “Finish installation.”
    7. Remove the bootable USB flash drive and reboot the machine into the Raid bootable USB we just created.
    8. Optional: Update the kernel by downloading the deb files into a temp folder and executing sudo dpkg -i *.deb. See http://www.upubuntu.com/2013/09/installupgrade-to-linux-kernel-311.html for ready script and commands.
    9. Install ZFS:
      1. # apt-add-repository –yes ppa:zfs-native/stable
      2. # apt-get update
      3. # apt-get install ubuntu-zfs
    10. Optional: Move /tmp to tmpfs (ram disk):
      1. # nano /etc/fstab
      2. Append the following: tmpfs /tmp tmpfs defaults,noexec,nosuid 0 0
    11. Format the drives (repeat for all):
      1. # parted –align=opt /dev/sda
      2. (parted) mklabel gpt
      3. (parted) mkpart primary 2048s 100%
    12. Find the device names/labels by ID: # ls -al /dev/disk/by-id
    13. Create the zpool with 4096b sectors:
      # zpool create -o ashift=12 tank raidz2 scsi-SATA_WDC_WD30EFRX-68_WD-WMC1T0000001 scsi-SATA_WDC_WD30EFRX-68_WD-WMC1T0000002 scsi-SATA_WDC_WD30EFRX-68_WD-WMC1T0000003 scsi-SATA_WDC_WD30EFRX-68_WD-WMC1T0000004 scsi-SATA_WDC_WD30EFRX-68_WD-WMC1T0000005 scsi-SATA_WDC_WD30EFRX-68_WD-WMC1T0000006
      An optional mountpoint may be specified using -m switch. Example: -m /mnt/data. The default mountpoint is the pool name in the root. In my case /tank.
    14. Optional: Enable deduplication (see notes below): # set dedup=on tank
    15. Optional: Enable compression by default: # set compression=gzip-7 tank
    Outside the box with the compact format keyboard and the 2x 120mm fans blowing on the drives visible.

    Outside the box with the compact format keyboard and the 2x 120mm fans blowing on the drives visible.

    Notes

    A few notes on my particular choices:

    First, I chose to have a swap drive mostly to avoid problems down the road. I didn’t know what software might one day need some extra virtual memory and didn’t want the system to be limited by RAM. Speaking of RAM, I was rather short on it and would absolutely have loved to have a good 16GB. Sadly, prices have been soaring for the past couple of years and they haven’t stopped yet. I had to do with 8GB. Also, my motherboard is limited to 16GB (a choice based on my budget). So when push comes to shove, I can’t go beyond 16GB. I also had sufficient boot disk space, so wasn’t worried that I’d ran out. Of course the swap drive is raid-0 as performance is always critical when already swapping and there are no data integrity concerns (a corruption will probably take down the process in question, but that’d threat the boot drive as well). Raid-1 is used for the boot partition, which is a mirror, meaning I had two copies of my boot data.

    Second, alignment is extremely important for both flash drives and large-format drives (a.k.a. 4096-byte sectors). Flash drives comes from factory formatted with the correct alignment. There is no need to repartition or reformat the drives, unless we need to change the filesystem or have special needs. However if we must, the trick is to create the partition at an offset of 2048 sectors (or a megabyte). This ensures that even if the internal logical block (which is the smallest unit used by the flash firmware to write data) is as large as 1024KB, it will still be correctly aligned. Notice that logical units of 512KB are not uncommon.

    Device Boot Start End Blocks Id System
    /dev/sdg1 2048 11327487 5662720 fd Linux raid autodetect
    /dev/sdg2 * 11327488 30867455 9769984 fd Linux raid autodetect

    ZFS will do the right thing if we create the pool on the root of the drive and not partitions; it will create a correctly aligned partition. I manually created partitions beforehand mostly because I wanted to see whether or not the drives were native large-format or it was emulating. However we absolutely must mark the block size to be 4096 when creating the pool, otherwise ZFS might not detect the correct sector size. Indeed, for my WD RED drives, the native sector size is advertised as 512! Marking the block size is done by ‘ashift’ and it’s given in powers of two; for 4096 ‘ashift’ is set to 12.

    Third, it is crucial to create the pool using disk IDs and not their dynamically assigned names (eg. sda, hdb, etc.). The IDs will not change as they are static, but the assigned names almost certainly will and that will cause headache. I had to deal with this problem (more later) even though, and as you can see in the command above, I had used the disk IDs when creating my zpool. Notice that using the disk ID will also save you from the common mistake of create the zpool using the partitions of the disk, rather than the root of disk (the IDs are unique to the disks but the partition and disk have each its own assigned name).

    Trouble in paradise

    I’ll fast forward to discuss a particular problem I faced that is a valuable lesson. After upgrading from Ubuntu raring (13.04) to saucy (13.10) the pool showed up as UNAVAILABLE. After the initial shock had passed I started trying to understand what had happened. Without having an idea of what the issue is, it’s near impossible to solve it. UNAVAILABLE, as scary it looks at you, doesn’t say much as to why the system couldn’t find it.

    # zpool status
    pool: tank
    state: UNAVAIL
    status: One or more devices could not be used because the label is missing or invalid.  There are insufficient replicas for the pool to continue functioning.
    action: Destroy and re-create the pool from a backup source.
    see: http://www.sun.com/msg/ZFS-8000-5E
    scan: none requested
    config:NAME        STATE     READ WRITE CKSUM
    zfs         UNAVAIL      0     0     0  insufficient replicas
    raidz2-0  UNAVAIL      0     0     0  insufficient replicas

    First thing I did was a reality check; sure enough my home was on the boot (flash) drive. Good thing it wasn’t very outdated since I had moved /usr, /home and /var to the zpool. I was glad the machine booted and I had essentially everything I needed to troubleshoot. The link in the zpool output above turned out to be less than useful.

    The real hint in the status message above is the “label is missing” part. After reading on the status and googling parts of the messages above, I wasn’t any closer to understanding the problem. I went back to my shell and listed the devices. I could see the 6 drives. Clearly they are detected. So it’s not a bad motherboard or controller issue, and possibly not a dead drive either. After all, it’s a zpool-2 (equivalent to raid-6) so unless three drives failed at once, or half my stock, “there will be sufficient replicas for the pool to continue functioning.”

    Clearly what happened was related to the upgrade. That was my biggest hint as to what triggered it. This wasn’t helpful in googling, but I had to keep it in mind. At this point I was already disappointed that the upgrade wasn’t seamless. I listed the devices and started looking for clues. I had created the pool using the device IDs, which are unique and never change from system to system. So my expectation was that it wasn’t a drive mapping issue. Alas, it was precisely a problem of drive mapping.
    The reason turned out to be that the “scsi” IDs that I’ve used to create the pool were now no longer listed under /dev/disk/by-id/. Instead, there were only the “ata” IDs. At the time of creating the pool I had both “scsi” and “ata” IDs. I chose the former for one reason or another. Turns out that the “scsi” names were removed from the /dev/disk/by-id/ listing.

    The solution turned out to be rather simple, finding it was anything but. By exporting and importing the pool the new IDs were detected and the pool reconstructed.

    # zpool export tank
    # zpool import

    After exporting, zpool status would complain that there were no pools. During importing, zfs detected the drives and mapped them correctly.

    Mounting Trouble

    At this point I was happy again, but for a short while. Turns out I wasn’t done yet. The three root directories I had moved to the zpool were not mounting anymore. I could forcefully mount them (with great difficulty as every time it’d complain it couldn’t mount,) only to find the directories were the original ones on the boot drive and not the zpool versions. The way it was supposed to work was by mounting the zpool directory to the same mountpoint as the boot drive ones, they masked the latter.

    After a rather long chase, and many reboots to see if my changes stuck or not, I found out that the process responsible for mounting is mountall. However ZFS has its own custom build, which apparently got reverted with the upgrade.
    This page has all the details about mountall and ZFS and troubleshooting. First thing I did was:

    # apt-cache policy mountall
    mountall:
    Installed: 2.48build1-zfs2
    Candidate: 2.51-zfs1
    Version table:
    2.52 0
    500 http://ca.archive.ubuntu.com/ubuntu/ saucy/main amd64 Packages
    2.51-zfs1 0
    1001 http://ppa.launchpad.net/zfs-native/stable/ubuntu/ saucy/main amd64 Packages
    *** 2.48build1-zfs2 0
    100 /var/lib/dpkg/status

    Clearly I’m using an old mountall version. How about zfs?

    # apt-cache policy ubuntu-zfs
    ubuntu-zfs:
    Installed: 7~raring
    Candidate: 7~saucy
    Version table:
    7~saucy 0
    1001 http://ppa.launchpad.net/zfs-native/stable/ubuntu/ saucy/main amd64 Packages
    *** 7~raring 0
    100 /var/lib/dpkg/status

    Good: there is a saucy version. Bad: Ubuntu upgrade didn’t get it automatically. I suspect this has to do with the fact that I had used the raring package URL. Still, one expects a bit better upgrade support when it comes to kernel modules that can lock one out of the machine.

    Upgrading ZFS to Saucy

    First, I appended the saucy PPAs to /etc/apt/sources.list:

    # ZFS
    deb http://ppa.launchpad.net/zfs-native/stable/ubuntu saucy main
    deb-src http://ppa.launchpad.net/zfs-native/stable/ubuntu saucy main

    And reinstalled ZFS to force removing the current version for the newer one.

    # apt-get install --reinstall ubuntu-zfs
    Reading package lists... Done
    Building dependency tree
    Reading state information... Done
    The following packages were automatically installed and are no longer required:
    avahi-daemon avahi-utils libavahi-core7 libdaemon0 libnss-mdns
    Use 'apt-get autoremove' to remove them.
    Suggested packages:
    zfs-auto-snapshot
    The following packages will be upgraded:
    ubuntu-zfs
    1 upgraded, 0 newly installed, 0 to remove and 348 not upgraded.
    Need to get 1,728 B of archives.
    After this operation, 0 B of additional disk space will be used.
    Get:1 http://ppa.launchpad.net/zfs-native/stable/ubuntu/ saucy/main ubuntu-zfs amd64 7~saucy [1,728 B]
    Fetched 1,728 B in 0s (6,522 B/s)
    (Reading database ... 89609 files and directories currently installed.)
    Preparing to replace ubuntu-zfs 7~raring (using .../ubuntu-zfs_7~saucy_amd64.deb) ...
    Unpacking replacement ubuntu-zfs ...
    Setting up ubuntu-zfs (7~saucy) ...

    Now, to check if all is as expected:

    # apt-cache policy ubuntu-zfs
    ubuntu-zfs:
    Installed: 7~saucy
    Candidate: 7~saucy
    Version table:
    *** 7~saucy 0
    1001 http://ppa.launchpad.net/zfs-native/stable/ubuntu/ saucy/main amd64 Packages
    100 /var/lib/dpkg/status
    
    # grep parse_zfs_list /sbin/mountall
    Binary file /sbin/mountall matches
    
    # apt-cache policy mountall
    mountall:
    Installed: 2.52
    Candidate: 2.51-zfs1
    Version table:
    *** 2.52 0
    500 http://ca.archive.ubuntu.com/ubuntu/ saucy/main amd64 Packages
    100 /var/lib/dpkg/status
    2.51-zfs1 0
    1001 http://ppa.launchpad.net/zfs-native/stable/ubuntu/ saucy/main amd64 Packages

    Rebooting was all I needed from this point on and all was finally upgraded and fully functional.

    Share
    Nov 112013
     

    I have recently built a home NAS / HTPC rig. Here is my experience from research, building it, and experimentation, for the interested in building a similar solution or to improve upon it… or just for the curious. I ended up including more details and writing longer than I first planned, but I guess you can skip over the familiar parts. I’d certainly have appreciated reading a similar review or write up while shopping and researching.

    Reds-New

    6x 3TB WD RED drives cut from the same stock.

    I have included a number of benchmarks to give actual performance numbers. But first, the goals:

    Purpose: RAID array with >= 8TiB usable space, to double as media server.

    Cost: Minimum with highest data-security.

    Performance requirements: Low write loads (backups, downloads, camera dumps etc.), many reads >= 100mbps with 2-3 clients.

    TL;DR: ZFS on Linux, powered by AMD A8 APU, 2x4GB RAM and 2x16GB flash drive in Raid-1 boot drive, backed by 6x3TB WD Red in Raidz2 (Raid-6 equivalent) for under $1400 inc. tax + shipping. The setup was the cheapest that met or exceeded my goals and is very stable and performing. AMD’s APUs are very powerful for ZFS and transcoding video, RAM is sufficient for this array size and flash drives are more than adequate for booting purposes (with the caveat of low reliability in the long-run). ZFS is a very stable and powerful FS with advanced and modern features at the cost of learning to self-serve. The build gives 10.7TiB of usable space with double-parity and transparent compression and deduplication, with ample power to transcode video, at a TCO of under $125 / TiB (~2x raw disk cost). Reads/Writes are sustained above 350MB/s with gzip-9 but without deduplication.

    This is significantly cheaper than ready NAS solutions, even when ignoring all the advantages of ZFS and generic Linux running on a modern quad core APU (compare with Atom or Celeron that often plague home NAS solution).

    Research on hardware vs. software RAID

    The largest cost of a NAS are the drives. Unless one wants to spend an arm and a leg on h/w raid cards, that is. Regardless, the drives were my first decision point. Raid-5 gives 1 disk redundancy, but due to high resilver time (rebuilding a degraded array) chances of secondary failure increase substantially during the days and sometimes weeks that resilvering takes. Drive failures aren’t random or independent occurrences, as drives from the same batch, used in the same array, tend to have very similar wear and failure reasons. As such, Raid-5 was not good enough for my purposes (high data-security). Raid-6 gives 2 drive redundancy, but requires a minimum of 5 drives to make it worthwhile. With 4 drives, 2 used for parity, Raid-6 is about as good as a mirror. Mirrors however have the disadvantage of being susceptible to failure if the 2 drives that fail happen to be the same on both sides of the mirror. Raid-6 is immune to this, but IO performance is significantly poorer than mirroring.

    Resilver time could be reduced significantly with true h/w raid cards. However they cost upwards of $300 for the cheapest and realistically $600-700 for the better ones. In addition, most give peak performance with backup battery, which costs more and will need some maintenance I expect. At this point I started comparing h/w with s/w performance. My personal experience with software data processing told me that a machine that isn’t under high-load, or is dedicated for storage, should do at least as good as, if not better than, the raid card’s on-board processor. After all, the cheapest CPUs are much more powerful, have ample fast cache and with system RAM that is in the GBs running at least at 1333 Mhz, they should beat h/w raid easily. The main advantage of h/w raid is that, with the backup battery, it can flush cached data to disk even on power failure. But this assumes that the drives still have power! For a storage box, everything is powered from the same source. So the same UPS that will keep the drives spinning will also keep the CPU and RAM pumping data long enough to flush the cache to disk. (This is true provided no new data is being written when on battery power.) The trouble with software raid is that there is no abstraction of the disks to the OS, so it’s much harder to maintain (the admin will maintain the raid in software). Also, resilvering with h/w will probably be lighter on the system as the card will handle the IO without affecting the rest of the system. But, I was to accept the performance penalty I was probably going to meet my goals even during resilvering. So I decided to go with software Raid.

    The best software solutions were the following: Linux Raid using MD, BtrFS or ZFS. The first is limited to traditional Raid-5 and Raid-6 and is straightforward to use, is bootable and well-supported, but it lacks any modern features like deduplication, compression, encryption or snapshots. BtrFS and ZFS have these features, but are more complicated to administer. Also, BtrFS is still not production-ready, unlike ZFS. So ZFS it was. Great feedback online on ZFS too. One important note on software raid is that they don’t play well with h/w raid cards. So if there is a raid controller between the drives and the system, it should be set to bypass the devices or work in JBOD mode. I’ll have more to say on ZFS in subsequent posts.

    To reach 8TiB with 2 drive redundancy I had to either go with 4x4TB drives or 5x3TB. But with ZFS (RaidZ) growing the array is impossible. The only solutions are to either add larger drives (one at a time and resilver until all have larger capacity and then the new space becomes available to the pool,) or, to create a new vdev with a new set of drives and extend the pool. While simply adding a 6th drive to the 5 existing would have been a sweet deal, when the time comes I could upgrade all drives with larger one and enjoy new drive longevity and extra disk space. But first I had to have some headroom, so it was either 5x4TB = 12TB or 6x3TB=12TB.

    Which drives? The storage market is still recovering from the Thailand flood. Prices are coming down, but they are still not great. The cheapest 3TB are very affordable, but they are 7200 rpm. Heat, noise and power bill are all high with 6 drives in an enclosure. They also come with 1 year warranty! Greens are cool and low on power requirements, but they are more expensive. The warranty isn’t much better, if at all longer. WD Red drives cost ~$20 more than the greens, come with all the advantages of 5400 rpm drive, are designed for 24/7 operation and have 3 year warranty. The only disadvantage of 5400 rpm drives is lower IOPS. But 7200 rpm doesn’t make a night-and-day difference anyway. Considering that it’s more likely than not that more than 1 drive will fail during 3 years, the $20 premium is a warranty purchase if not for the advantage of NAS drive vs. home usage. There was no 4 TB Red to consider at the time (Seagate and WD have “SE” 4TB drives that cost substantially more), although the cost per GB would be the same, it was outside my budget (~$800 for the drives) and I didn’t have immediate use for 16TB space of usable to justify the extra cost.

    Computer hardware

    Inside-Wide

    AMD’s APU with its tiny heatsink and 2x 4GB DIMMs. Noticeable is the absence of a GPU (which is on the CPU chip).

    I wanted to buy the cheapest hardware I could buy to do the job. I needed no monitor, just an enclosure with motherboard, ram and cpu. The PSU had to be solid to supply clean, stable power to the 6 drives. Rosewill’s Capstone is one of the best on the market at a very good price. The 450W version delivers continuous 450W power, not peak (which is probably in the ~600W range). I only needed ~260W continuous plus headroom for initial spin up. The case had to be big enough for the 6 drives + front fans for keeping the already cool-running drives even cooler (drive temperature is very important for data integrity and drive longevity). Motherboards with > 6 SATA ports are fewer and typically cost significantly more than with 6 or less. With 6 drives in raid, I was missing a boot drive. I searched high and low for a PCI-e SSD, but it seems there was nothing on offer for a good price, not even used ones (even the smallest ones were very expensive). Best price was for WD Blue 250GB (platter) for ~$40, but that was precious port that it would take, or cost me more in motherboard with 7 SATA ports. My solution was to use a flash drive. They are SSD and they come in all sizes and at all prices. I got two A-DATA 16GB drives for $16 each, thinking I’d keep the second one for personal use. It was after I placed the order that I thought I should RAID-1 the two drives to get better reliability.

    With ZFS, RAM is a must, especially for deduplication (if desired). It is recommended to have 1-2GB for each TB of storage. So far, I see ~145 bytes / block used on core (RAM) which for ~1.3TiB of user data in 10million blocks = 1382MB of RAM. Those 10million blocks were used by <50K files (yes, mostly documentaries and movies at this point). The per-block requirement goes down with increased duplicate blocks, so it’s important to know how much duplication there are in those 1.3TiB. In this particular case, almost none (there were <70K duplicate bocks in those 10million). So if this was all the data I had, I should disable dedup and save myself RAM and processing time. But I still have ~5TiB of data to load with all of my backups, which sure have a metric ton of dups in them. Bottom line: 1GB of ram per 1TiB of data is a good rule of thumb, but it looks like it’s a worse-case scenario here (and that would leave little room for file caching). So I’m happy to report that my 8GB ram will do OK all the way to 8TiB of user data and realistically much more as I certainly have duplicates (yes, had to go for 8GB as budget and RAM price hike of 40-45% this year alone didn’t help. Had downwards price trends continued from last year, I should have gotten 16GB for almost the same dough). Updates on RAM and performance below.

    CPU wise, nothing could beat AMD APU, which includes Radeon GPU, in terms of price/performance ratio. I could either go for dual core at $65 or quad core for $100 and upgrade L2 cache from 1MB to 4MB and better GPU core. I went for the latter to future proof video decoding and transcoding and give ZFS ample cycles for compression, checksum, hashing and deduplication. The GPU in the CPU also loves high-clock RAM. After shopping for a good pair of RAMs that work in dual-pump @ 1600Mhz, I found 1866Mhz ones for $5 more that is reported to clock to over 2000Mhz. So G.Skill wins the day yet again for me as is the case on my bigger machine with 4x8GB @ 1866 G.Skill. I should add that my first choice in both cases had been Corsair as I’ve been a fan for over a decade. But at least on my big build they failed me as they weren’t really quad-pump (certainly not at the reported frequency and G.Skill has overclocked to 2040Mhz from 1866Mhz while the CPU is at 4.6Ghz, but that the big boy, not this NAS/HTPC).

    Putting it all together

    I got the drives for $150 each and the PC cost me about $350. Two 16GB USB3.0 flash drives are partitioned for swap and rootfs. Swap is on Raid-0, ext4 on Raid-1. Even though I can boot off of ZFS, I didn’t want to install the system on the raid array, in case I need to recover it. It also simplifies things. The flash drives are for booting, really. /home, /usr, and /var should go on ZFS. I can backup everything to other machines and all I’d need is to dd the flash drive image onto a spare one to boot that machine in case of a catastrophic OS failure. Also, I keep a Linux Rescue disk on another flash drive at hand at all times. The rescue disk automatically detects MD partitions and will load mdadm and let me resilver a broken mirror. One good note is to set mdadm to boot in degraded mode and rebuild or send an email to get your attention. You probably don’t want to go in with a rescue disk and a blank screen to resilver the boot raid.

    The 6 Red drives run very quietly and are just warmer than the case metal (when ambient is ~22C), enough that they don’t feel metallic-cold at sustained writing thanks to two 120mm fans blowing on them. Besides that, no other fans are used. AMD comes with an unassuming little cooler that is less loud than my 5 year old laptop. A-Data in raid gives upwards of 80MB of sustained reads (average over full drive dd read) and drop to ~19MB of sustained write speed. Bursts can reach 280MB/s and writes a little over 100MB/s. Ubuntu Minimal 13.04 was used (which comes with Kernel 3.8) and kernel upgraded to 3.11, ZFS 28 (the latest available for Linux, Solaris is at 32, which has transparent encryption) installed and 16.2TiB of raw disk space reported after Raidz-2 zpool creation and 10.7TiB of usable space (excluding parity). The system boots faster than the monitor (a Philips 32” TV) turns on (that is to say in a few seconds). The box is connected with a Cat-5 to the router, which has a static IP assigned to it (just for my sanity).

    I experimented with ZFS for over a day just to learn to navigate it while reading on it before scratching the pool for the final build. Most info online are out of date (from 2009 when deduplication was all the rage in FS circles) so care must be taken when reading about ZFS. Checking out the code, building and browsing it certainly helps. For example, online articles will tell you Fletcher4 is the default checksum (it is not) and that one should use it if they want to improve dedup performance (instead of the much slower sha256), but the code will reveal that deduplication is defaulted and forced to sha256 checksum and that is the default even for on-disk checksums for integrity checks. Therefore, switching to Fletcher4 will only increase the risk of on-disk integrity checking, without affecting deduplication at all (Fletcher4 was removed from the dedup code when a severe bug was found due to endianness). The speed should only be worse with Fletcher4 if dedup is enabled because now both checksums must be done (without dedup Fletcher4 should improve the performance at the cost of data security as Fletcher4 is known to have a much higher collision rate than sha256).

    ZFS administration is reasonably easy and it does all the mounting transparently for you. It also has smb/nsf sharing administration built-in, as well as quotas and acl support. You can set up as many filesystems as necessary anywhere you like. Each filesystem looks like a folder with subfolders (the difference between the root of a filesystem within another or just a plain subfolder is not obvious). The advantage is that each filesystem has its own settings (which are inherited from the parent by default) and statistics (except for dedup stats, which are pool-wide). Raid performance was very good. Didn’t do extensive tests, but sustained reads reached 120MB/s. Ingesting data from 3 external drives connected over USB 2.0 is running at 100GB/hour using rsync. Each drive is writing into a different filesystem on the same zpool. One is copying RAW/Jpg/Tif images (7-8MB each) on gzip-9 and two copying compressed Video (~1-8GB) and SHN/FLAC/APE audio (~20-50MB) on gzip-7. Deduplication is enabled. Checksum is SHA256. ZFS has background integrity check and auto-rebuild of any corrupted data on disk which does have a non-negligible impact on the write rates as the Red drives could do no more than ~50 random read IOPS and ~110 random write IOPS, but for the aforementioned load each levels at ~400 IOPS per drive since most writes are sequential. These numbers fluctuate with smaller files such that the IOPS drops down to 200-250 per drive and average ingestion is 1/3rd at ~36GB/hour. This is mostly due to the FS overhead on reads and writes that force much higher seek rates vs sequential writes. CPU is doing ~15-20% user and ~50% kernel, leaving ~25% idle on each of the 4 cores at peak times and drops substantially otherwise. Reading iostats show about 30MB/s sustained reading rate from the source drives combined and writes on the Reds that average 50MB/s but spike at 90-120MB/s (this includes parity which is 50% of the data and updates of FS structure, checksums etc.)

    Back

    2x 16GB flash drives in RAID-1 as boot drive and HDMI connection.

    UPDATE: Since I wrote the above, it’s been 3 days. I now have over 2TiB of data ingested (I started fresh after the first 1.3TiB). The drives sustain at a very stable ~6000KB/s writes and anywhere between 200 and 500 IOPS (depending on how sequential they are). Typically it’s ~400 IOPS and ~5800KB/s. This translates into ~125GiB/hour (about 85GiB/hour of user data ingestion), including parity and FS overhead. Even though with gzip-9 and highly compressible data the rate or writing goes down, I now am writing from 4 threads and the drives are saturated at the aforementioned rates. So at this point I’m fairly confident the bottleneck of ingestion are the drives. Still, 85GiB/hour is decent for the price tag. I haven’t done any explicit performance tests because that was never in my goals. I’m curious to see the raw read/write performance, but this isn’t a raw Raid setup, so the filesystem overhead is always in the equation and that will be very much variable as data fills up and dedup tables grow. So the numbers wouldn’t be representative. Still, I do plan to do some tests when I ingest my data and have a real-life system with actual data.

    Regarding compression, high-compression settings affect only performance. If the data is not compressible, the original data is stored as-is and no penalty for reading it is inured (I read the code,) nor is there extra overhead in storage (incompressible data typically grows a bit when compressed). So for archival purposes the penalty is slower ingestion speed. Unless modification will happen, slow and good compression is a good compromise as it does yield a few % points compression even on mp3 and jpg files.

    With Plex Media Server installed on Linux, I could stream full HD movies over WiFi (thanks to my Asus dual-band router) transparently while ingesting data. Haven’t tried heavy transcoding (say HD to iphone) nor have I installed windows manager on Linux (AMD APUs show up in forums with Linux driver issues, but that’s mostly old and for 3D games etc.) Regarding the overhead of dedup, I can disable dedup per filesystem and remove the overhead for folders that don’t benefit anyway. So it’s very important to design the hierarchy correctly and have filesystems around file types. Worst case scenario: upgrade to 16GB RAM, which is the limit for this motherboard (I didn’t feel the need to pay an upfront premium for a 32GB max MB).

    I haven’t planned a UPS. Some are religious about availability and avoiding hard power cuts. I’m more concerned about the environmental impact of batteries than anything else. ZFS is very resilient to hard reboots, not least thanks to its journaling and data checksums and background scrubbing (validating checksums and rebuilding transparently). I had two hard recycles that recovered transparently. I also know ztest which is a dev test tool does all sorts of crazy corruptions and kills and it’s reported that in 1million tests no corruptions were found.

    Conclusion

    For perhaps anything but the smallest NAS solutions, a custom build will be cheaper and more versatile. The cost is the lack of warranties of satisfaction (responsibility is on you) and the possibility of ending up with something underpowered or worse. Maintenance might be an issue as well, but from what I gather ready NAS solutions are known to be very problematic, especially when they show any issues, like failed drive or buggy firmware or management software. ZFS proved, so far at least, to be fantastic! Especially that deduplication and compression really work well and increase the data density without compromising integrity. I also plan to make good use of snapshots, which can be configured to auto-snapshot with a preset interval, for backups and code. I only miss transparent encryption from ZFS on Linux (Solaris got it, but it hasn’t been allowed to trickle down yet.) Otherwise, I couldn’t be more satisfied (except may be with 16GB RAM, or larger drives… but I would settle for 16GB RAM for sure.)

    Parts

    PCPartPicker part list: http://pcpartpicker.com/p/1GqNv
    Price breakdown by merchant: http://pcpartpicker.com/p/1GqNv/by_merchant/
    Benchmarks: http://pcpartpicker.com/p/1GqNv/benchmarks/

    CPU: AMD A8-5600K 3.6GHz Quad-Core Processor ($99.99 @ Newegg)
    Motherboard: MSI FM2-A75MA-E35 Micro ATX FM2 Motherboard ($59.99 @ Newegg)
    Memory: G.Skill Sniper Series 8GB (2 x 4GB) DDR3-1866 Memory ($82.99 @ Newegg)
    Storage: Western Digital Red 3TB 3.5″ 5400RPM Internal Hard Drive ($134.99 @ Newegg)
    Storage: Western Digital Red 3TB 3.5″ 5400RPM Internal Hard Drive ($134.99 @ Newegg)
    Storage: Western Digital Red 3TB 3.5″ 5400RPM Internal Hard Drive ($134.99 @ Newegg)
    Storage: Western Digital Red 3TB 3.5″ 5400RPM Internal Hard Drive ($134.99 @ Newegg)
    Storage: Western Digital Red 3TB 3.5″ 5400RPM Internal Hard Drive ($134.99 @ Newegg)
    Storage: Western Digital Red 3TB 3.5″ 5400RPM Internal Hard Drive ($134.99 @ Newegg)
    Case: Cooler Master HAF 912 ATX Mid Tower Case ($59.99 @ Newegg)
    Power Supply: Rosewill Capstone 450W 80 PLUS Gold Certified ATX12V / EPS12V Power Supply ($49.99 @ Newegg)
    Other: ADATA Value-Driven S102 Pro Effortless Upgrade 16GB USB 3.0 Flash Drive (Gray) Model AS102P-16G-RGY
    Other: ADATA Value-Driven S102 Pro Effortless Upgrade 16GB USB 3.0 Flash Drive
    Total: $1147.89
    (Prices include shipping, taxes, and discounts when available.)
    (Generated by PCPartPicker 2013-09-22 12:33 EDT-0400)

    Share
    Apr 082013
     

    In part 4 we’ve replaced Parallel.ForEach with Task. This allowed us run the processes on the ThreadPool threads, but waited only in the main thread. So the worker threads were never blocked on waits. They executed the child process, then processed the output callbacks and exited promptly. All the while, the main thread is waiting for everything to finish completely. To do this, we needed to both break the Run logic from the Wait. In addition, we had to keep the Process instances alive for the callbacks to work and we can detect the end correctly.

    This worked well for us. Except for the nagging problem that we can’t use Parallel.ForEach. Or rather, if we did, even accidentally, we’d deadlock as we did before. Also, our wrapper isn’t readily reusable in other classes without explicitly separating the Run call from the Wait on separate threads as we did. Clearly this isn’t a bulletproof solution.

    It might be tempting to think that the Process class is a thin wrapper around the OS process, but in fact it’s rather complex. It does a lot for us, and we shouldn’t throw it away. It’d be great if we could avoid the problem with ThreadPool altogether. Remember the reason we’re using it was because the synchronous version deadlocked as well.

    What if we could improve the synchronous version?

    Synchronous I/O Take 2

    Recall that the deadlock happened because to read until the end of the output stream, we need to wait for the process to exit. The process, in its turn, wouldn’t exit until it has written all its output, which we’re reading. Since we’re reading only one stream at a time (either StandardOutput or StandardError,) if the buffer of the one we’re not reading gets full, we deadlock.

    The solution would be to read a little from each. This would work, except for the little problem that if we read from a stream that doesn’t have data, we’d block until it gets data. This is exactly like the situation we were trying to avoid. A deadlock will happen when the other stream’s buffer is full, so the child process will block on writing to it, while we are waiting to read from the other stream that has no data yet.

    Peek to the Rescue?

    The Process class exposes both StandardOutput or StandardError streams, which have a Peek() function that returns the next character without removing it from the buffer. It returns -1 when we have no data to read, so we postpone reading until Peek() returns > -1.

    Albeit, this won’t work. As many have pointed out, StreamReader.Peek can block! Which is ironic, considering that one would typically use it to poll the stream.

    It seems we have no more hope in the synchronous world. We have no getters to query the available data as in NetworkStream.DataAvailable and length will throw an exception as it needs a seekable stream (which we haven’t). So we’re back to the Asynchronous world.

    The Solution: No Solution!

    I was almost sure I found an answer with direct access to the StandardOutput or StandardError streams. After all, these are just wrappers around the Win32 pipes. The async I/O in .Net is really a wrapper around the native Windows async infrastructure. So, in theory, we don’t need all the layers that Process and other class add on top of the raw interfaces. Asynchronous I/O in Windows works by passing an (typically manual-reset) event object and a callback function. All we really need is the event to get triggered. Lo and behold, we are also get a wait-handle in the IAsyncResult that BeginRead of Stream returns. So we could wait on it directly, as these are triggered by the FileSystem drivers, after issuing async reads like this:

      var outAsyncRes = process.StandardOutput.BaseStream.BeginRead(outBuffer, 0, BUFFER_LEN, null, null);
      var errAsyncRes = process.StandardError.BaseStream.BeginRead(errBuffer, 0, BUFFER_LEN, null, null);
      var events = new[] { outAsyncRes.AsyncWaitHandle, errAsyncRes.AsyncWaitHandle };
      WaitHandle.WaitAny(events, waitTimeMs);

    Except, this wouldn’t work. There are two reasons why this doesn’t work, one blame goes to the OS and one to .Net.

    Async Event Not Triggered by OS

    The first issue is that Windows doesn’t always signal this even. You read that right. In fact, a comment in the FileStream code reads:

                    // Consider uncommenting this someday soon - the EventHandle 
                    // in the Overlapped struct is really useless half of the
                    // time today since the OS doesn't signal it. [...]

    True, the state of the event object is not changed if the operation finishes before the function returns.

    .Net Callback Interop via ThreadPool

    Because the event isn’t signaled in all cases, .Net needs to manually signal this event object when the Overlapped I/O callback is invoked. You’d think that would save the day. Albeit, the Overlapped I/O callback doesn’t call into managed code. The CLR handles such callbacks in a special way. In fact it knows about File I/O and .Net wrappers aren’t written in pure P/Invoke, but rather by support from the CLR as well as standard P/Invoke.

    Because the system can’t invoke managed callbacks, the solution is for the CLR to do it itself. Of course this needs to be one in a responsive fashion, and without blocking all of CLR for each callback invocation  What better solution than to queue a task on the ThreadPool that invokes the .Net callback? This callback will signal the event object we got in the IAsyncResult and, if set, it’ll call our delegate that we could pass to the BeginRead call.

    So we’re back 180 degrees to ThreadPool and the original dilemma.

    Conclusion

    The task at hand seemed simple enough. Indeed, even after 5 posts, I still feel the frustration of not finding a generic solution that is both scalable and abstract. We’ve tried simple synchronous I/O, then switched to async, only to find that our waits can’t be satisfied because they are serviced by the worker threads that we are using to wait for the reads to complete. This took us to a polling strategy, that, once again, failed because the classes we are working with do not allow us to poll without blocking. The OS could have saved the day but because we’re in the belly of .Net, we have to play with its rules and that meant the OS callbacks had to be serviced on the same worker threads we are blocking. The ThreadPool is another stubbornly designed process-wide object that doesn’t allow us to gracefully and, more importantly, thread-safely, query and modify.

    This means that we either need to explicitly use Tasks and the ProcessExecutor class we designed in the previous post or we need to roll our own internal thread pool to service the waits.

    It is very easy to overlook a cyclic dependency such as this, especially in the wake of abstraction and separation of responsibilities. The complex nature of things was the perfect setup to overlook the subtle assumptions and expectations of each part of the code: the process spawning, the I/O readers, Parallel.ForEach and ultimately, the generic and omnipresent, ThreadPool.

    The only hope for solving similar problems is to first find them. By incorrectly assuming (as I did) that any thread-safe function can be wrapped in Parallel.ForEach, and patting oneself for the marvels and simplicity of modern programming languages and for being proud of our silently-failing achievement, we only miss the opportunity to do so. By testing our code and verifying our assumptions, with skepticism and cynicism, rather than confidence and pride, do we stand a chance at finding out the sad truth, at least on the (hopefully) rare cases that we fail. Or abstraction fails, at any rate.

    I can only wonder with a grin about other similar cases in the wild and how they are running slower than their brain-dead, one-at-a-time versions.

    Share
    Apr 052013
     

    In part 3 we found out that executing Process instances in Parallel.ForEach could starve ThreadPool and cause a deadlock. In this part, we’ll attempt at solving the problem.

    What we’d like to have is a function or class that executes and reads the outputs of an external process such that it could be used concurrently, in Parallel.ForEach or with Tasks without ill-effects or without the user taking special precautions to avoid these problems.

    A Solution

    A naïve solution is to make sure there is at least one thread available in the pool when blocking on the child process and its output. In other words, the number of threads in the pool must be larger than the MaxDegreeOfParallelism of the ForEach loop. This will only work when there are no other users of the ThreadPool, then we can control these two numbers to guarantee this inequality. Even then, we might potentially need a large number of threads in the pool. But the problem is inescapable as we can’t control the complete process at all times. To make matters worse, the API for changing the number of workers in the pool are non-atomic and will always have race conditions when changing these process-wide settings.

    Broadly speaking, there are three solutions. The first is to replace Parallel.ForEach with something else. The second is to replace the Process class with our own, such that we have a more flexible design that avoid the wasting a thread to wait on the callback events. The third is to replace the ThreadPool. The last can be done by simply having a private pool for waiting on the callback events. That is, unless we can find a way to make the native Process work with Parallel.ForEach without worrying about this issue.

    Of course the best solution would be for the ThreadPool to be smarter and increase the number of threads available. This is the case when we set our wait functions to wait indefinitely. But that takes way too long (in my case about 12 seconds) before the ThreadPool realizes that no progress is being made, and it still has some tasks schedules for execution. It (correctly) assumes that there might be some interdependency between the running-but-not-progressing threads and those tasks waiting for execution.

    The third solution is overly complicated and I’d find very little reason to defend it. Thread pools are rather complicated beasts and unless we can reuse one, it’d be an overkill to develop one. The first two solution look promising, so let’s try them out.

    Replacing Parallel.ForEach

    Clearly the above workarounds aren’t bulletproof. We can easily end up in situations where we timeout, and so it’d be a Red Queen’s Race. A better solution is to avoid the root of the problem, namely, to avoid wasting ThreadPool threads to wait on the processes. This can be done if we could make the wait more efficient, by combining the waits of multiple processes together. In that case, it wouldn’t matter if we used a single ThreadPool thread, or a dedicated one.

    To that end, we need to do two things. First, we need to convert the single function into an object that we can move around, because we’ll need to reference its locals directly. Second, we need to separate the wait from all the other setup code.

    Here is a wrapper that is disposable, and wraps cleanly around Process.

            public class ProcessExecutor : IDisposable
            {
                public ProcessExecutor(string name, string path)
                {
                    _name = name;
                    _path = path;
                }
    
                public void Dispose()
                {
                    Close();
                }
    
                public string Name { get { return _name; } }
                public string StdOut { get { return _stdOut.ToString(); } }
                public string StdErr { get { return _stdErr.ToString(); } }
    
                // Returns the internal process. Used for getting exit code and other advanced usage.
                // May be proxied by getters. But for now let's trust the consumer.
                public Process Processs { get { return _process; } }
    
                public bool Run(string args)
                {
                    // Make sure we are don't have any old baggage.
                    Close();
    
                    // Fresh start.
                    _stdOut.Clear();
                    _stdErr.Clear();
                    _stdOutEvent = new ManualResetEvent(false);
                    _stdErrEvent = new ManualResetEvent(false);
    
                    _process = new Process();
                    _process.StartInfo = new ProcessStartInfo(_path)
                    {
                        Arguments = args,
                        UseShellExecute = false,
                        RedirectStandardOutput = true,
                        RedirectStandardError = true,
                        ErrorDialog = false,
                        CreateNoWindow = true,
                        WorkingDirectory = Path.GetDirectoryName(_path)
                    };
    
                    _process.OutputDataReceived += (sender, e) =>
                    {
                        _stdOut.AppendLine(e.Data);
                        if (e.Data == null)
                        {
                            var evt = _stdOutEvent;
                            if (evt != null)
                            {
                                lock (evt)
                                {
                                    evt.Set();
                                }
                            }
                        }
                    };
                    _process.ErrorDataReceived += (sender, e) =>
                    {
                        _stdErr.AppendLine(e.Data);
                        if (e.Data == null)
                        {
                            var evt = _stdErrEvent;
                            lock (evt)
                            {
                                evt.Set();
                            }
                        }
                    };
    
                    _sw = Stopwatch.StartNew();
                    _process.Start();
                    _process.BeginOutputReadLine();
                    _process.BeginErrorReadLine();
                    _process.Refresh();
                    return true;
                }
    
                public void Cancel()
                {
                    var proc = _process;
                    _process = null;
                    if (proc != null)
                    {
                        // Invalidate cached data to requery.
                        proc.Refresh();
    
                        // Cancel all pending IO ops.
                        proc.CancelErrorRead();
                        proc.CancelOutputRead();
    
                        Kill();
                    }
    
                    var outEvent = _stdOutEvent;
                    _stdOutEvent = null;
                    if (outEvent != null)
                    {
                        lock (outEvent)
                        {
                            outEvent.Close();
                            outEvent.Dispose();
                        }
                    }
    
                    var errEvent = _stdErrEvent;
                    _stdErrEvent = null;
                    if (errEvent != null)
                    {
                        lock (errEvent)
                        {
                            errEvent.Close();
                            errEvent.Dispose();
                        }
                    }
                }
    
                public void Wait()
                {
                    Wait(-1);
                }
    
                public bool Wait(int timeoutMs)
                {
                    try
                    {
                        if (timeoutMs < 0)
                        {
                            // Wait for process and all I/O to finish.
                            _process.WaitForExit();
                            return true;
                        }
    
                        // Timed waiting. We need to wait for I/O ourselves.
                        if (!_process.WaitForExit(timeoutMs))
                        {
                            Kill();
                        }
    
                        // Wait for the I/O to finish.
                        var waitMs = (int)(timeoutMs - _sw.ElapsedMilliseconds);
                        waitMs = Math.Max(waitMs, 10);
                        _stdOutEvent.WaitOne(waitMs);
    
                        waitMs = (int)(timeoutMs - _sw.ElapsedMilliseconds);
                        waitMs = Math.Max(waitMs, 10);
                        return _stdErrEvent.WaitOne(waitMs);
                    }
                    finally
                    {
                        // Cleanup.
                        Cancel();
                    }
                }
    
                private void Close()
                {
                    Cancel();
                    var proc = _process;
                    _process = null;
                    if (proc != null)
                    {
                        // Dispose in all cases.
                        proc.Close();
                        proc.Dispose();
                    }
                }
    
                private void Kill()
                {
                    try
                    {
                        // We need to do this in case of a non-UI proc
                        // or one to be forced to cancel.
                        var proc = _process;
                        if (proc != null && !proc.HasExited)
                        {
                            proc.Kill();
                        }
                    }
                    catch
                    {
                        // Kill will throw when/if the process has already exited.
                    }
                }
    
                private readonly string _name;
                private readonly string _path;
                private readonly StringBuilder _stdOut = new StringBuilder(4 * 1024);
                private readonly StringBuilder _stdErr = new StringBuilder(4 * 1024);
    
                private ManualResetEvent _stdOutEvent;
                private ManualResetEvent _stdErrEvent;
                private Process _process;
                private Stopwatch _sw;
            }

    Converting this to use Tasks is left as an exercise to the reader.

    Now, we can use this in a different way.

            public static void Run(List<KeyValuePair<string, string>> pathArgs, int timeout)
            {
                var cts = new CancellationTokenSource();
                var allProcesses = Task.Factory.StartNew(() =>
                {
                    var tasks = pathArgs.Select(pair => Task.Factory.StartNew(() =>
                    {
                        string name = Path.GetFileNameWithoutExtension(pair.Key);
                        var exec = new ProcessExecutor(name, pair.Key);
                        exec.Run(pair.Value);
                        cts.Token.Register(exec.Cancel);
                        return exec;
                    })).ToArray();
    
                    // Wait for individual tasks to finish.
                    foreach (var task in tasks)
                    {
                        if (task != null)
                        {
                            task.Result.Wait(timeout);
                            task.Result.Cancel();
                            task.Result.Dispose();
                            task.Dispose();
                        }
                    }
                });
    
                // Cancel, if we timed out.
                allProcesses.Wait(timeout);
                cts.Cancel();
            }

    This time, we fire each process executor in a separate thread (also a worker on the ThreadPool,) but we wait in a single thread. The worker threads will run, and they will have their async reads queued, which will run once the exec.Run() functions return, and free that thread, at which point the async reads will execute.

    Notice that we are creating the new tasks in a worker thread. This is so that we can limit the wait on all of them (although we’d need to have a timeout that depends on their number. But for illustration purpose the above code is sufficient. Now we have the luxury of waiting on all of them in a single Wait call and we can also cancel all of them using the CancellationTokenSource.

    The above code is typically finishing in about 5-6 seconds (and as low as 4006ms) for 500 child processes on 12 cores to echo a short string and exit.

    One thing to keep in mind when using this code is that if we use ProcessExecutor in another class, as a member, that class should also separate and expose the Run and Wait functions separately. That is, if it simply calls Run followed by Wait in the same function, then they will both execute on the same thread, which will result in the same problem if a number of them get executed on the ThreadPool, as we did. So the abstraction will leak again!

    In addition, this puts the onus in the hands of the consumer. Our ProcessExecutor class is not bulletproof on its own.

    In the next and final part we’ll go back to the Process class to try and avoid the deadlock issue without assuming a specific usage pattern.

    Share
    Apr 042013
     

    In part 2 we discovered that by executing Process instances in Parallel.ForEach we are getting reduced performance and our waits are timing out. In this part we’ll dive deep into the problem and find out what is going on.

    Deadlock

    Clearly the problem has to do with the Process class and/or with spawning processes in general. Looking more carefully, we notice that besides the spawned process we also have two asynchronous reads. We have intentionally requested these to be executed on separate threads. But that shouldn’t be a problem, unless we have misused the async API.

    It is reasonable to suspect that the approach used to do the async reading is at fault. This is where I ventured to look at the Process class code. After all, it’s a wrapper on Win32 API, and it might make assumptions that I was ignoring or contradicting. Regrettably, that didn’t help to figure out what was going on, except for initiating me to write the said previous post.

    Looking at the BeginOutputReadLine() function, we see it creating an AsyncStreamReader, which is internal to the .Net Framework and then calls BeginReadLine(), which presumably is where the async action happens.

            [System.Runtime.InteropServices.ComVisible(false)] 
            public void BeginOutputReadLine() {
    
                if(outputStreamReadMode == StreamReadMode.undefined) { 
                    outputStreamReadMode = StreamReadMode.asyncMode;
                } 
                else if (outputStreamReadMode != StreamReadMode.asyncMode) {
                    throw new InvalidOperationException(SR.GetString(SR.CantMixSyncAsyncOperation));
                }
    
                if (pendingOutputRead)
                    throw new InvalidOperationException(SR.GetString(SR.PendingAsyncOperation)); 
    
                pendingOutputRead = true;
                // We can't detect if there's a pending sychronous read, tream also doesn't. 
                if (output == null) {
                    if (standardOutput == null) {
                        throw new InvalidOperationException(SR.GetString(SR.CantGetStandardOut));
                    } 
    
                    Stream s = standardOutput.BaseStream; 
                    output = new AsyncStreamReader(this, s, new UserCallBack(this.OutputReadNotifyUser), standardOutput.CurrentEncoding); 
                }
                output.BeginReadLine(); 
            }

    Within the AsyncStreamReader.BeginReadLine() we see the familiar asynchronous read on Stream using Stream.BeginRead().

            // User calls BeginRead to start the asynchronous read
            internal void BeginReadLine() { 
                if( cancelOperation) {
                    cancelOperation = false; 
                } 
    
                if( sb == null ) { 
                    sb = new StringBuilder(DefaultBufferSize);
                    stream.BeginRead(byteBuffer, 0 , byteBuffer.Length,  new AsyncCallback(ReadBuffer), null);
                }
                else { 
                    FlushMessageQueue();
                } 
            }

    Unfortunately, I had incorrectly assumed that this async wait was executed on one of the I/O Completion Port threads of the ThreadPool. It seems that this is not the case, as ThreadPool.GetAvailableThreads() always returned the same number for completionPortThreads (incidentally, workerThreads value didn’t change much as well, but I didn’t notice that at first).

    A breakthrough came when I started changing the maximum parallelism (i.e. maximum thread count) of Parallel.ForEach.

            public static void ExecAll(List<KeyValuePair<string, string>> pathArgs, int timeout, int maxThreads)
            {
                Parallel.ForEach(pathArgs, new ParallelOptions { MaxDegreeOfParallelism = maxThreads },
                                 arg => Task.Factory.StartNew(() => DoJob(arg.Value.Split(' '))).Wait() );
            }

    I thought I should increase the maximum number of threads to resolve the issue. Indeed, for certain values of MaxDegreeOfParallelism, I could never reproduce the problem (all processes finished very swiftly, and no timeouts). For everything else, the problem was reproducible most of the time. Nine out of ten I’d get timeouts. However, and to my surprise, the problem went away when I reduced MaxDegreeOfParallelism!

    The magic number was 12. Yes, the number of cores at disposal on my dev machine. If we limit the number of concurrent ForEach executions to less than 12, everything finishes swiftly, otherwise, we get timeouts and finishing ExecAll() takes a long time. In fact, with maxThreads=11, 500 process executions finish under 8500ms, which is very commendable. However, with maxThreads=12, every 12 process wait until they timeout, which would take several minutes to finish all 500.

    With this information, I tried increasing the ThreadPool limit of threads using ThreadPool.SetMaxThreads(). But it turns out the defaults are 1023 worker threads and 1000 for I/O Completion Port threads, as reported by ThreadPool.GetMaxThreads(). I was assuming that if the available thread count was lower than the required, the ThreadPool would simply create new threads until it reached the maximum configured value.

    ThreadPool-Deadlock

    Diagram showing deadlock (created by www.gliffy.com)

    Putting It All Together

    The assumption that Parallel.ForEach executes its body on the ThreadPool, assuming said body is a black-box is clearly flawed. In our case the body is initiating asynchronous I/O which needs their own threads. Apparently, these do not come from the I/O thread pool but the worker thread pool. In addition, the number of threads in this pool is initially set to that of the available number of cores on the target machine. Even worse, it will resist creating new threads until absolutely necessary. Unfortunately, in our case it’s too late, as our waits are timing out. What I left until this point (both for dramatic effect and to leave the solution to you, the reader, to find out) is that the timeouts were happening on the StandardOutput and StandardError streams. That is, even though the child processes had exited a long time ago, we were still waiting to read their output.

    Let me spell it out, if it’s not obvious: Each call to spawn and wait for a child process is executed on a ThreadPool worker thread, and is using it exclusively until the waits return. The async stream reads on StandardOutput and StandardError need to run on some thread. Since they are apparently queued to run on a ThreadPool thread, they will starve if we use all of the available threads in the pool to wait on them to finish. Thereby timing out on the read waits (because we have a deadlock).

    This is a case of Leaky Abstraction, as our black box of a “execute on ThreadPool” failed miserably when the code executed itself depended on the ThreadPool. Specifically, when we had used all available threads in the pool, we left none for our code that depends on the ThreadPool to use. We shot ourselves in the proverbial foot. Our abstraction failed.

    In the next part we’ll attempt to solve the problem.

    Share
    Apr 032013
     

    In part 1 we discovered a deadlock in the synchronous approach to reading the output of Process and we solved it using asynchronous reads. Today we’ll parallelize the execution in an attempt to maximize efficiency and concurrency.

    Parallel Execution

    Now, let’s complicate our lives with some concurrency, shall we?

    If we are to spawn many processes, we could (and should) utilize all the cores at our disposal. Thanks to Parallel.For and Parallel.ForEach this task is made much simpler than otherwise.

            public static void ExecAll(List<KeyValuePair<string, string>> pathArgs, int timeout)
            {
                Parallel.ForEach(pathArgs, arg => ExecWithAsyncTasks(arg.Key, arg.Value, timeout));
            }

    Things couldn’t be any simpler! We pass a list of executable paths and their arguments as KeyValuePair and a timeout in milliseconds. Except, this won’t work… at least not always.

    First, let’s discuss how it will not work, then let’s understand the why before we attempt to fix it.

    When Abstraction Backfires

    The above code works like a charm in many cases. When it doesn’t, a number of waits timeout. This is unacceptable as we wouldn’t know if we got all the output or part of it, unless we get a clean exit with no timeouts. I first noticed this issue in a completely different way. I was looking at the task manager Process Explorer (if not using it, start now and I promise not to tell anyone,) to see how amazingly faster things are with that single ForEach line. I was expecting to see a dozen or so (on a 12-core machine) child processes spawning and vanishing in quick succession. Instead, and to my chagrin, I saw most of the time just one child! One!

    And after many trials and head-scratching and reading, it became clear that the waits were timing out, even though clearly the children had finished and exited. Indeed, because typically a process would run in much less time than the timeout, it was now slower with the parallelized code than with the sequential version. This wasn’t obvious at first, and reasonably I suspected some children were taking too long, or they had too much to write to the output pipes that could be deadlocking (which wasn’t unfamiliar to me).

    Testbed

    To troubleshoot something as complex as this, one should start with clean test-case, with minimum number of variables. This calls for a dummy child that would do exactly as I told it, so that I could simulate different scenarios. One such scenario would be not to spawn any children at all, and just test the Parallel.ForEach with some in-proc task (i.e. just a local function that does similar work to that of a child).

    using System;
    using System.Threading;
    
    namespace Child
    {
        class Program
        {
            static void Main(string[] args)
            {
                if (args.Length < 2 || args.Length % 2 != 0)
                {
                    Console.WriteLine("Usage: [echo|fill|sleep|return] ");
                    return;
                }
    
                DoJob(args);
            }
    
            private static void DoJob(string[] args)
            {
                for (int argIdx = 0; argIdx < args.Length; argIdx += 2)
                {
                    switch (args[argIdx].ToLowerInvariant())
                    {
                        case "echo":
                            Console.WriteLine(args[argIdx + 1]);
                            break;
    
                        case "fill":
                            var rd = new Random();
                            int bytes = int.Parse(args[argIdx + 1]);
                            while (bytes-- > 0)
                            {
                                // Generate a random string as long as the .
                                Console.Write(rd.Next('a', 'z'));
                            }
                            break;
    
                        case "sleep":
                            Thread.Sleep(int.Parse(args[argIdx + 1]));
                            break;
    
                        case "return":
                            Environment.ExitCode = int.Parse(args[argIdx + 1]);
                            break;
    
                        default:
                            Console.WriteLine("Unknown command [" + args[argIdx] + "]. Skipping.");
                            break;
                    }
                }
            }
        }
    }

    Now we can give the child process commands to change its behavior, from dumping data to its output to sleeping to returning immediately.

    Once the problem is reproduced, we can narrow it down to pin-point the source. Running the exact same command in the same process (i. e. without spawning another process) results in no problems at all. Calling DoJob 500 times directly in Parallel.ForEach finishes in under 500ms (often under 450ms). So we can be sure Parallel.ForEach is working fine.

            public static void ExecAll(List<KeyValuePair<string, string>> pathArgs, int timeout)
            {
                Parallel.ForEach(pathArgs, arg => Task.Factory.StartNew(() => DoJob(arg.Value.Split(' '))).Wait() );
            }

    Even executing as a new task (within the Parallel.ForEach) doesn’t result in any noticeable different in time. The reason for this good performance when running the jobs in new tasks is probably because the ThreadPool scheduler does fetch the task to execute immediately when we call Wait() and executes it. That is, because both the Task.Factory.StartNew() call as well as the DoJob() call are executed ultimately on the ThreadPool, and because Task is designed specifically to utilize it, when we call Wait() on the task, it knows that it should schedule the next job in the queue, which in this case is the job of the task on which we executed the Wait! Since the caller of Wait() happens to be running on the ThreadPool, it simply executes it instead of scheduling it on a different thread and blocking. Dumping the Thread.CurrentThread.ManagedThreadId from before the Task.Factory.StartNew() call and from within DoJob shows that indeed both are executed in the same thread. The overhead of creating and scheduling a Task is negligible, so we don’t see much of a change in time over 500 executions.

    All this is great and comforting, but still doesn’t help us resolve the problem at hand: why aren’t our processes spawned and executed at the highest possible efficiency? And why are they timing out?

    In the next part we’ll dive deep into the problem and find out what is going on.

    Share
    Apr 022013
     

    I’ve mentioned in a past post that it was conceived while reading the source code for the System.Diagnostics.Process class. This post is about the reason that pushed me to read the source code in an attempt to fix the issue. It turned out that this was yet another case of Leaky Abstraction, which is a special interest of mine.

    As it turned out, this post ended being way too long (even for me). I don’t like installments, but I felt that it is something that is worth trying as the size was prohibitive for single-post consumption. As such, I’ve split it up on 5 parts, so that each part would be around a 1000 words or less. I’ll post one part a day.

    To give you an idea of the scope and subject of what’s to come, here is a quick overview. In part 1 I’ll lay out the problem. We are trying to spawn processes, read their output and kill if they take too long. Our first attempt is to use simple synchronous I/O to read the output and discover a deadlock. We solve the deadlock using asynchronous I/O. In part 2 we parallelize the code and discover reduced performance and yet another deadlock. We create a testbed and set about to investigate the problem at depth. In part 3 we will find out the root cause and we’ll discuss the mechanics (how and why) we hit such a problem. In part 4 we’ll discuss solutions to the problem and develop a generic solutions (with code) to fix the problem. Finally, in part 5 we see whether or not a generic solution could work before we summarize and conclude.

    Let’s begin at the very beginning. Suppose you want to execute some program (call it child), get all its output (and error) and, if it doesn’t exit within some time limit, kill it. Notice that there is no interaction and no input. This is how tests are executed in Phalanger using a test runner.

    Synchronous I/O

    The Process class has conveniently exposed the underlying pipes to the child process using stream instances StandardOutput and StandardError. And, like many, we too might be tempted to simply call StandardOutput.ReadToEnd() and StandardError.ReadToEnd(). Albeit, that would work, until it doesn’t. As Raymond Chen noted, it’ll work as long as the data fits into the internal pipe buffer. The problem with this approach is that we are asking to read until we reach the end of the data, which will only happen for certainty when the child process we spawned exits. However, when the buffer of the pipe which the child writes its output to is full, the child has to wait until there is free space in the buffer to write to. But, you say, what if we always read and empty the buffer?

    Good idea, except, we need to do that for both StandardOutput and StandardError at the same time. In the StandardOutput.ReadToEnd() call we read every byte coming in the buffer until the child process exits. While we have drained the StandardOutput buffer (so that the child process can’t be possibly blocked on that,) if it fills the StandardError buffer, which we aren’t reading yet, we will deadlock. The child won’t exit until it fully writes to the StandardError buffer (which is full because no one is reading it,) meanwhile, we are waiting for the process to exit so we can be sure we read to the end of the StandardOutput before we return (and start reading StandardError). The same problem exists for StandardOutput, if we first read StandardError, hence the need to drain both pipe buffers as they are fed, not one after the other.

    Async Reading

    The obvious (and only practical) solution is to read both pipes at the same time using separate threads. To that end, there are mainly two approaches. The pre-4.0 approach (async events), and the 4.5-and-up approach (tasks).

    Async Reading with Events

    The code is reasonably straight forward as it uses .Net events. We have two manual-reset events and two delegates that get called asynchronously when we read a line from each pipe. We get null data when we hit the end of file (i.e. when the process exits) for each of the two pipes.

            public static string ExecWithAsyncEvents(string path, string args, int timeoutMs)
            {
                using (var outputWaitHandle = new ManualResetEvent(false))
                {
                    using (var errorWaitHandle = new ManualResetEvent(false))
                    {
                        using (var process = new Process())
                        {
                            process.StartInfo = new ProcessStartInfo(path);
                            process.StartInfo.Arguments = args;
                            process.StartInfo.UseShellExecute = false;
                            process.StartInfo.RedirectStandardOutput = true;
                            process.StartInfo.RedirectStandardError = true;
                            process.StartInfo.ErrorDialog = false;
                            process.StartInfo.CreateNoWindow = true;
    
                            var sb = new StringBuilder(1024);
                            process.OutputDataReceived += (sender, e) =>
                            {
                                sb.AppendLine(e.Data);
                                if (e.Data == null)
                                {
                                    outputWaitHandle.Set();
                                }
                            };
                            process.ErrorDataReceived += (sender, e) =>
                            {
                                sb.AppendLine(e.Data);
                                if (e.Data == null)
                                {
                                    errorWaitHandle.Set();
                                }
                            };
    
                            process.Start();
                            process.BeginOutputReadLine();
                            process.BeginErrorReadLine();
    
                            process.WaitForExit(timeoutMs);
                            outputWaitHandle.WaitOne(timeoutMs);
                            errorWaitHandle.WaitOne(timeoutMs);
    
                            process.CancelErrorRead();
                            process.CancelOutputRead();
    
                            return sb.ToString();
                        }
                    }
                }
            }

    We certainly can improve on the above code (for example we should make the total wait limit <= timeoutMs) but you get the point with this sample. Also, no error handling or killing the child process when it times out and doesn’t exit.

    Async Reading with Tasks

    A much more simplified and sanitized approach is to use the new System.Threading.Tasks namespace/framework to do all the heavy-lifting for us. As you can see, the code has been cut by half and it’s much more readable, but we need Framework 4.5 and newer for this to work (although my target is 4.0, but for comparison purposes I gave it a spin). The results are the same.

            public static string ExecWithAsyncTasks(string path, string args, int timeout)
            {
                using (var process = new Process())
                {
                    process.StartInfo = new ProcessStartInfo(path);
                    process.StartInfo.Arguments = args;
                    process.StartInfo.UseShellExecute = false;
                    process.StartInfo.RedirectStandardOutput = true;
                    process.StartInfo.RedirectStandardError = true;
                    process.StartInfo.ErrorDialog = false;
                    process.StartInfo.CreateNoWindow = true;
    
                    var sb = new StringBuilder(1024);
    
                    process.Start();
                    var stdOutTask = process.StandardOutput.ReadToEndAsync();
                    var stdErrTask = process.StandardError.ReadToEndAsync();
    
                    process.WaitForExit(timeout);
                    stdOutTask.Wait(timeout);
                    stdErrTask.Wait(timeout);
    
                    return sb.ToString();
                }
            }

    Again, a healthy doze of error-handling is in order, but for illustration purposes left out. A point worthy of mention is that we can’t assume we read the streams by the time the child exits. There is a race condition and we still need to wait for the I/O operations to finish before we can read the results.

    In the next part we’ll parallelize the execution in an attempt to maximize efficiency and concurrency.

    Share
    QR Code Business Card