Lexington, MA, United States
Lexington, MA, United States

Time filter

Source Type

Bender M.A.,Tokutek, Inc. | Gilbert S.,National University of Singapore
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS | Year: 2011

This paper presents a new algorithm for mutual exclusion in which each passage through the critical section costs amortized O(log 2 log n) RMRs with high probability. The algorithm operates in a standard asynchronous, local spinning, shared memory model with an oblivious adversary. It guarantees that every process enters the critical section with high probability. The algorithm achieves its efficient performance by exploiting a connection between mutual exclusion and approximate counting. © 2011 IEEE.


A.Bender M.,Tokutek, Inc. | Farach-Colton M.,Rutgers University | Fekete S.R.,TU Braunschweig | Fineman J.T.,Georgetown University | Gilbert S.,National University of Singapore
Annual ACM Symposium on Parallelism in Algorithms and Architectures | Year: 2013

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This paper shows how to service the requests while minimizing the reallocation cost. We focus on the classic problem of scheduling jobs on a multiprocessor system. Each unit-size job has a time window in which it can be executed. Jobs are dynamically added and removed from the system. We provide an algorithm that maintains a valid schedule, as long as a sufficiently feasible schedule exists. The algorithm reschedules only O(min{log*n, log*A}) jobs for each job that is inserted or deleted from the system, where n is the number of active jobs and △ is the size of the largest window. © 2013 ACM.


Alistarh D.,Ecole Polytechnique Federale de Lausanne | Bender M.A.,Tokutek, Inc. | Gilbert S.,National University of Singapore | Guerraoui R.,Ecole Polytechnique Federale de Lausanne
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS | Year: 2012

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m + p log p log2 m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m + p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the Ω(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks. © 2012 IEEE.


Grant
Agency: National Science Foundation | Branch: | Program: SBIR | Phase: Phase II | Award Amount: 500.00K | Year: 2011

This Small Business Innovation Research (SBIR) Phase II project will apply multithreading techniques to provide multi-terabyte (and larger) high-performance databases in MySQL. The company has developed a highperformance storage engine for MySQL, which maintains indexes on live data 100 times faster than current commonly-used structures. The technology solves the problem of maintaining indexes on large databases in the face of high trickle-load indexing rates. In Phase I, the company developed a multithreaded bulk loader to solve the problem of how to load data quickly. The next significant research problems for large MySQL databases are to allow online, or "hot", schema changes in which, for example, an index can be added without taking the database down, and to use multithreading to speed up joins and reductions so that the large data sets can be queried quickly. In this project, the researchers will investigate the use of multithreading to support hot indexing and parallel joins reductions. If successful, multi-terabyte and larger databases will be manageable and fast on modest hardware, and the hardware will be scalable both with CPU cores and disks. The broader impact of this work is driven by faster, cheaper, lower-power on-disk storage. Organizations that have very large databases will be able to use much less hardware, both saving money and reducing power consumption significantly. Currently many application areas do not employ databases because their performance is too slow. Speeding up databases by two orders-of-magnitude can help grow the market. Currently, many organizations fail to make good use of the data they have collected because they cannot manage it, index it, or query it fast enough to be useful. Applications in finance, retail, homeland security, telecommunications, and scientific computing will benefit from improved manageability and performance. As users' appetite for data continues to outstrip the availability of fast memory, organizing multithreaded queries on disk-based data for performance will continue to grow in importance.


Grant
Agency: National Science Foundation | Branch: | Program: SBIR | Phase: Phase I | Award Amount: 150.00K | Year: 2010

This Small Business Innovation Research Phase I project will investigate techniques for implementing high-performance databases on multi-core computers by focusing on how to support concurrent activity with provably good thread scheduling in "Fractal Tree" databases. Today's databases suffer from resource imbalances between storage bandwidth, disk-seek rate, and CPU core capacity, leading to underperformance, cumbersome workarounds, and energy inefficiency. The company has developed a high-performance storage engine for MySQL that maintains indexes on live data 100 times faster than traditional engines. The approach employs cache-oblivious Fractal-Tree indexes, which scale with storage bandwidth rather than seek rate, thus addressing the imbalance between bandwidth and disk-seek rate. If successful, this research will produce a database implementation that for each query that either saturates the CPU cores, saturates disk bandwidth, or consumes all of the inherent parallelism in the query. The target market comprises organizations that have very large databases and a workload dominated by insertions and queries. There are many application areas that do not employ databases because their performance is too slow. Orders-of-magnitude speedup for databases can help grow the market. Applications in finance, retail, homeland security, telecommunications, and scientific computing will benefit from high-performance databases. Furthermore the researchers hope to lead all database implementers into the multi-core realm. The proposed research will further the understanding of how to schedule database queries when data is well laid out on disk. As users' appetite for data continues to outstrip the availability of fast memory, organizing multithreaded queries on disk-based data for performance will only grow in importance.


Grant
Agency: NSF | Branch: Standard Grant | Program: | Phase: SMALL BUSINESS PHASE II | Award Amount: 425.00K | Year: 2011

This Small Business Innovation Research (SBIR) Phase II project will apply multithreading techniques to provide multi-terabyte (and larger) high-performance databases in MySQL. The company has developed a highperformance storage engine for MySQL, which maintains indexes on live data 100 times faster than current commonly-used structures. The technology solves the problem of maintaining indexes on large databases in the face of high trickle-load indexing rates. In Phase I, the company developed a multithreaded bulk loader to solve the problem of how to load data quickly. The next significant research problems for large MySQL databases are to allow online, or hot, schema changes in which, for example, an index can be added without taking the database down, and to use multithreading to speed up joins and reductions so that the large data sets can be queried quickly. In this project, the researchers will investigate the use of multithreading to support hot indexing and parallel joins reductions.

If successful, multi-terabyte and larger databases will be manageable and fast on modest hardware, and the hardware will be scalable both with CPU cores and disks. The broader impact of this work is driven by faster, cheaper, lower-power on-disk storage. Organizations that have very large databases will be able to use much less hardware, both saving money and reducing power consumption significantly. Currently many application areas do not employ databases because their performance is too slow. Speeding up databases by two orders-of-magnitude can help grow the market. Currently, many organizations fail to make good use of the data they have collected because they cannot manage it, index it, or query it fast enough to be useful. Applications in finance, retail, homeland security, telecommunications, and scientific computing will benefit from improved manageability and performance. As users appetite for data continues to outstrip the availability of fast memory, organizing multithreaded queries on disk-based data for performance will continue to grow in importance.


News Article | January 26, 2015
Site: www.zdnet.com

MySQL services firm Percona says the integration of Tokutek's database storage engine into its popular Percona Server MySQL fork will give users substantially better performance and compression. The two firms have joined forces to offer Percona Server 5.6 with the option of TokuDB as a drop-in replacement for the standard InnoDB storage engine. The resulting read-write performance shows a 20 times improvement over InnoDB, while data compression is up between five and 25 times, according to Percona. "TokuDB is the only other MySQL open-source transactional storage engine, besides InnoDB, which I consider production-ready. It has truly innovative fractal trees technology and is also a very solid piece of engineering," Percona CEO Peter Zaitsev said. "There are many demanding workloads that MySQL developers can use to evaluate the TokuDB storage engine as an alternative to InnoDB. Having TokuDB available with Percona Server makes this comparison easier." Using a master-system with Percona Server, TokuDB and a PCIe card for the beta release of its Percona Cloud Tools, Percona said it achieved 500 million data-point insertions per day and hundreds of monitored instances. It said those figures, together with others collected since the beta release, show the potential of TokuDB to help Percona Server users with large datasets and high read-write workloads, such as those found in applications running real-time advertising analytics, social media, and e-commerce. Percona Server is an open-source MySQL alternative, which the company says has been downloaded 1.4 million times and is optimised for cloud computing, NoSQL access, and hardware such as SSD and Flash storage. Tokutek ascribes the speed of open-source TokuDB to its use of a fractal-tree index data structure to aggregate database access requests at base nodes intelligently. The result is greater compression and reduced memory use. "Many MySQL applications are ingesting very large volumes of data at ingestion rates never imagined 40 years ago, when B-tree indexing was conceived," Tokutek CEO John Partridge said in a statement. "With a modern fractal-tree indexing engine, MySQL applications can scale up to meet the needs of these applications much more cost-effectively than alternative approaches." Percona is also offering support for Percona Server with TokuDB, together with consulting services for companies that want to use the TokuDB storage engine in their MySQL environments.


News Article | August 20, 2010
Site: www.xconomy.com

Tokutek’s patent-pending technology is a result of ten years of research and development by experts in cache-oblivious algorithmics and is used to accelerate key database operations by orders of magnitude. Tokutek’s solution is based on a revolutionary new Fractal Tree™ technology. The Tokutek solution plugs into the back-end of any database, allowing operating practices to continue without change while the performance of the system improves dramatically.


News Article | November 21, 2012
Site: www.xconomy.com

Tokutek’s patent-pending technology is a result of ten years of research and development by experts in cache-oblivious algorithmics and is used to accelerate key database operations by orders of magnitude. Tokutek’s solution is based on a revolutionary new Fractal Tree technology. The Tokutek solution plugs into the back-end of any database, allowing operating practices to continue without change while the performance of the system improves dramatically.

Loading Tokutek, Inc. collaborators
Loading Tokutek, Inc. collaborators