Frequently Asked Questions about Ken
- What is Ken?
- "Ken" refers to both a simple rollback-recovery
protocol and its implementation as a C library. Both are
described in Yoo et al., "Composable Reliability for
Asynchronous Systems," 2012 USENIX Annual Technical
Conference. Ken (in both senses of the term) facilitates
reliable distributed application development. The name
and protocol both come
from Waterken, the
Java platform that first implemented the Ken protocol.
Waterken provides different programming abstractions
compared to the C implementation of Ken.
- How does Ken work?
- One way to think about Ken is that it starts with the
"actor" or "communicating event loop"
distributed programming paradigm and adds a twist: Each
iteration of each event loop is an ACID transaction. It
turns out that remarkably strong global correctness
guarantees follow from transactional event loops.
- What kinds of guarantees does Ken provide?
- Tolerated failures (crash-restart failures such as power
outages and OS kernel panics) cannot corrupt or destroy
local process state nor messages between Ken processes
in a distributed system. Messages are delivered exactly
once in FIFO order between each sender-receiver pair.
Ken furthermore guarantees "distributed
consistency" in the sense that a distributed system
can't end up in a causality-violating state wherein one
process remembers having received a message but, due to
crash-induced amnesia, no other process remembers having
sent it. More importantly, Ken masks failures in
in the sense that an external observer can't infer the
occurrence of tolerated failures within a Ken-based
distributed system by observing the system's collective
outputs. Finally, Ken's global correctness guarantees
compose when independently developed Ken-based
distributed systems are integrated, even when the
integration was not foreseen nor planned for.
- Such strong guarantees must require substantial programmer effort, no?
- On the contrary, Ken completely automates reliability.
The Ken application programmer takes no explicit steps to
ensure reliability other than writing atop the Ken
platform. For example, the programmer does not
specify the beginning and end of transactions. Apart from
programming in Ken fashion, achieving Ken's guarantees is
effortless and foolproof.
- What is it like to program a Ken application?
- You write a handler function that processes incoming
messages and inputs. The handler function can allocate
and de-allocate data on a persistent heap, and the handler
can send messages to other Ken processes and emit outputs.
There are a few other facilities provided but Ken is quite
simple. If you're familiar with existing event-driven
programming paradigms, e.g., GUI programming or AJAX, the
learning curve will be gentle.
- What kinds of applications is Ken for?
- Distributed applications that must prevent crash-restart
failures from causing incorrect behavior or
corrupting/destroying application state. Specific
programs that we have built atop Ken and
include distributed hash tables, a distributed graph
analysis program, and a distributed e-commerce
scenario. In our experience, programming in Ken is
convenient, and Ken is a versatile platform.
- But is there a specific "sweet spot" use case?
- Anecdotally, it appears that programmers confronted with
the requirement to protect both local process state and
inter-process messages from crashes frequently employ
message queuing middleware for the latter and a
relational database for the former, even when
relational DB features aren't fundamentally required.
The RDBMS is used simply to keep application state safe,
because writing homebrew checkpointing and recovery code
atop an ordinary file system is too tedious and
error-prone. In the RDBMS-plus-MQ pattern, it is the
programmer's responsibility to orchestrate the delicate
interplay between two sets of operations: transactions
that evolve the database from one consistent state to the
next, and operations that ensure reliable messages. The
slightest mistake (e.g., failing to record an outbound
message in the database) can leave the application
vulnerable to crash-induced distributed inconsistency.
Furthermore the individual reliability guarantees of
independently developed applications written in the
RDBMS-plus-MQ pattern are unlikely to compose without
additional programmer effort. Ken automates both process
state reliability and message reliability, masks failures
globally, and preserves global correctness under
- What about offbeat/unforeseen uses?
- Perhaps the most remarkable unforeseen use of Ken occurred
in July 2012, when a small group of developers integrated
Ken into a mature, full-featured Scheme interpreter. The
group reports that this took them only one day, and
they received zero assistance from the Ken team.
The result, "SchemeKen," is to the best of their
knowledge the first crash-resilient Scheme interpreter.
In August 2012 the Vrije Universiteit Brussel
SchemeKen as Open Source software.
- Is Ken an alternative to conventional databases?
- Sometimes. If your goal is to protect the integrity of
application state from crash-restart failures, and if you
want to update application state via ACID transactions,
then Ken might be a reasonable way to achieve these goals.
Ken is especially suitable when you want to store and
manipulate your data in arbitrary C/C++ data structures
rather than in relational format. A conventional database
is a better choice if you require features such as
relational algebra, schemas, and SQL.
- Is Ken an alternative to reliable-messaging middleware?
- Sometimes. Ken provides only a small subset of the
functionality of a full-featured message queuing
middleware package. Specifically, Ken provides only
reliable exactly-once message delivery in FIFO order
between each sender and receiver pair. If that's your
only message reliability requirement, Ken might be a
reasonable way to fulfill it, particularly if Ken's other
features address your other requirements.
- Are Ken transactions fast?
- That depends on the storage medium that provides data
durability. On an enterprise-class RAID system backed by
15K RPM spinning disks, Ken transactions take a few
milliseconds; ACID transactions in conventional databases
take roughly as long atop the same storage medium.
Flash-based SSDs would likely be faster, and emerging
non-volatile memory (NVRAM) would likely be faster still.
Regardless of the storage medium, data durability to
preserve data integrity entails a performance overhead.
Ken currently strives for reasonable performance in two
ways: Ken overlaps execution of the next iteration of
the event loop with committing the previous iteration's
checkpoint to durable storage; and Ken's checkpoints
- Tell me about the alternate "Go-Back-N" transport.
- Ken's default UDP-based transport retransmits messages
with a simple exponential backoff until an ACK is
received. This is fine for client-server interactions
and it's also fine if programmers use the
ken_ackd() interface to avoid overloading a
recipient with too many messages. The MaceKen team at
Purdue University has contributed an alternative UDP-based
transport that implements the "Go-Back-N"
re-transmission policy. The alternative transport is
available as a replacement for the default
kenext.c file. The Go-Back-N implementation
has been tested and used at Purdue but has not been
extensively tested in Palo Alto. It may offer superior
performance and/or convenience in some situations.
- Can you make Ken faster by relaxing its guarantees?
- Yes, but our intention for the foreseeable future is to
maintain Ken's correctness guarantees rather than weaken
them for the sake of performance.
- What about trading simplicity for speed?
- Maybe some day; probably not soon. Complexifying the
programming model or the implementation wouldn't help
reliability, which is a higher priority.
- Can I use Ken with C++, particularly STL?
- Yes, if you're careful. Ken is implemented in C89, but we
have successfully integrated Ken into the Mace distributed
systems toolkit from Purdue University, which is written
in C++ and uses STL extensively. It can be done.
As of August 2012 the distribution includes a sample Ken
application that uses C++ STL.
- What kinds of OSes can Ken run on?
- Ken is intended to be portable across POSIX-compliant
systems. It has been tested on HP-UX and on several
distributions of Linux.
- What about Mac OS X?
- Members of the Ken community have reported that Ken can be
made to work successfully on Mac OS X, with a bit of
effort. Mac OS X appears to have a few POSIX
non-compliance issues that complicate compilation, and
special compilation may be required to ensure successful
recovery. Furthermore the default file system reportedly
doesn't support sparse files, which Ken requires. The
workaround suggestions we've heard include: change the
code to catch SIGBUS rather than SIGSEGV when memory pages
are dirtied; use fcntl(F_FULLSYNC) instead of fsync()
because the latter doesn't provide durability on Mac OS X;
and "run Ken on a separate sparse disk image"
(not yet tested) or reduce the size of Ken's state blob to
circumvent the lack of sparse file support (tested
successfully). Compiling with "gcc -Xlinker
-no_pie" reportedly fixes an issue with mmap() that
might be due to address space layout randomization. These
suggestions come from the Ken community and have not been
evaluated by the core Ken team because we lack Mac OS X
machines. We have received a patch that embodies several
of the above workarounds; write to us if you'd like to try
it. (A much better solution would be for Mac OS X to
support POSIX compliance, at least as an option, if it
- Which Open Source license covers Ken?
- Can you help me get started with Ken?
- The Ken team will try to help those who have tried to
help themselves, particularly if you're committed to
building something useful atop Ken. We will also try
to leverage support from the Ken user and developer
community. If you're interested in improving the Ken
infrastructure rather than developing applications
atop Ken, we can try to work together.