An Evaluation of Object Name Hashing

Ceph splits files into objects, which end up distributed across the Ceph cluster. What would happen if the objects ended all up on the same OSD?

prefix_hashing.png
Figure 1: Default Object Hashing vs. Striper Prefix Hashing

I called this modification Striper Prefix Hashing, as I modified the object name hash to only include the prefix added by the Striper. The striper is the piece of code that does the file-to-object splitting (Ceph Dev Doc, Ceph User Doc). Since I was at it I also tested a different hash function.

The analysis uses the most real-world data I was able to find: A 10% sample of a tape-based archive system used by the European Centre for Medium-Range Weather Forecasts (ECMWF). I focused on balance of the resulting cluster (Objects / OSD, Size / OSD), since I could not obtain a Ceph cluster for ~ 1.6 PiB data to do performance testing on.

I did the aforementioned as part of my Master's Thesis. The results are quite interesting: Striper Prefix Hashing doesn't ruin the balance of the cluster.

Update 2016-01-26:

I reran the tests with more hash functions:

Implementation

My changes are available on github: Branch, Diff with current master branch (Old changes, without crypto hashes: Branch, Diff with current master branch)

The changes branch of the Ceph master branch (commit-ish 256dc84) from Jan 14, 2016.

The key change introduced by Striper Prefix Hashing is in the pg_pool_t:: hash_key method. It is called by OSDMap::object_locator_to_pg, which converts an object ID (object_t oid) and object locator (object_locator_t loc, it also contains the pool ID) to a placement group (pg_t pg).

  uint32_t pg_pool_t::hash_key(const string& key,
                               const string& ns) const
  {
    string n = make_hash_str(key, ns);
    return ceph_str_hash(object_hash, n.c_str(), n.length());
  }

The changed method, truncates the object's name at the first dot found in the string inkey, which happens to be the sequence number part for object names generated by the Ceph Striper.

  uint32_t pg_pool_t::hash_key(const string& inkey,
                               const string& ns) const
  {
    string key(inkey);

    if (flags & FLAG_HASHPSONLYPREFIX) {
      string::size_type n = inkey.find(".");

      if (n != string::npos) {
        key = inkey.substr(0, n) ;
      }
    }

    string n = make_hash_str(key, ns);
    return ceph_str_hash(object_hash, n.c_str(), n.length());
  }

Ceph's Hash Functions

Object name hashes are 32 Bit and computed using a variant of the RJenkins Robert J. Jenkins: Hash Functions for Hash Table Lookup, Ceph's implementation hash function. It is not cryptographic and designed for hash tables.

Ceph also contains code of the Linux dcache hash function, which is not used for object names and without changes to the code, not configurable. Its implementation is quite succinct compared to the 57 SLOC of RJenkins:

/*
 * linux dcache hash
 */
unsigned ceph_str_hash_linux(const char *str, unsigned length)
{
        unsigned long hash = 0;

        while (length--) {
                unsigned char c = *str++;
                hash = (hash + (c << 4) + (c >> 4)) * 11;
        }
        return hash;
}

Since the implementation was already there I included it in the benchmarks. I plan on re-running the tests with a cryptographic hash function soon.

The new ceph_str_hash functions are wrappers around crypto++'s functions (See: ceph_hash.cc). Endianness was a bit tricky. I hardcoded the conversions of crypto++'s byte arrays to unsigned long and put some sanity checks in the hash simulator. For truncation of SHA-1 and MD5 I used crypto++'s CalculateTruncatedDigest function.

Methodology

Workload

The workload was taken from the research paper Analysis of the ECMWF Storage Landscape Paper and presentation, tools and traces. . The paper discusses two systems; I used the ECFS HPSS trace, which is a tape-based general purpose archive system. It consists of filenames, sizes, access and modification timestamps.

As the trace is quite large with 14.8 PiB and 137 million files, I used a 10% random sample. It is still 1.595 PiB, which would need at least 544 3 TiB hard drives in a pool without replication.

Trace in summary:

  • 14950112 files
  • 1.595 PiB data in total
  • The biggest file is 32 GiB
  • 47.04 % of all files are smaller or equal to 4 MB (one Ceph object), but in total amount only to 5.495 GiB data (0.34 % total storage)

File size distribution:

workload_p10_filesize_histogram.png
Figure 2: Histogram: File size distribution. Each bucket inclusive e.g 0 < x ≤ 4 MiB

Ceph Settings

600 OSDs with 38400 placement groups. Flat OSD layout without failure domains. Simulation ran 4 times, once per setting.

Simulator

I found that running a whole Ceph stack with Ceph FS to simulate ~ 1.6 PiB is far too slow. I tried it anyway, and wrote a FUSE blackhole filesystem to store ~ 1.6 PiB without actually storing it. It's an overlay filesystem that keeps everything (file sizes, xattrs, metadata) except the actual data. Still to slow.

Simulation and lots of CPU cores to the rescue… I could borrow a 32 Core Xeon machine during my research back then, with a little help of some UNIX tools and scripting, each run took 45 minutes.

45 minutes for for ~ 1.6 PiB (600 OSDs), the 10% sample. I tried the full trace with 6000 OSDs, but quickly decided against it after the first run tool over 3 days.

The simulation code is in the branch on github. It compiles as part of the Ceph sources. It expects input on stdin with filename and object size separated by spaces. For each line of input it computes the placement data and outputs the following:

  • Filename
  • Size
  • Number of striper extents
  • Number of object names generated by the striper
  • Number of unique placement groups assigned to the file
  • Number of OSDs assigned to the file
  • Number of unique primary OSDs assigned to the file
  • JSON encoded data:
    • List of Object IDs
    • List of Placement Groups
    • List of OSDs

Results

This is a compilation of the IMHO most interesting results.

Distinct OSDs per File

The Table shows statistics for the number of distinct primary OSDs of all files in the workload that are larger than 4 MiB, because the number of OSDs per file is always 1 for files with only one object. Striper Prefix Hasing works :)

Table 1: Distinct primary OSDs per file for files larger than 4 MiB
Statistic RJenkins Linux dcache RJenkins+Prefix Linux+Prefix
Min. 1 1 1 1
Q1 3 3 1 1
Median 9 9 1 1
Q3 35 35 1 1
Max. 600 600 1 1

Balance

In an ideal balanced Ceph cluster all OSDs store the same amount of data and objects. The next figures show the measured balance for Objects / OSD and Size / OSD .

Note that the graphs are cut off at 8T / 2000000 objects. Outliers of Adler-32 go beyond that.

boxplot_objects_per_osd.png
Figure 3: Boxplot: Number of object per OSD
boxplot_size_per_osd.png
Figure 4: Boxplot: Size of data per OSD
ecdf_objects_per_osd.png
Figure 5: ECDF: Number of object per OSD
ecdf_size_per_osd.png
Figure 6: ECDF: Size of data per OSD

Adler-32 is obviously a bad choice. For standard hashing all choices (except Adler-32) work. CRC32, RJenkins, MD5 and SHA-1 are close. Linux dcache is slightly inferior.

With Striper Prefix Hashing more differences show: Linux becomes a too weak. RJenkins and CRC32 work especially well, with CRC32 even slightly better.

The following table compares the 99th percentiles with and without Striper Prefix Hashing enabled. The values give an estimate on how much more space the OSDs need for Striper Prefix Hashing to work. For CRC32 and RJenkins it is below 250GB.

Table 2: Percentiles: Difference Standard vs. Striper Prefix Hashing in Data / OSD
  Adler-32 CRC32 Linux dcache MD5 truncated RJenkins SHA-1 truncated
90% 1.0TB 46.7GB 121.8GB 63.3GB 47.9GB 45.2GB
99% 3.9TB 48.9GB 411.4GB 125.7GB 121.8GB 153.7GB
99.9% 7.4TB 156.7GB 646.7GB 328.4GB 153.6GB 415.2GB
99.99% 8.4TB 221.3GB 638.8GB 340.7GB 223.5GB 452.9GB
99.999% 8.4TB 227.8GB 638.0GB 341.9GB 230.5GB 456.6GB
Max 8.5TB 228.5GB 638.0GB 342.0GB 231.2GB 457.0GB

Discussion / Conclusion

First of all: It works. With Striper Prefix Hashing all objects of a file end up on the same OSD.

Secondly: It does not cause dramatic imbalance for a real-world workload.

What is it good for?

Locality: Small and medium sized files might work better, as the OSDs could prefetch objects belonging to the same file.

What's missing?

Performance Implications: The results do not show the performance implications of storing all objects of a file on a single OSD. All objects of the same file on the same OSD could also improve performance by exploiting locality. But, so far, Ceph OSDs are not optimized for this use case.

In case a storage pool only consists of large files like disk images this locality might not be beneficial.

Footnotes: