--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -131,7 +131,8 @@ class changelog(revlog):
         return extra
 
     def encode_extra(self, d):
-        items = [_string_escape(":".join(t)) for t in d.iteritems()]
+        # keys must be sorted to produce a deterministic changelog entry
+        items = [_string_escape('%s:%s' % (k, d[k])) for k in sorted(d)]
         return "\0".join(items)
 
     def extract(self, text):