376 lines
28 KiB
HTML
376 lines
28 KiB
HTML
<!DOCTYPE html>
|
||
|
||
<html lang="en">
|
||
<head>
|
||
<meta charset="utf-8" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.19: https://docutils.sourceforge.io/" />
|
||
|
||
<title>Priority Queues — FoundationDB ON documentation</title>
|
||
<link rel="stylesheet" type="text/css" href="_static/pygments.css" />
|
||
<link rel="stylesheet" type="text/css" href="_static/bootstrap-sphinx.css" />
|
||
<script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
|
||
<script src="_static/jquery.js"></script>
|
||
<script src="_static/underscore.js"></script>
|
||
<script src="_static/_sphinx_javascript_frameworks_compat.js"></script>
|
||
<script src="_static/doctools.js"></script>
|
||
<link rel="search" title="Search" href="search.html" />
|
||
<link rel="next" title="Priority Queues" href="priority-queues-java.html" />
|
||
<link rel="prev" title="Multimaps" href="multimaps-java.html" />
|
||
<meta charset='utf-8'>
|
||
<meta http-equiv='X-UA-Compatible' content='IE=edge,chrome=1'>
|
||
<meta name='viewport' content='width=device-width, initial-scale=1.0, maximum-scale=1'>
|
||
<meta name="apple-mobile-web-app-capable" content="yes">
|
||
<script type="text/javascript" src="_static/js/jquery-1.12.4.min.js"></script>
|
||
<script type="text/javascript" src="_static/js/jquery-fix.js"></script>
|
||
<script type="text/javascript" src="_static/bootstrap-3.4.1/js/bootstrap.min.js"></script>
|
||
<script type="text/javascript" src="_static/bootstrap-sphinx.js"></script>
|
||
|
||
</head><body>
|
||
|
||
<div id="navbar" class="navbar navbar-default navbar-fixed-top">
|
||
<div class="container">
|
||
<div class="navbar-header">
|
||
<!-- .btn-navbar is used as the toggle for collapsed navbar content -->
|
||
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".nav-collapse">
|
||
<span class="icon-bar"></span>
|
||
<span class="icon-bar"></span>
|
||
<span class="icon-bar"></span>
|
||
</button>
|
||
<a class="navbar-brand" href="index.html">
|
||
FoundationDB</a>
|
||
<span class="navbar-text navbar-version pull-left"><b>7.3.57</b></span>
|
||
</div>
|
||
|
||
<div class="collapse navbar-collapse nav-collapse">
|
||
<ul class="nav navbar-nav">
|
||
|
||
<li><a href="contents.html">Site Map</a></li>
|
||
|
||
|
||
<li class="dropdown globaltoc-container">
|
||
<a role="button"
|
||
id="dLabelGlobalToc"
|
||
data-toggle="dropdown"
|
||
data-target="#"
|
||
href="index.html">Site <b class="caret"></b></a>
|
||
<ul class="dropdown-menu globaltoc"
|
||
role="menu"
|
||
aria-labelledby="dLabelGlobalToc"><ul class="current">
|
||
<li class="toctree-l1"><a class="reference internal" href="local-dev.html">Local Development</a></li>
|
||
<li class="toctree-l1"><a class="reference internal" href="internal-dev-tools.html">Internal Dev Tools</a></li>
|
||
<li class="toctree-l1"><a class="reference internal" href="why-foundationdb.html">Why FoundationDB</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="transaction-manifesto.html">Transaction Manifesto</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="cap-theorem.html">CAP Theorem</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="consistency.html">Consistency</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="scalability.html">Scalability</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="technical-overview.html">Technical Overview</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="architecture.html">Architecture</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="performance.html">Performance</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="benchmarking.html">Benchmarking</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="engineering.html">Engineering</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="features.html">Features</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="layer-concept.html">Layer Concept</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="anti-features.html">Anti-Features</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="experimental-features.html">Experimental-Features</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="transaction-processing.html">Transaction Processing</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="fault-tolerance.html">Fault Tolerance</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="flow.html">Flow</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="testing.html">Simulation and Testing</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="kv-architecture.html">FoundationDB Architecture</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="read-write-path.html">FDB Read and Write Path</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="ha-write-path.html">FDB HA Write Path: How a mutation travels in FDB HA</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="consistency-check-urgent.html">Consistency Checker Urgent</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="client-design.html">Client Design</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="getting-started-mac.html">Getting Started on macOS</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="getting-started-linux.html">Getting Started on Linux</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="downloads.html">Downloads</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="developer-guide.html">Developer Guide</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="data-modeling.html">Data Modeling</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="client-testing.html">Client Testing</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="client-testing.html#testing-error-handling-with-buggify">Testing Error Handling with Buggify</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="client-testing.html#simulation-and-cluster-workloads">Simulation and Cluster Workloads</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="client-testing.html#api-tester">API Tester</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="api-general.html">Using FoundationDB Clients</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="transaction-tagging.html">Transaction Tagging</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="known-limitations.html">Known Limitations</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="transaction-profiler-analyzer.html">Transaction profiling and analyzing</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="api-version-upgrade-guide.html">API Version Upgrade Guide</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="tenants.html">Tenants</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="automatic-idempotency.html">Automatic Idempotency</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1 current"><a class="reference internal" href="design-recipes.html">Design Recipes</a><ul class="current">
|
||
<li class="toctree-l2"><a class="reference internal" href="blob.html">Blob</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="blob-java.html">Blob</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="hierarchical-documents.html">Hierarchical Documents</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="hierarchical-documents-java.html">Hierarchical Documents</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="multimaps.html">Multimaps</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="multimaps-java.html">Multimaps</a></li>
|
||
<li class="toctree-l2 current"><a class="current reference internal" href="#">Priority Queues</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="priority-queues-java.html">Priority Queues</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="queues.html">Queues</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="queues-java.html">Queues</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="segmented-range-reads.html">Segmented Range Reads</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="segmented-range-reads-java.html">Segmented Range Reads</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="simple-indexes.html">Simple Indexes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="simple-indexes-java.html">Simple Indexes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="spatial-indexing.html">Spatial Indexing</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="spatial-indexing-java.html">Spatial Indexing</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="subspace-indirection.html">Subspace Indirection</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="subspace-indirection-java.html">Subspace Indirection</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="tables.html">Tables</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="tables-java.html">Tables</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="vector.html">Vector</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="vector-java.html">Vector</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="api-reference.html">API Reference</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="api-python.html">Python API</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="api-ruby.html">Ruby API</a></li>
|
||
<li class="toctree-l2"><a class="reference external" href="relative://javadoc/index.html">Java API</a></li>
|
||
<li class="toctree-l2"><a class="reference external" href="https://godoc.org/github.com/apple/foundationdb/bindings/go/src/fdb">Go API</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="api-c.html">C API</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="api-error-codes.html">Error Codes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="special-keys.html">Special Keys</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="global-configuration.html">Global Configuration</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="tutorials.html">Tutorials</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="class-scheduling.html">Class Scheduling</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="largeval.html">Managing Large Values and Blobs</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="time-series.html">Time-Series Data</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="administration.html">Administration</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="configuration.html">Configuration</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="moving-a-cluster.html">Moving a Cluster to New Machines</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="tls.html">Transport Layer Security</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="authorization.html">Authorization</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="monitored-metrics.html"><strong>Monitored Metrics</strong></a></li>
|
||
<li class="toctree-l1"><a class="reference internal" href="redwood.html">Redwood Storage Engine</a></li>
|
||
<li class="toctree-l1"><a class="reference internal" href="visibility.html">Visibility Documents</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="request-tracing.html">Request Tracing</a></li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="earlier-release-notes.html">Earlier Release Notes</a><ul>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-014.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-016.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-021.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-022.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-023.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-100.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-200.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-300.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-400.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-410.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-420.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-430.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-440.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-450.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-460.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-500.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-510.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-520.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-600.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-610.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-620.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-630.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-700.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-710.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-720.html">Release Notes</a></li>
|
||
<li class="toctree-l2"><a class="reference internal" href="release-notes/release-notes-730.html">Release Notes</a></li>
|
||
</ul>
|
||
</li>
|
||
</ul>
|
||
</ul>
|
||
</li>
|
||
|
||
<li class="dropdown">
|
||
<a role="button"
|
||
id="dLabelLocalToc"
|
||
data-toggle="dropdown"
|
||
data-target="#"
|
||
href="#">Page <b class="caret"></b></a>
|
||
<ul class="dropdown-menu localtoc"
|
||
role="menu"
|
||
aria-labelledby="dLabelLocalToc"><ul>
|
||
<li><a class="reference internal" href="#">Priority Queues</a><ul>
|
||
<li><a class="reference internal" href="#goal">Goal</a></li>
|
||
<li><a class="reference internal" href="#challenge">Challenge</a></li>
|
||
<li><a class="reference internal" href="#explanation">Explanation</a></li>
|
||
<li><a class="reference internal" href="#ordering">Ordering</a></li>
|
||
<li><a class="reference internal" href="#pattern">Pattern</a></li>
|
||
<li><a class="reference internal" href="#extensions">Extensions</a></li>
|
||
<li><a class="reference internal" href="#code">Code</a></li>
|
||
</ul>
|
||
</li>
|
||
</ul>
|
||
</ul>
|
||
</li>
|
||
|
||
|
||
|
||
|
||
|
||
<li>
|
||
<a href="multimaps-java.html" title="Previous Chapter: Multimaps"><span class="glyphicon glyphicon-chevron-left visible-sm"></span><span class="hidden-sm hidden-tablet">« Multimaps</span>
|
||
</a>
|
||
</li>
|
||
<li>
|
||
<a href="priority-queues-java.html" title="Next Chapter: Priority Queues"><span class="glyphicon glyphicon-chevron-right visible-sm"></span><span class="hidden-sm hidden-tablet">Priority Queues »</span>
|
||
</a>
|
||
</li>
|
||
|
||
|
||
|
||
|
||
|
||
</ul>
|
||
|
||
|
||
|
||
<form class="navbar-form navbar-right" action="search.html" method="get">
|
||
<div class="form-group">
|
||
<input type="text" name="q" class="form-control" placeholder="Search" />
|
||
</div>
|
||
<input type="hidden" name="check_keywords" value="yes" />
|
||
<input type="hidden" name="area" value="default" />
|
||
</form>
|
||
|
||
</div>
|
||
</div>
|
||
</div>
|
||
|
||
<div class="container">
|
||
<div class="row">
|
||
<div class="col-md-3">
|
||
<div id="sidebar" class="bs-sidenav" role="complementary"><ul>
|
||
<li><a class="reference internal" href="#">Priority Queues</a><ul>
|
||
<li><a class="reference internal" href="#goal">Goal</a></li>
|
||
<li><a class="reference internal" href="#challenge">Challenge</a></li>
|
||
<li><a class="reference internal" href="#explanation">Explanation</a></li>
|
||
<li><a class="reference internal" href="#ordering">Ordering</a></li>
|
||
<li><a class="reference internal" href="#pattern">Pattern</a></li>
|
||
<li><a class="reference internal" href="#extensions">Extensions</a></li>
|
||
<li><a class="reference internal" href="#code">Code</a></li>
|
||
</ul>
|
||
</li>
|
||
</ul>
|
||
|
||
</div>
|
||
</div>
|
||
<div class="body col-md-9 content" role="main">
|
||
|
||
<section id="priority-queues">
|
||
<h1>Priority Queues</h1>
|
||
<p><strong>Python</strong> <a class="reference internal" href="priority-queues-java.html"><span class="doc">Java</span></a></p>
|
||
<section id="goal">
|
||
<h2>Goal</h2>
|
||
<p>Create a data structure for <a class="reference external" href="http://en.wikipedia.org/wiki/Priority_queue">priority queues</a> supporting operations for push, pop_min, peek_min, pop_max, and peek_max. You may find it helpful to review the <a class="reference internal" href="queues.html"><span class="doc">Queues</span></a> recipe before this one.</p>
|
||
</section>
|
||
<section id="challenge">
|
||
<h2>Challenge</h2>
|
||
<p>Allow efficient operations on a shared priority queue by multiple clients acting concurrently.</p>
|
||
</section>
|
||
<section id="explanation">
|
||
<h2>Explanation</h2>
|
||
<p>We can model a priority queue using a key formed from a tuple of three elements: an item’s priority, an increasing integer encoding the order in which the item was pushed, and a random element to make the key unique. By making keys unique, we can minimize conflicts for concurrent pushes.</p>
|
||
</section>
|
||
<section id="ordering">
|
||
<h2>Ordering</h2>
|
||
<p>The ordering of keys will sort items first by priority, then by push order, then randomly (to break ties in concurrent pushes). The minimum and maximum priority items will always be at the beginning and end of the queue, respectively, allowing us to efficiently peek or pop them.</p>
|
||
</section>
|
||
<section id="pattern">
|
||
<h2>Pattern</h2>
|
||
<p>We create a subspace for the priority queue, which takes care of packing our tuples into byte strings.</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">pq</span> <span class="o">=</span> <span class="n">fdb</span><span class="o">.</span><span class="n">Subspace</span><span class="p">((</span><span class="s1">'P'</span><span class="p">,))</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>Push operations will construct a key-value pair of the form:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">tr</span><span class="p">[</span> <span class="n">pq</span><span class="p">[</span> <span class="n">priority</span> <span class="p">][</span> <span class="n">count</span> <span class="p">][</span> <span class="n">random</span> <span class="p">]</span> <span class="p">]</span> <span class="o">=</span> <span class="n">value</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>where priority is supplied by the client, count is an integer that increases by 1 for each item pushed with priority, and random is a randomly generated integer.</p>
|
||
<p>Items of the same priority that are pushed concurrently may occasionally be assigned the same count, but their keys will still be distinct and ordered (in this case, randomly). The count is derived by reading and incrementing the highest count previously used for a given priority. By using a snapshot read, we guarantee that pushing is conflict-free.</p>
|
||
<p>To implement this model, we need an efficient way of finding the first and last key in the queue. (The ordering of keys guarantees that these will always be the proper keys to pop or peek.) FoundationDB’s range reads have limit and reverse options that let us accomplish this. Given the range of the subspace:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">r</span> <span class="o">=</span> <span class="n">pq</span><span class="o">.</span><span class="n">range</span><span class="p">()</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>we can find the first and last key-value pairs in the range with:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">tr</span><span class="o">.</span><span class="n">get_range</span><span class="p">(</span><span class="n">r</span><span class="o">.</span><span class="n">start</span><span class="p">,</span> <span class="n">r</span><span class="o">.</span><span class="n">stop</span><span class="p">,</span> <span class="n">limit</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span> <span class="c1"># first</span>
|
||
<span class="n">tr</span><span class="o">.</span><span class="n">get_range</span><span class="p">(</span><span class="n">r</span><span class="o">.</span><span class="n">start</span><span class="p">,</span> <span class="n">r</span><span class="o">.</span><span class="n">stop</span><span class="p">,</span> <span class="n">limit</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">reverse</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span> <span class="c1"># last</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
<section id="extensions">
|
||
<h2>Extensions</h2>
|
||
<p><em>High-Contention Pop Operations</em></p>
|
||
<p>To minimize conflicts during pop operations, we can use a staging technique to service the requests. If a pop operation doesn’t initially succeed, it registers a pop request in a semi-ordered set of such requests. It then enters a retry loop in which it attempts to fulfill outstanding requests.</p>
|
||
</section>
|
||
<section id="code">
|
||
<h2>Code</h2>
|
||
<p>Here’s a basic implementation of the model:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">os</span>
|
||
|
||
<span class="n">pq</span> <span class="o">=</span> <span class="n">fdb</span><span class="o">.</span><span class="n">Subspace</span><span class="p">((</span><span class="s1">'P'</span><span class="p">,))</span>
|
||
|
||
<span class="nd">@fdb</span><span class="o">.</span><span class="n">transactional</span>
|
||
<span class="k">def</span> <span class="nf">push</span><span class="p">(</span><span class="n">tr</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span> <span class="n">priority</span><span class="p">):</span>
|
||
<span class="n">tr</span><span class="p">[</span><span class="n">pq</span><span class="p">[</span><span class="n">priority</span><span class="p">][</span><span class="n">_next_count</span><span class="p">(</span><span class="n">tr</span><span class="p">,</span> <span class="n">priority</span><span class="p">)][</span><span class="n">os</span><span class="o">.</span><span class="n">urandom</span><span class="p">(</span><span class="mi">20</span><span class="p">)]]</span> <span class="o">=</span> <span class="n">value</span>
|
||
|
||
<span class="nd">@fdb</span><span class="o">.</span><span class="n">transactional</span>
|
||
<span class="k">def</span> <span class="nf">_next_count</span><span class="p">(</span><span class="n">tr</span><span class="p">,</span> <span class="n">priority</span><span class="p">):</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="n">pq</span><span class="p">[</span><span class="n">priority</span><span class="p">]</span><span class="o">.</span><span class="n">range</span><span class="p">()</span>
|
||
<span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">tr</span><span class="o">.</span><span class="n">snapshot</span><span class="o">.</span><span class="n">get_range</span><span class="p">(</span><span class="n">r</span><span class="o">.</span><span class="n">start</span><span class="p">,</span> <span class="n">r</span><span class="o">.</span><span class="n">stop</span><span class="p">,</span> <span class="n">limit</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">reverse</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">pq</span><span class="p">[</span><span class="n">priority</span><span class="p">]</span><span class="o">.</span><span class="n">unpack</span><span class="p">(</span><span class="n">key</span><span class="p">)[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span>
|
||
<span class="k">return</span> <span class="mi">0</span>
|
||
|
||
<span class="nd">@fdb</span><span class="o">.</span><span class="n">transactional</span>
|
||
<span class="k">def</span> <span class="nf">pop</span><span class="p">(</span><span class="n">tr</span><span class="p">,</span> <span class="nb">max</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="n">pq</span><span class="o">.</span><span class="n">range</span><span class="p">()</span>
|
||
<span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">tr</span><span class="o">.</span><span class="n">get_range</span><span class="p">(</span><span class="n">r</span><span class="o">.</span><span class="n">start</span><span class="p">,</span> <span class="n">r</span><span class="o">.</span><span class="n">stop</span><span class="p">,</span> <span class="n">limit</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">reverse</span><span class="o">=</span><span class="nb">max</span><span class="p">):</span>
|
||
<span class="k">del</span> <span class="n">tr</span><span class="p">[</span><span class="n">item</span><span class="o">.</span><span class="n">key</span><span class="p">]</span>
|
||
<span class="k">return</span> <span class="n">item</span><span class="o">.</span><span class="n">value</span>
|
||
|
||
<span class="nd">@fdb</span><span class="o">.</span><span class="n">transactional</span>
|
||
<span class="k">def</span> <span class="nf">peek</span><span class="p">(</span><span class="n">tr</span><span class="p">,</span> <span class="nb">max</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="n">pq</span><span class="o">.</span><span class="n">range</span><span class="p">()</span>
|
||
<span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">tr</span><span class="o">.</span><span class="n">get_range</span><span class="p">(</span><span class="n">r</span><span class="o">.</span><span class="n">start</span><span class="p">,</span> <span class="n">r</span><span class="o">.</span><span class="n">stop</span><span class="p">,</span> <span class="n">limit</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">reverse</span><span class="o">=</span><span class="nb">max</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">item</span><span class="o">.</span><span class="n">value</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
</section>
|
||
|
||
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
<footer class="footer">
|
||
<div class="container">
|
||
<p class="pull-right">
|
||
<a href="#">Back to top</a>
|
||
|
||
<br/>
|
||
|
||
<div id="sourcelink">
|
||
<a href="_sources/priority-queues.rst.txt"
|
||
rel="nofollow">Source</a>
|
||
</div>
|
||
|
||
</p>
|
||
<p>
|
||
© Copyright 2013-2022 Apple, Inc and the FoundationDB project authors.<br/>
|
||
Last updated on Nov 20, 2024.<br/>
|
||
</p>
|
||
</div>
|
||
</footer>
|
||
</body>
|
||
</html> |