A lightning fast, transactional, file-based FIFO for Android and Java.

Related tags

Data Structures tape
Overview

Tape by Square, Inc.

Tape is a collection of queue-related classes for Android and Java.

QueueFile is a lightning-fast, transactional, file-based FIFO. Addition and removal from an instance is an O(1) operation and is atomic. Writes are synchronous; data will be written to disk before an operation returns. The underlying file is structured to survive process and even system crashes and if an I/O exception is thrown during a mutating change, the change is aborted.

NOTE: The current implementation is built for file systems that support atomic segment writes (like YAFFS). Most conventional file systems don't support this; if the power goes out while writing a segment, the segment will contain garbage and the file will be corrupt.

An ObjectQueue represents an ordering of arbitrary objects which can be backed either by the filesystem (via QueueFile) or in memory only.

Download

Download the latest JAR or grab via Maven:

<dependency>
  <groupId>com.squareup.tape2</groupId>
  <artifactId>tape</artifactId>
  <version>2.0.0-beta1</version>
</dependency>

or Gradle:

compile 'com.squareup.tape2:tape:2.0.0-beta1'

Snapshots of the development version are available in Sonatype's snapshots repository.

Usage

Create a QueueFile instance.

File file = // ...
QueueFile queueFile = new QueueFile.Builder(file).build();

Add some data to the queue to the end of the queue. QueueFile accepts a byte[] of arbitrary length.

queueFile.add("data".getBytes());

Read data at the head of the queue.

byte[] data = queueFile.peek();

Remove processed elements.

// Remove the eldest element.
queueFile.remove();

// Remove multiple elements.
queueFile.remove(n);

// Remove all elements.
queueFile.clear();

Read and process multiple elements with the iterator API.

Iterator<byte[]> iterator = queueFile.iterator();
while (iterator.hasNext()) {
  byte[] element = iterator.next();
  process(element);
  iterator.remove();
}

While QueueFile works with byte[], ObjectQueue works with arbitrary Java objects with a similar API. An ObjectQueue may be backed by a persistent QueueFile, or in memory. A persistent ObjectQueue requires a Converter to encode and decode objects.

// A persistent ObjectQueue.
ObjectQueue<String> queue = ObjectQueue.create(queueFile, converter);

// An in-memory ObjectQueue.
ObjectQueue<String> queue = ObjectQueue.createInMemory();

Add some data to the queue to the end of the queue.

queue.add("data");

Read data at the head of the queue.

// Peek the eldest elements.
String data = queue.peek();

// Peek the eldest `n` elements.
List<String> data = queue.peek(n);

// Peek all elements.
List<String> data = queue.asList();

Remove processed elements.

// Remove the eldest element.
queue.remove();

// Remove multiple elements.
queue.remove(n);

// Remove all elements.
queue.clear();

Read and process multiple elements with the iterator API.

Iterator<String> iterator = queue.iterator();
while (iterator.hasNext()) {
  String element = iterator.next();
  process(element);
  iterator.remove();
}

Converter

A Converter encodes objects to bytes and decodes objects from bytes.

/** Converter which uses Moshi to serialize instances of class T to disk. */
class MoshiConverter<T> implements Converter<T> {
  private final JsonAdapter<T> jsonAdapter;

  public MoshiConverter(Moshi moshi, Class<T> type) {
    this.jsonAdapter = moshi.adapter(type);
  }

  @Override public T from(byte[] bytes) throws IOException {
    return jsonAdapter.fromJson(new Buffer().write(bytes));
  }

  @Override public void toStream(T val, OutputStream os) throws IOException {
    try (BufferedSink sink = Okio.buffer(Okio.sink(os))) {
      jsonAdapter.toJson(sink, val);
    }
  }
}

License

Copyright 2012 Square, Inc.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

   http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Comments
  • Prevent corruption when expanding a perfectly saturated queue

    Prevent corruption when expanding a perfectly saturated queue

    If a QueueFile has no unused space, and the first element begins somewhere other than at the beginning of the queue, elements at the beginning of the file are not copied after the existing elements as the file is expanded. The next peek() may then return no data or corrupted data.

    This change contains a test to demonstrate the flaw and simple fix.

    opened by chetbox 10
  • Drop FileException, prefer (checked) IOException instead

    Drop FileException, prefer (checked) IOException instead

    FileException was an unchecked wrapper around IOException.

    Change the ObjectQueue interface to indicate it throws IOException, and change example users of the interface to handle (well, throw) when IOExceptions occur.

    Fixes issue #35.

    opened by evmar 10
  • C port of QueueFile

    C port of QueueFile

    Please have a look at my port of QueueFile.

    The comment formats are a little inconsistent - I can fix them up depending on whether we use Doxygen or some other auto doc tool.

    The Makefile will evolve...

    opened by bitmanlger 8
  • Early abort for forEach, peek multiple

    Early abort for forEach, peek multiple

    Adds the capability to peek at multiple entries at the head of the queue. I didn't have to change QueueFile, as its forEach already can avoid reading bytes, but this optimization to abort early saves some object creation.

    Not a breaking API change.

    opened by pforhan 7
  • Changes QueueFile#ringRead to use the offset parameter in all cases

    Changes QueueFile#ringRead to use the offset parameter in all cases

    When trying to use forEach and an ElementReader to read data into offset positions of a single byte array, I noticed that the bytes starting at offset 0 would be repeatedly overwritten, rather than subsequent elements' data being read into the expected offsets of my byte array.

    I believe the culprit is the use of the constant offset 0 in the first branch of the conditional logic in QueueFile#ringRead. I've included a test that should fail against the current logic in master, and pass with my changes.

    Thanks for your time and consideration!

    opened by mfurtak 7
  • Replace RuntimeException with new UncheckedIOException

    Replace RuntimeException with new UncheckedIOException

    This is the same as Java 8's UncheckedIOException. We've copied it so that we can maintain compatibility with Java 7.

    Other options:

    • Continue to throw RuntimeException with a nicer error message (i.e. remove the "todo")
    • Create a custom exception Tape class like we had in tape v1 (ref #154)

    I think this is nicer than the second as it keeps the ergonomics of Java 8 for those stuck on having to support Java 7.

    opened by f2prateek 6
  • Unit test errors on Windows due to files being left open

    Unit test errors on Windows due to files being left open

    Added close calls to tests where files were being left open. This resulted in test case errors on Windows when files were deleted in cleanup (Did not occur on Linux).

    Closes #177.

    opened by chrissmith-mcafee 6
  • File handle leak when exception in QueueFile construction

    File handle leak when exception in QueueFile construction

    Fixed issue where a file handle was being leaked when an exception occurred during construction of QueueFile.

    This issue was discovered when attempting to delete the file associated with the QueueFile. The file was locked and couldn't be deleted (this only occurs on Windows as Linux does not prevent deletion).

    In the fix, if any exceptions occur during the construction of QueueFile, the random access file is closed before returning.

    opened by chrissmith-mcafee 6
  • Retrieve All Tasks

    Retrieve All Tasks

    Expose an API that allows clients to retrieve all elements in the queue, perform an operation, and clear the queue in one atomic operation.

    A use case would be when the server can accept a batched operation, and it's more network efficient to perform one large post request, over numerous smaller ones.

    This would simply add the ability to see all tasks in the queue and clear the queue. Essentially combining #25 and #26.

    opened by f2prateek 6
  • On file resize, only zero old memory chunks after header has been written

    On file resize, only zero old memory chunks after header has been written

    There is that very unlike corner case when things crash after the wrapped chunk has been moved to oldFileLength, but the header has not been updated yet, causing file corruption.

    Zero-ing the old interval after the header has been written fixes this.

    opened by paulo-raca 5
  • Add QueueFile builder

    Add QueueFile builder

    Let's wait until we finish the v2 format changes so we can add options for those in the builder as well.

    There's some awkwardness of using the builder with the ObjectQueue API. Either we

    1. Duplicate the builder for the file object queue.
    2. Let users construct a QueueFile manually and pass it into the factory method create(QueueFile queueFile, Converter<T> converter). This approach makes it awkward for keeping the raw file reference for error reporting.
    opened by f2prateek 5
  • Split transfer data because of the size limit of FileChannelImpl

    Split transfer data because of the size limit of FileChannelImpl

    What changes

    • Split the data that need to transfer into pieces with a maximum size Integer.MAX_VALUE
    • Add a unit test to cover the case of transferring large data (more than 2GB)

    Why needs these changes

    In the underlying FileChannelImpl, it can transfer at most 2 GB data at a time, which will cause an error if we transfer more than 2 GB data directly: https://github.com/square/tape/blob/445cd3fd0a7b3ec48c9ea3e0e86663fe6d3735d8/tape/src/main/java/com/squareup/tape2/QueueFile.java#L462-L464

    opened by wecharyu 6
  • Fail to Remove from FileObjectQueue

    Fail to Remove from FileObjectQueue

    Similar to this issue, we are also seeing exceptions while removing the object from the Queue.

    java.lang.ArrayIndexOutOfBoundsException:length=32; regionStart=0; regionLength=-2053298290
    libcore.util.throwsIfOutOfBounds ( ArrayUtils .java :40)
    libcore.io.read ( IoBridge .java :508)
    java.io.readBytes ( RandomAccessFile .java :387)
    java.io.read ( RandomAccessFile .java :416)
    java.io.readFully ( RandomAccessFile .java :475)
    com.squareup.tape2.ringRead ( QueueFile .java :350)
    com.squareup.tape2.remove ( QueueFile .java :631)
    com.squareup.tape2.remove ( FileObjectQueue .java :51)
    

    Impacted users are considerably low (a few per millions). However, when it happens, user will stuck in the state and app crashes whenever it tries to perform the same execution again. Therefore, the raw crash count is actually now low.

    What's the best way to handle this? If we can't fix the root, we might as well just drop off all the records in the Queue and give it a clean start. Given the error happens at the time of removal, it seems unlikely we can do it tough.

    Note: we've only found this issue from Android 9 and 10 by far.

    opened by csv8674xn 0
  • DBR-204 support writing asynchronously

    DBR-204 support writing asynchronously

    I see that because of being reliable, writers need to be synchronous. Although in case that the performance has higher priority than reliability so the writer could be asynchronous

    opened by parian66 0
  • Consider DequeFile

    Consider DequeFile

    There's not much reason to be solely a queue when behaving like a stack is trivial. We should consider making QueueFile a DequeFile, perhaps with stack-only or queue-only interfaces? Same for the object mapping layer.

    Maybe we ship master as is for Tape 2 and then make this Tape 3. Or we could change QueueFile to an interface so that we can add StackFile and DequeFile later.

    enhancement 
    opened by JakeWharton 1
  • Issues while writing and reading from different daemons with flock

    Issues while writing and reading from different daemons with flock

    I understand that with tape I need to use an external lock if I am accessing object queue file from two different daemons. I use flock to lock the file before I do any of the operations (add, peek, remove). My writer daemon produces slower than the reader, so once the reader consumes everything, it reports the queue size as zero and continues to do so even when the writer writes after some mili seconds. If I create the object queue newly, it gets the size right, but object converter doesn't work properly, looks like the file is corrupted somewhat. Any solution you can suggest here?

    opened by ABaligar 0
  • QueueFileTest.testSaturatedFileExpansionMovesElements hanged

    QueueFileTest.testSaturatedFileExpansionMovesElements hanged

    modified variable QueueFile.INITIAL_LENGTH from 4096 to 2048 , then run the test

    channel.transferTo(headerLength, count, channel) != count
    

    get hanged

    opened by realvalkyrie 3
A fast, simple persistent queue written in Java

Ladder Introduction Ladder is a lightning fast persistent queue written in Java. Usage Installation // TODO publish to Maven Central Create persistent

null 6 Sep 9, 2022
gRPC and protocol buffers for Android, Kotlin, and Java.

Wire “A man got to have a code!” - Omar Little See the project website for documentation and APIs. As our teams and programs grow, the variety and vol

Square 3.9k Sep 30, 2022
A FlinkSQL studio and real-time computing platform based on Apache Flink

Dinky 简介 实时即未来,Dinky 为 Apache Flink 而生,让 Flink SQL 纵享丝滑,并致力于实时计算平台建设。 Dinky 架构于 Apache Flink,增强 Flink 的应用与体验,探索流式数仓。即站在巨人肩膀上创新与实践,Dinky 在未来批流一体的发展趋势下潜

null 1.3k Sep 26, 2022
Facebook Clone created using java based on Graph data Structure

Facebook Clone Facebook Clone created using java based on Graph data Structure Representation of Social Media using Graph Data Structure in Java It is

yogita pandurang chaudhari 1 Jan 16, 2022
This repository contains codes for various data structures and algorithms in C, C++, Java, Python, C#, Go, JavaScript and Kotlin.

Overview The goal of this project is to have codes for various data structures and algorithms - in C, C++, Java, Python, C#, Go, JavaScript and Kotlin

Manan 25 Mar 2, 2022
This repository contains all the Data Structures and Algorithms concepts and their implementation in several ways

An Open-Source repository that contains all the Data Structures and Algorithms concepts and their implementation in several ways, programming questions and Interview questions. The main aim of this repository is to help students who are learning Data Structures and Algorithms or preparing for an interview.

Pranay Gupta 628 Sep 26, 2022
A repository that contains Data Structure and Algorithms coded on Java

A repository that contains Data Structure and Algorithms coded on Java . It will also contain solutions of questions from Leetcode.

Akshat Gupta 1 Jan 10, 2022
🎓☕ Repository of lessons and exercises from loiane.training's course on data structure with Java

☕ Curso estrutura de dados com Java by @loiane.training Repositório com as aulas e exercícios do curso de estrutura de dados com Java da loiane.traini

Leticia Campos 2 Feb 1, 2022
Worker-queue implementation on top of Java and database

Database Queue Library provides worker-queue implementation on top of Java and database. Fintech company YooMoney uses db-queue in cases where reliabi

null 16 Sep 22, 2022
Data structures and algorithms exercises in java

Data structure and algorithms in Java About The Project [] In this repository you can find examples of data structure exercises solved in java and som

Luis Perez Contreras 1 Nov 25, 2021
Data structures & algorithms implemented in Java and solutions to leetcode problems.

Hello, World! ?? Hey everyone, I'm Sharad ☃ , and I'm a Software Engineer ?? at eGain! This repository ?? is all about data structures & algorithms an

Sharad Dutta 13 Aug 11, 2022
Union, intersection, and set cardinality in loglog space

HyperMinHash-java A Java implementation of the HyperMinHash algorithm, presented by Yu and Weber. HyperMinHash allows approximating set unions, inters

LiveRamp 48 Sep 22, 2022
Popular Algorithms and Data Structures implemented in popular languages

Algos Community (college) maintained list of Algorithms and Data Structures implementations. Implemented Algorithms Algorithm C CPP Java Python Golang

IIIT Vadodara Open Source 1k Oct 2, 2022
Flink Table Store is a unified streaming and batch store for building dynamic tables on Apache Flink

Flink Table Store is a unified streaming and batch store for building dynamic tables on Apache Flink

The Apache Software Foundation 280 Oct 1, 2022
Algorithm and Data Structrue

SWE241P Algorithm and Data Structure Ex1 TreeSet with Red-Black Tree HashSet LinkedList Set Ex 2 Selection Sort Insertion Sort Heap Sort Merge Sort Qu

Tiger Liu 4 Apr 13, 2022
A Persistent Java Collections Library

PCollections A Persistent Java Collections Library Overview PCollections serves as a persistent and immutable analogue of the Java Collections Framewo

harold cooper 700 Sep 21, 2022
A better compressed bitset in Java

RoaringBitmap Bitsets, also called bitmaps, are commonly used as fast data structures. Unfortunately, they can use too much memory. To compensate, we

Roaring bitmaps: A better compressed bitset 2.8k Oct 3, 2022
Example of implementing data structures in Java

Data Structures Example of implementing data structures in Java Implemented data structure : Queue Stack Linked List Binary Search Tree (BST) Trie Hea

Ismaïl BENHALLAM 2 Sep 27, 2021
Material de apoio da turma de introdução ao JAVA da Let's Code

Introdução ao Java Esse repositório foi criado com o intuito de servir como material de apoio ao módulo de Introdução a Java da Let's Code. Sumário Li

Bruno Pereira Pinho 4 May 12, 2022