Refactor common invalidation framework types

Convert the Invalidation struct into a class.  This allows us to hide
its members, so we can do things like add a DCHECK to make sure we never
access the payload field of an unknown version invalidation.  It also
lets us use factory methods and constructors to initialize it rather
than having to initialize its fields one by one.

Convert the ObjectIdInvalidationMap from a typedef into a class.  Unlike
the typedef, the class supports multiple invalidations for the same
object ID.  It uses the newly introduced SingleObjectInvalidationSet to
manage the set of invalidations belonging to a particular ID.  Note that
the current code still sends only one invalidation per type; that will
be changed in a future commit.

The end goal of this refactoring is to make these classes smarter so
they can help manage the complexity that will be introduced when we
implement invalidation 'trickles' support.

Note that this commit changes the on-disk format for invalidations, so
any invalidations currently stored in the profile may be lost on
upgrade.  There should be no other notable changes to invalidations
behavior in this CL.

TBR=brettw
BUG=233437

Review URL: https://codereview.chromium.org/23441042

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@226949 0039d316-1c4b-4281-b951-d872f2087c98

59 files changed, 1381 insertions, 699 deletions

diff --git a/chrome/browser/drive/drive_notification_manager.cc b/chrome/browser/drive/drive_notification_manager.cc
index 198c0148..d4141b0 100644
--- a/chrome/browser/drive/drive_notification_manager.cc
+++ b/chrome/browser/drive/drive_notification_manager.cc
@@ -68,18 +68,18 @@ void DriveNotificationManager::OnInvalidatorStateChange(
 void DriveNotificationManager::OnIncomingInvalidation(
     const syncer::ObjectIdInvalidationMap& invalidation_map) {
   DVLOG(2) << "XMPP Drive Notification Received";
-  DCHECK_EQ(1U, invalidation_map.size());
+  syncer::ObjectIdSet ids = invalidation_map.GetObjectIds();
+  DCHECK_EQ(1U, ids.size());
   const invalidation::ObjectId object_id(
       ipc::invalidation::ObjectSource::COSMO_CHANGELOG,
       kDriveInvalidationObjectId);
-  DCHECK_EQ(1U, invalidation_map.count(object_id));
+  DCHECK_EQ(1U, ids.count(object_id));
 
   // TODO(dcheng): Only acknowledge the invalidation once the fetch has
   // completed. http://crbug.com/156843
   DCHECK(invalidation_service_);
-  invalidation_service_->AcknowledgeInvalidation(
-      invalidation_map.begin()->first,
-      invalidation_map.begin()->second.ack_handle);
+  syncer::Invalidation inv = invalidation_map.ForObject(object_id).back();
+  invalidation_service_->AcknowledgeInvalidation(object_id, inv.ack_handle());
 
   NotifyObserversToUpdate(NOTIFICATION_XMPP);
 }
diff --git a/chrome/browser/extensions/api/push_messaging/push_messaging_apitest.cc b/chrome/browser/extensions/api/push_messaging/push_messaging_apitest.cc
index 6e98160..8cc3000 100644
--- a/chrome/browser/extensions/api/push_messaging/push_messaging_apitest.cc
+++ b/chrome/browser/extensions/api/push_messaging/push_messaging_apitest.cc
@@ -80,11 +80,10 @@ class PushMessagingApiTest : public ExtensionApiTest {
 
   void EmitInvalidation(
       const invalidation::ObjectId& object_id,
+      int64 version,
       const std::string& payload) {
     fake_invalidation_service_->EmitInvalidationForTest(
-        object_id,
-        syncer::Invalidation::kUnknownVersion,
-        payload);
+        syncer::Invalidation::Init(object_id, version, payload));
   }
 
   PushMessagingAPI* GetAPI() {
@@ -129,11 +128,11 @@ IN_PROC_BROWSER_TEST_F(PushMessagingApiTest, ReceivesPush) {
   // each subchannel at install, so trigger the suppressions first.
   for (int i = 0; i < 3; ++i) {
     EmitInvalidation(
-        ExtensionAndSubchannelToObjectId(extension->id(), i), std::string());
+        ExtensionAndSubchannelToObjectId(extension->id(), i), i, std::string());
   }
 
   EmitInvalidation(
-      ExtensionAndSubchannelToObjectId(extension->id(), 1), "payload");
+      ExtensionAndSubchannelToObjectId(extension->id(), 1), 5, "payload");
   EXPECT_TRUE(catcher.GetNextResult()) << catcher.message();
 }
 
diff --git a/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler.cc b/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler.cc
index 0535a75..fe20842 100644
--- a/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler.cc
+++ b/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler.cc
@@ -13,6 +13,7 @@
 #include "chrome/browser/invalidation/invalidation_service.h"
 #include "chrome/common/extensions/extension.h"
 #include "google/cacheinvalidation/types.pb.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace extensions {
 
@@ -124,29 +125,38 @@ void PushMessagingInvalidationHandler::OnInvalidatorStateChange(
 void PushMessagingInvalidationHandler::OnIncomingInvalidation(
     const syncer::ObjectIdInvalidationMap& invalidation_map) {
   DCHECK(thread_checker_.CalledOnValidThread());
-  for (syncer::ObjectIdInvalidationMap::const_iterator it =
-           invalidation_map.begin(); it != invalidation_map.end(); ++it) {
-    service_->AcknowledgeInvalidation(it->first, it->second.ack_handle);
+  syncer::ObjectIdSet ids = invalidation_map.GetObjectIds();
+  for (syncer::ObjectIdSet::const_iterator it = ids.begin();
+       it != ids.end(); ++it) {
+    const syncer::SingleObjectInvalidationSet& list =
+        invalidation_map.ForObject(*it);
+    const syncer::Invalidation& invalidation = list.back();
+    service_->AcknowledgeInvalidation(*it, invalidation.ack_handle());
+
+    std::string payload;
+    if (invalidation.is_unknown_version()) {
+      payload = std::string();
+    } else {
+      payload = list.back().payload();
+    }
 
     syncer::ObjectIdSet::iterator suppressed_id =
-        suppressed_ids_.find(it->first);
+        suppressed_ids_.find(*it);
     if (suppressed_id != suppressed_ids_.end()) {
       suppressed_ids_.erase(suppressed_id);
       continue;
     }
     DVLOG(2) << "Incoming push message, id is: "
-             << syncer::ObjectIdToString(it->first)
-             << " and payload is:" << it->second.payload;
+             << syncer::ObjectIdToString(*it)
+             << " and payload is:" << payload;
 
     std::string extension_id;
     int subchannel;
-    if (ObjectIdToExtensionAndSubchannel(it->first,
-                                         &extension_id,
-                                         &subchannel)) {
+    if (ObjectIdToExtensionAndSubchannel(*it, &extension_id, &subchannel)) {
       DVLOG(2) << "Sending push message to reciever, extension is "
                << extension_id << ", subchannel is " << subchannel
-               << ", and payload is " << it->second.payload;
-      delegate_->OnMessage(extension_id, subchannel, it->second.payload);
+               << ", and payload is " << payload;
+      delegate_->OnMessage(extension_id, subchannel, payload);
     }
   }
 }
diff --git a/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler_unittest.cc b/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler_unittest.cc
index 2b0fac4..5c29b50 100644
--- a/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler_unittest.cc
+++ b/chrome/browser/extensions/api/push_messaging/push_messaging_invalidation_handler_unittest.cc
@@ -10,6 +10,7 @@
 #include "chrome/browser/invalidation/invalidation_service.h"
 #include "google/cacheinvalidation/types.pb.h"
 #include "sync/internal_api/public/base/invalidation_test_util.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
@@ -17,6 +18,7 @@ using ::testing::_;
 using ::testing::NotNull;
 using ::testing::SaveArg;
 using ::testing::StrictMock;
+using syncer::AckHandle;
 
 namespace extensions {
 
@@ -104,67 +106,79 @@ TEST_F(PushMessagingInvalidationHandlerTest, RegisterUnregisterExtension) {
 }
 
 TEST_F(PushMessagingInvalidationHandlerTest, Dispatch) {
-  syncer::ObjectIdSet ids;
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
-      "U/dddddddddddddddddddddddddddddddd/0"));
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
-      "U/dddddddddddddddddddddddddddddddd/3"));
+  syncer::ObjectIdInvalidationMap invalidation_map;
+  // A normal invalidation.
+  invalidation_map.Insert(
+      syncer::Invalidation::Init(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
+              "U/dddddddddddddddddddddddddddddddd/0"),
+          10,
+          "payload"));
+
+  // An unknown version invalidation.
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+      invalidation::ObjectId(
+        ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
+        "U/dddddddddddddddddddddddddddddddd/3")));
+
   EXPECT_CALL(delegate_,
               OnMessage("dddddddddddddddddddddddddddddddd", 0, "payload"));
   EXPECT_CALL(delegate_,
-              OnMessage("dddddddddddddddddddddddddddddddd", 3, "payload"));
+              OnMessage("dddddddddddddddddddddddddddddddd", 3, ""));
+
+  syncer::ObjectIdSet ids = invalidation_map.GetObjectIds();
   for (syncer::ObjectIdSet::const_iterator it = ids.begin(); it != ids.end();
        ++it) {
-    EXPECT_CALL(service_, AcknowledgeInvalidation(
-        *it, syncer::AckHandle::InvalidAckHandle()));
+    const syncer::Invalidation& inv = invalidation_map.ForObject(*it).back();
+    const syncer::AckHandle& ack_handle = inv.ack_handle();
+    EXPECT_CALL(service_, AcknowledgeInvalidation(*it, ack_handle));
   }
-  handler_->OnIncomingInvalidation(
-      ObjectIdSetToInvalidationMap(
-          ids,
-          syncer::Invalidation::kUnknownVersion,
-          "payload"));
+  handler_->OnIncomingInvalidation(invalidation_map);
 }
 
 // Tests that malformed object IDs don't trigger spurious callbacks.
 TEST_F(PushMessagingInvalidationHandlerTest, DispatchInvalidObjectIds) {
-  syncer::ObjectIdSet ids;
+  syncer::ObjectIdInvalidationMap invalidation_map;
   // Completely incorrect format.
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::TEST,
-      "Invalid"));
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::TEST,
+              "Invalid")));
   // Incorrect source.
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::TEST,
-      "U/dddddddddddddddddddddddddddddddd/3"));
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::TEST,
+              "U/dddddddddddddddddddddddddddddddd/3")));
   // Incorrect format type.
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
-      "V/dddddddddddddddddddddddddddddddd/3"));
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
+              "V/dddddddddddddddddddddddddddddddd/3")));
   // Invalid extension ID length.
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
-      "U/ddddddddddddddddddddddddddddddddd/3"));
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
+              "U/ddddddddddddddddddddddddddddddddd/3")));
   // Non-numeric subchannel.
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
-      "U/dddddddddddddddddddddddddddddddd/z"));
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
+              "U/dddddddddddddddddddddddddddddddd/z")));
   // Subchannel out of range.
-  ids.insert(invalidation::ObjectId(
-      ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
-      "U/dddddddddddddddddddddddddddddddd/4"));
+  invalidation_map.Insert(syncer::Invalidation::InitUnknownVersion(
+          invalidation::ObjectId(
+              ipc::invalidation::ObjectSource::CHROME_PUSH_MESSAGING,
+              "U/dddddddddddddddddddddddddddddddd/4")));
   // Invalid object IDs should still be acknowledged.
+  syncer::ObjectIdSet ids = invalidation_map.GetObjectIds();
   for (syncer::ObjectIdSet::const_iterator it = ids.begin(); it != ids.end();
        ++it) {
-    EXPECT_CALL(service_, AcknowledgeInvalidation(
-        *it, syncer::AckHandle::InvalidAckHandle()));
+    const syncer::Invalidation& inv = invalidation_map.ForObject(*it).back();
+    const syncer::AckHandle& ack_handle = inv.ack_handle();
+    EXPECT_CALL(service_, AcknowledgeInvalidation(*it, ack_handle));
   }
-  handler_->OnIncomingInvalidation(
-      ObjectIdSetToInvalidationMap(
-          ids,
-          syncer::Invalidation::kUnknownVersion,
-          "payload"));
+  handler_->OnIncomingInvalidation(invalidation_map);
 }
 
 }  // namespace extensions
diff --git a/chrome/browser/invalidation/DEPS b/chrome/browser/invalidation/DEPS
index f66fb34..f049819 100644
--- a/chrome/browser/invalidation/DEPS
+++ b/chrome/browser/invalidation/DEPS
@@ -2,9 +2,7 @@ include_rules = [
   # Needed for P2PInvalidationService construction.
   "+jingle/notifier",
 
-  # Needed for SyncMaxInvalidationVersions Migration.
-  "+sync/internal_api/public/base/model_type.h",
-  "+sync/internal_api/public/base/invalidation_test_util.h",
+  "+sync/internal_api/public/base",
 
   # Needed for InvalidationController JNI methods.
   "+sync/jni/InvalidationController_jni.h",
diff --git a/chrome/browser/invalidation/fake_invalidation_service.cc b/chrome/browser/invalidation/fake_invalidation_service.cc
index dcf5c2f..f789ac8 100644
--- a/chrome/browser/invalidation/fake_invalidation_service.cc
+++ b/chrome/browser/invalidation/fake_invalidation_service.cc
@@ -65,24 +65,17 @@ void FakeInvalidationService::SetInvalidatorState(
   invalidator_registrar_.UpdateInvalidatorState(state);
 }
 
-syncer::AckHandle FakeInvalidationService::EmitInvalidationForTest(
-      const invalidation::ObjectId& object_id,
-      int64 version,
-      const std::string& payload) {
+void FakeInvalidationService::EmitInvalidationForTest(
+    const syncer::Invalidation& invalidation) {
   syncer::ObjectIdInvalidationMap invalidation_map;
 
-  syncer::Invalidation inv;
-  inv.version = version;
-  inv.payload = payload;
-  inv.ack_handle = syncer::AckHandle::CreateUnique();
-
-  invalidation_map.insert(std::make_pair(object_id, inv));
+  invalidation_map.Insert(invalidation);
   unacknowledged_handles_.push_back(
-      AckHandleList::value_type(inv.ack_handle, object_id));
+      AckHandleList::value_type(
+          invalidation.ack_handle(),
+          invalidation.object_id()));
 
   invalidator_registrar_.DispatchInvalidationsToHandlers(invalidation_map);
-
-  return inv.ack_handle;
 }
 
 bool FakeInvalidationService::IsInvalidationAcknowledged(
diff --git a/chrome/browser/invalidation/fake_invalidation_service.h b/chrome/browser/invalidation/fake_invalidation_service.h
index b52b33b..5887912 100644
--- a/chrome/browser/invalidation/fake_invalidation_service.h
+++ b/chrome/browser/invalidation/fake_invalidation_service.h
@@ -41,10 +41,7 @@ class FakeInvalidationService : public InvalidationService {
   const syncer::InvalidatorRegistrar& invalidator_registrar() const {
     return invalidator_registrar_;
   }
-  syncer::AckHandle EmitInvalidationForTest(
-      const invalidation::ObjectId& object_id,
-      int64 version,
-      const std::string& payload);
+  void EmitInvalidationForTest(const syncer::Invalidation& invalidation);
 
   // Determines if the given AckHandle has been acknowledged.
   bool IsInvalidationAcknowledged(const syncer::AckHandle& ack_handle) const;
diff --git a/chrome/browser/invalidation/invalidation_service_android.cc b/chrome/browser/invalidation/invalidation_service_android.cc
index 7e03cc2b..72a7046 100644
--- a/chrome/browser/invalidation/invalidation_service_android.cc
+++ b/chrome/browser/invalidation/invalidation_service_android.cc
@@ -77,11 +77,9 @@ void InvalidationServiceAndroid::Observe(
 
   // An empty map implies that we should invalidate all.
   const syncer::ObjectIdInvalidationMap& effective_invalidation_map =
-      object_invalidation_map.empty() ?
-      ObjectIdSetToInvalidationMap(
-          invalidator_registrar_.GetAllRegisteredIds(),
-          syncer::Invalidation::kUnknownVersion,
-          std::string()) :
+      object_invalidation_map.Empty() ?
+      syncer::ObjectIdInvalidationMap::InvalidateAll(
+          invalidator_registrar_.GetAllRegisteredIds()) :
       object_invalidation_map;
 
   invalidator_registrar_.DispatchInvalidationsToHandlers(
diff --git a/chrome/browser/invalidation/invalidation_service_test_template.h b/chrome/browser/invalidation/invalidation_service_test_template.h
index 85a467c..05e9928 100644
--- a/chrome/browser/invalidation/invalidation_service_test_template.h
+++ b/chrome/browser/invalidation/invalidation_service_test_template.h
@@ -76,9 +76,11 @@
 #include "chrome/browser/invalidation/invalidation_service.h"
 #include "google/cacheinvalidation/include/types.h"
 #include "google/cacheinvalidation/types.pb.h"
+#include "sync/internal_api/public/base/ack_handle.h"
+#include "sync/internal_api/public/base/invalidation.h"
+#include "sync/internal_api/public/base/object_id_invalidation_map_test_util.h"
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/object_id_invalidation_map.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 template <typename InvalidatorTestDelegate>
@@ -120,13 +122,13 @@ TYPED_TEST_P(InvalidationServiceTest, Basic) {
 
   invalidator->RegisterInvalidationHandler(&handler);
 
-  syncer::ObjectIdInvalidationMap states;
-  states[this->id1].payload = "1";
-  states[this->id2].payload = "2";
-  states[this->id3].payload = "3";
+  syncer::ObjectIdInvalidationMap invalidation_map;
+  invalidation_map.Insert(syncer::Invalidation::Init(this->id1, 1, "1"));
+  invalidation_map.Insert(syncer::Invalidation::Init(this->id2, 2, "2"));
+  invalidation_map.Insert(syncer::Invalidation::Init(this->id3, 3, "3"));
 
   // Should be ignored since no IDs are registered to |handler|.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(0, handler.GetInvalidationCount());
 
   syncer::ObjectIdSet ids;
@@ -138,25 +140,26 @@ TYPED_TEST_P(InvalidationServiceTest, Basic) {
       syncer::INVALIDATIONS_ENABLED);
   EXPECT_EQ(syncer::INVALIDATIONS_ENABLED, handler.GetInvalidatorState());
 
-  syncer::ObjectIdInvalidationMap expected_states;
-  expected_states[this->id1].payload = "1";
-  expected_states[this->id2].payload = "2";
+  syncer::ObjectIdInvalidationMap expected_invalidations;
+  expected_invalidations.Insert(syncer::Invalidation::Init(this->id1, 1, "1"));
+  expected_invalidations.Insert(syncer::Invalidation::Init(this->id2, 2, "2"));
 
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(1, handler.GetInvalidationCount());
-  EXPECT_THAT(expected_states, Eq(handler.GetLastInvalidationMap()));
+  EXPECT_THAT(expected_invalidations, Eq(handler.GetLastInvalidationMap()));
 
   ids.erase(this->id1);
   ids.insert(this->id3);
   invalidator->UpdateRegisteredInvalidationIds(&handler, ids);
 
-  expected_states.erase(this->id1);
-  expected_states[this->id3].payload = "3";
+  expected_invalidations = syncer::ObjectIdInvalidationMap();
+  expected_invalidations.Insert(syncer::Invalidation::Init(this->id2, 2, "2"));
+  expected_invalidations.Insert(syncer::Invalidation::Init(this->id3, 3, "3"));
 
   // Removed object IDs should not be notified, newly-added ones should.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(2, handler.GetInvalidationCount());
-  EXPECT_THAT(expected_states, Eq(handler.GetLastInvalidationMap()));
+  EXPECT_THAT(expected_invalidations, Eq(handler.GetLastInvalidationMap()));
 
   this->delegate_.TriggerOnInvalidatorStateChange(
       syncer::TRANSIENT_INVALIDATION_ERROR);
@@ -171,7 +174,7 @@ TYPED_TEST_P(InvalidationServiceTest, Basic) {
   invalidator->UnregisterInvalidationHandler(&handler);
 
   // Should be ignored since |handler| isn't registered anymore.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(2, handler.GetInvalidationCount());
 }
 
@@ -226,25 +229,28 @@ TYPED_TEST_P(InvalidationServiceTest, MultipleHandlers) {
             handler4.GetInvalidatorState());
 
   {
-    syncer::ObjectIdInvalidationMap states;
-    states[this->id1].payload = "1";
-    states[this->id2].payload = "2";
-    states[this->id3].payload = "3";
-    states[this->id4].payload = "4";
-    this->delegate_.TriggerOnIncomingInvalidation(states);
-
-    syncer::ObjectIdInvalidationMap expected_states;
-    expected_states[this->id1].payload = "1";
-    expected_states[this->id2].payload = "2";
+    syncer::ObjectIdInvalidationMap invalidation_map;
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id1, 1, "1"));
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id2, 2, "2"));
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id3, 3, "3"));
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id4, 4, "4"));
+    this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
+
+    syncer::ObjectIdInvalidationMap expected_invalidations;
+    expected_invalidations.Insert(
+        syncer::Invalidation::Init(this->id1, 1, "1"));
+    expected_invalidations.Insert(
+        syncer::Invalidation::Init(this->id2, 2, "2"));
 
     EXPECT_EQ(1, handler1.GetInvalidationCount());
-    EXPECT_THAT(expected_states, Eq(handler1.GetLastInvalidationMap()));
+    EXPECT_THAT(expected_invalidations, Eq(handler1.GetLastInvalidationMap()));
 
-    expected_states.clear();
-    expected_states[this->id3].payload = "3";
+    expected_invalidations = syncer::ObjectIdInvalidationMap();
+    expected_invalidations.Insert(
+        syncer::Invalidation::Init(this->id3, 3, "3"));
 
     EXPECT_EQ(1, handler2.GetInvalidationCount());
-    EXPECT_THAT(expected_states, Eq(handler2.GetLastInvalidationMap()));
+    EXPECT_THAT(expected_invalidations, Eq(handler2.GetLastInvalidationMap()));
 
     EXPECT_EQ(0, handler3.GetInvalidationCount());
     EXPECT_EQ(0, handler4.GetInvalidationCount());
@@ -304,11 +310,11 @@ TYPED_TEST_P(InvalidationServiceTest, EmptySetUnregisters) {
   EXPECT_EQ(syncer::INVALIDATIONS_ENABLED, handler2.GetInvalidatorState());
 
   {
-    syncer::ObjectIdInvalidationMap states;
-    states[this->id1].payload = "1";
-    states[this->id2].payload = "2";
-    states[this->id3].payload = "3";
-    this->delegate_.TriggerOnIncomingInvalidation(states);
+    syncer::ObjectIdInvalidationMap invalidation_map;
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id1, 1, "1"));
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id2, 2, "2"));
+    invalidation_map.Insert(syncer::Invalidation::Init(this->id3, 3, "3"));
+    this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
     EXPECT_EQ(0, handler1.GetInvalidationCount());
     EXPECT_EQ(1, handler2.GetInvalidationCount());
   }
diff --git a/chrome/browser/invalidation/invalidator_storage_unittest.cc b/chrome/browser/invalidation/invalidator_storage_unittest.cc
index 985ec94..224ed0d 100644
--- a/chrome/browser/invalidation/invalidator_storage_unittest.cc
+++ b/chrome/browser/invalidation/invalidator_storage_unittest.cc
@@ -275,8 +275,8 @@ TEST_F(InvalidatorStorageTest, DeserializeFromListBasic) {
   EXPECT_EQ(1U, map.size());
   EXPECT_EQ(20, map[kAppNotificationsId_].version);
   EXPECT_EQ("testing", map[kAppNotificationsId_].payload);
-  EXPECT_THAT(map[kAppNotificationsId_].current, Eq(ack_handle_1));
-  EXPECT_THAT(map[kAppNotificationsId_].expected, Eq(ack_handle_2));
+  EXPECT_THAT(map[kAppNotificationsId_].current, syncer::Eq(ack_handle_1));
+  EXPECT_THAT(map[kAppNotificationsId_].expected, syncer::Eq(ack_handle_2));
 }
 
 // Tests that deserializing well-formed values when optional parameters are
diff --git a/chrome/browser/invalidation/p2p_invalidation_service.cc b/chrome/browser/invalidation/p2p_invalidation_service.cc
index 855d052..c802136 100644
--- a/chrome/browser/invalidation/p2p_invalidation_service.cc
+++ b/chrome/browser/invalidation/p2p_invalidation_service.cc
@@ -64,8 +64,8 @@ void P2PInvalidationService::AcknowledgeInvalidation(
 }
 
 void P2PInvalidationService::SendInvalidation(
-    const syncer::ObjectIdInvalidationMap& invalidation_map) {
-  invalidator_->SendInvalidation(invalidation_map);
+    const syncer::ObjectIdSet& ids) {
+  invalidator_->SendInvalidation(ids);
 }
 
 syncer::InvalidatorState P2PInvalidationService::GetInvalidatorState() const {
diff --git a/chrome/browser/invalidation/p2p_invalidation_service.h b/chrome/browser/invalidation/p2p_invalidation_service.h
index bbb18b9..8a6e3c0 100644
--- a/chrome/browser/invalidation/p2p_invalidation_service.h
+++ b/chrome/browser/invalidation/p2p_invalidation_service.h
@@ -49,8 +49,7 @@ class P2PInvalidationService
   void UpdateCredentials(const std::string& username,
                          const std::string& password);
 
-  void SendInvalidation(
-      const syncer::ObjectIdInvalidationMap& invalidation_map);
+  void SendInvalidation(const syncer::ObjectIdSet& ids);
 
  private:
   scoped_ptr<syncer::P2PInvalidator> invalidator_;
diff --git a/chrome/browser/policy/cloud/DEPS b/chrome/browser/policy/cloud/DEPS
index c99509b..e806e80 100644
--- a/chrome/browser/policy/cloud/DEPS
+++ b/chrome/browser/policy/cloud/DEPS
@@ -32,6 +32,10 @@ specific_include_rules = {
     "+content/test/net",
   ],
 
+  r"cloud_policy_browsertest.cc": [
+    "+sync/internal_api/public/base/invalidation.h",
+  ],
+
   # TODO(joaodasilva): remove these exceptions.
   r"cloud_external_data_manager_base_unittest\.cc": [
     "+content/public/test/test_browser_thread_bundle.h",
diff --git a/chrome/browser/policy/cloud/cloud_policy_browsertest.cc b/chrome/browser/policy/cloud/cloud_policy_browsertest.cc
index 84ef567..62cd375 100644
--- a/chrome/browser/policy/cloud/cloud_policy_browsertest.cc
+++ b/chrome/browser/policy/cloud/cloud_policy_browsertest.cc
@@ -39,6 +39,7 @@
 #include "policy/policy_constants.h"
 #include "policy/proto/chrome_settings.pb.h"
 #include "policy/proto/cloud_policy.pb.h"
+#include "sync/internal_api/public/base/invalidation.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 #include "url/gurl.h"
@@ -309,9 +310,10 @@ IN_PROC_BROWSER_TEST_F(CloudPolicyTest, InvalidatePolicy) {
   // Update the homepage in the policy and trigger an invalidation.
   ASSERT_NO_FATAL_FAILURE(SetServerPolicy(GetTestPolicy("youtube.com", 0)));
   GetInvalidationService()->EmitInvalidationForTest(
-      invalidation::ObjectId(16, "test_policy"),
-      1 /* version */,
-      "payload");
+      syncer::Invalidation::Init(
+          invalidation::ObjectId(16, "test_policy"),
+          1 /* version */,
+          "payload"));
   {
     base::RunLoop run_loop;
     on_policy_updated_ = run_loop.QuitClosure();
diff --git a/chrome/browser/policy/cloud/cloud_policy_invalidator.cc b/chrome/browser/policy/cloud/cloud_policy_invalidator.cc
index e4fed05..c55409b 100644
--- a/chrome/browser/policy/cloud/cloud_policy_invalidator.cc
+++ b/chrome/browser/policy/cloud/cloud_policy_invalidator.cc
@@ -92,13 +92,13 @@ void CloudPolicyInvalidator::OnIncomingInvalidation(
     const syncer::ObjectIdInvalidationMap& invalidation_map) {
   DCHECK(state_ == STARTED);
   DCHECK(thread_checker_.CalledOnValidThread());
-  const syncer::ObjectIdInvalidationMap::const_iterator invalidation =
-      invalidation_map.find(object_id_);
-  if (invalidation == invalidation_map.end()) {
+  const syncer::SingleObjectInvalidationSet& list =
+      invalidation_map.ForObject(object_id_);
+  if (list.IsEmpty()) {
     NOTREACHED();
     return;
   }
-  HandleInvalidation(invalidation->second);
+  HandleInvalidation(list.back());
 }
 
 void CloudPolicyInvalidator::OnCoreConnected(CloudPolicyCore* core) {}
@@ -156,7 +156,7 @@ void CloudPolicyInvalidator::HandleInvalidation(
     const syncer::Invalidation& invalidation) {
   // The invalidation service may send an invalidation more than once if there
   // is a delay in acknowledging it. Duplicate invalidations are ignored.
-  if (invalid_ && ack_handle_.Equals(invalidation.ack_handle))
+  if (invalid_ && ack_handle_.Equals(invalidation.ack_handle()))
     return;
 
   // If there is still a pending invalidation, acknowledge it, since we only
@@ -166,15 +166,17 @@ void CloudPolicyInvalidator::HandleInvalidation(
 
   // Update invalidation state.
   invalid_ = true;
-  ack_handle_ = invalidation.ack_handle;
-  invalidation_version_ = invalidation.version;
+  ack_handle_ = invalidation.ack_handle();
 
   // When an invalidation with unknown version is received, use negative
   // numbers based on the number of such invalidations received. This
   // ensures that the version numbers do not collide with "real" versions
   // (which are positive) or previous invalidations with unknown version.
-  if (invalidation_version_ == syncer::Invalidation::kUnknownVersion)
+  if (invalidation.is_unknown_version()) {
     invalidation_version_ = -(++unknown_version_invalidation_count_);
+  } else {
+    invalidation_version_ = invalidation.version();
+  }
 
   // In order to prevent the cloud policy server from becoming overwhelmed when
   // a policy with many users is modified, delay for a random period of time
@@ -184,11 +186,14 @@ void CloudPolicyInvalidator::HandleInvalidation(
   base::TimeDelta delay = base::TimeDelta::FromMilliseconds(
       base::RandInt(20, max_fetch_delay_));
 
+  std::string payload;
+  if (!invalidation.is_unknown_version())
+    payload = invalidation.payload();
+
   // If there is a payload, the policy can be refreshed at any time, so set
   // the version and payload on the client immediately. Otherwise, the refresh
   // must only run after at least kMissingPayloadDelay minutes.
-  const std::string& payload = invalidation.payload;
-  if (!invalidation.payload.empty())
+  if (!payload.empty())
     core_->client()->SetInvalidationInfo(invalidation_version_, payload);
   else
     delay += base::TimeDelta::FromMinutes(kMissingPayloadDelay);
diff --git a/chrome/browser/policy/cloud/cloud_policy_invalidator_unittest.cc b/chrome/browser/policy/cloud/cloud_policy_invalidator_unittest.cc
index 9340768..eff1388 100644
--- a/chrome/browser/policy/cloud/cloud_policy_invalidator_unittest.cc
+++ b/chrome/browser/policy/cloud/cloud_policy_invalidator_unittest.cc
@@ -117,7 +117,7 @@ class CloudPolicyInvalidatorTest : public testing::Test {
   // Causes the invalidation service to fire an invalidation with unknown
   // version. Returns an ack handle which be used to verify that the
   // invalidation was acknowledged.
-  syncer::AckHandle FireInvalidation(PolicyObject object);
+  syncer::AckHandle FireUnknownVersionInvalidation(PolicyObject object);
 
   // Checks the expected value of the currently set invalidation info.
   bool CheckInvalidationInfo(int64 version, const std::string& payload);
@@ -305,18 +305,20 @@ syncer::AckHandle CloudPolicyInvalidatorTest::FireInvalidation(
     PolicyObject object,
     int64 version,
     const std::string& payload) {
-  return invalidation_service_.EmitInvalidationForTest(
+  syncer::Invalidation invalidation = syncer::Invalidation::Init(
       GetPolicyObjectId(object),
       version,
       payload);
+  invalidation_service_.EmitInvalidationForTest(invalidation);
+  return invalidation.ack_handle();
 }
 
-syncer::AckHandle CloudPolicyInvalidatorTest::FireInvalidation(
+syncer::AckHandle CloudPolicyInvalidatorTest::FireUnknownVersionInvalidation(
     PolicyObject object) {
-  return invalidation_service_.EmitInvalidationForTest(
-      GetPolicyObjectId(object),
-      syncer::Invalidation::kUnknownVersion,
-      std::string());
+  syncer::Invalidation invalidation =
+      syncer::Invalidation::InitUnknownVersion(GetPolicyObjectId(object));
+  invalidation_service_.EmitInvalidationForTest(invalidation);
+  return invalidation.ack_handle();
 }
 
 bool CloudPolicyInvalidatorTest::CheckInvalidationInfo(
@@ -420,7 +422,7 @@ TEST_F(CloudPolicyInvalidatorTest, Uninitialized) {
   StartInvalidator(false /* initialize */, true /* start_refresh_scheduler */);
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_FALSE(IsInvalidatorRegistered());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 }
 
@@ -430,7 +432,7 @@ TEST_F(CloudPolicyInvalidatorTest, RefreshSchedulerNotStarted) {
   StartInvalidator(true /* initialize */, false /* start_refresh_scheduler */);
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_FALSE(IsInvalidatorRegistered());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 }
 
@@ -442,7 +444,7 @@ TEST_F(CloudPolicyInvalidatorTest, DisconnectCoreThenInitialize) {
   InitializeInvalidator();
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_FALSE(IsInvalidatorRegistered());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 }
 
@@ -457,7 +459,7 @@ TEST_F(CloudPolicyInvalidatorTest, InitializeThenStartRefreshScheduler) {
   StartRefreshScheduler();
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_TRUE(IsInvalidatorRegistered());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
 }
 
@@ -466,25 +468,25 @@ TEST_F(CloudPolicyInvalidatorTest, RegisterOnStoreLoaded) {
   StartInvalidator();
   EXPECT_FALSE(IsInvalidatorRegistered());
   EXPECT_FALSE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_A);
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 
   // No registration when store is loaded with no invalidation object id.
   StorePolicy(POLICY_OBJECT_NONE);
   EXPECT_FALSE(IsInvalidatorRegistered());
   EXPECT_FALSE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_A);
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 
   // Check registration when store is loaded for object A.
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_TRUE(IsInvalidatorRegistered());
   EXPECT_TRUE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 }
 
@@ -494,11 +496,11 @@ TEST_F(CloudPolicyInvalidatorTest, ChangeRegistration) {
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_TRUE(IsInvalidatorRegistered());
   EXPECT_TRUE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
-  syncer::AckHandle ack = FireInvalidation(POLICY_OBJECT_A);
+  syncer::AckHandle ack = FireUnknownVersionInvalidation(POLICY_OBJECT_A);
 
   // Check re-registration for object B. Make sure the pending invalidation for
   // object A is acknowledged without making the callback.
@@ -510,9 +512,9 @@ TEST_F(CloudPolicyInvalidatorTest, ChangeRegistration) {
 
   // Make sure future invalidations for object A are ignored and for object B
   // are processed.
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
 }
 
@@ -522,25 +524,25 @@ TEST_F(CloudPolicyInvalidatorTest, UnregisterOnStoreLoaded) {
   StorePolicy(POLICY_OBJECT_A);
   EXPECT_TRUE(IsInvalidatorRegistered());
   EXPECT_TRUE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
 
   // Check unregistration when store is loaded with no invalidation object id.
-  syncer::AckHandle ack = FireInvalidation(POLICY_OBJECT_A);
+  syncer::AckHandle ack = FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_FALSE(IsInvalidationAcknowledged(ack));
   StorePolicy(POLICY_OBJECT_NONE);
   EXPECT_FALSE(IsInvalidatorRegistered());
   EXPECT_TRUE(IsInvalidationAcknowledged(ack));
   EXPECT_FALSE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_A);
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyNotRefreshed());
 
   // Check re-registration for object B.
   StorePolicy(POLICY_OBJECT_B);
   EXPECT_TRUE(IsInvalidatorRegistered());
   EXPECT_TRUE(InvalidationsEnabled());
-  FireInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
 }
 
@@ -567,7 +569,7 @@ TEST_F(CloudPolicyInvalidatorTest, HandleInvalidationWithUnknownVersion) {
   // Register and fire invalidation with unknown version.
   StorePolicy(POLICY_OBJECT_A);
   StartInvalidator();
-  syncer::AckHandle ack = FireInvalidation(POLICY_OBJECT_A);
+  syncer::AckHandle ack = FireUnknownVersionInvalidation(POLICY_OBJECT_A);
 
   // Make sure client info is not set until after the invalidation callback is
   // made.
@@ -616,15 +618,15 @@ TEST_F(CloudPolicyInvalidatorTest,
   // unique invalidation version numbers.
   StorePolicy(POLICY_OBJECT_A);
   StartInvalidator();
-  syncer::AckHandle ack1 = FireInvalidation(POLICY_OBJECT_A);
+  syncer::AckHandle ack1 = FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckInvalidationInfo(0, std::string()));
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
   EXPECT_TRUE(CheckInvalidationInfo(-1, std::string()));
-  syncer::AckHandle ack2 = FireInvalidation(POLICY_OBJECT_A);
+  syncer::AckHandle ack2 = FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckInvalidationInfo(0, std::string()));
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
   EXPECT_TRUE(CheckInvalidationInfo(-2, std::string()));
-  syncer::AckHandle ack3 = FireInvalidation(POLICY_OBJECT_A);
+  syncer::AckHandle ack3 = FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   EXPECT_TRUE(CheckInvalidationInfo(0, std::string()));
   EXPECT_TRUE(CheckPolicyRefreshedWithUnknownVersion());
   EXPECT_TRUE(CheckInvalidationInfo(-3, std::string()));
@@ -830,13 +832,13 @@ TEST_F(CloudPolicyInvalidatorTest, InvalidationMetrics) {
   // Generate a mix of versioned and unknown-version invalidations.
   StorePolicy(POLICY_OBJECT_A);
   StartInvalidator();
-  FireInvalidation(POLICY_OBJECT_B);
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_B);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   FireInvalidation(POLICY_OBJECT_B, 1, "test");
   FireInvalidation(POLICY_OBJECT_A, 1, "test");
   FireInvalidation(POLICY_OBJECT_A, 2, "test");
-  FireInvalidation(POLICY_OBJECT_A);
-  FireInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
+  FireUnknownVersionInvalidation(POLICY_OBJECT_A);
   FireInvalidation(POLICY_OBJECT_A, 3, "test");
   FireInvalidation(POLICY_OBJECT_A, 4, "test");
 
diff --git a/chrome/browser/sync/glue/sync_backend_host.cc b/chrome/browser/sync/glue/sync_backend_host.cc
index 84c0b16..2ce1d56 100644
--- a/chrome/browser/sync/glue/sync_backend_host.cc
+++ b/chrome/browser/sync/glue/sync_backend_host.cc
@@ -1505,13 +1505,14 @@ void SyncBackendHost::OnInvalidatorStateChange(syncer::InvalidatorState state) {
 
 void SyncBackendHost::OnIncomingInvalidation(
     const syncer::ObjectIdInvalidationMap& invalidation_map) {
-  // TODO(dcheng): Acknowledge immediately for now. Fix this once the
-  // invalidator doesn't repeatedly ping for unacknowledged invaliations, since
-  // it conflicts with the sync scheduler's internal backoff algorithm.
-  // See http://crbug.com/124149 for more information.
-  for (syncer::ObjectIdInvalidationMap::const_iterator it =
-       invalidation_map.begin(); it != invalidation_map.end(); ++it) {
-    invalidator_->AcknowledgeInvalidation(it->first, it->second.ack_handle);
+  // TODO(rlarocque): Acknowledge these invalidations only after the syncer has
+  // acted on them and saved the results to disk.
+  syncer::ObjectIdSet ids = invalidation_map.GetObjectIds();
+  for (syncer::ObjectIdSet::const_iterator it = ids.begin();
+       it != ids.end(); ++it) {
+    const syncer::AckHandle& handle =
+        invalidation_map.ForObject(*it).back().ack_handle();
+    invalidator_->AcknowledgeInvalidation(*it, handle);
   }
 
   registrar_->sync_thread()->message_loop()->PostTask(
diff --git a/chrome/browser/sync/glue/sync_backend_host_unittest.cc b/chrome/browser/sync/glue/sync_backend_host_unittest.cc
index 2fd3ccf..8a4ef24 100644
--- a/chrome/browser/sync/glue/sync_backend_host_unittest.cc
+++ b/chrome/browser/sync/glue/sync_backend_host_unittest.cc
@@ -30,7 +30,6 @@
 #include "sync/internal_api/public/test/fake_sync_manager.h"
 #include "sync/internal_api/public/util/experiments.h"
 #include "sync/notifier/invalidator_state.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "sync/protocol/encryption.pb.h"
 #include "sync/protocol/sync_protocol_error.h"
 #include "sync/util/test_unrecoverable_error_handler.h"
diff --git a/chrome/browser/sync/profile_sync_service_android.cc b/chrome/browser/sync/profile_sync_service_android.cc
index a3d58d0..19f94ec 100644
--- a/chrome/browser/sync/profile_sync_service_android.cc
+++ b/chrome/browser/sync/profile_sync_service_android.cc
@@ -105,8 +105,10 @@ void ProfileSyncServiceAndroid::SendNudgeNotification(
   invalidation::ObjectId object_id(
       object_source,
       str_object_id);
+  syncer::ObjectIdInvalidationMap object_ids_with_states;
   if (version == ipc::invalidation::Constants::UNKNOWN) {
-    version = syncer::Invalidation::kUnknownVersion;
+    object_ids_with_states.Insert(
+        syncer::Invalidation::InitUnknownVersion(object_id));
   } else {
     ObjectIdVersionMap::iterator it =
         max_invalidation_versions_.find(object_id);
@@ -116,13 +118,10 @@ void ProfileSyncServiceAndroid::SendNudgeNotification(
       return;
     }
     max_invalidation_versions_[object_id] = version;
+    object_ids_with_states.Insert(
+        syncer::Invalidation::Init(object_id, version, state));
   }
 
-  syncer::ObjectIdSet object_ids;
-  object_ids.insert(object_id);
-  syncer::ObjectIdInvalidationMap object_ids_with_states =
-      syncer::ObjectIdSetToInvalidationMap(object_ids, version, state);
-
   content::NotificationService::current()->Notify(
       chrome::NOTIFICATION_SYNC_REFRESH_REMOTE,
       content::Source<Profile>(profile_),
diff --git a/chrome/browser/sync/profile_sync_service_harness.cc b/chrome/browser/sync/profile_sync_service_harness.cc
index 67aea310..f156fdd 100644
--- a/chrome/browser/sync/profile_sync_service_harness.cc
+++ b/chrome/browser/sync/profile_sync_service_harness.cc
@@ -504,12 +504,7 @@ void ProfileSyncServiceHarness::OnSyncCycleCompleted() {
     syncer::ModelTypeSet model_types =
         snap.model_neutral_state().commit_request_types;
     syncer::ObjectIdSet ids = ModelTypeSetToObjectIdSet(model_types);
-    syncer::ObjectIdInvalidationMap invalidation_map =
-        syncer::ObjectIdSetToInvalidationMap(
-            ids,
-            syncer::Invalidation::kUnknownVersion,
-            "");
-    p2p_invalidation_service_->SendInvalidation(invalidation_map);
+    p2p_invalidation_service_->SendInvalidation(ids);
   }
 
   OnStateChanged();
diff --git a/chrome/browser/sync/test/integration/sync_test.cc b/chrome/browser/sync/test/integration/sync_test.cc
index 212ea59..217c31d 100644
--- a/chrome/browser/sync/test/integration/sync_test.cc
+++ b/chrome/browser/sync/test/integration/sync_test.cc
@@ -676,11 +676,8 @@ void SyncTest::TriggerNotification(syncer::ModelTypeSet changed_types) {
       syncer::P2PNotificationData(
           "from_server",
           syncer::NOTIFY_ALL,
-          syncer::ObjectIdSetToInvalidationMap(
-              syncer::ModelTypeSetToObjectIdSet(changed_types),
-              syncer::Invalidation::kUnknownVersion,
-              std::string())
-          ).ToString();
+          syncer::ObjectIdInvalidationMap::InvalidateAll(
+              syncer::ModelTypeSetToObjectIdSet(changed_types))).ToString();
   const std::string& path =
       std::string("chromiumsync/sendnotification?channel=") +
       syncer::kSyncP2PNotificationChannel + "&data=" + data;
diff --git a/sync/engine/sync_scheduler_impl.cc b/sync/engine/sync_scheduler_impl.cc
index 78010d7..d8f754c 100644
--- a/sync/engine/sync_scheduler_impl.cc
+++ b/sync/engine/sync_scheduler_impl.cc
@@ -393,12 +393,12 @@ void SyncSchedulerImpl::ScheduleInvalidationNudge(
     const ObjectIdInvalidationMap& invalidation_map,
     const tracked_objects::Location& nudge_location) {
   DCHECK(CalledOnValidThread());
-  DCHECK(!invalidation_map.empty());
+  DCHECK(!invalidation_map.Empty());
 
   SDVLOG_LOC(nudge_location, 2)
       << "Scheduling sync because we received invalidation for "
-      << ModelTypeSetToString(ObjectIdSetToModelTypeSet(
-              ObjectIdInvalidationMapToSet(invalidation_map)));
+      << ModelTypeSetToString(
+          ObjectIdSetToModelTypeSet(invalidation_map.GetObjectIds()));
   nudge_tracker_.RecordRemoteInvalidation(invalidation_map);
   ScheduleNudgeImpl(desired_delay, nudge_location);
 }
diff --git a/sync/internal_api/debug_info_event_listener.cc b/sync/internal_api/debug_info_event_listener.cc
index 51e6c0f..222fa23d 100644
--- a/sync/internal_api/debug_info_event_listener.cc
+++ b/sync/internal_api/debug_info_event_listener.cc
@@ -135,19 +135,15 @@ void DebugInfoEventListener::OnNudgeFromDatatype(ModelType datatype) {
 }
 
 void DebugInfoEventListener::OnIncomingNotification(
-    const ObjectIdInvalidationMap& invalidations) {
+    const ObjectIdInvalidationMap& invalidation_map) {
   DCHECK(thread_checker_.CalledOnValidThread());
   sync_pb::DebugEventInfo event_info;
-  ModelTypeSet types = ObjectIdSetToModelTypeSet(ObjectIdInvalidationMapToSet(
-          invalidations));
-
-  for (ObjectIdInvalidationMap::const_iterator it = invalidations.begin();
-       it != invalidations.end(); ++it) {
-    ModelType type = UNSPECIFIED;
-    if (ObjectIdToRealModelType(it->first, &type)) {
-      event_info.add_datatypes_notified_from_server(
-          GetSpecificsFieldNumberFromModelType(type));
-    }
+  ModelTypeSet types =
+      ObjectIdSetToModelTypeSet(invalidation_map.GetObjectIds());
+
+  for (ModelTypeSet::Iterator it = types.First(); it.Good(); it.Inc()) {
+    event_info.add_datatypes_notified_from_server(
+        GetSpecificsFieldNumberFromModelType(it.Get()));
   }
 
   AddEventToQueue(event_info);
diff --git a/sync/internal_api/public/base/DEPS b/sync/internal_api/public/base/DEPS
index 6eae52a..047cfd4 100644
--- a/sync/internal_api/public/base/DEPS
+++ b/sync/internal_api/public/base/DEPS
@@ -1,4 +1,8 @@
 include_rules = [
+  # Invalidations headers depend on this.  We should move them to sync/notifier
+  # then remove this rule.
+  "+google/cacheinvalidation",
+
   "-sync",
   "+sync/base",
   "+sync/internal_api/public/base",
diff --git a/sync/internal_api/public/base/ack_handle.cc b/sync/internal_api/public/base/ack_handle.cc
new file mode 100644
index 0000000..f5ddf12
--- /dev/null
+++ b/sync/internal_api/public/base/ack_handle.cc
@@ -0,0 +1,67 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "sync/internal_api/public/base/ack_handle.h"
+
+#include <cstddef>
+#include "base/rand_util.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/values.h"
+
+namespace syncer {
+
+namespace {
+// Hopefully enough bytes for uniqueness.
+const size_t kBytesInHandle = 16;
+}  // namespace
+
+AckHandle AckHandle::CreateUnique() {
+  // This isn't a valid UUID, so we don't attempt to format it like one.
+  uint8 random_bytes[kBytesInHandle];
+  base::RandBytes(random_bytes, sizeof(random_bytes));
+  return AckHandle(base::HexEncode(random_bytes, sizeof(random_bytes)),
+                   base::Time::Now());
+}
+
+AckHandle AckHandle::InvalidAckHandle() {
+  return AckHandle(std::string(), base::Time());
+}
+
+bool AckHandle::Equals(const AckHandle& other) const {
+  return state_ == other.state_ && timestamp_ == other.timestamp_;
+}
+
+scoped_ptr<base::DictionaryValue> AckHandle::ToValue() const {
+  scoped_ptr<base::DictionaryValue> value(new base::DictionaryValue());
+  value->SetString("state", state_);
+  value->SetString("timestamp",
+                   base::Int64ToString(timestamp_.ToInternalValue()));
+  return value.Pass();
+}
+
+bool AckHandle::ResetFromValue(const base::DictionaryValue& value) {
+  if (!value.GetString("state", &state_))
+    return false;
+  std::string timestamp_as_string;
+  if (!value.GetString("timestamp", &timestamp_as_string))
+    return false;
+  int64 timestamp_value;
+  if (!base::StringToInt64(timestamp_as_string, &timestamp_value))
+    return false;
+  timestamp_ = base::Time::FromInternalValue(timestamp_value);
+  return true;
+}
+
+bool AckHandle::IsValid() const {
+  return !state_.empty();
+}
+
+AckHandle::AckHandle(const std::string& state, base::Time timestamp)
+    : state_(state), timestamp_(timestamp) {
+}
+
+AckHandle::~AckHandle() {
+}
+
+}  // namespace syncer
diff --git a/sync/internal_api/public/base/ack_handle.h b/sync/internal_api/public/base/ack_handle.h
new file mode 100644
index 0000000..99d03af
--- /dev/null
+++ b/sync/internal_api/public/base/ack_handle.h
@@ -0,0 +1,47 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ACK_HANDLE_H
+#define SYNC_INTERNAL_API_PUBLIC_BASE_ACK_HANDLE_H
+
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/time/time.h"
+#include "sync/base/sync_export.h"
+
+namespace base {
+class DictionaryValue;
+}
+
+namespace syncer {
+
+// Opaque class that represents a local ack handle. We don't reuse the
+// invalidation ack handles to avoid unnecessary dependencies.
+class SYNC_EXPORT AckHandle {
+ public:
+  static AckHandle CreateUnique();
+  static AckHandle InvalidAckHandle();
+
+  bool Equals(const AckHandle& other) const;
+
+  scoped_ptr<base::DictionaryValue> ToValue() const;
+  bool ResetFromValue(const base::DictionaryValue& value);
+
+  bool IsValid() const;
+
+  ~AckHandle();
+
+ private:
+  // Explicitly copyable and assignable for STL containers.
+  AckHandle(const std::string& state, base::Time timestamp);
+
+  std::string state_;
+  base::Time timestamp_;
+};
+
+}  // namespace syncer
+
+#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_ACK_HANDLE_H
diff --git a/sync/internal_api/public/base/invalidation.cc b/sync/internal_api/public/base/invalidation.cc
index b503d07..55fdcc7 100644
--- a/sync/internal_api/public/base/invalidation.cc
+++ b/sync/internal_api/public/base/invalidation.cc
@@ -5,100 +5,144 @@
 #include "sync/internal_api/public/base/invalidation.h"
 
 #include <cstddef>
+
+#include "base/json/json_string_value_serializer.h"
 #include "base/rand_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/values.h"
+#include "sync/notifier/invalidation_util.h"
 
 namespace syncer {
 
 namespace {
-// Hopefully enough bytes for uniqueness.
-const size_t kBytesInHandle = 16;
-}  // namespace
-
-AckHandle AckHandle::CreateUnique() {
-  // This isn't a valid UUID, so we don't attempt to format it like one.
-  uint8 random_bytes[kBytesInHandle];
-  base::RandBytes(random_bytes, sizeof(random_bytes));
-  return AckHandle(base::HexEncode(random_bytes, sizeof(random_bytes)),
-                   base::Time::Now());
+const char kObjectIdKey[] = "objectId";
+const char kIsUnknownVersionKey[] = "isUnknownVersion";
+const char kVersionKey[] = "version";
+const char kPayloadKey[] = "payload";
 }
 
-AckHandle AckHandle::InvalidAckHandle() {
-  return AckHandle(std::string(), base::Time());
+Invalidation Invalidation::Init(
+    const invalidation::ObjectId& id,
+    int64 version,
+    const std::string& payload) {
+  return Invalidation(id, false, version, payload, AckHandle::CreateUnique());
 }
 
-bool AckHandle::Equals(const AckHandle& other) const {
-  return state_ == other.state_ && timestamp_ == other.timestamp_;
+Invalidation Invalidation::InitUnknownVersion(
+    const invalidation::ObjectId& id) {
+  return Invalidation(id, true, -1, std::string(), AckHandle::CreateUnique());
 }
 
-scoped_ptr<base::DictionaryValue> AckHandle::ToValue() const {
-  scoped_ptr<base::DictionaryValue> value(new base::DictionaryValue());
-  value->SetString("state", state_);
-  value->SetString("timestamp",
-                   base::Int64ToString(timestamp_.ToInternalValue()));
-  return value.Pass();
-}
+scoped_ptr<Invalidation> Invalidation::InitFromValue(
+    const base::DictionaryValue& value) {
+  invalidation::ObjectId id;
 
-bool AckHandle::ResetFromValue(const base::DictionaryValue& value) {
-  if (!value.GetString("state", &state_))
-    return false;
-  std::string timestamp_as_string;
-  if (!value.GetString("timestamp", &timestamp_as_string))
-    return false;
-  int64 timestamp_value;
-  if (!base::StringToInt64(timestamp_as_string, &timestamp_value))
-    return false;
-  timestamp_ = base::Time::FromInternalValue(timestamp_value);
-  return true;
+  const base::DictionaryValue* object_id_dict;
+  if (!value.GetDictionary(kObjectIdKey, &object_id_dict)
+      || !ObjectIdFromValue(*object_id_dict, &id)) {
+    DLOG(WARNING) << "Failed to parse id";
+    return scoped_ptr<Invalidation>();
+  }
+  bool is_unknown_version;
+  if (!value.GetBoolean(kIsUnknownVersionKey, &is_unknown_version)) {
+    DLOG(WARNING) << "Failed to parse is_unknown_version flag";
+    return scoped_ptr<Invalidation>();
+  }
+  if (is_unknown_version) {
+    return scoped_ptr<Invalidation>(new Invalidation(
+        id,
+        true,
+        -1,
+        std::string(),
+        AckHandle::CreateUnique()));
+  } else {
+    int64 version;
+    std::string version_as_string;
+    if (!value.GetString(kVersionKey, &version_as_string)
+        || !base::StringToInt64(version_as_string, &version)) {
+      DLOG(WARNING) << "Failed to parse version";
+      return scoped_ptr<Invalidation>();
+    }
+    std::string payload;
+    if (!value.GetString(kPayloadKey, &payload)) {
+      DLOG(WARNING) << "Failed to parse payload";
+      return scoped_ptr<Invalidation>();
+    }
+    return scoped_ptr<Invalidation>(new Invalidation(
+        id,
+        false,
+        version,
+        payload,
+        AckHandle::CreateUnique()));
+  }
 }
 
-bool AckHandle::IsValid() const {
-  return !state_.empty();
+Invalidation::~Invalidation() {}
+
+invalidation::ObjectId Invalidation::object_id() const {
+  return id_;
 }
 
-AckHandle::AckHandle(const std::string& state, base::Time timestamp)
-    : state_(state), timestamp_(timestamp) {
+bool Invalidation::is_unknown_version() const {
+  return is_unknown_version_;
 }
 
-AckHandle::~AckHandle() {
+int64 Invalidation::version() const {
+  DCHECK(!is_unknown_version_);
+  return version_;
 }
 
-const int64 Invalidation::kUnknownVersion = -1;
+const std::string& Invalidation::payload() const {
+  DCHECK(!is_unknown_version_);
+  return payload_;
+}
 
-Invalidation::Invalidation()
-    : version(kUnknownVersion), ack_handle(AckHandle::InvalidAckHandle()) {
+const AckHandle& Invalidation::ack_handle() const {
+  return ack_handle_;
 }
 
-Invalidation::~Invalidation() {
+void Invalidation::set_ack_handle(const AckHandle& ack_handle) {
+  ack_handle_ = ack_handle;
 }
 
 bool Invalidation::Equals(const Invalidation& other) const {
-  return (version == other.version) && (payload == other.payload) &&
-      ack_handle.Equals(other.ack_handle);
+  return id_ == other.id_
+      && is_unknown_version_ == other.is_unknown_version_
+      && version_ == other.version_
+      && payload_ == other.payload_;
 }
 
 scoped_ptr<base::DictionaryValue> Invalidation::ToValue() const {
   scoped_ptr<base::DictionaryValue> value(new base::DictionaryValue());
-  value->SetString("version", base::Int64ToString(version));
-  value->SetString("payload", payload);
-  value->Set("ackHandle", ack_handle.ToValue().release());
+  value->Set(kObjectIdKey, ObjectIdToValue(id_).release());
+  if (is_unknown_version_) {
+    value->SetBoolean(kIsUnknownVersionKey, true);
+  } else {
+    value->SetBoolean(kIsUnknownVersionKey, false);
+    value->SetString(kVersionKey, base::Int64ToString(version_));
+    value->SetString(kPayloadKey, payload_);
+  }
   return value.Pass();
 }
 
-bool Invalidation::ResetFromValue(const base::DictionaryValue& value) {
-  const base::DictionaryValue* ack_handle_value = NULL;
-  std::string version_as_string;
-  if (value.GetString("version", &version_as_string)) {
-    if (!base::StringToInt64(version_as_string, &version))
-      return false;
-  } else {
-    version = kUnknownVersion;
-  }
-  return
-      value.GetString("payload", &payload) &&
-      value.GetDictionary("ackHandle", &ack_handle_value) &&
-      ack_handle.ResetFromValue(*ack_handle_value);
+std::string Invalidation::ToString() const {
+  std::string output;
+  JSONStringValueSerializer serializer(&output);
+  serializer.set_pretty_print(true);
+  serializer.Serialize(*ToValue().get());
+  return output;
 }
 
+Invalidation::Invalidation(
+    const invalidation::ObjectId& id,
+    bool is_unknown_version,
+    int64 version,
+    const std::string& payload,
+    AckHandle ack_handle)
+  : id_(id),
+    is_unknown_version_(is_unknown_version),
+    version_(version),
+    payload_(payload),
+    ack_handle_(ack_handle) {}
+
 }  // namespace syncer
diff --git a/sync/internal_api/public/base/invalidation.h b/sync/internal_api/public/base/invalidation.h
index 851dbed..2b83564b 100644
--- a/sync/internal_api/public/base/invalidation.h
+++ b/sync/internal_api/public/base/invalidation.h
@@ -9,59 +9,73 @@
 
 #include "base/basictypes.h"
 #include "base/memory/scoped_ptr.h"
-#include "base/time/time.h"
+#include "base/values.h"
+#include "google/cacheinvalidation/include/types.h"
 #include "sync/base/sync_export.h"
-
-namespace base {
-class DictionaryValue;
-}  // namespace
+#include "sync/internal_api/public/base/ack_handle.h"
 
 namespace syncer {
 
-// Opaque class that represents a local ack handle. We don't reuse the
-// invalidation ack handles to avoid unnecessary dependencies.
-class SYNC_EXPORT AckHandle {
+class DroppedInvalidationTracker;
+class AckHandler;
+
+// Represents a local invalidation, and is roughly analogous to
+// invalidation::Invalidation.  Unlike invalidation::Invalidation, this class
+// supports "local" ack-tracking and simple serialization to pref values.
+class SYNC_EXPORT Invalidation {
  public:
-  static AckHandle CreateUnique();
-  static AckHandle InvalidAckHandle();
+  // Factory functions.
+  static Invalidation Init(
+      const invalidation::ObjectId& id,
+      int64 version,
+      const std::string& payload);
+  static Invalidation InitUnknownVersion(const invalidation::ObjectId& id);
+  static scoped_ptr<Invalidation> InitFromValue(
+      const base::DictionaryValue& value);
+
+  ~Invalidation();
+
+  // Compares two invalidations.  The comparison ignores ack-tracking state.
+  bool Equals(const Invalidation& other) const;
 
-  bool Equals(const AckHandle& other) const;
+  invalidation::ObjectId object_id() const;
+  bool is_unknown_version() const;
 
-  scoped_ptr<base::DictionaryValue> ToValue() const;
-  bool ResetFromValue(const base::DictionaryValue& value);
+  // Safe to call only if is_unknown_version() returns false.
+  int64 version() const;
 
-  bool IsValid() const;
+  // Safe to call only if is_unknown_version() returns false.
+  const std::string& payload() const;
 
-  ~AckHandle();
+  const AckHandle& ack_handle() const;
+  void set_ack_handle(const AckHandle& ack_handle);
+
+  scoped_ptr<base::DictionaryValue> ToValue() const;
+  std::string ToString() const;
 
  private:
-  // Explicitly copyable and assignable for STL containers.
-  AckHandle(const std::string& state, base::Time timestamp);
+  Invalidation(const invalidation::ObjectId& id,
+               bool is_unknown_version,
+               int64 version,
+               const std::string& payload,
+               AckHandle ack_handle);
 
-  std::string state_;
-  base::Time timestamp_;
-};
+  // The ObjectId to which this invalidation belongs.
+  invalidation::ObjectId id_;
 
-// Represents a local invalidation, and is roughly analogous to
-// invalidation::Invalidation. It contains a version (which may be
-// kUnknownVersion), a payload (which may be empty) and an
-// associated ack handle that an InvalidationHandler implementation can use to
-// acknowledge receipt of the invalidation. It does not embed the object ID,
-// since it is typically associated with it through ObjectIdInvalidationMap.
-struct SYNC_EXPORT Invalidation {
-  static const int64 kUnknownVersion;
-
-  Invalidation();
-  ~Invalidation();
+  // This flag is set to true if this is an unknown version invalidation.
+  bool is_unknown_version_;
 
-  bool Equals(const Invalidation& other) const;
+  // The version number of this invalidation.  Should not be accessed if this is
+  // an unkown version invalidation.
+  int64 version_;
 
-  scoped_ptr<base::DictionaryValue> ToValue() const;
-  bool ResetFromValue(const base::DictionaryValue& value);
+  // The payaload associated with this invalidation.  Should not be accessed if
+  // this is an unknown version invalidation.
+  std::string payload_;
 
-  int64 version;
-  std::string payload;
-  AckHandle ack_handle;
+  // A locally generated unique ID used to manage local acknowledgements.
+  AckHandle ack_handle_;
 };
 
 }  // namespace syncer
diff --git a/sync/internal_api/public/base/invalidation_test_util.cc b/sync/internal_api/public/base/invalidation_test_util.cc
index 3f3910b..3c610da 100644
--- a/sync/internal_api/public/base/invalidation_test_util.cc
+++ b/sync/internal_api/public/base/invalidation_test_util.cc
@@ -75,7 +75,18 @@ InvalidationEqMatcher::InvalidationEqMatcher(
 
 bool InvalidationEqMatcher::MatchAndExplain(
     const Invalidation& actual, MatchResultListener* listener) const {
-  return expected_.payload == actual.payload;
+  if (!(expected_.object_id() == actual.object_id())) {
+    return false;
+  }
+  if (expected_.is_unknown_version() && actual.is_unknown_version()) {
+    return true;
+  } else if (expected_.is_unknown_version() != actual.is_unknown_version()) {
+    return false;
+  } else {
+    // Neither is unknown version.
+    return expected_.payload() == actual.payload()
+        && expected_.version() == actual.version();
+  }
 }
 
 void InvalidationEqMatcher::DescribeTo(::std::ostream* os) const {
@@ -99,12 +110,8 @@ Matcher<const AckHandle&> Eq(const AckHandle& expected) {
   return MakeMatcher(new AckHandleEqMatcher(expected));
 }
 
-void PrintTo(const Invalidation& state, ::std::ostream* os) {
-  std::string printable_payload;
-  base::JsonDoubleQuote(state.payload,
-                        true /* put_in_quotes */,
-                        &printable_payload);
-  *os << "{ payload: " << printable_payload << " }";
+void PrintTo(const Invalidation& inv, ::std::ostream* os) {
+  *os << "{ payload: " << inv.ToString() << " }";
 }
 
 Matcher<const Invalidation&> Eq(const Invalidation& expected) {
diff --git a/sync/internal_api/public/base/invalidation_test_util.h b/sync/internal_api/public/base/invalidation_test_util.h
index 9376a28..e7c08caa 100644
--- a/sync/internal_api/public/base/invalidation_test_util.h
+++ b/sync/internal_api/public/base/invalidation_test_util.h
@@ -12,7 +12,7 @@
 namespace syncer {
 
 class AckHandle;
-struct Invalidation;
+class Invalidation;
 
 void PrintTo(const AckHandle& ack_handle, ::std::ostream* os);
 ::testing::Matcher<const AckHandle&> Eq(const AckHandle& expected);
diff --git a/sync/internal_api/public/base/model_type_test_util.cc b/sync/internal_api/public/base/model_type_test_util.cc
index 242b398..efad29c1 100644
--- a/sync/internal_api/public/base/model_type_test_util.cc
+++ b/sync/internal_api/public/base/model_type_test_util.cc
@@ -12,16 +12,9 @@ ObjectIdInvalidationMap BuildInvalidationMap(
     const std::string& payload) {
   ObjectIdInvalidationMap map;
   invalidation::ObjectId id;
-  Invalidation invalidation;
-
   bool result = RealModelTypeToObjectId(type, &id);
-  DCHECK(result)
-      << "Conversion of model type to object id failed: "
-      << ModelTypeToString(type);
-  invalidation.version = version;
-  invalidation.payload = payload;
-
-  map.insert(std::make_pair(id, invalidation));
+  DCHECK(result);
+  map.Insert(Invalidation::Init(id, version, payload));
   return map;
 }
 
diff --git a/sync/notifier/object_id_invalidation_map_test_util.cc b/sync/internal_api/public/base/object_id_invalidation_map_test_util.cc
index f2f8285..777fc69 100644
--- a/sync/notifier/object_id_invalidation_map_test_util.cc
+++ b/sync/internal_api/public/base/object_id_invalidation_map_test_util.cc
@@ -1,8 +1,8 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
+#include "sync/internal_api/public/base/object_id_invalidation_map_test_util.h"
 
 #include <algorithm>
 
@@ -24,7 +24,7 @@ class ObjectIdInvalidationMapEqMatcher
   explicit ObjectIdInvalidationMapEqMatcher(
       const ObjectIdInvalidationMap& expected);
 
-  virtual bool MatchAndExplain(const ObjectIdInvalidationMap& actual,
+  virtual bool MatchAndExplain(const ObjectIdInvalidationMap& lhs,
                                MatchResultListener* listener) const;
   virtual void DescribeTo(::std::ostream* os) const;
   virtual void DescribeNegationTo(::std::ostream* os) const;
@@ -39,37 +39,57 @@ ObjectIdInvalidationMapEqMatcher::ObjectIdInvalidationMapEqMatcher(
     const ObjectIdInvalidationMap& expected) : expected_(expected) {
 }
 
+namespace {
+
+struct InvalidationEqPredicate {
+  InvalidationEqPredicate(const Invalidation& inv1)
+      : inv1_(inv1) { }
+
+  bool operator()(const Invalidation& inv2) {
+    return inv1_.Equals(inv2);
+  }
+
+  const Invalidation& inv1_;
+};
+
+}
+
 bool ObjectIdInvalidationMapEqMatcher::MatchAndExplain(
     const ObjectIdInvalidationMap& actual,
     MatchResultListener* listener) const {
-  ObjectIdInvalidationMap expected_only;
-  ObjectIdInvalidationMap actual_only;
-  typedef std::pair<invalidation::ObjectId,
-                    std::pair<Invalidation, Invalidation> >
-      ValueDifference;
-  std::vector<ValueDifference> value_differences;
-
-  std::set_difference(expected_.begin(), expected_.end(),
-                      actual.begin(), actual.end(),
-                      std::inserter(expected_only, expected_only.begin()),
-                      expected_.value_comp());
-  std::set_difference(actual.begin(), actual.end(),
-                      expected_.begin(), expected_.end(),
-                      std::inserter(actual_only, actual_only.begin()),
-                      actual.value_comp());
-
-  for (ObjectIdInvalidationMap::const_iterator it = expected_.begin();
-       it != expected_.end(); ++it) {
-    ObjectIdInvalidationMap::const_iterator find_it =
-        actual.find(it->first);
-    if (find_it != actual.end() &&
-        !Matches(Eq(it->second))(find_it->second)) {
-      value_differences.push_back(std::make_pair(
-          it->first, std::make_pair(it->second, find_it->second)));
+
+  std::vector<syncer::Invalidation> expected_invalidations;
+  std::vector<syncer::Invalidation> actual_invalidations;
+
+  expected_.GetAllInvalidations(&expected_invalidations);
+  actual.GetAllInvalidations(&actual_invalidations);
+
+  std::vector<syncer::Invalidation> expected_only;
+  std::vector<syncer::Invalidation> actual_only;
+
+  for (std::vector<syncer::Invalidation>::iterator it =
+       expected_invalidations.begin();
+       it != expected_invalidations.end(); ++it) {
+    if (std::find_if(actual_invalidations.begin(),
+                     actual_invalidations.end(),
+                     InvalidationEqPredicate(*it))
+        == actual_invalidations.end()) {
+      expected_only.push_back(*it);
     }
   }
 
-  if (expected_only.empty() && actual_only.empty() && value_differences.empty())
+  for (std::vector<syncer::Invalidation>::iterator it =
+       actual_invalidations.begin();
+       it != actual_invalidations.end(); ++it) {
+    if (std::find_if(expected_invalidations.begin(),
+                     expected_invalidations.end(),
+                     InvalidationEqPredicate(*it))
+        == expected_invalidations.end()) {
+      actual_only.push_back(*it);
+    }
+  }
+
+  if (expected_only.empty() && actual_only.empty())
     return true;
 
   bool printed_header = false;
@@ -86,12 +106,6 @@ bool ObjectIdInvalidationMapEqMatcher::MatchAndExplain(
     printed_header = true;
   }
 
-  if (!value_differences.empty()) {
-    *listener << (printed_header ? ",\nand" : "which")
-              << " differ in the following values: "
-              << PrintToString(value_differences);
-  }
-
   return false;
 }
 
@@ -99,8 +113,8 @@ void ObjectIdInvalidationMapEqMatcher::DescribeTo(::std::ostream* os) const {
   *os << " is equal to " << PrintToString(expected_);
 }
 
-void ObjectIdInvalidationMapEqMatcher::DescribeNegationTo
-(::std::ostream* os) const {
+void ObjectIdInvalidationMapEqMatcher::DescribeNegationTo(
+    ::std::ostream* os) const {
   *os << " isn't equal to " << PrintToString(expected_);
 }
 
diff --git a/sync/notifier/object_id_invalidation_map_test_util.h b/sync/internal_api/public/base/object_id_invalidation_map_test_util.h
index 0217da8..5d71979 100644
--- a/sync/notifier/object_id_invalidation_map_test_util.h
+++ b/sync/internal_api/public/base/object_id_invalidation_map_test_util.h
@@ -1,13 +1,12 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_TEST_UTILH_
-#define SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_TEST_UTILH_
+#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_OBJECT_ID_INVALIDATION_MAP_TEST_UTIL_H_
+#define SYNC_INTERNAL_API_PUBLIC_BASE_OBJECT_ID_INVALIDATION_MAP_TEST_UTIL_H_
 
 // Convince googletest to use the correct overload for PrintTo().
 #include "sync/internal_api/public/base/invalidation_test_util.h"
-#include "sync/internal_api/public/base/model_type.h"
 #include "sync/notifier/object_id_invalidation_map.h"
 #include "testing/gmock/include/gmock/gmock.h"
 
@@ -18,4 +17,4 @@ namespace syncer {
 
 }  // namespace syncer
 
-#endif  // SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_TEST_UTILH_
+#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_OBJECT_ID_INVALIDATION_MAP_TEST_UTIL_H_
diff --git a/sync/internal_api/sync_manager_impl.cc b/sync/internal_api/sync_manager_impl.cc
index f79213d..418fd1f 100644
--- a/sync/internal_api/sync_manager_impl.cc
+++ b/sync/internal_api/sync_manager_impl.cc
@@ -1005,7 +1005,7 @@ base::DictionaryValue* SyncManagerImpl::NotificationInfoToValue(
 
   for (NotificationInfoMap::const_iterator it = notification_info.begin();
       it != notification_info.end(); ++it) {
-    const std::string& model_type_str = ModelTypeToString(it->first);
+    const std::string model_type_str = ModelTypeToString(it->first);
     value->Set(model_type_str, it->second.ToValue());
   }
 
@@ -1148,13 +1148,22 @@ JsArgList SyncManagerImpl::GetChildNodeIds(const JsArgList& args) {
 
 void SyncManagerImpl::UpdateNotificationInfo(
     const ObjectIdInvalidationMap& invalidation_map) {
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
+  ObjectIdSet ids = invalidation_map.GetObjectIds();
+  for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
     ModelType type = UNSPECIFIED;
-    if (ObjectIdToRealModelType(it->first, &type)) {
+    if (!ObjectIdToRealModelType(*it, &type)) {
+      continue;
+    }
+    const SingleObjectInvalidationSet& type_invalidations =
+        invalidation_map.ForObject(*it);
+    for (SingleObjectInvalidationSet::const_iterator inv_it =
+         type_invalidations.begin(); inv_it != type_invalidations.end();
+         ++inv_it) {
       NotificationInfo* info = &notification_info_map_[type];
       info->total_count++;
-      info->payload = it->second.payload;
+      std::string payload =
+          inv_it->is_unknown_version() ? "UNKNOWN" : inv_it->payload();
+      info->payload = payload;
     }
   }
 }
@@ -1185,7 +1194,7 @@ void SyncManagerImpl::OnIncomingInvalidation(
   DCHECK(thread_checker_.CalledOnValidThread());
 
   // We should never receive IDs from non-sync objects.
-  ObjectIdSet ids = ObjectIdInvalidationMapToSet(invalidation_map);
+  ObjectIdSet ids = invalidation_map.GetObjectIds();
   for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
     ModelType type;
     if (!ObjectIdToRealModelType(*it, &type)) {
@@ -1193,7 +1202,7 @@ void SyncManagerImpl::OnIncomingInvalidation(
     }
   }
 
-  if (invalidation_map.empty()) {
+  if (invalidation_map.Empty()) {
     LOG(WARNING) << "Sync received invalidation without any type information.";
   } else {
     allstatus_.IncrementNudgeCounter(NUDGE_SOURCE_NOTIFICATION);
@@ -1209,7 +1218,8 @@ void SyncManagerImpl::OnIncomingInvalidation(
     base::DictionaryValue details;
     base::ListValue* changed_types = new base::ListValue();
     details.Set("changedTypes", changed_types);
-    ObjectIdSet id_set = ObjectIdInvalidationMapToSet(invalidation_map);
+
+    ObjectIdSet id_set = invalidation_map.GetObjectIds();
     ModelTypeSet nudged_types = ObjectIdSetToModelTypeSet(id_set);
     DCHECK(!nudged_types.Empty());
     for (ModelTypeSet::Iterator it = nudged_types.First();
diff --git a/sync/internal_api/sync_manager_impl_unittest.cc b/sync/internal_api/sync_manager_impl_unittest.cc
index 2e0d9ae..5549895 100644
--- a/sync/internal_api/sync_manager_impl_unittest.cc
+++ b/sync/internal_api/sync_manager_impl_unittest.cc
@@ -985,9 +985,7 @@ class SyncManagerTest : public testing::Test,
     DCHECK(sync_manager_.thread_checker_.CalledOnValidThread());
     ObjectIdSet id_set = ModelTypeSetToObjectIdSet(model_types);
     ObjectIdInvalidationMap invalidation_map =
-        ObjectIdSetToInvalidationMap(id_set,
-                                     Invalidation::kUnknownVersion,
-                                     std::string());
+        ObjectIdInvalidationMap::InvalidateAll(id_set);
     sync_manager_.OnIncomingInvalidation(invalidation_map);
   }
 
diff --git a/sync/notifier/invalidation_notifier_unittest.cc b/sync/notifier/invalidation_notifier_unittest.cc
index 623bfa9..1f14319 100644
--- a/sync/notifier/invalidation_notifier_unittest.cc
+++ b/sync/notifier/invalidation_notifier_unittest.cc
@@ -16,7 +16,6 @@
 #include "sync/notifier/fake_invalidation_state_tracker.h"
 #include "sync/notifier/invalidation_state_tracker.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
diff --git a/sync/notifier/invalidator_registrar.cc b/sync/notifier/invalidator_registrar.cc
index c2a18f9..43afa6e 100644
--- a/sync/notifier/invalidator_registrar.cc
+++ b/sync/notifier/invalidator_registrar.cc
@@ -8,6 +8,7 @@
 #include <utility>
 
 #include "base/logging.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace syncer {
 
@@ -17,7 +18,7 @@ InvalidatorRegistrar::InvalidatorRegistrar()
 InvalidatorRegistrar::~InvalidatorRegistrar() {
   DCHECK(thread_checker_.CalledOnValidThread());
   CHECK(!handlers_.might_have_observers());
-  // |id_to_handler_map_| may be non-empty but that's okay.
+  CHECK(handler_to_ids_map_.empty());
 }
 
 void InvalidatorRegistrar::RegisterHandler(InvalidationHandler* handler) {
@@ -33,29 +34,29 @@ void InvalidatorRegistrar::UpdateRegisteredIds(
   DCHECK(thread_checker_.CalledOnValidThread());
   CHECK(handler);
   CHECK(handlers_.HasObserver(handler));
-  // Remove all existing entries for |handler|.
-  for (IdHandlerMap::iterator it = id_to_handler_map_.begin();
-       it != id_to_handler_map_.end(); ) {
-    if (it->second == handler) {
-      IdHandlerMap::iterator erase_it = it;
-      ++it;
-      id_to_handler_map_.erase(erase_it);
-    } else {
-      ++it;
+
+  for (HandlerIdsMap::const_iterator it = handler_to_ids_map_.begin();
+       it != handler_to_ids_map_.end(); ++it) {
+    if (it->first == handler) {
+      continue;
     }
-  }
 
-  // Now add the entries for |handler|. We keep track of the last insertion
-  // point so we only traverse the map once to insert all the new entries.
-  IdHandlerMap::iterator insert_it = id_to_handler_map_.begin();
-  for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
-    insert_it =
-        id_to_handler_map_.insert(insert_it, std::make_pair(*it, handler));
-    CHECK_EQ(handler, insert_it->second)
+    std::vector<invalidation::ObjectId> intersection;
+    std::set_intersection(
+        it->second.begin(), it->second.end(),
+        ids.begin(), ids.end(),
+        intersection.begin(), ObjectIdLessThan());
+    CHECK(intersection.empty())
         << "Duplicate registration: trying to register "
-        << ObjectIdToString(insert_it->first) << " for "
+        << ObjectIdToString(*intersection.begin()) << " for "
         << handler << " when it's already registered for "
-        << insert_it->second;
+        << it->first;
+  }
+
+  if (ids.empty()) {
+    handler_to_ids_map_.erase(handler);
+  } else {
+    handler_to_ids_map_[handler] = ids;
   }
 }
 
@@ -64,27 +65,26 @@ void InvalidatorRegistrar::UnregisterHandler(InvalidationHandler* handler) {
   CHECK(handler);
   CHECK(handlers_.HasObserver(handler));
   handlers_.RemoveObserver(handler);
+  handler_to_ids_map_.erase(handler);
 }
 
 ObjectIdSet InvalidatorRegistrar::GetRegisteredIds(
     InvalidationHandler* handler) const {
   DCHECK(thread_checker_.CalledOnValidThread());
-  ObjectIdSet registered_ids;
-  for (IdHandlerMap::const_iterator it = id_to_handler_map_.begin();
-       it != id_to_handler_map_.end(); ++it) {
-    if (it->second == handler) {
-      registered_ids.insert(it->first);
-    }
+  HandlerIdsMap::const_iterator lookup = handler_to_ids_map_.find(handler);
+  if (lookup != handler_to_ids_map_.end()) {
+    return lookup->second;
+  } else {
+    return ObjectIdSet();
   }
-  return registered_ids;
 }
 
 ObjectIdSet InvalidatorRegistrar::GetAllRegisteredIds() const {
   DCHECK(thread_checker_.CalledOnValidThread());
   ObjectIdSet registered_ids;
-  for (IdHandlerMap::const_iterator it = id_to_handler_map_.begin();
-       it != id_to_handler_map_.end(); ++it) {
-    registered_ids.insert(it->first);
+  for (HandlerIdsMap::const_iterator it = handler_to_ids_map_.begin();
+       it != handler_to_ids_map_.end(); ++it) {
+    registered_ids.insert(it->second.begin(), it->second.end());
   }
   return registered_ids;
 }
@@ -97,23 +97,13 @@ void InvalidatorRegistrar::DispatchInvalidationsToHandlers(
     return;
   }
 
-  typedef std::map<InvalidationHandler*, ObjectIdInvalidationMap> DispatchMap;
-  DispatchMap dispatch_map;
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
-    InvalidationHandler* const handler = ObjectIdToHandler(it->first);
-    // Filter out invalidations for IDs with no handler.
-    if (handler)
-      dispatch_map[handler].insert(*it);
-  }
-
-  // Emit invalidations only for handlers in |handlers_|.
-  ObserverListBase<InvalidationHandler>::Iterator it(handlers_);
-  InvalidationHandler* handler = NULL;
-  while ((handler = it.GetNext()) != NULL) {
-    DispatchMap::const_iterator dispatch_it = dispatch_map.find(handler);
-    if (dispatch_it != dispatch_map.end())
-      handler->OnIncomingInvalidation(dispatch_it->second);
+  for (HandlerIdsMap::iterator it = handler_to_ids_map_.begin();
+       it != handler_to_ids_map_.end(); ++it) {
+    ObjectIdInvalidationMap to_emit =
+        invalidation_map.GetSubsetWithObjectIds(it->second);
+    if (!to_emit.Empty()) {
+      it->first->OnIncomingInvalidation(to_emit);
+    }
   }
 }
 
@@ -142,11 +132,4 @@ void InvalidatorRegistrar::DetachFromThreadForTest() {
   thread_checker_.DetachFromThread();
 }
 
-InvalidationHandler* InvalidatorRegistrar::ObjectIdToHandler(
-    const invalidation::ObjectId& id) {
-  DCHECK(thread_checker_.CalledOnValidThread());
-  IdHandlerMap::const_iterator it = id_to_handler_map_.find(id);
-  return (it == id_to_handler_map_.end()) ? NULL : it->second;
-}
-
 }  // namespace syncer
diff --git a/sync/notifier/invalidator_registrar.h b/sync/notifier/invalidator_registrar.h
index f2a3c63..fb6b388 100644
--- a/sync/notifier/invalidator_registrar.h
+++ b/sync/notifier/invalidator_registrar.h
@@ -13,7 +13,6 @@
 #include "sync/base/sync_export.h"
 #include "sync/notifier/invalidation_handler.h"
 #include "sync/notifier/invalidation_util.h"
-#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace invalidation {
 class ObjectId;
@@ -21,6 +20,8 @@ class ObjectId;
 
 namespace syncer {
 
+class ObjectIdInvalidationMap;
+
 // A helper class for implementations of the Invalidator interface.  It helps
 // keep track of registered handlers and which object ID registrations are
 // associated with which handlers, so implementors can just reuse the logic
@@ -76,15 +77,11 @@ class SYNC_EXPORT InvalidatorRegistrar {
   void DetachFromThreadForTest();
 
  private:
-  typedef std::map<invalidation::ObjectId, InvalidationHandler*,
-                   ObjectIdLessThan>
-      IdHandlerMap;
-
-  InvalidationHandler* ObjectIdToHandler(const invalidation::ObjectId& id);
+  typedef std::map<InvalidationHandler*, ObjectIdSet> HandlerIdsMap;
 
   base::ThreadChecker thread_checker_;
   ObserverList<InvalidationHandler> handlers_;
-  IdHandlerMap id_to_handler_map_;
+  HandlerIdsMap handler_to_ids_map_;
   InvalidatorState state_;
 
   DISALLOW_COPY_AND_ASSIGN(InvalidatorRegistrar);
diff --git a/sync/notifier/invalidator_registrar_unittest.cc b/sync/notifier/invalidator_registrar_unittest.cc
index ad22247..7a01401 100644
--- a/sync/notifier/invalidator_registrar_unittest.cc
+++ b/sync/notifier/invalidator_registrar_unittest.cc
@@ -9,7 +9,6 @@
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/invalidator_registrar.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
diff --git a/sync/notifier/invalidator_test_template.h b/sync/notifier/invalidator_test_template.h
index 0353000..b86cf50 100644
--- a/sync/notifier/invalidator_test_template.h
+++ b/sync/notifier/invalidator_test_template.h
@@ -81,11 +81,11 @@
 #include "base/compiler_specific.h"
 #include "google/cacheinvalidation/include/types.h"
 #include "google/cacheinvalidation/types.pb.h"
+#include "sync/internal_api/public/base/invalidation_test_util.h"
+#include "sync/internal_api/public/base/object_id_invalidation_map_test_util.h"
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/fake_invalidation_state_tracker.h"
 #include "sync/notifier/invalidator.h"
-#include "sync/notifier/object_id_invalidation_map.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
@@ -135,13 +135,13 @@ TYPED_TEST_P(InvalidatorTest, Basic) {
 
   invalidator->RegisterHandler(&handler);
 
-  ObjectIdInvalidationMap states;
-  states[this->id1].payload = "1";
-  states[this->id2].payload = "2";
-  states[this->id3].payload = "3";
+  ObjectIdInvalidationMap invalidation_map;
+  invalidation_map.Insert(Invalidation::Init(this->id1, 1, "1"));
+  invalidation_map.Insert(Invalidation::Init(this->id2, 2, "2"));
+  invalidation_map.Insert(Invalidation::Init(this->id3, 3, "3"));
 
   // Should be ignored since no IDs are registered to |handler|.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(0, handler.GetInvalidationCount());
 
   ObjectIdSet ids;
@@ -152,25 +152,26 @@ TYPED_TEST_P(InvalidatorTest, Basic) {
   this->delegate_.TriggerOnInvalidatorStateChange(INVALIDATIONS_ENABLED);
   EXPECT_EQ(INVALIDATIONS_ENABLED, handler.GetInvalidatorState());
 
-  ObjectIdInvalidationMap expected_states;
-  expected_states[this->id1].payload = "1";
-  expected_states[this->id2].payload = "2";
+  ObjectIdInvalidationMap expected_invalidations;
+  expected_invalidations.Insert(Invalidation::Init(this->id1, 1, "1"));
+  expected_invalidations.Insert(Invalidation::Init(this->id2, 2, "2"));
 
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(1, handler.GetInvalidationCount());
-  EXPECT_THAT(expected_states, Eq(handler.GetLastInvalidationMap()));
+  EXPECT_THAT(expected_invalidations, Eq(handler.GetLastInvalidationMap()));
 
   ids.erase(this->id1);
   ids.insert(this->id3);
   invalidator->UpdateRegisteredIds(&handler, ids);
 
-  expected_states.erase(this->id1);
-  expected_states[this->id3].payload = "3";
+  expected_invalidations = ObjectIdInvalidationMap();
+  expected_invalidations.Insert(Invalidation::Init(this->id2, 2, "2"));
+  expected_invalidations.Insert(Invalidation::Init(this->id3, 3, "3"));
 
   // Removed object IDs should not be notified, newly-added ones should.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(2, handler.GetInvalidationCount());
-  EXPECT_THAT(expected_states, Eq(handler.GetLastInvalidationMap()));
+  EXPECT_THAT(expected_invalidations, Eq(handler.GetLastInvalidationMap()));
 
   this->delegate_.TriggerOnInvalidatorStateChange(TRANSIENT_INVALIDATION_ERROR);
   EXPECT_EQ(TRANSIENT_INVALIDATION_ERROR,
@@ -184,7 +185,7 @@ TYPED_TEST_P(InvalidatorTest, Basic) {
   invalidator->UnregisterHandler(&handler);
 
   // Should be ignored since |handler| isn't registered anymore.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(2, handler.GetInvalidationCount());
 }
 
@@ -236,25 +237,26 @@ TYPED_TEST_P(InvalidatorTest, MultipleHandlers) {
   EXPECT_EQ(TRANSIENT_INVALIDATION_ERROR, handler4.GetInvalidatorState());
 
   {
-    ObjectIdInvalidationMap states;
-    states[this->id1].payload = "1";
-    states[this->id2].payload = "2";
-    states[this->id3].payload = "3";
-    states[this->id4].payload = "4";
-    this->delegate_.TriggerOnIncomingInvalidation(states);
+    ObjectIdInvalidationMap invalidation_map;
+    invalidation_map.Insert(Invalidation::Init(this->id1, 1, "1"));
+    invalidation_map.Insert(Invalidation::Init(this->id2, 2, "2"));
+    invalidation_map.Insert(Invalidation::Init(this->id3, 3, "3"));
+    invalidation_map.Insert(Invalidation::Init(this->id4, 4, "4"));
 
-    ObjectIdInvalidationMap expected_states;
-    expected_states[this->id1].payload = "1";
-    expected_states[this->id2].payload = "2";
+    this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
+
+    ObjectIdInvalidationMap expected_invalidations;
+    expected_invalidations.Insert(Invalidation::Init(this->id1, 1, "1"));
+    expected_invalidations.Insert(Invalidation::Init(this->id2, 2, "2"));
 
     EXPECT_EQ(1, handler1.GetInvalidationCount());
-    EXPECT_THAT(expected_states, Eq(handler1.GetLastInvalidationMap()));
+    EXPECT_THAT(expected_invalidations, Eq(handler1.GetLastInvalidationMap()));
 
-    expected_states.clear();
-    expected_states[this->id3].payload = "3";
+    expected_invalidations = ObjectIdInvalidationMap();
+    expected_invalidations.Insert(Invalidation::Init(this->id3, 3, "3"));
 
     EXPECT_EQ(1, handler2.GetInvalidationCount());
-    EXPECT_THAT(expected_states, Eq(handler2.GetLastInvalidationMap()));
+    EXPECT_THAT(expected_invalidations, Eq(handler2.GetLastInvalidationMap()));
 
     EXPECT_EQ(0, handler3.GetInvalidationCount());
     EXPECT_EQ(0, handler4.GetInvalidationCount());
@@ -306,11 +308,11 @@ TYPED_TEST_P(InvalidatorTest, EmptySetUnregisters) {
   EXPECT_EQ(INVALIDATIONS_ENABLED, handler2.GetInvalidatorState());
 
   {
-    ObjectIdInvalidationMap states;
-    states[this->id1].payload = "1";
-    states[this->id2].payload = "2";
-    states[this->id3].payload = "3";
-    this->delegate_.TriggerOnIncomingInvalidation(states);
+    ObjectIdInvalidationMap invalidation_map;
+    invalidation_map.Insert(Invalidation::Init(this->id1, 1, "1"));
+    invalidation_map.Insert(Invalidation::Init(this->id2, 2, "2"));
+    invalidation_map.Insert(Invalidation::Init(this->id3, 3, "3"));
+    this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
     EXPECT_EQ(0, handler1.GetInvalidationCount());
     EXPECT_EQ(1, handler2.GetInvalidationCount());
   }
diff --git a/sync/notifier/non_blocking_invalidator_unittest.cc b/sync/notifier/non_blocking_invalidator_unittest.cc
index f463077..e9cf31e 100644
--- a/sync/notifier/non_blocking_invalidator_unittest.cc
+++ b/sync/notifier/non_blocking_invalidator_unittest.cc
@@ -17,7 +17,6 @@
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/invalidation_state_tracker.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
diff --git a/sync/notifier/object_id_invalidation_map.cc b/sync/notifier/object_id_invalidation_map.cc
index bde2e4c..e1f584d 100644
--- a/sync/notifier/object_id_invalidation_map.cc
+++ b/sync/notifier/object_id_invalidation_map.cc
@@ -1,93 +1,112 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sync/notifier/object_id_invalidation_map.h"
 
-#include <algorithm>
-
-#include "base/compiler_specific.h"
-#include "base/values.h"
+#include "base/json/json_string_value_serializer.h"
 
 namespace syncer {
 
-ObjectIdSet ObjectIdInvalidationMapToSet(
-    const ObjectIdInvalidationMap& invalidation_map) {
-  ObjectIdSet ids;
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
-    ids.insert(it->first);
+// static
+ObjectIdInvalidationMap ObjectIdInvalidationMap::InvalidateAll(
+    const ObjectIdSet& ids) {
+  ObjectIdInvalidationMap invalidate_all;
+  for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
+    invalidate_all.Insert(Invalidation::InitUnknownVersion(*it));
   }
-  return ids;
+  return invalidate_all;
+}
+
+ObjectIdInvalidationMap::ObjectIdInvalidationMap() {}
+
+ObjectIdInvalidationMap::~ObjectIdInvalidationMap() {}
+
+ObjectIdSet ObjectIdInvalidationMap::GetObjectIds() const {
+  ObjectIdSet ret;
+  for (IdToListMap::const_iterator it = map_.begin(); it != map_.end(); ++it) {
+    ret.insert(it->first);
+  }
+  return ret;
+}
+
+bool ObjectIdInvalidationMap::Empty() const {
+  return map_.empty();
+}
+
+void ObjectIdInvalidationMap::Insert(const Invalidation& invalidation) {
+  map_[invalidation.object_id()].Insert(invalidation);
 }
 
-ObjectIdInvalidationMap ObjectIdSetToInvalidationMap(
-    const ObjectIdSet& ids, int64 version, const std::string& payload) {
-  ObjectIdInvalidationMap invalidation_map;
+ObjectIdInvalidationMap ObjectIdInvalidationMap::GetSubsetWithObjectIds(
+    const ObjectIdSet& ids) const {
+  IdToListMap new_map;
   for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
-    // TODO(dcheng): Do we need to provide a way to set AckHandle?
-    invalidation_map[*it].version = version;
-    invalidation_map[*it].payload = payload;
+    IdToListMap::const_iterator lookup = map_.find(*it);
+    if (lookup != map_.end()) {
+      new_map[*it] = lookup->second;
+    }
   }
-  return invalidation_map;
+  return ObjectIdInvalidationMap(new_map);
 }
 
-namespace {
+const SingleObjectInvalidationSet& ObjectIdInvalidationMap::ForObject(
+    invalidation::ObjectId id) const {
+  IdToListMap::const_iterator lookup = map_.find(id);
+  DCHECK(lookup != map_.end());
+  DCHECK(!lookup->second.IsEmpty());
+  return lookup->second;
+}
 
-struct ObjectIdInvalidationMapValueEquals {
-  bool operator()(const ObjectIdInvalidationMap::value_type& value1,
-                  const ObjectIdInvalidationMap::value_type& value2) const {
-    return
-        (value1.first == value2.first) &&
-        value1.second.Equals(value2.second);
+void ObjectIdInvalidationMap::GetAllInvalidations(
+    std::vector<syncer::Invalidation>* out) const {
+  for (IdToListMap::const_iterator it = map_.begin(); it != map_.end(); ++it) {
+    out->insert(out->begin(), it->second.begin(), it->second.end());
   }
-};
-
-}  // namespace
-
-bool ObjectIdInvalidationMapEquals(
-    const ObjectIdInvalidationMap& invalidation_map1,
-    const ObjectIdInvalidationMap& invalidation_map2) {
-  return
-      (invalidation_map1.size() == invalidation_map2.size()) &&
-      std::equal(invalidation_map1.begin(), invalidation_map1.end(),
-                 invalidation_map2.begin(),
-                 ObjectIdInvalidationMapValueEquals());
 }
 
-scoped_ptr<base::ListValue> ObjectIdInvalidationMapToValue(
-    const ObjectIdInvalidationMap& invalidation_map) {
+bool ObjectIdInvalidationMap::operator==(
+    const ObjectIdInvalidationMap& other) const {
+  return map_ == other.map_;
+}
+
+scoped_ptr<base::ListValue> ObjectIdInvalidationMap::ToValue() const {
   scoped_ptr<base::ListValue> value(new base::ListValue());
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
-    base::DictionaryValue* entry = new base::DictionaryValue();
-    entry->Set("objectId", ObjectIdToValue(it->first).release());
-    entry->Set("state", it->second.ToValue().release());
-    value->Append(entry);
+  for (IdToListMap::const_iterator it1 = map_.begin();
+       it1 != map_.end(); ++it1) {
+    for (SingleObjectInvalidationSet::const_iterator it2 =
+         it1->second.begin(); it2 != it1->second.end(); ++it2) {
+      value->Append(it2->ToValue().release());
+    }
   }
   return value.Pass();
 }
 
-bool ObjectIdInvalidationMapFromValue(const base::ListValue& value,
-                               ObjectIdInvalidationMap* out) {
-  out->clear();
-  for (base::ListValue::const_iterator it = value.begin();
-       it != value.end(); ++it) {
-    const base::DictionaryValue* entry = NULL;
-    const base::DictionaryValue* id_value = NULL;
-    const base::DictionaryValue* invalidation_value = NULL;
-    invalidation::ObjectId id;
-    Invalidation invalidation;
-    if (!(*it)->GetAsDictionary(&entry) ||
-        !entry->GetDictionary("objectId", &id_value) ||
-        !entry->GetDictionary("state", &invalidation_value) ||
-        !ObjectIdFromValue(*id_value, &id) ||
-        !invalidation.ResetFromValue(*invalidation_value)) {
+bool ObjectIdInvalidationMap::ResetFromValue(const base::ListValue& value) {
+  map_.clear();
+  for (size_t i = 0; i < value.GetSize(); ++i) {
+    const DictionaryValue* dict;
+    if (!value.GetDictionary(i, &dict)) {
       return false;
     }
-    ignore_result(out->insert(std::make_pair(id, invalidation)));
+    scoped_ptr<Invalidation> invalidation = Invalidation::InitFromValue(*dict);
+    if (!invalidation) {
+      return false;
+    }
+    Insert(*invalidation.get());
   }
   return true;
 }
 
+std::string ObjectIdInvalidationMap::ToString() const {
+  std::string output;
+  JSONStringValueSerializer serializer(&output);
+  serializer.set_pretty_print(true);
+  serializer.Serialize(*ToValue().get());
+  return output;
+}
+
+ObjectIdInvalidationMap::ObjectIdInvalidationMap(const IdToListMap& map)
+  : map_(map) {}
+
 }  // namespace syncer
diff --git a/sync/notifier/object_id_invalidation_map.h b/sync/notifier/object_id_invalidation_map.h
index bb97fb3..c17e101 100644
--- a/sync/notifier/object_id_invalidation_map.h
+++ b/sync/notifier/object_id_invalidation_map.h
@@ -1,4 +1,4 @@
-// Copyright 2012 The Chromium Authors. All rights reserved.
+// Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -6,40 +6,67 @@
 #define SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_H_
 
 #include <map>
-#include <string>
+#include <vector>
 
-#include "base/basictypes.h"
-#include "base/memory/scoped_ptr.h"
-#include "google/cacheinvalidation/include/types.h"
 #include "sync/base/sync_export.h"
 #include "sync/internal_api/public/base/invalidation.h"
 #include "sync/notifier/invalidation_util.h"
-
-namespace base {
-class ListValue;
-}  // namespace base
+#include "sync/notifier/single_object_invalidation_set.h"
 
 namespace syncer {
 
-typedef std::map<invalidation::ObjectId,
-                 Invalidation,
-                 ObjectIdLessThan> ObjectIdInvalidationMap;
+// A set of notifications with some helper methods to organize them by object ID
+// and version number.
+class SYNC_EXPORT ObjectIdInvalidationMap {
+  public:
+   // Creates an invalidation map that includes an 'unknown version'
+   // invalidation for each specified ID in |ids|.
+   static ObjectIdInvalidationMap InvalidateAll(const ObjectIdSet& ids);
+
+   ObjectIdInvalidationMap();
+   ~ObjectIdInvalidationMap();
+
+   // Returns set of ObjectIds for which at least one invalidation is present.
+   ObjectIdSet GetObjectIds() const;
+
+   // Returns true if this map contains no invalidations.
+   bool Empty() const;
+
+   // Returns true if both maps contain the same set of invalidations.
+   bool operator==(const ObjectIdInvalidationMap& other) const;
+
+   // Inserts a new invalidation into this map.
+   void Insert(const Invalidation& invalidation);
+
+   // Returns a new map containing the subset of invaliations from this map
+   // whose IDs were in the specified |ids| set.
+   ObjectIdInvalidationMap GetSubsetWithObjectIds(const ObjectIdSet& ids) const;
+
+   // Returns the subset of invalidations with IDs matching |id|.
+   const SingleObjectInvalidationSet& ForObject(
+       invalidation::ObjectId id) const;
+
+   // Returns the contents of this map in a single vector.
+   void GetAllInvalidations(std::vector<syncer::Invalidation>* out) const;
+
+   // Serialize this map to a value.
+   scoped_ptr<base::ListValue> ToValue() const;
+
+   // Deserialize the value into a map and use it to re-initialize this object.
+   bool ResetFromValue(const base::ListValue& value);
 
-// Converts between ObjectIdInvalidationMaps and ObjectIdSets.
-ObjectIdSet ObjectIdInvalidationMapToSet(
-    const ObjectIdInvalidationMap& invalidation_map);
-SYNC_EXPORT ObjectIdInvalidationMap ObjectIdSetToInvalidationMap(
-    const ObjectIdSet& ids, int64 version, const std::string& payload);
+   // Prints the contentes of this map as a human-readable string.
+   std::string ToString() const;
 
-SYNC_EXPORT bool ObjectIdInvalidationMapEquals(
-    const ObjectIdInvalidationMap& invalidation_map1,
-    const ObjectIdInvalidationMap& invalidation_map2);
+  private:
+   typedef std::map<invalidation::ObjectId,
+                    SingleObjectInvalidationSet,
+                    ObjectIdLessThan> IdToListMap;
 
-scoped_ptr<base::ListValue> ObjectIdInvalidationMapToValue(
-    const ObjectIdInvalidationMap& invalidation_map);
+   ObjectIdInvalidationMap(const IdToListMap& map);
 
-bool ObjectIdInvalidationMapFromValue(const base::ListValue& value,
-                               ObjectIdInvalidationMap* out);
+   IdToListMap map_;
+};
 
 }  // namespace syncer
 
diff --git a/sync/notifier/object_id_invalidation_map_unittest.cc b/sync/notifier/object_id_invalidation_map_unittest.cc
new file mode 100644
index 0000000..1acd920
--- /dev/null
+++ b/sync/notifier/object_id_invalidation_map_unittest.cc
@@ -0,0 +1,104 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "sync/notifier/object_id_invalidation_map.h"
+
+#include "google/cacheinvalidation/types.pb.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace syncer {
+
+namespace {
+
+class ObjectIdInvalidationMapTest : public testing::Test {
+ public:
+  ObjectIdInvalidationMapTest()
+      : kIdOne(ipc::invalidation::ObjectSource::TEST, "one"),
+        kIdTwo(ipc::invalidation::ObjectSource::TEST, "two"),
+        kInv1(Invalidation::Init(kIdOne, 10, "ten")) {
+    set1.insert(kIdOne);
+    set2.insert(kIdTwo);
+    all_set.insert(kIdOne);
+    all_set.insert(kIdTwo);
+
+    one_invalidation.Insert(kInv1);
+    invalidate_all = ObjectIdInvalidationMap::InvalidateAll(all_set);
+  }
+
+ protected:
+  const invalidation::ObjectId kIdOne;
+  const invalidation::ObjectId kIdTwo;
+  const Invalidation kInv1;
+
+  ObjectIdSet set1;
+  ObjectIdSet set2;
+  ObjectIdSet all_set;
+  ObjectIdInvalidationMap empty;
+  ObjectIdInvalidationMap one_invalidation;
+  ObjectIdInvalidationMap invalidate_all;
+};
+
+TEST_F(ObjectIdInvalidationMapTest, Empty) {
+  EXPECT_TRUE(empty.Empty());
+  EXPECT_FALSE(one_invalidation.Empty());
+  EXPECT_FALSE(invalidate_all.Empty());
+}
+
+TEST_F(ObjectIdInvalidationMapTest, Equality) {
+  ObjectIdInvalidationMap empty2;
+  EXPECT_TRUE(empty == empty2);
+
+  ObjectIdInvalidationMap one_invalidation2;
+  one_invalidation2.Insert(kInv1);
+  EXPECT_TRUE(one_invalidation == one_invalidation2);
+
+  EXPECT_FALSE(empty == invalidate_all);
+}
+
+TEST_F(ObjectIdInvalidationMapTest, GetObjectIds) {
+  EXPECT_EQ(ObjectIdSet(), empty.GetObjectIds());
+  EXPECT_EQ(set1, one_invalidation.GetObjectIds());
+  EXPECT_EQ(all_set, invalidate_all.GetObjectIds());
+}
+
+TEST_F(ObjectIdInvalidationMapTest, GetSubsetWithObjectIds) {
+  EXPECT_TRUE(empty.GetSubsetWithObjectIds(set1).Empty());
+
+  EXPECT_TRUE(one_invalidation.GetSubsetWithObjectIds(set1) ==
+              one_invalidation);
+  EXPECT_TRUE(one_invalidation.GetSubsetWithObjectIds(all_set) ==
+              one_invalidation);
+  EXPECT_TRUE(one_invalidation.GetSubsetWithObjectIds(set2).Empty());
+
+  EXPECT_TRUE(invalidate_all.GetSubsetWithObjectIds(ObjectIdSet()).Empty());
+}
+
+TEST_F(ObjectIdInvalidationMapTest, SerializeEmpty) {
+  scoped_ptr<base::ListValue> value = empty.ToValue();
+  ASSERT_TRUE(value.get());
+  ObjectIdInvalidationMap deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(empty == deserialized);
+}
+
+TEST_F(ObjectIdInvalidationMapTest, SerializeOneInvalidation) {
+  scoped_ptr<base::ListValue> value = one_invalidation.ToValue();
+  ASSERT_TRUE(value.get());
+  ObjectIdInvalidationMap deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(one_invalidation == deserialized);
+}
+
+TEST_F(ObjectIdInvalidationMapTest, SerializeInvalidateAll) {
+  scoped_ptr<base::ListValue> value = invalidate_all.ToValue();
+  ASSERT_TRUE(value.get());
+  ObjectIdInvalidationMap deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(invalidate_all == deserialized);
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/notifier/p2p_invalidator.cc b/sync/notifier/p2p_invalidator.cc
index 2468a51..3d47f41 100644
--- a/sync/notifier/p2p_invalidator.cc
+++ b/sync/notifier/p2p_invalidator.cc
@@ -14,6 +14,7 @@
 #include "jingle/notifier/listener/push_client.h"
 #include "sync/notifier/invalidation_handler.h"
 #include "sync/notifier/invalidation_util.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace syncer {
 
@@ -27,7 +28,7 @@ const char kNotifyAll[] = "notifyAll";
 
 const char kSenderIdKey[] = "senderId";
 const char kNotificationTypeKey[] = "notificationType";
-const char kIdInvalidationMapKey[] = "idInvalidationMap";
+const char kInvalidationsKey[] = "invalidations";
 
 }  // namespace
 
@@ -96,8 +97,7 @@ bool P2PNotificationData::Equals(const P2PNotificationData& other) const {
   return
       (sender_id_ == other.sender_id_) &&
       (target_ == other.target_) &&
-      ObjectIdInvalidationMapEquals(invalidation_map_,
-                                    other.invalidation_map_);
+      (invalidation_map_ == other.invalidation_map_);
 }
 
 std::string P2PNotificationData::ToString() const {
@@ -105,8 +105,7 @@ std::string P2PNotificationData::ToString() const {
   dict->SetString(kSenderIdKey, sender_id_);
   dict->SetString(kNotificationTypeKey,
                   P2PNotificationTargetToString(target_));
-  dict->Set(kIdInvalidationMapKey,
-            ObjectIdInvalidationMapToValue(invalidation_map_).release());
+  dict->Set(kInvalidationsKey, invalidation_map_.ToValue().release());
   std::string json;
   base::JSONWriter::Write(dict.get(), &json);
   return json;
@@ -129,10 +128,9 @@ bool P2PNotificationData::ResetFromString(const std::string& str) {
   }
   target_ = P2PNotificationTargetFromString(target_str);
   const base::ListValue* invalidation_map_list = NULL;
-  if (!data_dict->GetList(kIdInvalidationMapKey, &invalidation_map_list) ||
-      !ObjectIdInvalidationMapFromValue(*invalidation_map_list,
-                                        &invalidation_map_)) {
-    LOG(WARNING) << "Could not parse " << kIdInvalidationMapKey;
+  if (!data_dict->GetList(kInvalidationsKey, &invalidation_map_list) ||
+      !invalidation_map_.ResetFromValue(*invalidation_map_list)) {
+    LOG(WARNING) << "Could not parse " << kInvalidationsKey;
   }
   return true;
 }
@@ -161,8 +159,7 @@ void P2PInvalidator::RegisterHandler(InvalidationHandler* handler) {
 }
 
 void P2PInvalidator::UpdateRegisteredIds(InvalidationHandler* handler,
-                                      const ObjectIdSet& ids) {
-  // TODO(akalin): Handle arbitrary object IDs (http://crbug.com/140411).
+                                         const ObjectIdSet& ids) {
   DCHECK(thread_checker_.CalledOnValidThread());
   ObjectIdSet new_ids;
   const ObjectIdSet& old_ids = registrar_.GetRegisteredIds(handler);
@@ -173,10 +170,8 @@ void P2PInvalidator::UpdateRegisteredIds(InvalidationHandler* handler,
   registrar_.UpdateRegisteredIds(handler, ids);
   const P2PNotificationData notification_data(
       invalidator_client_id_,
-      NOTIFY_SELF,
-      ObjectIdSetToInvalidationMap(new_ids,
-                                   Invalidation::kUnknownVersion,
-                                   std::string()));
+      send_notification_target_,
+      ObjectIdInvalidationMap::InvalidateAll(ids));
   SendNotificationData(notification_data);
 }
 
@@ -213,9 +208,10 @@ void P2PInvalidator::UpdateCredentials(
   logged_in_ = true;
 }
 
-void P2PInvalidator::SendInvalidation(
-    const ObjectIdInvalidationMap& invalidation_map) {
+void P2PInvalidator::SendInvalidation(const ObjectIdSet& ids) {
   DCHECK(thread_checker_.CalledOnValidThread());
+  ObjectIdInvalidationMap invalidation_map =
+      ObjectIdInvalidationMap::InvalidateAll(ids);
   const P2PNotificationData notification_data(
       invalidator_client_id_, send_notification_target_, invalidation_map);
   SendNotificationData(notification_data);
@@ -230,9 +226,8 @@ void P2PInvalidator::OnNotificationsEnabled() {
     const P2PNotificationData notification_data(
         invalidator_client_id_,
         NOTIFY_SELF,
-        ObjectIdSetToInvalidationMap(registrar_.GetAllRegisteredIds(),
-                                     Invalidation::kUnknownVersion,
-                                     std::string()));
+        ObjectIdInvalidationMap::InvalidateAll(
+            registrar_.GetAllRegisteredIds()));
     SendNotificationData(notification_data);
   }
 }
@@ -266,9 +261,8 @@ void P2PInvalidator::OnIncomingNotification(
     notification_data = P2PNotificationData(
         invalidator_client_id_,
         NOTIFY_ALL,
-        ObjectIdSetToInvalidationMap(registrar_.GetAllRegisteredIds(),
-                                     Invalidation::kUnknownVersion,
-                                     std::string()));
+        ObjectIdInvalidationMap::InvalidateAll(
+            registrar_.GetAllRegisteredIds()));
   }
   if (!notification_data.IsTargeted(invalidator_client_id_)) {
     DVLOG(1) << "Not a target of the notification -- "
@@ -288,7 +282,7 @@ void P2PInvalidator::SendNotificationDataForTest(
 void P2PInvalidator::SendNotificationData(
     const P2PNotificationData& notification_data) {
   DCHECK(thread_checker_.CalledOnValidThread());
-  if (notification_data.GetIdInvalidationMap().empty()) {
+  if (notification_data.GetIdInvalidationMap().Empty()) {
     DVLOG(1) << "Not sending XMPP notification with empty state map: "
              << notification_data.ToString();
     return;
diff --git a/sync/notifier/p2p_invalidator.h b/sync/notifier/p2p_invalidator.h
index 515b27b..bf622f0 100644
--- a/sync/notifier/p2p_invalidator.h
+++ b/sync/notifier/p2p_invalidator.h
@@ -24,6 +24,7 @@
 #include "sync/notifier/invalidator.h"
 #include "sync/notifier/invalidator_registrar.h"
 #include "sync/notifier/invalidator_state.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace notifier {
 class PushClient;
@@ -118,8 +119,7 @@ class SYNC_EXPORT_PRIVATE P2PInvalidator
   virtual void OnIncomingNotification(
       const notifier::Notification& notification) OVERRIDE;
 
-  void SendInvalidation(
-      const ObjectIdInvalidationMap& invalidation_map);
+  void SendInvalidation(const ObjectIdSet& ids);
 
   void SendNotificationDataForTest(
       const P2PNotificationData& notification_data);
diff --git a/sync/notifier/p2p_invalidator_unittest.cc b/sync/notifier/p2p_invalidator_unittest.cc
index 24cfe02..3cbabaf 100644
--- a/sync/notifier/p2p_invalidator_unittest.cc
+++ b/sync/notifier/p2p_invalidator_unittest.cc
@@ -10,7 +10,6 @@
 #include "sync/internal_api/public/base/model_type.h"
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
@@ -98,9 +97,7 @@ class P2PInvalidatorTest : public testing::Test {
   ObjectIdInvalidationMap MakeInvalidationMap(ModelTypeSet types) {
     ObjectIdInvalidationMap invalidations;
     ObjectIdSet ids = ModelTypeSetToObjectIdSet(types);
-    return ObjectIdSetToInvalidationMap(ids,
-                                        Invalidation::kUnknownVersion,
-                                        std::string());
+    return ObjectIdInvalidationMap::InvalidateAll(ids);
   }
 
   // Simulate receiving all the notifications we sent out since last
@@ -166,10 +163,10 @@ TEST_F(P2PInvalidatorTest, P2PNotificationDataDefault) {
   EXPECT_TRUE(notification_data.IsTargeted(std::string()));
   EXPECT_FALSE(notification_data.IsTargeted("other1"));
   EXPECT_FALSE(notification_data.IsTargeted("other2"));
-  EXPECT_TRUE(notification_data.GetIdInvalidationMap().empty());
+  EXPECT_TRUE(notification_data.GetIdInvalidationMap().Empty());
   const std::string& notification_data_str = notification_data.ToString();
   EXPECT_EQ(
-      "{\"idInvalidationMap\":[],\"notificationType\":\"notifySelf\","
+      "{\"invalidations\":[],\"notificationType\":\"notifySelf\","
       "\"senderId\":\"\"}", notification_data_str);
 
   P2PNotificationData notification_data_parsed;
@@ -180,27 +177,22 @@ TEST_F(P2PInvalidatorTest, P2PNotificationDataDefault) {
 // Make sure the P2PNotificationData <-> string conversions work for a
 // non-default-constructed P2PNotificationData.
 TEST_F(P2PInvalidatorTest, P2PNotificationDataNonDefault) {
-  const ObjectIdInvalidationMap& invalidation_map =
-      ObjectIdSetToInvalidationMap(
-          ModelTypeSetToObjectIdSet(ModelTypeSet(BOOKMARKS, THEMES)),
-          Invalidation::kUnknownVersion,
-          std::string());
-  const P2PNotificationData notification_data(
-      "sender", NOTIFY_ALL, invalidation_map);
+  ObjectIdInvalidationMap invalidation_map =
+      MakeInvalidationMap(ModelTypeSet(BOOKMARKS, THEMES));
+  const P2PNotificationData notification_data("sender",
+                                              NOTIFY_ALL,
+                                              invalidation_map);
   EXPECT_TRUE(notification_data.IsTargeted("sender"));
   EXPECT_TRUE(notification_data.IsTargeted("other1"));
   EXPECT_TRUE(notification_data.IsTargeted("other2"));
-  EXPECT_THAT(invalidation_map,
-              Eq(notification_data.GetIdInvalidationMap()));
+  EXPECT_EQ(invalidation_map, notification_data.GetIdInvalidationMap());
   const std::string& notification_data_str = notification_data.ToString();
   EXPECT_EQ(
-      "{\"idInvalidationMap\":["
-      "{\"objectId\":{\"name\":\"BOOKMARK\",\"source\":1004},"
-      "\"state\":{\"ackHandle\":{\"state\":\"\",\"timestamp\":\"0\"},"
-      "\"payload\":\"\",\"version\":\"-1\"}},"
-      "{\"objectId\":{\"name\":\"THEME\",\"source\":1004},"
-      "\"state\":{\"ackHandle\":{\"state\":\"\",\"timestamp\":\"0\"},"
-      "\"payload\":\"\",\"version\":\"-1\"}}"
+      "{\"invalidations\":["
+      "{\"isUnknownVersion\":true,"
+       "\"objectId\":{\"name\":\"BOOKMARK\",\"source\":1004}},"
+      "{\"isUnknownVersion\":true,"
+       "\"objectId\":{\"name\":\"THEME\",\"source\":1004}}"
       "],\"notificationType\":\"notifyAll\","
       "\"senderId\":\"sender\"}", notification_data_str);
 
@@ -248,14 +240,8 @@ TEST_F(P2PInvalidatorTest, NotificationsBasic) {
 
   // Sent with target NOTIFY_OTHERS so should not be propagated to
   // |fake_handler_|.
-  {
-    const ObjectIdInvalidationMap& invalidation_map =
-        ObjectIdSetToInvalidationMap(
-            ModelTypeSetToObjectIdSet(ModelTypeSet(THEMES, APPS)),
-            Invalidation::kUnknownVersion,
-            std::string());
-    invalidator->SendInvalidation(invalidation_map);
-  }
+  invalidator->SendInvalidation(
+      ModelTypeSetToObjectIdSet(ModelTypeSet(THEMES, APPS)));
 
   ReflectSentNotifications();
   EXPECT_EQ(1, fake_handler_.GetInvalidationCount());
@@ -270,9 +256,7 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
   const ModelTypeSet expected_types(THEMES);
 
   const ObjectIdInvalidationMap& invalidation_map =
-      ObjectIdSetToInvalidationMap(ModelTypeSetToObjectIdSet(changed_types),
-                                   Invalidation::kUnknownVersion,
-                                   std::string());
+      MakeInvalidationMap(changed_types);
 
   P2PInvalidator* const invalidator = delegate_.GetInvalidator();
   notifier::FakePushClient* const push_client = delegate_.GetPushClient();
@@ -288,23 +272,23 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
 
   ReflectSentNotifications();
   EXPECT_EQ(1, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(MakeInvalidationMap(enabled_types),
-              Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(ModelTypeSetToObjectIdSet(enabled_types),
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(P2PNotificationData());
   ReflectSentNotifications();
   EXPECT_EQ(1, fake_handler_.GetInvalidationCount());
 
-  const ObjectIdInvalidationMap& expected_ids =
-      MakeInvalidationMap(expected_types);
+  const ObjectIdSet& expected_ids = ModelTypeSetToObjectIdSet(expected_types);
 
   // Should be propagated.
   invalidator->SendNotificationDataForTest(
       P2PNotificationData("sender", NOTIFY_SELF, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(2, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(
@@ -329,7 +313,8 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
       P2PNotificationData("sender2", NOTIFY_OTHERS, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(3, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(
@@ -342,14 +327,16 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
       P2PNotificationData("sender", NOTIFY_ALL, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(4, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be propagated.
   invalidator->SendNotificationDataForTest(
       P2PNotificationData("sender2", NOTIFY_ALL, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(5, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(
diff --git a/sync/notifier/single_object_invalidation_set.cc b/sync/notifier/single_object_invalidation_set.cc
new file mode 100644
index 0000000..55202bb
--- /dev/null
+++ b/sync/notifier/single_object_invalidation_set.cc
@@ -0,0 +1,130 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "sync/notifier/single_object_invalidation_set.h"
+
+#include "base/values.h"
+#include "sync/notifier/invalidation_util.h"
+
+namespace syncer {
+
+bool InvalidationVersionLessThan::operator()(
+    const Invalidation& a,
+    const Invalidation& b) {
+  DCHECK(a.object_id() == b.object_id())
+      << "a: " << ObjectIdToString(a.object_id()) << ", "
+      << "b: " << ObjectIdToString(a.object_id());
+
+  if (a.is_unknown_version() && !b.is_unknown_version())
+    return true;
+
+  if (!a.is_unknown_version() && b.is_unknown_version())
+    return false;
+
+  if (a.is_unknown_version() && b.is_unknown_version())
+    return false;
+
+  return a.version() < b.version();
+}
+
+SingleObjectInvalidationSet::SingleObjectInvalidationSet() {}
+
+SingleObjectInvalidationSet::~SingleObjectInvalidationSet() {}
+
+void SingleObjectInvalidationSet::Insert(const Invalidation& invalidation) {
+  invalidations_.insert(invalidation);
+}
+
+void SingleObjectInvalidationSet::InsertAll(
+    const SingleObjectInvalidationSet& other) {
+  invalidations_.insert(other.begin(), other.end());
+}
+
+void SingleObjectInvalidationSet::Clear() {
+  invalidations_.clear();
+}
+
+bool SingleObjectInvalidationSet::StartsWithUnknownVersion() const {
+  return !invalidations_.empty() &&
+      invalidations_.begin()->is_unknown_version();
+}
+
+size_t SingleObjectInvalidationSet::GetSize() const {
+  return invalidations_.size();
+}
+
+bool SingleObjectInvalidationSet::IsEmpty() const {
+  return invalidations_.empty();
+}
+
+namespace {
+
+struct InvalidationComparator {
+  bool operator()(const Invalidation& inv1, const Invalidation& inv2) {
+    return inv1.Equals(inv2);
+  }
+};
+
+}  // namespace
+
+bool SingleObjectInvalidationSet::operator==(
+    const SingleObjectInvalidationSet& other) const {
+  return std::equal(invalidations_.begin(),
+                    invalidations_.end(),
+                    other.invalidations_.begin(),
+                    InvalidationComparator());
+}
+
+SingleObjectInvalidationSet::const_iterator
+SingleObjectInvalidationSet::begin() const {
+  return invalidations_.begin();
+}
+
+SingleObjectInvalidationSet::const_iterator
+SingleObjectInvalidationSet::end() const {
+  return invalidations_.end();
+}
+
+SingleObjectInvalidationSet::const_reverse_iterator
+SingleObjectInvalidationSet::rbegin() const {
+  return invalidations_.rbegin();
+}
+
+SingleObjectInvalidationSet::const_reverse_iterator
+SingleObjectInvalidationSet::rend() const {
+  return invalidations_.rend();
+}
+
+const Invalidation& SingleObjectInvalidationSet::back() const {
+  return *invalidations_.rbegin();
+}
+
+scoped_ptr<base::ListValue> SingleObjectInvalidationSet::ToValue() const {
+  scoped_ptr<base::ListValue> value(new ListValue);
+  for (InvalidationsSet::const_iterator it = invalidations_.begin();
+       it != invalidations_.end(); ++it) {
+    value->Append(it->ToValue().release());
+  }
+  return value.Pass();
+}
+
+bool SingleObjectInvalidationSet::ResetFromValue(
+    const base::ListValue& list) {
+  for (size_t i = 0; i < list.GetSize(); ++i) {
+    const base::DictionaryValue* dict;
+    if (!list.GetDictionary(i, &dict)) {
+      DLOG(WARNING) << "Could not find invalidation at index " << i;
+      return false;
+    }
+    scoped_ptr<Invalidation> invalidation = Invalidation::InitFromValue(*dict);
+    if (!invalidation) {
+      DLOG(WARNING) << "Failed to parse invalidation at index " << i;
+      return false;
+    }
+    invalidations_.insert(*invalidation);
+  }
+  return true;
+}
+
+}  // namespace syncer
diff --git a/sync/notifier/single_object_invalidation_set.h b/sync/notifier/single_object_invalidation_set.h
new file mode 100644
index 0000000..c4dd051
--- /dev/null
+++ b/sync/notifier/single_object_invalidation_set.h
@@ -0,0 +1,66 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef SYNC_NOTIFIER_SINGLE_OBJECT_INVALIDATION_SET_H_
+#define SYNC_NOTIFIER_SINGLE_OBJECT_INVALIDATION_SET_H_
+
+#include <set>
+
+#include "base/memory/scoped_ptr.h"
+#include "sync/base/sync_export.h"
+#include "sync/internal_api/public/base/invalidation.h"
+
+namespace base {
+class ListValue;
+}  // namespace base
+
+namespace syncer {
+
+struct InvalidationVersionLessThan {
+  bool operator()(const Invalidation& a, const Invalidation& b);
+};
+
+// Holds a list of invalidations that all share the same Object ID.
+//
+// The list is kept sorted by version to make it easier to perform common
+// operations, like checking for an unknown version invalidation or fetching the
+// highest invalidation with the highest version number.
+class SYNC_EXPORT SingleObjectInvalidationSet {
+ public:
+  typedef std::set<Invalidation, InvalidationVersionLessThan> InvalidationsSet;
+  typedef InvalidationsSet::const_iterator const_iterator;
+  typedef InvalidationsSet::const_reverse_iterator const_reverse_iterator;
+
+  SingleObjectInvalidationSet();
+  ~SingleObjectInvalidationSet();
+
+  void Insert(const Invalidation& invalidation);
+  void InsertAll(const SingleObjectInvalidationSet& other);
+  void Clear();
+
+  // Returns true if this list contains an unknown version.
+  //
+  // Unknown version invalidations always end up at the start of the list,
+  // because they have the lowest possible value in the sort ordering.
+  bool StartsWithUnknownVersion() const;
+  size_t GetSize() const;
+  bool IsEmpty() const;
+  bool operator==(const SingleObjectInvalidationSet& other) const;
+
+  const_iterator begin() const;
+  const_iterator end() const;
+  const_reverse_iterator rbegin() const;
+  const_reverse_iterator rend() const;
+  const Invalidation& back() const;
+
+  scoped_ptr<base::ListValue> ToValue() const;
+  bool ResetFromValue(const base::ListValue& list);
+
+ private:
+  InvalidationsSet invalidations_;
+};
+
+}  // syncer
+
+#endif  // SYNC_NOTIFIER_SINGLE_OBJECT_INVALIDATION_SET_H_
diff --git a/sync/notifier/single_object_invalidation_set_unittest.cc b/sync/notifier/single_object_invalidation_set_unittest.cc
new file mode 100644
index 0000000..3fe074e
--- /dev/null
+++ b/sync/notifier/single_object_invalidation_set_unittest.cc
@@ -0,0 +1,110 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "sync/notifier/single_object_invalidation_set.h"
+
+#include "google/cacheinvalidation/types.pb.h"
+#include "sync/internal_api/public/base/invalidation_test_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace syncer {
+
+namespace {
+
+class SingleObjectInvalidationSetTest : public testing::Test {
+ public:
+  SingleObjectInvalidationSetTest()
+      : kId(ipc::invalidation::ObjectSource::TEST, "one") {
+  }
+ protected:
+  const invalidation::ObjectId kId;
+};
+
+TEST_F(SingleObjectInvalidationSetTest, InsertionAndOrdering) {
+  SingleObjectInvalidationSet l1;
+  SingleObjectInvalidationSet l2;
+
+  Invalidation inv0 = Invalidation::InitUnknownVersion(kId);
+  Invalidation inv1 = Invalidation::Init(kId, 1, "one");
+  Invalidation inv2 = Invalidation::Init(kId, 5, "five");
+
+  l1.Insert(inv0);
+  l1.Insert(inv1);
+  l1.Insert(inv2);
+
+  l2.Insert(inv1);
+  l2.Insert(inv2);
+  l2.Insert(inv0);
+
+  ASSERT_EQ(3U, l1.GetSize());
+  ASSERT_EQ(3U, l2.GetSize());
+
+  SingleObjectInvalidationSet::const_iterator it1 = l1.begin();
+  SingleObjectInvalidationSet::const_iterator it2 = l2.begin();
+  EXPECT_THAT(inv0, Eq(*it1));
+  EXPECT_THAT(inv0, Eq(*it2));
+  it1++;
+  it2++;
+  EXPECT_THAT(inv1, Eq(*it1));
+  EXPECT_THAT(inv1, Eq(*it2));
+  it1++;
+  it2++;
+  EXPECT_THAT(inv2, Eq(*it1));
+  EXPECT_THAT(inv2, Eq(*it2));
+  it1++;
+  it2++;
+  EXPECT_TRUE(it1 == l1.end());
+  EXPECT_TRUE(it2 == l2.end());
+}
+
+TEST_F(SingleObjectInvalidationSetTest, StartWithUnknownVersion) {
+  SingleObjectInvalidationSet list;
+  EXPECT_FALSE(list.StartsWithUnknownVersion());
+
+  list.Insert(Invalidation::Init(kId, 1, "one"));
+  EXPECT_FALSE(list.StartsWithUnknownVersion());
+
+  list.Insert(Invalidation::InitUnknownVersion(kId));
+  EXPECT_TRUE(list.StartsWithUnknownVersion());
+
+  list.Clear();
+  EXPECT_FALSE(list.StartsWithUnknownVersion());
+}
+
+TEST_F(SingleObjectInvalidationSetTest, SerializeEmpty) {
+  SingleObjectInvalidationSet list;
+
+  scoped_ptr<base::ListValue> value = list.ToValue();
+  ASSERT_TRUE(value.get());
+  SingleObjectInvalidationSet deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(list == deserialized);
+}
+
+TEST_F(SingleObjectInvalidationSetTest, SerializeOne) {
+  SingleObjectInvalidationSet list;
+  list.Insert(Invalidation::Init(kId, 1, "one"));
+
+  scoped_ptr<base::ListValue> value = list.ToValue();
+  ASSERT_TRUE(value.get());
+  SingleObjectInvalidationSet deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(list == deserialized);
+}
+
+TEST_F(SingleObjectInvalidationSetTest, SerializeMany) {
+  SingleObjectInvalidationSet list;
+  list.Insert(Invalidation::Init(kId, 1, "one"));
+  list.Insert(Invalidation::InitUnknownVersion(kId));
+
+  scoped_ptr<base::ListValue> value = list.ToValue();
+  ASSERT_TRUE(value.get());
+  SingleObjectInvalidationSet deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(list == deserialized);
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/notifier/sync_invalidation_listener.cc b/sync/notifier/sync_invalidation_listener.cc
index ed07f20..71be3ec 100644
--- a/sync/notifier/sync_invalidation_listener.cc
+++ b/sync/notifier/sync_invalidation_listener.cc
@@ -22,6 +22,8 @@ namespace {
 
 const char kApplicationName[] = "chrome-sync";
 
+static const int64 kUnknownVersion = -1;
+
 }  // namespace
 
 namespace syncer {
@@ -220,7 +222,7 @@ void SyncInvalidationListener::InvalidateUnknownVersion(
   ids.insert(object_id);
   PrepareInvalidation(
       ids,
-      Invalidation::kUnknownVersion,
+      kUnknownVersion,
       std::string(),
       client,
       ack_handle);
@@ -237,7 +239,7 @@ void SyncInvalidationListener::InvalidateAll(
 
   PrepareInvalidation(
       registered_ids_,
-      Invalidation::kUnknownVersion,
+      kUnknownVersion,
       std::string(),
       client,
       ack_handle);
@@ -275,13 +277,22 @@ void SyncInvalidationListener::EmitInvalidation(
     const invalidation::AckHandle& ack_handle,
     const AckHandleMap& local_ack_handles) {
   DCHECK(CalledOnValidThread());
-  ObjectIdInvalidationMap invalidation_map =
-      ObjectIdSetToInvalidationMap(ids, version, payload);
+
+  ObjectIdInvalidationMap invalidation_map;
   for (AckHandleMap::const_iterator it = local_ack_handles.begin();
        it != local_ack_handles.end(); ++it) {
     // Update in-memory copy of the invalidation state.
     invalidation_state_map_[it->first].expected = it->second;
-    invalidation_map[it->first].ack_handle = it->second;
+
+    if (version == kUnknownVersion) {
+      Invalidation inv = Invalidation::InitUnknownVersion(it->first);
+      inv.set_ack_handle(it->second);
+      invalidation_map.Insert(inv);
+    } else {
+      Invalidation inv = Invalidation::Init(it->first, version, payload);
+      inv.set_ack_handle(it->second);
+      invalidation_map.Insert(inv);
+    }
   }
   ack_tracker_.Track(ids);
   delegate_->OnInvalidate(invalidation_map);
@@ -291,13 +302,19 @@ void SyncInvalidationListener::EmitInvalidation(
 void SyncInvalidationListener::OnTimeout(const ObjectIdSet& ids) {
   ObjectIdInvalidationMap invalidation_map;
   for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
-    Invalidation invalidation;
-    invalidation.ack_handle = invalidation_state_map_[*it].expected;
-    invalidation.version = invalidation_state_map_[*it].version;
-    invalidation.payload = invalidation_state_map_[*it].payload;
-    invalidation_map.insert(std::make_pair(*it, invalidation));
+    if (invalidation_state_map_[*it].version == kUnknownVersion) {
+      Invalidation inv = Invalidation::InitUnknownVersion(*it);
+      inv.set_ack_handle(invalidation_state_map_[*it].expected);
+      invalidation_map.Insert(inv);
+    } else {
+      Invalidation inv = Invalidation::Init(
+          *it,
+          invalidation_state_map_[*it].version,
+          invalidation_state_map_[*it].payload);
+      inv.set_ack_handle(invalidation_state_map_[*it].expected);
+      invalidation_map.Insert(inv);
+    }
   }
-
   delegate_->OnInvalidate(invalidation_map);
 }
 
diff --git a/sync/notifier/sync_invalidation_listener_unittest.cc b/sync/notifier/sync_invalidation_listener_unittest.cc
index d3aa712..18dd123 100644
--- a/sync/notifier/sync_invalidation_listener_unittest.cc
+++ b/sync/notifier/sync_invalidation_listener_unittest.cc
@@ -141,37 +141,62 @@ class FakeDelegate : public SyncInvalidationListener::Delegate {
         state_(TRANSIENT_INVALIDATION_ERROR) {}
   virtual ~FakeDelegate() {}
 
-  int GetInvalidationCount(const ObjectId& id) const {
-    ObjectIdCountMap::const_iterator it = invalidation_counts_.find(id);
-    return (it == invalidation_counts_.end()) ? 0 : it->second;
+  size_t GetInvalidationCount(const ObjectId& id) const {
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      return 0;
+    } else {
+      return it->second.size();
+    }
   }
 
   int64 GetVersion(const ObjectId& id) const {
-    ObjectIdInvalidationMap::const_iterator it = invalidations_.find(id);
-    return (it == invalidations_.end()) ? 0 : it->second.version;
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      ADD_FAILURE() << "No invalidations for ID " << ObjectIdToString(id);
+      return 0;
+    } else {
+      return it->second.back().version();
+    }
   }
 
   std::string GetPayload(const ObjectId& id) const {
-    ObjectIdInvalidationMap::const_iterator it = invalidations_.find(id);
-    return (it == invalidations_.end()) ? std::string() : it->second.payload;
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      ADD_FAILURE() << "No invalidations for ID " << ObjectIdToString(id);
+      return "";
+    } else {
+      return it->second.back().payload();
+    }
   }
 
+  bool IsUnknownVersion(const ObjectId& id) const {
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      ADD_FAILURE() << "No invalidations for ID " << ObjectIdToString(id);
+      return false;
+    } else {
+      return it->second.back().is_unknown_version();
+    }
+  }
   InvalidatorState GetInvalidatorState() const {
     return state_;
   }
 
   void Acknowledge(const ObjectId& id) {
-    listener_->Acknowledge(id, invalidations_[id].ack_handle);
+    listener_->Acknowledge(id, invalidations_[id].back().ack_handle());
   }
 
   // SyncInvalidationListener::Delegate implementation.
 
   virtual void OnInvalidate(
       const ObjectIdInvalidationMap& invalidation_map) OVERRIDE {
-    for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-         it != invalidation_map.end(); ++it) {
-      ++invalidation_counts_[it->first];
-      invalidations_[it->first] = it->second;
+    ObjectIdSet ids = invalidation_map.GetObjectIds();
+    for (ObjectIdSet::iterator it = ids.begin(); it != ids.end(); ++it) {
+      const SingleObjectInvalidationSet& incoming =
+          invalidation_map.ForObject(*it);
+      List& list = invalidations_[*it];
+      list.insert(list.end(), incoming.begin(), incoming.end());
     }
   }
 
@@ -181,8 +206,9 @@ class FakeDelegate : public SyncInvalidationListener::Delegate {
 
  private:
   typedef std::map<ObjectId, int, ObjectIdLessThan> ObjectIdCountMap;
-  ObjectIdCountMap invalidation_counts_;
-  ObjectIdInvalidationMap invalidations_;
+  typedef std::vector<Invalidation> List;
+  typedef std::map<ObjectId, List, ObjectIdLessThan> Map;
+  Map invalidations_;
   SyncInvalidationListener* listener_;
   InvalidatorState state_;
 };
@@ -308,6 +334,10 @@ class SyncInvalidationListenerTest : public testing::Test {
     return fake_delegate_.GetPayload(id);
   }
 
+  bool IsUnknownVersion(const ObjectId& id) const {
+    return fake_delegate_.IsUnknownVersion(id);
+  }
+
   InvalidatorState GetInvalidatorState() const {
     return fake_delegate_.GetInvalidatorState();
   }
@@ -489,7 +519,6 @@ TEST_F(SyncInvalidationListenerTest, InvalidateUnregisteredWithPayload) {
   const ObjectId& id = kUnregisteredId;
 
   EXPECT_EQ(0, GetInvalidationCount(id));
-  EXPECT_EQ("", GetPayload(id));
   EXPECT_EQ(kMinVersion, GetMaxVersion(id));
 
   FireInvalidate(id, kVersion1, "unregistered payload");
@@ -524,25 +553,18 @@ TEST_F(SyncInvalidationListenerTest, InvalidateVersion) {
   VerifyAcknowledged(id);
 }
 
-// Fire an invalidation with an unknown version twice.  It shouldn't
-// update the payload or version either time, but it should still be
-// processed.
+// Fire an invalidation with an unknown version twice.  It shouldn't update the
+// version either time, but it should still be processed.
 TEST_F(SyncInvalidationListenerTest, InvalidateUnknownVersion) {
   const ObjectId& id = kBookmarksId_;
 
   FireInvalidateUnknownVersion(id);
 
   EXPECT_EQ(1, GetInvalidationCount(id));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(id));
-  EXPECT_EQ("", GetPayload(id));
-  EXPECT_EQ(kMinVersion, GetMaxVersion(id));
+  EXPECT_TRUE(IsUnknownVersion(id));
   AcknowledgeAndVerify(id);
 
   FireInvalidateUnknownVersion(id);
-
-  EXPECT_EQ(2, GetInvalidationCount(id));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(id));
-  EXPECT_EQ("", GetPayload(id));
   EXPECT_EQ(kMinVersion, GetMaxVersion(id));
   AcknowledgeAndVerify(id);
 }
@@ -555,8 +577,7 @@ TEST_F(SyncInvalidationListenerTest, InvalidateAll) {
   for (ObjectIdSet::const_iterator it = registered_ids_.begin();
        it != registered_ids_.end(); ++it) {
     EXPECT_EQ(1, GetInvalidationCount(*it));
-    EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(*it));
-    EXPECT_EQ("", GetPayload(*it));
+    EXPECT_TRUE(IsUnknownVersion(*it));
     EXPECT_EQ(kMinVersion, GetMaxVersion(*it));
     AcknowledgeAndVerify(*it);
   }
@@ -601,14 +622,12 @@ TEST_F(SyncInvalidationListenerTest, InvalidateMultipleIds) {
   FireInvalidateAll();
 
   EXPECT_EQ(2, GetInvalidationCount(kBookmarksId_));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(kBookmarksId_));
-  EXPECT_EQ("", GetPayload(kBookmarksId_));
+  EXPECT_TRUE(IsUnknownVersion(kBookmarksId_));
   EXPECT_EQ(3, GetMaxVersion(kBookmarksId_));
   AcknowledgeAndVerify(kBookmarksId_);
 
   EXPECT_EQ(1, GetInvalidationCount(kPreferencesId_));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(kPreferencesId_));
-  EXPECT_EQ("", GetPayload(kPreferencesId_));
+  EXPECT_TRUE(IsUnknownVersion(kBookmarksId_));
   EXPECT_EQ(kMinVersion, GetMaxVersion(kPreferencesId_));
   AcknowledgeAndVerify(kPreferencesId_);
 
diff --git a/sync/sessions/data_type_tracker.cc b/sync/sessions/data_type_tracker.cc
index a061679..b0b4649 100644
--- a/sync/sessions/data_type_tracker.cc
+++ b/sync/sessions/data_type_tracker.cc
@@ -5,6 +5,8 @@
 #include "sync/sessions/data_type_tracker.h"
 
 #include "base/logging.h"
+#include "sync/internal_api/public/base/invalidation.h"
+#include "sync/notifier/single_object_invalidation_set.h"
 #include "sync/sessions/nudge_tracker.h"
 
 namespace syncer {
@@ -27,13 +29,20 @@ void DataTypeTracker::RecordLocalRefreshRequest() {
   local_refresh_request_count_++;
 }
 
-void DataTypeTracker::RecordRemoteInvalidation(
-    const std::string& payload) {
-  pending_payloads_.push_back(payload);
-  if (pending_payloads_.size() > payload_buffer_size_) {
-    // Drop the oldest payload if we've overflowed.
-    pending_payloads_.pop_front();
-    local_payload_overflow_ = true;
+void DataTypeTracker::RecordRemoteInvalidations(
+    const SingleObjectInvalidationSet& invalidations) {
+  for (SingleObjectInvalidationSet::const_iterator it =
+       invalidations.begin(); it != invalidations.end(); ++it) {
+    if (it->is_unknown_version()) {
+      server_payload_overflow_ = true;
+    } else {
+      pending_payloads_.push_back(it->payload());
+      if (pending_payloads_.size() > payload_buffer_size_) {
+        // Drop the oldest payload if we've overflowed.
+        pending_payloads_.pop_front();
+        local_payload_overflow_ = true;
+      }
+    }
   }
 }
 
diff --git a/sync/sessions/data_type_tracker.h b/sync/sessions/data_type_tracker.h
index 30bc3b6..6ecaa0e 100644
--- a/sync/sessions/data_type_tracker.h
+++ b/sync/sessions/data_type_tracker.h
@@ -14,6 +14,10 @@
 #include "sync/protocol/sync.pb.h"
 
 namespace syncer {
+
+class Invalidation;
+class SingleObjectInvalidationSet;
+
 namespace sessions {
 
 typedef std::deque<std::string> PayloadList;
@@ -32,8 +36,9 @@ class DataTypeTracker {
   // Tracks that a local refresh request has been made for this type.
   void RecordLocalRefreshRequest();
 
-  // Tracks that we received an invalidation notification for this type.
-  void RecordRemoteInvalidation(const std::string& payload);
+  // Tracks that we received invalidation notifications for this type.
+  void RecordRemoteInvalidations(
+      const SingleObjectInvalidationSet& invalidations);
 
   // Records that a sync cycle has been performed successfully.
   // Generally, this means that all local changes have been committed and all
diff --git a/sync/sessions/nudge_tracker.cc b/sync/sessions/nudge_tracker.cc
index 8ec8970..2794747 100644
--- a/sync/sessions/nudge_tracker.cc
+++ b/sync/sessions/nudge_tracker.cc
@@ -96,16 +96,17 @@ void NudgeTracker::RecordRemoteInvalidation(
     const ObjectIdInvalidationMap& invalidation_map) {
   updates_source_ = sync_pb::GetUpdatesCallerInfo::NOTIFICATION;
 
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
+  ObjectIdSet ids = invalidation_map.GetObjectIds();
+  for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
     ModelType type;
-    if (!ObjectIdToRealModelType(it->first, &type)) {
+    if (!ObjectIdToRealModelType(*it, &type)) {
       NOTREACHED()
-          << "Object ID " << ObjectIdToString(it->first)
+          << "Object ID " << ObjectIdToString(*it)
           << " does not map to valid model type";
     }
     DCHECK(type_trackers_.find(type) != type_trackers_.end());
-    type_trackers_[type].RecordRemoteInvalidation(it->second.payload);
+    type_trackers_[type].RecordRemoteInvalidations(
+        invalidation_map.ForObject(*it));
   }
 }
 
diff --git a/sync/sync_internal_api.gypi b/sync/sync_internal_api.gypi
index be3ce71..f9aeeca 100644
--- a/sync/sync_internal_api.gypi
+++ b/sync/sync_internal_api.gypi
@@ -32,6 +32,8 @@
     'internal_api/js_sync_encryption_handler_observer.h',
     'internal_api/js_sync_manager_observer.cc',
     'internal_api/js_sync_manager_observer.h',
+    'internal_api/public/base/ack_handle.cc',
+    'internal_api/public/base/ack_handle.h',
     'internal_api/public/base/cancelation_observer.cc',
     'internal_api/public/base/cancelation_observer.h',
     'internal_api/public/base/cancelation_signal.cc',
@@ -67,8 +69,8 @@
     'internal_api/public/http_bridge.h',
     'internal_api/public/http_post_provider_factory.h',
     'internal_api/public/http_post_provider_interface.h',
-    'internal_api/public/internal_components_factory_impl.h',
     'internal_api/public/internal_components_factory.h',
+    'internal_api/public/internal_components_factory_impl.h',
     'internal_api/public/read_node.h',
     'internal_api/public/read_transaction.h',
     'internal_api/public/sessions/model_neutral_state.cc',
diff --git a/sync/sync_notifier.gypi b/sync/sync_notifier.gypi
index ba40772..365ed33 100644
--- a/sync/sync_notifier.gypi
+++ b/sync/sync_notifier.gypi
@@ -35,6 +35,8 @@
     'notifier/invalidator_state.h',
     'notifier/object_id_invalidation_map.cc',
     'notifier/object_id_invalidation_map.h',
+    'notifier/single_object_invalidation_set.cc',
+    'notifier/single_object_invalidation_set.h',
   ],
   'conditions': [
     ['OS != "android"', {
diff --git a/sync/sync_tests.gypi b/sync/sync_tests.gypi
index 93d6ed8..b0901b5 100644
--- a/sync/sync_tests.gypi
+++ b/sync/sync_tests.gypi
@@ -111,16 +111,14 @@
         'sync',
       ],
       'sources': [
+        'notifier/fake_invalidation_handler.cc',
+        'notifier/fake_invalidation_handler.h',
         'notifier/fake_invalidation_state_tracker.cc',
         'notifier/fake_invalidation_state_tracker.h',
         'notifier/fake_invalidator.cc',
         'notifier/fake_invalidator.h',
-        'notifier/fake_invalidation_handler.cc',
-        'notifier/fake_invalidation_handler.h',
         'notifier/invalidator_test_template.cc',
         'notifier/invalidator_test_template.h',
-        'notifier/object_id_invalidation_map_test_util.cc',
-        'notifier/object_id_invalidation_map_test_util.h',
       ],
     },
 
@@ -149,6 +147,8 @@
       'sources': [
         'internal_api/public/base/invalidation_test_util.cc',
         'internal_api/public/base/invalidation_test_util.h',
+        'internal_api/public/base/object_id_invalidation_map_test_util.cc',
+        'internal_api/public/base/object_id_invalidation_map_test_util.h',
         'internal_api/public/test/fake_sync_manager.h',
         'internal_api/public/test/test_entry_factory.h',
         'internal_api/public/test/test_internal_components_factory.h',
@@ -331,6 +331,8 @@
               'notifier/invalidation_notifier_unittest.cc',
               'notifier/invalidator_registrar_unittest.cc',
               'notifier/non_blocking_invalidator_unittest.cc',
+              'notifier/object_id_invalidation_map_unittest.cc',
+              'notifier/single_object_invalidation_set_unittest.cc',
               'notifier/p2p_invalidator_unittest.cc',
               'notifier/push_client_channel_unittest.cc',
               'notifier/registration_manager_unittest.cc',
diff --git a/sync/tools/sync_listen_notifications.cc b/sync/tools/sync_listen_notifications.cc
index b70ee6d..f9d1989 100644
--- a/sync/tools/sync_listen_notifications.cc
+++ b/sync/tools/sync_listen_notifications.cc
@@ -59,12 +59,10 @@ class NotificationPrinter : public InvalidationHandler {
 
   virtual void OnIncomingInvalidation(
       const ObjectIdInvalidationMap& invalidation_map) OVERRIDE {
-    for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-         it != invalidation_map.end(); ++it) {
-      LOG(INFO) << "Remote invalidation: id = "
-                << ObjectIdToString(it->first)
-                << ", version = " << it->second.version
-                << ", payload = " << it->second.payload;
+    ObjectIdSet ids = invalidation_map.GetObjectIds();
+    for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
+      LOG(INFO) << "Remote invalidation: "
+                << invalidation_map.ToString();
     }
   }