~todd-deshane/openstack-manuals/working

<title xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:d="http://docbook.org/ns/docbook">4.5.7.3. History of the Ring Design - OpenStack Object Storage Administrator Manual

- Trunk (in progress)</title><meta xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:d="http://docbook.org/ns/docbook" name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><link rel="home" href="index.html" title="OpenStack Object Storage Administrator Manual"/><link rel="up" href="ch04s05s07.html" title="4.5.7. Working with Rings"/><link rel="prev" href="ch04s05s07s02.html" title="4.5.7.2. Building the Ring"/><link rel="next" href="ch04s05s08.html" title="4.5.8. The Account Reaper"/><meta http-equiv="Content-Type" content="text/html; charset=utf-8"/><script type="text/javascript">

//The id for tree cookie

var treeCookieId = "treeview-3584";

var language = "en";

var w = new Object();

//Localization

txt_filesfound = 'Results';

txt_enter_at_least_1_char = "You must enter at least one character.";

txt_browser_not_supported = "Your browser is not supported. Use of Mozilla Firefox is recommended.";

txt_please_wait = "Please wait. Search in progress...";

txt_results_for = "Results for: ";

</script><style type="text/css">

input {

margin-bottom: 5px;

margin-top: 2px;

}

.folder {

display: block;

height: 22px;

padding-left: 20px;

background: transparent url(../common/jquery/treeview/images/folder.gif) 0 0px no-repeat;

}

</style><link rel="shortcut icon" href="../favicon.ico" type="image/x-icon"/><link rel="stylesheet" type="text/css" href="../common/css/positioning.css"/><link rel="stylesheet" type="text/css" href="../common/jquery/theme-redmond/jquery-ui-1.8.2.custom.css"/><link rel="stylesheet" type="text/css" href="../common/jquery/treeview/jquery.treeview.css"/><script type="text/javascript" src="../common/jquery/jquery-1.4.2.min.js"></script><script type="text/javascript" src="../common/jquery/jquery-ui-1.8.2.custom.min.js"></script><script type="text/javascript" src="../common/jquery/jquery.cookie.js"></script><script type="text/javascript" src="../common/jquery/treeview/jquery.treeview.min.js"></script><script type="text/javascript" src="search/htmlFileList.js"></script><script type="text/javascript" src="search/htmlFileInfoList.js"></script><script type="text/javascript" src="search/nwSearchFnt.js"></script><script type="text/javascript" src="search/stemmers/en_stemmer.js"></script><script type="text/javascript" src="search/index-1.js"></script><script type="text/javascript" src="search/index-2.js"></script><script type="text/javascript" src="search/index-3.js"></script></head><body><div xmlns="" id="header"><img src="../common/images/openstack-logo.png" alt="OpenStack Documentation" width="157" height="47"/><p class="breadcrumbs"><a href="http://docs.openstack.org/">OpenStack Manuals</a></p><h1>4.5.7.3. History of the Ring Design</h1><div id="navheader" align="right"><table class="navLinks"><tr><td><a id="showHideButton" onclick="showHideToc();" class="pointLeft" title="Hide TOC tree">Sidebar

</a></td><td><a accesskey="p" class="navLinkPrevious" href="ch04s05s07s02.html">Prev</a>

<a accesskey="n" class="navLinkNext" href="ch04s05s08.html">Next</a></td></tr></table></div></div><div id="content"><div class="section" title="4.5.7.3. History of the Ring Design"><div class="titlepage"><div><div><h4 class="title"><a id="d252e1302"/>4.5.7.3. History of the Ring Design</h4></div></div></div><p>The ring code went through many iterations before arriving at what it is now

and while it has been stable for a while now, the algorithm may be tweaked or

perhaps even fundamentally changed if new ideas emerge. This section will try

to describe the previous ideas attempted and attempt to explain why they were

discarded.</p><p>A “live ring” option was considered where each server could maintain its own

copy of the ring and the servers would use a gossip protocol to communicate the

changes they made. This was discarded as too complex and error prone to code

correctly in the project time span available. One bug could easily gossip bad

data out to the entire cluster and be difficult to recover from. Having an

externally managed ring simplifies the process, allows full validation of data

before it's shipped out to the servers, and guarantees each server is using a

ring from the same timeline. It also means that the servers themselves aren't

spending a lot of resources maintaining rings.</p><p>A couple of “ring server” options were considered. One was where all ring

lookups would be done by calling a service on a separate server or set of

servers, but this was discarded due to the latency involved. Another was much

like the current process but where servers could submit change requests to the

ring server to have a new ring built and shipped back out to the servers. This

was discarded due to project time constraints and because ring changes are

currently infrequent enough that manual control was sufficient. However, lack

of quick automatic ring changes did mean that other parts of the system had to

be coded to handle devices being unavailable for a period of hours until

someone could manually update the ring.</p><p>The current ring process has each replica of a partition independently assigned

to a device. A version of the ring that used a third of the memory was tried,

where the first replica of a partition was directly assigned and the other two

were determined by “walking” the ring until finding additional devices in other

zones. This was discarded as control was lost as to how many replicas for a

given partition moved at once. Keeping each replica independent allows for

moving only one partition replica within a given time window (except due to

device failures). Using the additional memory was deemed a good tradeoff for

moving data around the cluster much less often.</p><p>Another ring design was tried where the partition to device assignments weren't

stored in a big list in memory but instead each device was assigned a set of

hashes, or anchors. The partition would be determined from the data item's hash

and the nearest device anchors would determine where the replicas should be

stored. However, to get reasonable distribution of data each device had to have

a lot of anchors and walking through those anchors to find replicas started to

add up. In the end, the memory savings wasn't that great and more processing

power was used, so the idea was discarded.</p><p>A completely non-partitioned ring was also tried but discarded as the

partitioning helps many other parts of the system, especially replication.

Replication can be attempted and retried in a partition batch with the other

replicas rather than each data item independently attempted and retried. Hashes

of directory structures can be calculated and compared with other replicas to

reduce directory walking and network traffic.</p><p>Partitioning and independently assigning partition replicas also allowed for

the best balanced cluster. The best of the other strategies tended to give

+-10% variance on device balance with devices of equal weight and +-15% with

devices of varying weights. The current strategy allows us to get +-3% and +-8%

respectively.</p><p>Various hashing algorithms were tried. SHA offers better security, but the ring

doesn't need to be cryptographically secure and SHA is slower. Murmur was much

faster, but MD5 was built-in and hash computation is a small percentage of the

overall request handling time. In all, once it was decided the servers wouldn't

be maintaining the rings themselves anyway and only doing hash lookups, MD5 was

chosen for its general availability, good distribution, and adequate speed.</p></div><script xmlns="" type="text/javascript" src="../common/main.js"></script><hr xmlns=""/><h2 xmlns="" class="userNotes">User Notes On This Page</h2><div xmlns="" id="disqus_thread"><script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'openstackdocs';

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

100

</script><noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript><a href="http://disqus.com" class="dsq-brlink">User notes powered by <span class="logo-disqus">Disqus</span></a></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch04s05s07s02.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch04s05s07.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch04s05s08.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top"> </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> </td></tr></table></div></div><div xmlns=""><div id="leftnavigation" style="padding-top:3px; background-color:white;"><div id="tabs"><ul><li><a href="#treeDiv"><span class="contentsTab">Contents</span></a></li><li><a href="#searchDiv"><span class="searchTab">Search</span></a></li></ul><div id="treeDiv"><img src="../../../common/images/loading.gif" alt="loading table of contents..." id="tocLoading" style="display:block;"/><div id="ulTreeDiv" style="display:none"><ul id="tree" class="filetree"><li xmlns="http://www.w3.org/1999/xhtml"><span class="file"><a href="ch_getting-started-with-openstack.html">1. Getting Started with OpenStack</a></span><ul><li><span class="file"><a href="what-is-openstack.html">1.1. What is OpenStack?</a></span></li><li><span class="file"><a href="components-of-openstack.html">1.2. Components of OpenStack</a></span></li><li><span class="file"><a href="why-cloud.html">1.3. Why Cloud?</a></span></li></ul></li><li xmlns="http://www.w3.org/1999/xhtml"><span class="file"><a href="ch_introduction-to-openstack-object-storage.html">2. Introduction to OpenStack Object Storage</a></span><ul><li><span class="file"><a href="accounts-and-account-servers.html">2.1. Accounts and Account Servers</a></span></li><li><span class="file"><a href="authentication-and-access-permissions.html">2.2. Authentication and Access Permissions</a></span></li><li><span class="file"><a href="containers-and-objects.html">2.3. Containers and Objects</a></span></li><li><span class="file"><a href="operations.html">2.4. Operations</a></span></li><li><span class="file"><a href="language-specific-api-bindings.html">2.5. Language-Specific API Bindings</a></span></li></ul></li><li xmlns="http://www.w3.org/1999/xhtml"><span class="file"><a href="ch_installing-and-configuring-openstack-object-storage.html">3. Installing and Configuring OpenStack Object Storage</a></span><ul><li><span class="file"><a href="object-storage-system-requirements.html">3.1. System Requirements</a></span></li><li><span class="file"><a href="installing-openstack-object-storage-on-ubuntu.html">3.2. Installing OpenStack Object Storage on Ubuntu</a></span><ul><li><span class="file"><a href="ch03s02s01.html">3.2.1. Before You Begin</a></span></li><li><span class="file"><a href="ch03s02s02.html">3.2.2. Example Installation Architecture</a></span></li><li><span class="file"><a href="ch03s02s03.html">3.2.3. Network Setup Notes</a></span></li><li><span class="file"><a href="ch03s02s04.html">3.2.4. General Installation Steps </a></span></li></ul></li><li><span class="file"><a href="configuring-openstack-object-storage.html">3.3. Configuring OpenStack Object Storage </a></span><ul><li><span class="file"><a href="ch03s03s01.html">3.3.1. Installing and Configuring the Proxy Node</a></span></li><li><span class="file"><a href="ch03s03s02.html">3.3.2. Installing and Configuring the Auth Node</a></span></li><li><span class="file"><a href="ch03s03s03.html">3.3.3. Installing and Configuring the Storage Nodes</a></span><ul><li><span class="file"><a href="ch03s03s03s01.html">3.3.3.1. Create OpenStack Object Storage admin Account and Verify the Installation</a></span></li><li><span class="file"><a href="ch03s03s03s02.html">3.3.3.2. Adding a Proxy Server</a></span></li><li><span class="file"><a href="ch03s03s03s03.html">3.3.3.3. Troubleshooting Notes</a></span></li></ul></li></ul></li></ul></li><li xmlns="http://www.w3.org/1999/xhtml"><span class="file"><a href="ch_running-openstack-object-storage.html">4. Running OpenStack Object Storage</a></span><ul><li><span class="file"><a href="understanding-how-object-storage-works.html">4.1. Understanding How Object Storage Works</a></span><ul><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e383">4.1.1. The Ring</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e391">4.1.2. Proxy Server</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e396">4.1.3. Object Server</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e400">4.1.4. Container Server</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e403">4.1.5. Account Server</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e406">4.1.6. Replication</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e412">4.1.7. Updaters</a></span></li><li><span class="file"><a href="understanding-how-object-storage-works.html#d252e416">4.1.8. Auditors</a></span></li></ul></li><li><span class="file"><a href="configuring-and-tuning-openstack-object-storage.html">4.2. Configuring and Tuning OpenStack Object Storage</a></span></li><li><span class="file"><a href="preparing-the-ring.html">4.3. Preparing the Ring</a></span></li><li><span class="file"><a href="server-configuration-reference.html">4.4. Server Configuration Reference</a></span><ul><li><span class="file"><a href="ch04s04s01.html">4.4.1. Object Server Configuration</a></span></li><li><span class="file"><a href="ch04s04s02.html">4.4.2. Container Server Configuration</a></span></li><li><span class="file"><a href="ch04s04s03.html">4.4.3. Account Server Configuration</a></span></li><li><span class="file"><a href="ch04s04s04.html">4.4.4. Proxy Server Configuration</a></span></li></ul></li><li><span class="file"><a href="considerations-and-tuning.html">4.5. Considerations and Tuning</a></span><ul><li><span class="file"><a href="ch04s05s01.html">4.5.1. Memcached Considerations</a></span></li><li><span class="file"><a href="ch04s05s02.html">4.5.2. System Time</a></span></li><li><span class="file"><a href="ch04s05s03.html">4.5.3. General Service Tuning</a></span></li><li><span class="file"><a href="ch04s05s04.html">4.5.4. Filesystem Considerations</a></span></li><li><span class="file"><a href="ch04s05s05.html">4.5.5. General System Tuning</a></span></li><li><span class="file"><a href="ch04s05s06.html">4.5.6. Logging Considerations</a></span></li><li><span class="file"><a href="ch04s05s07.html">4.5.7. Working with Rings</a></span><ul><li><span class="file"><a href="ch04s05s07s01.html">4.5.7.1. Managing Rings with the Ring Builder</a></span><ul><li><span class="file"><a href="ch04s05s07s01s01.html">About the Ring Data Structure</a></span><ul><li><span class="file"><a href="ch04s05s07s01s01s01.html">List of Devices in the Ring</a></span></li></ul></li><li><span class="file"><a href="ch04s05s07s01s02.html">Partition Assignment List</a></span></li><li><span class="file"><a href="ch04s05s07s01s03.html">Partition Shift Value</a></span></li></ul></li><li><span class="file"><a href="ch04s05s07s02.html">4.5.7.2. Building the Ring</a></span></li><li id="webhelp-currentid"><span class="file"><a href="ch04s05s07s03.html">4.5.7.3. History of the Ring Design</a></span></li></ul></li><li><span class="file"><a href="ch04s05s08.html">4.5.8. The Account Reaper</a></span><ul><li><span class="file"><a href="ch04s05s08s01.html">4.5.8.1. Account Reaper Background and History</a></span></li></ul></li></ul></li><li><span class="file"><a href="replication.html">4.6. Replication</a></span><ul><li><span class="file"><a href="ch04s06s01.html">4.6.1. Database Replication</a></span></li><li><span class="file"><a href="ch04s06s02.html">4.6.2. Object Replication</a></span></li></ul></li><li><span class="file"><a href="managing-large-objects.html">4.7. Managing Large Objects (Greater than 5 GB)</a></span><ul><li><span class="file"><a href="ch04s07s01.html">4.7.1. Using st to Manage Segmented Objects</a></span></li><li><span class="file"><a href="ch04s07s02.html">4.7.2. Direct API Management of Large Objects</a></span></li><li><span class="file"><a href="ch04s07s03.html">4.7.3. Additional Notes on Large Objects</a></span></li><li><span class="file"><a href="ch04s07s04.html">4.7.4. Large Object Storage History and Background</a></span></li></ul></li><li><span class="file"><a href="throttling-resources-by-setting-rate-limits.html">4.8. Throttling Resources by Setting Rate Limits</a></span><ul><li><span class="file"><a href="ch04s08s01.html">4.8.1. Configuration for Rate Limiting</a></span></li></ul></li><li><span class="file"><a href="managing-openstack-object-storage-with-st.html">4.9. Managing OpenStack Object Storage with ST</a></span><ul><li><span class="file"><a href="ch04s09s01.html">4.9.1. ST Basics</a></span><ul><li><span class="file"><a href="ch04s09s01.html#d252e1463">4.9.1.1. stat [container] [object]</a></span></li><li><span class="file"><a href="ch04s09s01.html#d252e1466">4.9.1.2. list [options] [container]</a></span></li><li><span class="file"><a href="ch04s09s01.html#d252e1469">4.9.1.3. upload [options] container file_or_directory [file_or_directory] […]</a></span></li><li><span class="file"><a href="ch04s09s01.html#d252e1472">4.9.1.4. post [options] [container] [object]</a></span></li><li><span class="file"><a href="ch04s09s01.html#d252e1476">4.9.1.5. download —all OR download container [object] [object] …</a></span></li><li><span class="file"><a href="ch04s09s01.html#d252e1479">4.9.1.6. delete —all OR delete container [object] [object] …</a></span></li><li><span class="file"><a href="ch04s09s01.html#d252e1483">4.9.1.7. Options for st</a></span></li></ul></li><li><span class="file"><a href="ch04s09s02.html">4.9.2. Analyzing Log Files with ST</a></span></li></ul></li></ul></li><li xmlns="http://www.w3.org/1999/xhtml"><span class="file"><a href="ch_openstack-object-storage-tutorials.html">5. OpenStack Object Storage Tutorials</a></span><ul><li><span class="file"><a href="storing-large-photos-or-videos-on-the-cloud.html">5.1. Storing Large Photos or Videos on the Cloud</a></span><ul><li><span class="file"><a href="part-i-setting-up-secure-access.html">5.1.1. Part I: Setting Up Secure Access</a></span></li><li><span class="file"><a href="part-ii-configuring-cyberduck.html">5.1.2. Part II: Configuring Cyberduck</a></span></li><li><span class="file"><a href="part-iii-copying-files.html">5.1.3. Part III: Copying Files</a></span></li></ul></li></ul></li><li xmlns="http://www.w3.org/1999/xhtml"><span class="file"><a href="ch_support-and-troubleshooting.html">6. Support and Troubleshooting</a></span><ul><li><span class="file"><a href="community-support.html">6.1. Community Support</a></span><ul><li><span class="file"><a href="community-support.html#d252e1557">6.1.1. The Launchpad Answers area</a></span></li><li><span class="file"><a href="community-support.html#d252e1562">6.1.2. OpenStack mailing list</a></span></li><li><span class="file"><a href="community-support.html#d252e1567">6.1.3. The OpenStack Wiki search </a></span></li><li><span class="file"><a href="community-support.html#d252e1571">6.1.4. The Launchpad Bugs area </a></span></li><li><span class="file"><a href="community-support.html#d252e1587">6.1.5. The OpenStack IRC channel </a></span></li></ul></li><li><span class="file"><a href="troubleshooting-openstack-object-storage.html">6.2. Troubleshooting OpenStack Object Storage</a></span><ul><li><span class="file"><a href="ch06s02s01.html">6.2.1. Handling Drive Failure</a></span></li><li><span class="file"><a href="ch06s02s02.html">6.2.2. Handling Server Failure</a></span></li><li><span class="file"><a href="ch06s02s03.html">6.2.3. Detecting Failed Drives</a></span></li></ul></li><li><span class="file"><a href="troubleshooting-openstack-compute.html">6.3. Troubleshooting OpenStack Compute</a></span><ul><li><span class="file"><a href="ch06s03s01.html">6.3.1. Log files for OpenStack Compute</a></span></li><li><span class="file"><a href="ch06s03s02.html">6.3.2. Common Errors and Fixes for OpenStack Compute</a></span></li></ul></li></ul></li></ul></div></div><div id="searchDiv"><div id="search"><form onsubmit="Verifie(ditaSearch_Form);return false" name="ditaSearch_Form" class="searchForm"><fieldset class="searchFieldSet"><legend>Search</legend><center><input id="textToSearch" name="textToSearch" type="text" class="searchText"/>   <input onclick="Verifie(ditaSearch_Form)" type="button" class="searchButton" value="Go" id="doSearch"/></center></fieldset></form></div><div id="searchResults"><center/></div><p class="searchHighlight"><a href="#" onclick="toggleHighlight()">Search Highlighter (On/Off)</a></p></div></div></div></div></body></html>

b'\\ No newline at end of file'

Older »