[kudu-CR] threadpool: token-based task sequencing

["Adar Dembo (Code Review)" <ge...@cloudera.org>]

Hello Dan Burkert, David Ribeiro Alves, Todd Lipcon, Kudu Jenkins,

I'd like you to reexamine a change.  Please visit

    http://gerrit.cloudera.org:8080/6874

to look at the new patch set (#2).

Change subject: threadpool: token-based task sequencing
......................................................................

threadpool: token-based task sequencing

This patch adds task sequencing to util/threadpool. Task sequencing allows
m contexts to share a single pool with n threads while also ensuring that
the pool executes tasks belonging to each context in order. Previously this
was only achievable via "one singleton pool per context", which grossly
inflated the total number of threads and overall state.

A group of tasks are sequenced by submission to a dedicated "slot". A client
obtains exclusive access to a slot via AllocateTokenSlot(), which returns a
"token" that can be used for task submission/waiting. When the token is
destroyed (or Release() is called), the slot is returned to the pool. For
implementation simplicity, clients must wait for a token's outstanding tasks
to complete before destroying their token.

Some notes:
- Slots and tokens are mapped 1-1 so they could theoretically be combined,
  but I prefer this separation of concerns.
- The current implementation requires tokens to have no outstanding tasks
  when they are released. This was a conscious choice made so that token
  destruction (especially when done as part of a larger object graph
  destruct) won't take an unusually long amount of time.
- I evaluated two other implementations. In one, tokens had an implicit
  lifecycle that was automatically managed by the threadpool. While simpler
  for clients, the threadpool was more inefficient with more allocations and
  deallocations in each submission. In the other, token submission was built
  using regular task submission. This afforded a certain separation between
  the "core" of the threadpool and the token logic, but it complicated
  locking and tracking of queued tasks.
- I tried to keep submission (whether token-based or tokenless) fast. Just
  the change from std::list to std::deque for the main queue ought to
  improve performance of tokenless submissions. The next bottleneck is
  likely to be lock contention on the global threadpool lock.

Change-Id: If46dc34212027b6ea5dbc2ead7c7af8be57f2c70
---
M src/kudu/util/debug-util.h
M src/kudu/util/threadpool-test.cc
M src/kudu/util/threadpool.cc
M src/kudu/util/threadpool.h
4 files changed, 708 insertions(+), 70 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/74/6874/2
-- 
To view, visit http://gerrit.cloudera.org:8080/6874
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: If46dc34212027b6ea5dbc2ead7c7af8be57f2c70
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Dan Burkert <da...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <da...@gmail.com>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>