diff --git a/autotests/libs/protocolhelpertest.cpp b/autotests/libs/protocolhelpertest.cpp
--- a/autotests/libs/protocolhelpertest.cpp
+++ b/autotests/libs/protocolhelpertest.cpp
@@ -19,6 +19,7 @@
 
 #include "test_utils.h"
 #include "protocolhelper.cpp"
+#include "attributestorage.cpp"
 
 using namespace Akonadi;
 
diff --git a/autotests/libs/tagtest.cpp b/autotests/libs/tagtest.cpp
--- a/autotests/libs/tagtest.cpp
+++ b/autotests/libs/tagtest.cpp
@@ -66,6 +66,7 @@
     void testMonitor();
     void testTagAttributeConfusionBug();
     void testFetchItemsByTag();
+    void tagModifyJobShouldOnlySendModifiedAttributes();
 };
 
 void TagTest::initTestCase()
@@ -352,7 +353,6 @@
     {
         Akonadi::TagAttribute *attr = tag.attribute<Akonadi::TagAttribute>(Tag::AddIfMissing);
         attr->setDisplayName(QStringLiteral("display name"));
-        tag.addAttribute(attr);
         tag.setParent(Tag(0));
         tag.setType("mytype");
         TagModifyJob *modJob = new TagModifyJob(tag, this);
@@ -455,7 +455,6 @@
         TagAttribute *attr = tag.attribute<TagAttribute>(Tag::AddIfMissing);
         attr->setDisplayName(QStringLiteral("name"));
         attr->setInToolbar(true);
-        tag.addAttribute(attr);
         TagCreateJob *createjob = new TagCreateJob(tag, this);
         AKVERIFYEXEC(createjob);
         QVERIFY(createjob->tag().isValid());
@@ -890,6 +889,64 @@
     AKVERIFYEXEC(deleteJob);
 }
 
+void TagTest::tagModifyJobShouldOnlySendModifiedAttributes()
+{
+    // Given a tag with an attribute
+    Tag tag(QStringLiteral("tagWithAttr"));
+    auto *attr = new Akonadi::TagAttribute;
+    attr->setDisplayName(QStringLiteral("display name"));
+    tag.addAttribute(attr);
+    {
+        auto *createjob = new TagCreateJob(tag, this);
+        AKVERIFYEXEC(createjob);
+        tag = createjob->tag();
+    }
+
+    // When one job modifies this attribute, and another one does an unrelated modify job
+    Tag attrModTag(tag.id());
+    Akonadi::TagAttribute *modAttr = attrModTag.attribute<Akonadi::TagAttribute>(Tag::AddIfMissing);
+    modAttr->setDisplayName(QStringLiteral("modified"));
+    TagModifyJob *attrModJob = new TagModifyJob(attrModTag, this);
+    AKVERIFYEXEC(attrModJob);
+
+    tag.setType(Tag::GENERIC);
+    // this job shouldn't send the old attribute again
+    auto *modJob = new TagModifyJob(tag, this);
+    AKVERIFYEXEC(modJob);
+
+    // Then the tag should have both the modified attribute and the modified type
+    {
+        auto *fetchJob = new TagFetchJob(this);
+        fetchJob->fetchScope().fetchAttribute<Akonadi::TagAttribute>();
+        AKVERIFYEXEC(fetchJob);
+        QCOMPARE(fetchJob->tags().size(), 1);
+        const Tag fetchedTag = fetchJob->tags().at(0);
+        QVERIFY(fetchedTag.hasAttribute<Akonadi::TagAttribute>());
+        QCOMPARE(fetchedTag.attribute<Akonadi::TagAttribute>()->displayName(), QStringLiteral("modified"));
+        QCOMPARE(fetchedTag.type(), Tag::GENERIC);
+    }
+
+    // And when adding a new attribute next to the old one
+    auto *attr2 = AttributeFactory::createAttribute("SecondType");
+    tag.addAttribute(attr2);
+    // this job shouldn't send the old attribute again
+    auto *modJob2 = new TagModifyJob(tag, this);
+    AKVERIFYEXEC(modJob2);
+
+    // Then the tag should have the modified attribute and the second one
+    {
+        auto *fetchJob = new TagFetchJob(this);
+        fetchJob->fetchScope().setFetchAllAttributes(true);
+        AKVERIFYEXEC(fetchJob);
+        QCOMPARE(fetchJob->tags().size(), 1);
+        const Tag fetchedTag = fetchJob->tags().at(0);
+        QVERIFY(fetchedTag.hasAttribute<Akonadi::TagAttribute>());
+        QCOMPARE(fetchedTag.attribute<Akonadi::TagAttribute>()->displayName(), QStringLiteral("modified"));
+        QCOMPARE(fetchedTag.type(), Tag::GENERIC);
+        QVERIFY(fetchedTag.attribute("SecondType"));
+    }
+}
+
 #include "tagtest.moc"
 
 QTEST_AKONADIMAIN(TagTest)
diff --git a/src/core/CMakeLists.txt b/src/core/CMakeLists.txt
--- a/src/core/CMakeLists.txt
+++ b/src/core/CMakeLists.txt
@@ -9,6 +9,7 @@
     asyncselectionhandler.cpp
     attribute.cpp
     attributefactory.cpp
+    attributestorage.cpp
     braveheart.cpp
     cachepolicy.cpp
     changemediator_p.cpp
diff --git a/src/core/attributestorage.cpp b/src/core/attributestorage.cpp
new file mode 100644
--- /dev/null
+++ b/src/core/attributestorage.cpp
@@ -0,0 +1,137 @@
+/*
+    Copyright (c) 2019 David Faure <faure@kde.org>
+
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Library General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or (at your
+    option) any later version.
+
+    This library is distributed in the hope that it will be useful, but WITHOUT
+    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
+    License for more details.
+
+    You should have received a copy of the GNU Library General Public License
+    along with this library; see the file COPYING.LIB.  If not, write to the
+    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+    02110-1301, USA.
+*/
+
+#include "attributestorage_p.h"
+
+using namespace Akonadi;
+
+AttributeStorage::AttributeStorage()
+{
+}
+
+AttributeStorage::AttributeStorage(const AttributeStorage &other)
+    : mModifiedAttributes(other.mModifiedAttributes),
+      mDeletedAttributes(other.mDeletedAttributes)
+{
+    for (Attribute *attr : qAsConst(other.mAttributes)) {
+        mAttributes.insert(attr->type(), attr->clone());
+    }
+}
+
+AttributeStorage &AttributeStorage::operator=(const AttributeStorage &other)
+{
+    AttributeStorage copy(other);
+    swap(copy);
+    return *this;
+}
+
+void AttributeStorage::swap(AttributeStorage &other) noexcept
+{
+    using std::swap;
+    swap(other.mAttributes, mAttributes);
+    swap(other.mModifiedAttributes, mModifiedAttributes);
+    swap(other.mDeletedAttributes, mDeletedAttributes);
+}
+
+AttributeStorage::~AttributeStorage()
+{
+    qDeleteAll(mAttributes);
+}
+
+void AttributeStorage::addAttribute(Attribute *attr)
+{
+    Q_ASSERT(attr);
+    const QByteArray type = attr->type();
+    Attribute *existing = mAttributes.value(type);
+    if (existing) {
+        if (attr == existing) {
+            return;
+        }
+        mAttributes.remove(type);
+        delete existing;
+    }
+    mAttributes.insert(type, attr);
+    markAttributeModified(type);
+}
+
+void AttributeStorage::removeAttribute(const QByteArray &type)
+{
+    mModifiedAttributes.erase(type);
+    mDeletedAttributes.insert(type);
+    delete mAttributes.take(type);
+}
+
+bool AttributeStorage::hasAttribute(const QByteArray &type) const
+{
+    return mAttributes.contains(type);
+}
+
+Attribute::List AttributeStorage::attributes() const
+{
+    return mAttributes.values();
+}
+
+void AttributeStorage::clearAttributes()
+{
+    for (Attribute *attr : qAsConst(mAttributes)) {
+        mDeletedAttributes.insert(attr->type());
+        delete attr;
+    }
+    mAttributes.clear();
+    mModifiedAttributes.clear();
+}
+
+Attribute *AttributeStorage::attribute(const QByteArray &type) const
+{
+    return mAttributes.value(type);
+}
+
+void AttributeStorage::markAttributeModified(const QByteArray &type)
+{
+    mDeletedAttributes.remove(type);
+    mModifiedAttributes.insert(type);
+}
+
+void AttributeStorage::resetChangeLog()
+{
+    mModifiedAttributes.clear();
+    mDeletedAttributes.clear();
+}
+
+QSet<QByteArray> AttributeStorage::deletedAttributes() const
+{
+    return mDeletedAttributes;
+}
+
+bool AttributeStorage::hasModifiedAttributes() const
+{
+    return !mModifiedAttributes.empty();
+}
+
+std::vector<Attribute *> AttributeStorage::modifiedAttributes() const
+{
+    std::vector<Attribute *> ret;
+    ret.reserve(mModifiedAttributes.size());
+    for (const auto &type : mModifiedAttributes) {
+        Attribute *attr = mAttributes.value(type);
+        Q_ASSERT(attr);
+        ret.push_back(attr);
+    }
+    return ret;
+}
diff --git a/src/core/attributestorage_p.h b/src/core/attributestorage_p.h
new file mode 100644
--- /dev/null
+++ b/src/core/attributestorage_p.h
@@ -0,0 +1,67 @@
+/*
+    Copyright (c) 2019 David Faure <faure@kde.org>
+
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Library General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or (at your
+    option) any later version.
+
+    This library is distributed in the hope that it will be useful, but WITHOUT
+    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
+    License for more details.
+
+    You should have received a copy of the GNU Library General Public License
+    along with this library; see the file COPYING.LIB.  If not, write to the
+    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+    02110-1301, USA.
+*/
+
+#ifndef ATTRIBUTESTORAGE_P_H
+#define ATTRIBUTESTORAGE_P_H
+
+#include <set>
+#include <vector>
+#include <QHash>
+#include <QSet>
+#include "attribute.h"
+
+namespace Akonadi {
+
+/**
+ * The AttributeStorage class is used by Collection, Item, Tag...
+ * to store a set of attributes, remembering modifications.
+ * I.e. it knows which attributes have been added or removed
+ * compared to the initial set (e.g. fetched from server).
+ */
+class AttributeStorage
+{
+public:
+    AttributeStorage();
+    AttributeStorage(const AttributeStorage &other);
+    AttributeStorage& operator=(const AttributeStorage &other);
+    void swap(AttributeStorage &other) noexcept;
+    ~AttributeStorage();
+
+    void addAttribute(Attribute *attr);
+    void removeAttribute(const QByteArray &type);
+    bool hasAttribute(const QByteArray &type) const;
+    Attribute::List attributes() const;
+    void clearAttributes();
+    Attribute *attribute(const QByteArray &type) const;
+    void markAttributeModified(const QByteArray &type);
+    void resetChangeLog();
+
+    QSet<QByteArray> deletedAttributes() const;
+    bool hasModifiedAttributes() const;
+    std::vector<Attribute *> modifiedAttributes() const;
+
+private:
+    QHash<QByteArray, Attribute *> mAttributes;
+    std::set<QByteArray> mModifiedAttributes;
+    QSet<QByteArray> mDeletedAttributes;
+};
+
+}
+
+#endif // ATTRIBUTESTORAGE_P_H
diff --git a/src/core/collection.h b/src/core/collection.h
--- a/src/core/collection.h
+++ b/src/core/collection.h
@@ -549,7 +549,7 @@
     friend class CollectionModifyJob;
     friend class ProtocolHelper;
 
-    void markAttributesChanged();
+    void markAttributeModified(const QByteArray &type);
 
     //@cond PRIVATE
     QSharedDataPointer<CollectionPrivate> d_ptr;
@@ -564,15 +564,15 @@
 {
     Q_UNUSED(option);
 
-    const T dummy;
-    if (hasAttribute(dummy.type())) {
-        T *attr = dynamic_cast<T *>(attribute(dummy.type()));
+    const QByteArray type = T().type();
+    if (hasAttribute(type)) {
+        T *attr = dynamic_cast<T *>(attribute(type));
         if (attr) {
-            markAttributesChanged();
+            markAttributeModified(type);
             return attr;
         }
         //Reuse 5250
-        qWarning() << "Found attribute of unknown type" << dummy.type()
+        qWarning() << "Found attribute of unknown type" << type
                    << ". Did you forget to call AttributeFactory::registerAttribute()?";
     }
 
diff --git a/src/core/collection.cpp b/src/core/collection.cpp
--- a/src/core/collection.cpp
+++ b/src/core/collection.cpp
@@ -166,48 +166,32 @@
 
 void Collection::addAttribute(Attribute *attr)
 {
-    Q_ASSERT(attr);
-    Attribute *existing = d_ptr->mAttributes.value(attr->type());
-    if (existing) {
-        if (attr == existing) {
-            return;
-        }
-        d_ptr->mAttributes.remove(attr->type());
-        delete existing;
-    }
-    d_ptr->mAttributes.insert(attr->type(), attr);
-    d_ptr->mDeletedAttributes.remove(attr->type());
-    d_ptr->attributesChanged = true;
+    d_ptr->mAttributeStorage.addAttribute(attr);
 }
 
 void Collection::removeAttribute(const QByteArray &type)
 {
-    d_ptr->mDeletedAttributes.insert(type);
-    delete d_ptr->mAttributes.take(type);
+    d_ptr->mAttributeStorage.removeAttribute(type);
 }
 
 bool Collection::hasAttribute(const QByteArray &type) const
 {
-    return d_ptr->mAttributes.contains(type);
+    return d_ptr->mAttributeStorage.hasAttribute(type);
 }
 
 Attribute::List Collection::attributes() const
 {
-    return d_ptr->mAttributes.values();
+    return d_ptr->mAttributeStorage.attributes();
 }
 
 void Akonadi::Collection::clearAttributes()
 {
-    for (Attribute *attr : qAsConst(d_ptr->mAttributes)) {
-        d_ptr->mDeletedAttributes.insert(attr->type());
-        delete attr;
-    }
-    d_ptr->mAttributes.clear();
+    return d_ptr->mAttributeStorage.clearAttributes();
 }
 
 Attribute *Collection::attribute(const QByteArray &type) const
 {
-    return d_ptr->mAttributes.value(type);
+    return d_ptr->mAttributeStorage.attribute(type);
 }
 
 Collection &Collection::parentCollection()
@@ -462,7 +446,7 @@
     return d_ptr->keepLocalChanges;
 }
 
-void Collection::markAttributesChanged()
+void Collection::markAttributeModified(const QByteArray &type)
 {
-    d_ptr->attributesChanged = true;
+    d_ptr->mAttributeStorage.markAttributeModified(type);
 }
diff --git a/src/core/collection_p.h b/src/core/collection_p.h
--- a/src/core/collection_p.h
+++ b/src/core/collection_p.h
@@ -23,6 +23,7 @@
 #include "collection.h"
 #include "cachepolicy.h"
 #include "collectionstatistics.h"
+#include "attributestorage_p.h"
 
 #include "qstringlist.h"
 
@@ -48,7 +49,6 @@
         , referencedChanged(false)
         , contentTypesChanged(false)
         , cachePolicyChanged(false)
-        , attributesChanged(false)
         , isVirtual(false)
         , mId(id)
         , mParent(nullptr)
@@ -62,10 +62,7 @@
         mId = other.mId;
         mRemoteId = other.mRemoteId;
         mRemoteRevision = other.mRemoteRevision;
-        for (Attribute *attr : qAsConst(other.mAttributes)) {
-            mAttributes.insert(attr->type(), attr->clone());
-        }
-        mDeletedAttributes = other.mDeletedAttributes;
+        mAttributeStorage = other.mAttributeStorage;
         if (other.mParent) {
             mParent = new Collection(*(other.mParent));
         }
@@ -86,12 +83,10 @@
         referenced = other.referenced;
         referencedChanged = other.referencedChanged;
         keepLocalChanges = other.keepLocalChanges;
-        attributesChanged = other.attributesChanged;
     }
 
     ~CollectionPrivate()
     {
-        qDeleteAll(mAttributes);
         delete mParent;
     }
 
@@ -102,8 +97,7 @@
         enabledChanged = false;
         listPreferenceChanged = false;
         referencedChanged = false;
-        attributesChanged = false;
-        mDeletedAttributes.clear();
+        mAttributeStorage.resetChangeLog();
     }
 
     static Collection newRoot()
@@ -124,16 +118,14 @@
     bool referencedChanged: 1;
     bool contentTypesChanged: 1;
     bool cachePolicyChanged: 1;
-    bool attributesChanged : 1;
     bool isVirtual: 1;
     // 2 bytes padding here
 
     Collection::Id mId;
     QString mRemoteId;
     QString mRemoteRevision;
-    QHash<QByteArray, Attribute *> mAttributes;
-    QSet<QByteArray> mDeletedAttributes;
     mutable Collection *mParent;
+    AttributeStorage mAttributeStorage;
     QString name;
     QString resource;
     CollectionStatistics statistics;
diff --git a/src/core/jobs/collectionmodifyjob.cpp b/src/core/jobs/collectionmodifyjob.cpp
--- a/src/core/jobs/collectionmodifyjob.cpp
+++ b/src/core/jobs/collectionmodifyjob.cpp
@@ -100,17 +100,17 @@
     if (d->mCollection.d_ptr->referencedChanged) {
         cmd->setReferenced(d->mCollection.referenced());
     }
-    if (d->mCollection.d_ptr->attributesChanged) {
-        cmd->setAttributes(ProtocolHelper::attributesToProtocol(d->mCollection));
+    if (d->mCollection.d_ptr->mAttributeStorage.hasModifiedAttributes()) {
+        cmd->setAttributes(ProtocolHelper::attributesToProtocol(d->mCollection.d_ptr->mAttributeStorage.modifiedAttributes()));
     }
     if (auto attr = d->mCollection.attribute<Akonadi::PersistentSearchAttribute>()) {
         cmd->setPersistentSearchCollections(attr->queryCollections());
         cmd->setPersistentSearchQuery(attr->queryString());
         cmd->setPersistentSearchRecursive(attr->isRecursive());
         cmd->setPersistentSearchRemote(attr->isRemoteSearchEnabled());
     }
-    if (!d->mCollection.d_ptr->mDeletedAttributes.isEmpty()) {
-        cmd->setRemovedAttributes(d->mCollection.d_ptr->mDeletedAttributes);
+    if (!d->mCollection.d_ptr->mAttributeStorage.deletedAttributes().empty()) {
+        cmd->setRemovedAttributes(d->mCollection.d_ptr->mAttributeStorage.deletedAttributes());
     }
 
     if (cmd->modifiedParts() == Protocol::ModifyCollectionCommand::None) {
diff --git a/src/core/jobs/tagfetchjob.cpp b/src/core/jobs/tagfetchjob.cpp
--- a/src/core/jobs/tagfetchjob.cpp
+++ b/src/core/jobs/tagfetchjob.cpp
@@ -20,6 +20,7 @@
 #include "tagfetchjob.h"
 #include "job_p.h"
 #include "tag.h"
+#include "tag_p.h"
 #include "protocolhelper_p.h"
 #include "tagfetchscope.h"
 #include "attributefactory.h"
diff --git a/src/core/jobs/tagmodifyjob.cpp b/src/core/jobs/tagmodifyjob.cpp
--- a/src/core/jobs/tagmodifyjob.cpp
+++ b/src/core/jobs/tagmodifyjob.cpp
@@ -65,18 +65,19 @@
     if (d->mTag.parent().isValid() && !d->mTag.isImmutable()) {
         cmd->setParentId(d->mTag.parent().id());
     }
-    if (!d->mTag.d_ptr->mDeletedAttributes.isEmpty()) {
-        cmd->setRemovedAttributes(d->mTag.d_ptr->mDeletedAttributes);
+    if (!d->mTag.d_ptr->mAttributeStorage.deletedAttributes().isEmpty()) {
+        cmd->setRemovedAttributes(d->mTag.d_ptr->mAttributeStorage.deletedAttributes());
+    }
+    if (d->mTag.d_ptr->mAttributeStorage.hasModifiedAttributes()) {
+        cmd->setAttributes(ProtocolHelper::attributesToProtocol(d->mTag.d_ptr->mAttributeStorage.modifiedAttributes()));
     }
-
-    cmd->setAttributes(ProtocolHelper::attributesToProtocol(d->mTag));
 
     d->sendCommand(cmd);
 }
 
 bool TagModifyJob::doHandleResponse(qint64 tag, const Protocol::CommandPtr &response)
 {
-    //Q_D(TagModifyJob);
+    Q_D(TagModifyJob);
 
     if (response->isResponse()) {
         if (response->type() == Protocol::Command::FetchTags) {
@@ -87,6 +88,7 @@
             return false;
         } else if (response->type() == Protocol::Command::ModifyTag) {
             // Done.
+            d->mTag.d_ptr->resetChangeLog();
             return true;
         }
     }
diff --git a/src/core/protocolhelper.cpp b/src/core/protocolhelper.cpp
--- a/src/core/protocolhelper.cpp
+++ b/src/core/protocolhelper.cpp
@@ -23,6 +23,7 @@
 #include "collectionstatistics.h"
 #include "item_p.h"
 #include "collection_p.h"
+#include "tag_p.h"
 #include "exceptionbase.h"
 #include "itemserializer_p.h"
 #include "itemserializerplugin.h"
@@ -205,6 +206,16 @@
     return attributesToProtocolImpl(tag, ns);
 }
 
+Protocol::Attributes ProtocolHelper::attributesToProtocol(const std::vector<Attribute *> &modifiedAttributes, bool ns)
+{
+    Protocol::Attributes attributes;
+    for (const Attribute *attr : modifiedAttributes) {
+        attributes.insert(ProtocolHelper::encodePartIdentifier(ns ? ProtocolHelper::PartAttribute : ProtocolHelper::PartGlobal, attr->type()),
+                          attr->serialized());
+    }
+    return attributes;
+}
+
 Collection ProtocolHelper::parseCollection(const Protocol::FetchCollectionsResponse &data, bool requireParent)
 {
     Collection collection(data.id());
@@ -254,6 +265,7 @@
     tag.setType(data.type());
     tag.setParent(Tag(data.parentId()));
     parseAttributes(data.attributes(), &tag);
+    tag.d_ptr->resetChangeLog();
 
     return tag;
 }
@@ -717,6 +729,7 @@
     tag.setParent(data.parentId() > 0 ? Tag(data.parentId()) : Tag());
 
     parseAttributes(data.attributes(), &tag);
+    tag.d_ptr->resetChangeLog();
     return tag;
 }
 
diff --git a/src/core/protocolhelper_p.h b/src/core/protocolhelper_p.h
--- a/src/core/protocolhelper_p.h
+++ b/src/core/protocolhelper_p.h
@@ -40,6 +40,7 @@
 #include <type_traits>
 #include <functional>
 #include <cassert>
+#include <set>
 
 namespace Akonadi
 {
@@ -136,6 +137,7 @@
     static Protocol::Attributes attributesToProtocol(const Item &item, bool ns = false);
     static Protocol::Attributes attributesToProtocol(const Collection &collection, bool ns = false);
     static Protocol::Attributes attributesToProtocol(const Tag &entity, bool ns = false);
+    static Protocol::Attributes attributesToProtocol(const std::vector<Attribute *> &modifiedAttributes, bool ns = false);
 
     /**
       Encodes part label and namespace.
diff --git a/src/core/tag.h b/src/core/tag.h
--- a/src/core/tag.h
+++ b/src/core/tag.h
@@ -198,9 +198,12 @@
 
 private:
     bool checkAttribute(Attribute *attr, const QByteArray &type) const;
+    void markAttributeModified(const QByteArray &type);
 
     //@cond PRIVATE
     friend class TagModifyJob;
+    friend class TagFetchJob;
+    friend class ProtocolHelper;
 
     QSharedDataPointer<TagPrivate> d_ptr;
     //@endcond
@@ -213,10 +216,11 @@
 {
     Q_UNUSED(option);
 
-    const T dummy;
-    if (hasAttribute(dummy.type())) {
-        T *attr = dynamic_cast<T *>(attribute(dummy.type()));
-        if (checkAttribute(attr, dummy.type())) {
+    const QByteArray type = T().type();
+    if (hasAttribute(type)) {
+        T *attr = dynamic_cast<T *>(attribute(type));
+        if (checkAttribute(attr, type)) {
+            markAttributeModified(type);
             return attr;
         }
     }
diff --git a/src/core/tag.cpp b/src/core/tag.cpp
--- a/src/core/tag.cpp
+++ b/src/core/tag.cpp
@@ -122,47 +122,32 @@
 
 void Tag::addAttribute(Attribute *attr)
 {
-    const QByteArray typeAttr = attr->type();
-    Attribute *existing = d_ptr->mAttributes.value(typeAttr);
-    if (existing) {
-        if (attr == existing) {
-            return;
-        }
-        d_ptr->mAttributes.remove(typeAttr);
-        delete existing;
-    }
-    d_ptr->mAttributes.insert(typeAttr, attr);
-    d_ptr->mDeletedAttributes.remove(typeAttr);
+   d_ptr->mAttributeStorage.addAttribute(attr);
 }
 
 void Tag::removeAttribute(const QByteArray &type)
 {
-    d_ptr->mDeletedAttributes.insert(type);
-    delete d_ptr->mAttributes.take(type);
+    d_ptr->mAttributeStorage.removeAttribute(type);
 }
 
 bool Tag::hasAttribute(const QByteArray &type) const
 {
-    return d_ptr->mAttributes.contains(type);
+    return d_ptr->mAttributeStorage.hasAttribute(type);
 }
 
 Attribute::List Tag::attributes() const
 {
-    return d_ptr->mAttributes.values();
+    return d_ptr->mAttributeStorage.attributes();
 }
 
 void Tag::clearAttributes()
 {
-    for (Attribute *attr : qAsConst(d_ptr->mAttributes)) {
-        d_ptr->mDeletedAttributes.insert(attr->type());
-        delete attr;
-    }
-    d_ptr->mAttributes.clear();
+    d_ptr->mAttributeStorage.clearAttributes();
 }
 
 Attribute *Tag::attribute(const QByteArray &type) const
 {
-    return d_ptr->mAttributes.value(type);
+    return d_ptr->mAttributeStorage.attribute(type);
 }
 
 void Tag::setId(Tag::Id identifier)
@@ -268,3 +253,8 @@
                                << ". Did you forget to call AttributeFactory::registerAttribute()?";
     return false;
 }
+
+void Tag::markAttributeModified(const QByteArray &type)
+{
+    d_ptr->mAttributeStorage.markAttributeModified(type);
+}
diff --git a/src/core/tag_p.h b/src/core/tag_p.h
--- a/src/core/tag_p.h
+++ b/src/core/tag_p.h
@@ -21,6 +21,7 @@
 #ifndef TAG_P_H
 #define TAG_P_H
 
+#include "attributestorage_p.h"
 #include "tag.h"
 
 namespace Akonadi
@@ -44,15 +45,16 @@
             parent.reset(new Tag(*other.parent));
         }
         type = other.type;
-        for (Attribute *attr : qAsConst(other.mAttributes)) {
-            mAttributes.insert(attr->type(), attr->clone());
-        }
-        mDeletedAttributes = other.mDeletedAttributes;
+        mAttributeStorage = other.mAttributeStorage;
     }
 
     ~TagPrivate()
     {
-        qDeleteAll(mAttributes);
+    }
+
+    void resetChangeLog()
+    {
+        mAttributeStorage.resetChangeLog();
     }
 
     // 4 bytes padding here (after QSharedData)
@@ -62,8 +64,7 @@
     QByteArray remoteId;
     QScopedPointer<Tag> parent;
     QByteArray type;
-    QHash<QByteArray, Attribute *> mAttributes;
-    QSet<QByteArray> mDeletedAttributes;
+    AttributeStorage mAttributeStorage;
 };
 
 }