From owner-freebsd-arch@FreeBSD.ORG Tue Sep 16 19:38:27 2014 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 9C275C27 for ; Tue, 16 Sep 2014 19:38:27 +0000 (UTC) Received: from khavrinen.csail.mit.edu (khavrinen.csail.mit.edu [IPv6:2001:470:8b2d:1e1c:21b:21ff:feb8:d7b0]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "khavrinen.csail.mit.edu", Issuer "Client CA" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 5D44010C for ; Tue, 16 Sep 2014 19:38:27 +0000 (UTC) Received: from khavrinen.csail.mit.edu (localhost [127.0.0.1]) by khavrinen.csail.mit.edu (8.14.7/8.14.7) with ESMTP id s8GJcP7f029344 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL CN=khavrinen.csail.mit.edu issuer=Client+20CA) for ; Tue, 16 Sep 2014 15:38:25 -0400 (EDT) (envelope-from wollman@khavrinen.csail.mit.edu) Received: (from wollman@localhost) by khavrinen.csail.mit.edu (8.14.7/8.14.7/Submit) id s8GJcOVi029341; Tue, 16 Sep 2014 15:38:24 -0400 (EDT) (envelope-from wollman) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <21528.37296.395002.628214@khavrinen.csail.mit.edu> Date: Tue, 16 Sep 2014 15:38:24 -0400 From: Garrett Wollman To: freebsd-arch@freebsd.org Subject: OpLog: a library for scaling update-heavy data structures X-Mailer: VM 7.17 under 21.4 (patch 22) "Instant Classic" XEmacs Lucid X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.4.3 (khavrinen.csail.mit.edu [127.0.0.1]); Tue, 16 Sep 2014 15:38:25 -0400 (EDT) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 16 Sep 2014 19:38:27 -0000 I just wanted to point out the following recent publication by people who happen to work in the same building as I do: OpLog: a library for scaling update-heavy data structures Author: Boyd-Wickizer, Silas; Kaashoek, M. Frans; Morris, Robert; Zeldovich, Nickolai Citable URI: http://hdl.handle.net/1721.1/89653 Other Contributors: Parallel and Distributed Operating Systems Advisor: Nickolai Zeldovich Date Issued: 2014-09-16 Abstract: Existing techniques (e.g., RCU) can achieve good multi-core scaling for read-mostly data, but for update-heavy data structures only special-purpose techniques exist. This paper presents OpLog, a general-purpose library supporting good scalability for update-heavy data structures. OpLog achieves scalability by logging each update in a low-contention per-core log; it combines logs only when required by a read to the data structure. OpLog achieves generality by logging operations without having to understand them, to ease application to existing data structures. OpLog can further increase performance if the programmer indicates which operations can be combined in the logs. An evaluation shows how to apply OpLog to three update-heavy Linux kernel data structures. Measurements on a 48-core AMD server show that the result significantly improves the performance of the Apache web server and the Exim mail server under certain workloads. URI: http://hdl.handle.net/1721.1/89653 Series/Report no.: MIT-CSAIL-TR-2014-019 -GAWollman