Google Git
Sign in
apache / beam-site / 8066db78465c0d76bfe854be06941aea4657c8d5 / . / javadoc / javadoc / org / apache / beam / sdk / io / range / RangeTracker.html
blob: 160b63f2ccf61a7649155af44631b60af562807c [file] [log] [blame]
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="en">
<head>
<!-- Generated by javadoc (1.8.0_181-google-v7) on Mon Jan 27 16:42:31 PST 2020 -->
<title>RangeTracker (Apache Beam 2.20.0-SNAPSHOT)</title>
<meta name="date" content="2020-01-27">
<link rel="stylesheet" type="text/css" href="../../../../../../stylesheet.css" title="Style">
<script type="text/javascript" src="../../../../../../script.js"></script>
</head>
<body>
<script type="text/javascript"><!--
try {
if (location.href.indexOf('is-external=true') == -1) {
parent.document.title="RangeTracker (Apache Beam 2.20.0-SNAPSHOT)";
}
}
catch(err) {
}
//-->
var methods = {"i0":6,"i1":6,"i2":6,"i3":6,"i4":6};
var tabs = {65535:["t0","All Methods"],2:["t2","Instance Methods"],4:["t3","Abstract Methods"]};
var altColor = "altColor";
var rowColor = "rowColor";
var tableTab = "tableTab";
var activeTableTab = "activeTableTab";
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar.top">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.top" title="Skip navigation links">Skip navigation links</a></div>
<a name="navbar.top.firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../../../../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../../org/apache/beam/sdk/io/range/OffsetRangeTracker.html" title="class in org.apache.beam.sdk.io.range"><span class="typeNameLink">Prev&nbsp;Class</span></a></li>
<li>Next&nbsp;Class</li>
</ul>
<ul class="navList">
<li><a href="../../../../../../index.html?org/apache/beam/sdk/io/range/RangeTracker.html" target="_top">Frames</a></li>
<li><a href="RangeTracker.html" target="_top">No&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="../../../../../../allclasses-noframe.html">All&nbsp;Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_top");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li>Constr&nbsp;|&nbsp;</li>
<li><a href="#method.summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li>Constr&nbsp;|&nbsp;</li>
<li><a href="#method.detail">Method</a></li>
</ul>
</div>
<a name="skip.navbar.top">
<!-- -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<!-- ======== START OF CLASS DATA ======== -->
<div class="header">
<div class="subTitle">org.apache.beam.sdk.io.range</div>
<h2 title="Interface RangeTracker" class="title">Interface RangeTracker&lt;PositionT&gt;</h2>
</div>
<div class="contentContainer">
<div class="description">
<ul class="blockList">
<li class="blockList">
<dl>
<dt><span class="paramLabel">Type Parameters:</span></dt>
<dd><code>PositionT</code> - Type of positions used by the source to define ranges and identify records.</dd>
</dl>
<dl>
<dt>All Known Implementing Classes:</dt>
<dd><a href="../../../../../../org/apache/beam/sdk/io/range/ByteKeyRangeTracker.html" title="class in org.apache.beam.sdk.io.range">ByteKeyRangeTracker</a>, <a href="../../../../../../org/apache/beam/sdk/io/range/OffsetRangeTracker.html" title="class in org.apache.beam.sdk.io.range">OffsetRangeTracker</a></dd>
</dl>
<hr>
<br>
<pre>public interface <span class="typeNameLabel">RangeTracker&lt;PositionT&gt;</span></pre>
<div class="block">A <code>RangeTracker</code> is a thread-safe helper object for implementing dynamic work rebalancing
in position-based <a href="../../../../../../org/apache/beam/sdk/io/BoundedSource.BoundedReader.html" title="class in org.apache.beam.sdk.io"><code>BoundedSource.BoundedReader</code></a> subclasses.
<h3>Usage of the RangeTracker class hierarchy</h3>
The abstract <code>RangeTracker</code> interface should not be used per se - all users should use its
subclasses directly. We declare it here because all subclasses have roughly the same interface
and the same properties, to centralize the documentation. Currently we provide one implementation
- <a href="../../../../../../org/apache/beam/sdk/io/range/OffsetRangeTracker.html" title="class in org.apache.beam.sdk.io.range"><code>OffsetRangeTracker</code></a>.
<h3>Position-based sources</h3>
A position-based source is one where the source can be described by a range of positions of an
ordered type and the records returned by the reader can be described by positions of the same
type.
<p>In case a record occupies a range of positions in the source, the most important thing about
the record is the position where it starts.
<p>Defining the semantics of positions for a source is entirely up to the source class, however
the chosen definitions have to obey certain properties in order to make it possible to correctly
split the source into parts, including dynamic splitting. Two main aspects need to be defined:
<ul>
<li>How to assign starting positions to records.
<li>Which records should be read by a source with a range <code>[A, B)</code>.
</ul>
Moreover, reading a range must be <i>efficient</i>, i.e., the performance of reading a range
should not significantly depend on the location of the range. For example, reading the range
<code>[A, B)</code> should not require reading all data before <code>A</code>.
<p>The sections below explain exactly what properties these definitions must satisfy, and how to
use a <code>RangeTracker</code> with a properly defined source.
<h3>Properties of position-based sources</h3>
The main requirement for position-based sources is <i>associativity</i>: reading records from
<code>[A, B)</code> and records from <code>[B, C)</code> should give the same records as reading from
<code>[A, C)</code>, where <code>A &lt;= B &lt;= C</code>. This property ensures that no matter how a range of
positions is split into arbitrarily many sub-ranges, the total set of records described by them
stays the same.
<p>The other important property is how the source's range relates to positions of records in the
source. In many sources each record can be identified by a unique starting position. In this
case:
<ul>
<li>All records returned by a source <code>[A, B)</code> must have starting positions in this range.
<li>All but the last record should end within this range. The last record may or may not extend
past the end of the range.
<li>Records should not overlap.
</ul>
Such sources should define "read <code>[A, B)</code>" as "read from the first record starting at or
after A, up to but not including the first record starting at or after B".
<p>Some examples of such sources include reading lines or CSV from a text file, reading keys and
values from a BigTable, etc.
<p>The concept of <i>split points</i> allows to extend the definitions for dealing with sources
where some records cannot be identified by a unique starting position.
<p>In all cases, all records returned by a source <code>[A, B)</code> must <i>start</i> at or after
<code>A</code>.
<h3>Split points</h3>
<p>Some sources may have records that are not directly addressable. For example, imagine a file
format consisting of a sequence of compressed blocks. Each block can be assigned an offset, but
records within the block cannot be directly addressed without decompressing the block. Let us
refer to this hypothetical format as <i>CBF (Compressed Blocks Format)</i>.
<p>Many such formats can still satisfy the associativity property. For example, in CBF, reading
<code>[A, B)</code> can mean "read all the records in all blocks whose starting offset is in <code>[A, B)</code>".
<p>To support such complex formats, we introduce the notion of <i>split points</i>. We say that a
record is a split point if there exists a position <code>A</code> such that the record is the first
one to be returned when reading the range <code>[A, infinity)</code>. In CBF, the only split points
would be the first records in each block.
<p>Split points allow us to define the meaning of a record's position and a source's range in all
cases:
<ul>
<li>For a record that is at a split point, its position is defined to be the largest <code>A</code>
such that reading a source with the range <code>[A, infinity)</code> returns this record;
<li>Positions of other records are only required to be non-decreasing;
<li>Reading the source <code>[A, B)</code> must return records starting from the first split point
at or after <code>A</code>, up to but not including the first split point at or after <code>B</code>.
In particular, this means that the first record returned by a source MUST always be a split
point.
<li>Positions of split points must be unique.
</ul>
As a result, for any decomposition of the full range of the source into position ranges, the
total set of records will be the full set of records in the source, and each record will be read
exactly once.
<h3>Consumed positions</h3>
As the source is being read, and records read from it are being passed to the downstream
transforms in the pipeline, we say that positions in the source are being <i>consumed</i>. When a
reader has read a record (or promised to a caller that a record will be returned), positions up
to and including the record's start position are considered <i>consumed</i>.
<p>Dynamic splitting can happen only at <i>unconsumed</i> positions. If the reader just returned
a record at offset 42 in a file, dynamic splitting can happen only at offset 43 or beyond, as
otherwise that record could be read twice (by the current reader and by a reader of the task
starting at 43).
<h3>Example</h3>
The following example uses an <a href="../../../../../../org/apache/beam/sdk/io/range/OffsetRangeTracker.html" title="class in org.apache.beam.sdk.io.range"><code>OffsetRangeTracker</code></a> to support dynamically splitting a
source with integer positions (offsets).
<pre><code>
class MyReader implements BoundedReader&lt;Foo&gt; {
private MySource currentSource;
private final OffsetRangeTracker tracker = new OffsetRangeTracker();
...
MyReader(MySource source) {
this.currentSource = source;
this.tracker = new MyRangeTracker&lt;&gt;(source.getStartOffset(), source.getEndOffset())
}
...
boolean start() {
... (general logic for locating the first record) ...
if (!tracker.tryReturnRecordAt(true, recordStartOffset)) return false;
... (any logic that depends on the record being returned, e.g. counting returned records)
return true;
}
boolean advance() {
... (general logic for locating the next record) ...
if (!tracker.tryReturnRecordAt(isAtSplitPoint, recordStartOffset)) return false;
... (any logic that depends on the record being returned, e.g. counting returned records)
return true;
}
double getFractionConsumed() {
return tracker.getFractionConsumed();
}
}
</code></pre>
<h3>Usage with different models of iteration</h3>
When using this class to protect a <a href="../../../../../../org/apache/beam/sdk/io/BoundedSource.BoundedReader.html" title="class in org.apache.beam.sdk.io"><code>BoundedSource.BoundedReader</code></a>,
follow the pattern described above.
<p>When using this class to protect iteration in the <code>hasNext()/next()</code> model, consider the
record consumed when <code>hasNext()</code> is about to return true, rather than when <code>next()</code>
is called, because <code>hasNext()</code> returning true is promising the caller that <code>next()</code>
will have an element to return - so <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#trySplitAtPosition-PositionT-"><code>trySplitAtPosition(PositionT)</code></a> must not split the range in a way
that would make the record promised by <code>hasNext()</code> belong to a different range.
<p>Also note that implementations of <code>hasNext()</code> need to ensure that they call <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#tryReturnRecordAt-boolean-PositionT-"><code>tryReturnRecordAt(boolean, PositionT)</code></a> only once even if <code>hasNext()</code> is called repeatedly, due to the
requirement on uniqueness of split point positions.</div>
</li>
</ul>
</div>
<div class="summary">
<ul class="blockList">
<li class="blockList">
<!-- ========== METHOD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="method.summary">
<!-- -->
</a>
<h3>Method Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Method Summary table, listing methods, and an explanation">
<caption><span id="t0" class="activeTableTab"><span>All Methods</span><span class="tabEnd">&nbsp;</span></span><span id="t2" class="tableTab"><span><a href="javascript:show(2);">Instance Methods</a></span><span class="tabEnd">&nbsp;</span></span><span id="t3" class="tableTab"><span><a href="javascript:show(4);">Abstract Methods</a></span><span class="tabEnd">&nbsp;</span></span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Method and Description</th>
</tr>
<tr id="i0" class="altColor">
<td class="colFirst"><code>double</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getFractionConsumed--">getFractionConsumed</a></span>()</code>
<div class="block">Returns the approximate fraction of positions in the source that have been consumed by
successful <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#tryReturnRecordAt-boolean-PositionT-"><code>tryReturnRecordAt(boolean, PositionT)</code></a> calls, or 0.0 if no such calls have happened.</div>
</td>
</tr>
<tr id="i1" class="rowColor">
<td class="colFirst"><code><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a></code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--">getStartPosition</a></span>()</code>
<div class="block">Returns the starting position of the current range, inclusive.</div>
</td>
</tr>
<tr id="i2" class="altColor">
<td class="colFirst"><code><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a></code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStopPosition--">getStopPosition</a></span>()</code>
<div class="block">Returns the ending position of the current range, exclusive.</div>
</td>
</tr>
<tr id="i3" class="rowColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#tryReturnRecordAt-boolean-PositionT-">tryReturnRecordAt</a></span>(boolean&nbsp;isAtSplitPoint,
<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a>&nbsp;recordStart)</code>
<div class="block">Atomically determines whether a record at the given position can be returned and updates
internal state.</div>
</td>
</tr>
<tr id="i4" class="altColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#trySplitAtPosition-PositionT-">trySplitAtPosition</a></span>(<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a>&nbsp;splitPosition)</code>
<div class="block">Atomically splits the current range [<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--"><code>getStartPosition()</code></a>, <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStopPosition--"><code>getStopPosition()</code></a>) into
a "primary" part [<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--"><code>getStartPosition()</code></a>, <code>splitPosition</code>) and a "residual" part
[<code>splitPosition</code>, <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStopPosition--"><code>getStopPosition()</code></a>), assuming the current last-consumed position
is within [<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--"><code>getStartPosition()</code></a>, splitPosition) (i.e., <code>splitPosition</code> has not been
consumed yet).</div>
</td>
</tr>
</table>
</li>
</ul>
</li>
</ul>
</div>
<div class="details">
<ul class="blockList">
<li class="blockList">
<!-- ============ METHOD DETAIL ========== -->
<ul class="blockList">
<li class="blockList"><a name="method.detail">
<!-- -->
</a>
<h3>Method Detail</h3>
<a name="getStartPosition--">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>getStartPosition</h4>
<pre><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a>&nbsp;getStartPosition()</pre>
<div class="block">Returns the starting position of the current range, inclusive.</div>
</li>
</ul>
<a name="getStopPosition--">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>getStopPosition</h4>
<pre><a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a>&nbsp;getStopPosition()</pre>
<div class="block">Returns the ending position of the current range, exclusive.</div>
</li>
</ul>
<a name="tryReturnRecordAt-boolean-java.lang.Object-">
<!-- -->
</a><a name="tryReturnRecordAt-boolean-PositionT-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>tryReturnRecordAt</h4>
<pre>boolean&nbsp;tryReturnRecordAt(boolean&nbsp;isAtSplitPoint,
<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a>&nbsp;recordStart)</pre>
<div class="block">Atomically determines whether a record at the given position can be returned and updates
internal state. In particular:
<ul>
<li>If <code>isAtSplitPoint</code> is <code>true</code>, and <code>recordStart</code> is outside the current
range, returns <code>false</code>;
<li>Otherwise, updates the last-consumed position to <code>recordStart</code> and returns <code>true</code>.
</ul>
<p>This method MUST be called on all split point records. It may be called on every record.</div>
</li>
</ul>
<a name="trySplitAtPosition-java.lang.Object-">
<!-- -->
</a><a name="trySplitAtPosition-PositionT-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>trySplitAtPosition</h4>
<pre>boolean&nbsp;trySplitAtPosition(<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html" title="type parameter in RangeTracker">PositionT</a>&nbsp;splitPosition)</pre>
<div class="block">Atomically splits the current range [<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--"><code>getStartPosition()</code></a>, <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStopPosition--"><code>getStopPosition()</code></a>) into
a "primary" part [<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--"><code>getStartPosition()</code></a>, <code>splitPosition</code>) and a "residual" part
[<code>splitPosition</code>, <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStopPosition--"><code>getStopPosition()</code></a>), assuming the current last-consumed position
is within [<a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#getStartPosition--"><code>getStartPosition()</code></a>, splitPosition) (i.e., <code>splitPosition</code> has not been
consumed yet).
<p>Updates the current range to be the primary and returns <code>true</code>. This means that all
further calls on the current object will interpret their arguments relative to the primary
range.
<p>If the split position has already been consumed, or if no <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#tryReturnRecordAt-boolean-PositionT-"><code>tryReturnRecordAt(boolean, PositionT)</code></a> call
was made yet, returns <code>false</code>. The second condition is to prevent dynamic splitting
during reader start-up.</div>
</li>
</ul>
<a name="getFractionConsumed--">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>getFractionConsumed</h4>
<pre>double&nbsp;getFractionConsumed()</pre>
<div class="block">Returns the approximate fraction of positions in the source that have been consumed by
successful <a href="../../../../../../org/apache/beam/sdk/io/range/RangeTracker.html#tryReturnRecordAt-boolean-PositionT-"><code>tryReturnRecordAt(boolean, PositionT)</code></a> calls, or 0.0 if no such calls have happened.</div>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<!-- ========= END OF CLASS DATA ========= -->
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar.bottom">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.bottom" title="Skip navigation links">Skip navigation links</a></div>
<a name="navbar.bottom.firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../../../../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../../org/apache/beam/sdk/io/range/OffsetRangeTracker.html" title="class in org.apache.beam.sdk.io.range"><span class="typeNameLink">Prev&nbsp;Class</span></a></li>
<li>Next&nbsp;Class</li>
</ul>
<ul class="navList">
<li><a href="../../../../../../index.html?org/apache/beam/sdk/io/range/RangeTracker.html" target="_top">Frames</a></li>
<li><a href="RangeTracker.html" target="_top">No&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="../../../../../../allclasses-noframe.html">All&nbsp;Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_bottom");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li>Constr&nbsp;|&nbsp;</li>
<li><a href="#method.summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li>Constr&nbsp;|&nbsp;</li>
<li><a href="#method.detail">Method</a></li>
</ul>
</div>
<a name="skip.navbar.bottom">
<!-- -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
</body>
</html>