   # Encodes an instance of `type`. Returns an iodata instead of a binary.
   # Made public for testing.
   @doc false
-  def encode_type(data, type)
-
-  def encode_type(str, :string) do
+  def encode_type(data, type, offset \\ nil)
+
+  def encode_type(str, :string, _) when is_binary(str) do
     [:small_ints.encode_zigzag_varint(byte_size(str)), str]
   end
 
-  def encode_type(i, type) when type in [:sint16, :sint32, :sint64] do
+  def encode_type(i, type, _) when type in [:sint16, :sint32, :sint64] and is_integer(i) do
     :small_ints.encode_zigzag_varint(i)
   end
 
-  defp field_name(field) when is_record(field, :named_field), do: named_field(field, :name)
+  def encode_type(map, :embedded_map, offset) when is_map(map) do
+    offset = offset + map_header_offset(map)
+
+    {keys, values, _} = Enum.reduce map, {[], [], offset}, fn({key, value}, {ks, vs, index}) ->
+      typed_field(value: value, type: type) = value
+      encoded_value = encode_type(value, type)
+      key = [type_to_int(:string), encode_type(key, :string), <<index :: 32-signed>>, type_to_int(type)]
+      index = index + IO.iodata_length(encoded_value)
+      {[key|ks], [encoded_value|vs], index}
+    end
+
+    nkeys = map |> Map.keys |> Enum.count |> :small_ints.encode_zigzag_varint
+
+    [nkeys, keys, values]
+  end
+
+  defp map_header_offset(map) do
+    keys = Map.keys(map)
+
+    # `6` means 4 bytes for the pointer to the data, 1 byte for the data type,
+    # and 1 byte for the key type.
+    nkeys       = :small_ints.encode_zigzag_varint(Enum.count(keys))
+    key_lengths = Enum.map(keys, &(IO.iodata_length(encode_type(&1, :string)) + 6))
+
+    byte_size(nkeys) + Enum.sum(key_lengths)
+  end
 
   # http://orientdb.com/docs/last/Types.html
   @types [

  # field, with a `:name` and a type (`:data_type`). Both records contain a
  # `:data_ptr` field that contains the index of the data structure for that
  # field in the serialized record.
  defrecordp :property, [:id, :data_ptr]
  defrecordp :named_field, [:name, :data_type, :data_ptr]

  defrecordp :map_key, [:key, :data_type, :data_ptr]

  defmodule Field do
    @type t :: %__MODULE__{
      name: binary,
      type: atom,
      pointer_to_data: non_neg_integer,
      encoded_value: iodata,
    }


defmodule MarcoPolo.Protocol.RecordSerialization do
  require Record

  # We're creating records instead of structs to avoid creating lots of
  # modules. `:property` identifies a field that is in the schema's metadata
