defmulti vs defprotocol?

Question

It seems like both can be used to define functions that you can implement later, with different data types. AFAIK the major difference is that defmulti works on maps and defprotocol works on records.

What other differences there? What are the benefits of using one over the other?

Answer 1

Short version: defmulti is much more flexible and general, while defprotocol performs better.

Slightly longer version:

defprotocol supports dispatch on type, which is like polymorphism in most mainstream programming languages.

defmulti is a more general mechanism where you can dispatch on other things than just a single type. This flexibility comes with a performance penalty.

More on protocols

More on multimethods

Answer 2

Just an addition to cover the motivation, corvuscorax's answer covers the origional question nicely.

Originally Clojure only had multimethods and very early on a lot of thought went into building a dispatch abstraction that could handle all cases very well and would not force people to structure their abstractions around a limitation of the abstractions offered by the language.

As Clojure matured the desire to create "clojure in clojure" required abstractions that where at least in theory capable of producing any bytecode that could be produced by java and thus the need for protocols, a dispatch abstraction that more closely matched native Java.
Clojure has a strong "embrace your platform" ideal and protocols suit this mindset very well.